A note on the linear transformation method for systolic array design

Author

Lin, Wei-Ming ; Kumar, Prasanna V K

Author_Institution

Dept. of Electr. Eng.-Syst., Univ. of Southern California, Los Angeles, CA, USA

Volume

39

Issue

3

fYear

1990

fDate

3/1/1990 12:00:00 AM

Firstpage

393

Lastpage

399

Abstract

The use of the linear transformation method to systolize the Warshall algorithm for computing the transitive closure of a graph on a mesh-connected array (without wraparound connections) is discussed. The technique is extended to design linear systolic arrays. The advantage of this approach is easy verification of correctness, as well as synthesis of a family of arrays with tradeoffs between I/O bandwidth, number of processing elements, and local storage. The technique can be further refined to cope with problems that entail nonconstant dependency vectors

Keywords

cellular arrays; logic arrays; logic design; parallel algorithms; I/O bandwidth; Warshall algorithm; correctness; graph; linear transformation method; local storage; mesh-connected array; processing elements; systolic array design; transitive closure; verification; Circuit testing; Design methodology; Image processing; Physics computing; Signal design; Signal processing; Signal synthesis; Solid state circuits; Systolic arrays; Very large scale integration;

fLanguage

English

Journal_Title

Computers, IEEE Transactions on

Publisher

ieee

ISSN

0018-9340

Type

jour

DOI

10.1109/12.48870

Filename

48870