Some space considerations of VLSI systolic array mappings

Author

Weston, J.H. ; Zhang, Chang N. ; Li, Hua

Author_Institution

Dept. of Math. & Stat., Regina Univ., Sask., Canada

Volume

48

Issue

4

fYear

2001

fDate

4/1/2001 12:00:00 AM

Firstpage

419

Lastpage

424

Abstract

In this brief, the space-time mapping of the dependency matrix of an algorithm is used to study spatial properties of a systolic array implementation of a three-nested loop structure. Elementary expressions are developed for both the number of processing elements and the area of the array. These expressions involve only the space-time transformation and the lengths of the loops. As well, characterizations have been found for the form of the space-time transformation which produces a systolic array with the minimum number of processing elements, and one which has both the minimum number of processing elements and the smallest area. Moreover, the approaches can also be extended to general algorithms, such as variable loop lengths

Keywords

VLSI; space-time adaptive processing; systolic arrays; VLSI; dependency matrix; processing elements; space-time mapping; space-time transformation; systolic array; systolic array mappings; three-nested loop structure; variable loop lengths; Area measurement; Costs; Extraterrestrial measurements; Fabrication; Partitioning algorithms; Polynomials; Signal processing algorithms; Software design; Systolic arrays; Very large scale integration;

fLanguage

English

Journal_Title

Circuits and Systems II: Analog and Digital Signal Processing, IEEE Transactions on

Publisher

ieee

ISSN

1057-7130

Type

jour

DOI

10.1109/82.933810

Filename

933810