A Formal Process for Systolic Array Design Using Recurrences

From bibtex.

Abstract

A systolic array is essentially a parallel processor which consists of a grid of locallyconnected sub-processors which receive, process and pump out data synchronously in such a way that the pattern of data-flow to and from each processor is identical to the flow to and from the other processors. Such arrays are repetitive and modular and require little length of communication interconnection, so that they are relatively simple to design and are amenable to efficient VLSI implementation. The systolic architecture has been found suitable for implementing many of the algorithms used in the field of signal- and image-processing. A formal design method is a well-defined process for constructing, given a well-defined function from a certain class, a well-defined object (e.g. a design) which performs that function. When proven correct, such methods are useful for designing equipment which is safety-critical or where a design fault discovered after manufacture would be expensive. This thesis presents a formal design method for producing high-level implementations for certain signal-processing and other algorithms. These high-level implementations can themselves usually be easily implemented as systolic arrays. As a necessary preliminary to the method, a calculus is defined. The basic concept, that of a "computation", is powerful enough to express both abstract algorithms and those whose suboperations have been assigned a place and a time to execute. Computations may be composed or abstracted (by having their variables hidden) or may have their variables renamed. The "simulation" of one computation by another is defined. Using this calculus it is possible to formalise concepts like "dependency" (of data or control) and "system of recurrence equations", which often appear in the literature on systolic array design. The design method is then presented. It consists of five stages: pipelining of data dependencies, scheduling, pipelining of the control variables, allocation of subprocessors to the subcomputations, and the final stage (in which the design is constructed). The main concepts are not new, but here they have been formalised, iv arranged and linked in a clearly defined way. The output of the method is a high-level design description which defines the functionality of each subprocessor in the array (for both data and control). It also defines scheduling and allocation of all the operations which are to be executed and the data and control input requirements of the array. The method is used to design a simple one-dimensional systolic convolver and then to design a more complicated two-dimensional systolic array which performs Given's algorithm for QR-factorisation, a task required in certain signal-processing applications such as adaptive estimation and bearing measurement. Alternative designs are briefly discussed. For the convolver and the two arrays for QR-factorisation, sketches of the architectures are given but these are hand-produced and are not the product of the method. A detailed proof is given that, subject to assumptions about the well-deflnedness of the computations handled and created, the design method will produce only designs which meet their specifications; however the final high-level design may imply a low-level implementation which may contain an interconnection structure which is arguably nonlocal. A proof is given that the well-defmedness conditions hold which are required for the validation of data-pipelining.