DocumentCode :
1151151
Title :
The Design of Optimal Systolic Arrays
Author :
Li, Guo-Jie ; Wah, Benjamin W.
Author_Institution :
School of Electrical Engineering, Purdue University
Issue :
1
fYear :
1985
Firstpage :
66
Lastpage :
77
Abstract :
Conventional design of systolic arrays is based on the mapping of an algorithm onto an interconnection of processing elements in a VLSI chip. This mapping is done in an ad hoc manner, and the resulting configuration usually represents a feasible but suboptimal design. In this paper, systolic arrays are characterized by three classes of parameters: the velocities of data flows, the spatial distributions of data, and the periods of computation. By relating these parameters in constraint equations that govern the correctness of the design, the design is formulated into an optimization problem. The size of the search space is a polynomial of the problem size, and a methodology to systematically search and reduce this space and to obtain the optimal design is proposed. Some examples of applying the method, including matrix multiplication, finite impulse response filtering, deconvolution, and triangular-matrix inversion, are given.
Keywords :
Data distribution; data flow; parameter method; period; recurrence equation; systolic array; velocity; Algorithm design and analysis; Constraint optimization; Data flow computing; Design optimization; Distributed computing; Equations; Finite impulse response filter; Polynomials; Systolic arrays; Very large scale integration; Data distribution; data flow; parameter method; period; recurrence equation; systolic array; velocity;
fLanguage :
English
Journal_Title :
Computers, IEEE Transactions on
Publisher :
ieee
ISSN :
0018-9340
Type :
jour
DOI :
10.1109/TC.1985.1676516
Filename :
1676516
Link To Document :
بازگشت