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

Journal of Inforamtion Science and Engineering, Vol.6 No.2, pp.117-137 (June 1990)
Three-Level FP Programs and the Derivation of
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

Received September 23, 1989; revised January 7, 1990.
Communicated by Lin-Shan Lee.
*An earlier version of this paper was presented at the National Computer Symposium, Taipei, December 1989.
this research was supported in part by the National Science Council of R.O.C. under contract NSc-78-0408-E011-06.