Recent Developments in Systolic Design

C. Lengauer and Jingling Xue

Abstract: A systolic array is a network of processors that are locally and regularly connected. This special-purpose computing paradigm supports the parallel implementation of iterative algorithms in a variety of areas, e.g., numerical analysis, signal or image processing and graph theory.

The special appeal of systolic arrays is that they can be derived mechanically by provably correct and (in a sense) optimal synthesis methods. These methods transform algorithmic descriptions that do not specify concurrency or commmunication - usually functional or imperative programs - into functions that distribute the program's operations over time and space. This process is called systolic design. The distribution functions can then be refined further and translated into a description for fabrication of a VLSI chip or into a distributed program for execution on a programmable processor array.

Systolic design has received a lot of attention in the past decade. This paper is an overview and bibliography of recent results and current issues in the mechanical synthesis of systolic arrays.

LFCS report ECS-LFCS-91-176

Previous | Index | Next