An Introduction to Systolic Algorithm Design

Parallel programming and the effective exploitation of parallel computers will play an increasingly important part in the future development of computer systems. One method of parallel processing which promises to deliver very high performance and algorithmically specialized devices at low cost by exploiting the capabilities of very large scale integration (VLSI) techniques is the systolic paradigm. The term systolic is derived from the term "systole" which means the regular, recurrent contraction of the heart for pumping blood around the body. Systolic processing is a technique for solving problems on a massively parallel computer architecture in a way that pumps information or data between processing elements in a regular and rhythmic pattern. This book is an introduction to systolic algorithms and how to design them in a systematic way so that they meet certain design objectives such as area and time efficiency. Topics covered include basic synthesis techniques, matrix computations, table generations, non-numerical algorithms, bit serial versus bit parallel methods of computation, and programmable systolic arrays.