JISE


  [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


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 (JISE_200601_06.pdf)