Home
 

The Formal Synthesis of Control Signals for Systolic Arrays

Jingling Xue

Abstract: The distinguishing features characteristic of systolic arrays are synchrony of computations, local and regular connections between processors and massive decentralised parallelism. The potential of the systolic array lies in its suitability for VLSI fabrication and its practicality for a variety of application areas such as signal or image processing and numeric analysis. With the increasing possibilities promised by advances in VLSI technology and computer architecture, more and more complex problems are now solvable by systolic arrays.

This thesis describes a systematic method for the synthesis of control signals for systolic arrays that are realised in hardware. Control signals ensure that the right computations are executed at the right processors at the right time. The proposed method applies for iterative algorithms defined over a domain that can be expressed by a convex set of integer coordinates. Algorithms that can be implemented as systolic arrays can be expressed this way; a large subclass can be phrased as affine (or uniform) recurrence equations in the functional style and as nested loops in the imperative style. The synthesis of control signals from a program specification is a process of program transformation and construction. The basic idea is to replace the domain predicates in the initial program specification which constitute the abstract specification of control signals by a system of uniform recurrence equations by means of data pipelining. Then, systolic arrays with a description of both data and control signals can be obtained by a direct application of the standard space-time mapping technique.

PhD Thesis - price £8.00

LFCS report ECS-LFCS-92-203 (also published as CST-90-92)

Previous | Index | Next