Efficient Systolic Arrays for the Solution of Toeplitz Systems: An Illustration of a Methodology for the Construction of Systolic Architectures in VLSI (Very Large Systems Integration)

摘要

Advanced high resolution methods for real-time signal processing require fast multiprocessor architectures, realized as Very Large Scale Integrated systems, for their implementation. A class of parallel structures, 'systolic arrays', fulfills the demands of signal processing and at the same time conforms to the limitations of VLSI technology. The design of efficient systems of systolic arrays is an iterative process in which the information gathered from mapping algorithms onto hardware is influential in the development of the algorithms. Presently, the absence of mapping tools makes it extremely difficult to find good systolic implementations for many important problems. Often, one cannot do better than implementing structurally simple but numerically inferior algorithms, which is undesirable for most signal processing tasks. A methodology is proposed that automates the mapping of recurrence equations to processor arrays. Two aspects distinguish our methodology from extant work: (1) complex coupled systems of recurrence equations can be systematically treated and (2) the resulting systolic systems are optimal. The methodology takes as input recurrence equations describing the algorithm, along with certain desirable hardware features.