On high-speed computing with a programmable linear array
PeiZong Lee, Zvi M. Kedem · Conference on High Performance Computing (Supercomputing) · 1988
It has been observed by many researchers that systolic arrays are very suitable for certain high-speed computations. In this paper, using a formal methodology, a single simple programmable linear systolic array capable of solving large number of problems drawn from a variety of applications is designed. The methodology is applicable to problems solvable by sequential algorithms that can be specified as nested for loops of arbitrary depth. The algorithms of this form that can be computed on the array presented in this paper include 25 algorithms dealing with signal and image processing, algebraic computations, matrix arithmetic, pattern matching, database operations, sorting, and transitive closure. Assuming bounded I/O, for 18 of those algorithms the time and storage complexities are optimal, and therefore no improvement can be expected by utilizing dedicated special purpose linear systolic arrays designed for individual algorithms.