Previous [ 1] [ 2] [ 3] [ 4] [ 5] [ 6] [ 7] [ 8] [ 9] [ 10] [ 11] [ 12] [ 13]

ˇ@

Journal of Information Science and Engineering, Vol. 22 No. 1, pp. 95-121 (January 2006)

A Programming Methodology for Designing Block Recursive Algorithms*

Min-Hsuan Fan, Chua-Huang Huang, Yeh-Ching Chung+, Jen-Shiuh Liu and Jei-Zhii Lee++
Department of Information Engineering and Computer Science
Feng Chia University
Taichung, 407 Taiwan
+Department of Computer Science
National Tsing Hua University
Hsinchu, 300 Taiwan
++Department of Computer Science and Information Engineering
National Dong Hwa University
Hualien, 974 Taiwan

In this paper, we use the tensor product notation as the framework of a programming methodology for designing block recursive algorithms. We first express a computational problem in its matrix form. Next, we formulate a matrix equation for the matrix of the computational problem. Then, we try to find a solution of the matrix equation such that the solution is composed of simple matrices. Finally, we recursively factorize the subproblem to obtain a tensor product formula representing an algorithm for the given problem. In this methodology, the operations of a tensor product formula can be mapped to language constructs of high-level programming languages. That is, we can generate computer programs, including programs for parallel computers and distributed-memory multiprocessors, from tensor product formulas. In this paper, we use the parallel prefix problem and the discrete Fourier transform problem as examples to illustrate the methodology and derive various parallel prefix and fast Fourier transform algorithms.

Keywords: programming methodology, tensor product, block recursive algorithm, parallel processing, distributed processing, parallel prefix, fast Fourier transform Retrieve PDF document (200601_06.pdf)

Received January 9, 2004; revised April 29, 2004; accepted June 8, 2004.
Communicated by Gen-Huey Chen.
* This work was supported in part by the National Science Council, R.O.C., No. NSC 89-2213-E-259-005.