Determining objective functions in systolic array designs

Author

Zhang, C.N. ; Weston, J.H. ; Yan, Y.-F.

Author_Institution

Dept. of Comput. Sci., Regina Univ., Sask., Canada

Volume

2

Issue

3

fYear

1994

Firstpage

357

Lastpage

360

Abstract

The space-time mapping of the dependency matrix of an algorithm may be used to study proposed systolic array implementations. In this paper we consider nested loop structures and use the space-time mapping approach to examine six objective functions, processor pipelining rate, computation time, throughput, number of processing elements, geometric area and space utilization. An elementary expression for each of these objective functions is derived which depends only on the space-time transformation and the size of loops. Moreover, several necessary and sufficient conditions for optimizing an individual objective function are provided.<>

Keywords

VLSI; logic CAD; matrix algebra; parallel algorithms; pipeline processing; systolic arrays; computation time; dependency matrix; geometric area; nested loop structures; objective functions; processing elements number; processor pipelining rate; space utilization; space-time mapping; systolic array designs; throughput; Algorithm design and analysis; Computer architecture; Concurrent computing; Fault tolerance; Hardware; Multiplexing; Redundancy; Solid state circuits; Systolic arrays; Very large scale integration;

fLanguage

English

Journal_Title

Very Large Scale Integration (VLSI) Systems, IEEE Transactions on

Publisher

ieee

ISSN

1063-8210

Type

jour

DOI

10.1109/92.311644

Filename

311644