JISE


  [1] [2] [3] [4] [5]


Journal of Information Science and Engineering, Vol. 6 No. 2, pp. 117-137


Three-Level FP Programs and the Derivation of Problem-Size-Dependent/Independent Systolic Algorithms


Yen-Chun Lin and Ferng-Ching Lin+
Department of Electronic Engineering 
National Taiwan Institute of Technology 
Taipei, Taiwan 10772, Republic of China 
+Department of Computer Science and Information Engineering 
National Taiwan University 
Taipei, Taiwan 10764, Republic of China


  The functional programming language FP has been advocated as a means of avoiding many of the defects of conventional programming languages and has been regarded as a language suitable for expressing parallel algorithms. Systolic algorithms are parallel algorithms executing on a regular array of processing elements in which data are communicated locally and operated on rhythmically. In this paper, we show in detail how to systematically derive systolic algorithms from FP programs in object, structure, and sequencing levels. Through these three levels of programming, complex systolic algorithms are derived from simple ones by the use of apply-to-all theorems. Not only problem-size-dependent systolic algorithms but also problem-size-independent ones can be constructed by the method.


Keywords: FP, functional programming, problem-size-independent, systolic algorithms

  Retrieve PDF document (JISE_199002_03.pdf)