DocumentCode :
3190949
Title :
A general approach to solving arbitrarily large problems in a fixed size systolic array
Author :
Chuang, Henry Y H ; Chen, Luo-nan
Author_Institution :
Dept. of Comput. Sci., Pittsburgh Univ., PA, USA
Volume :
2
fYear :
1988
fDate :
0-0 1988
Firstpage :
195
Lastpage :
204
Abstract :
Solving large problems in a small systolic array is considered difficult because the data arrays that pipeline through the array have to meet at the right place at the right time. Thus, partitioning and scheduling of data arrays for systolic computation is generally performed ad hoc. A general partitioning and scheduling method for solving large problems in a small systolic array is presented. Given a systolic array and its algorithm, a scheduling program that schedules the data blocks resulting from partitioning the data arrays can be obtained in a straightforward manner from the algorithm. The method, which can be easily mechanized, is applicable to loop algorithms and systolic arrays of various structures and shapes with or without local memory. Array emulation is an effective approach to solve large problems in a small processor array efficiently. Various array emulation methods are discussed, and the partitioning and scheduling method presented is shown to be useful for array emulation also.<>
Keywords :
cellular arrays; microprocessor chips; pipeline processing; scheduling; array emulation methods; data arrays; data blocks; fixed size systolic array; large problems; loop algorithms; partitioning; pipeline; scheduling program; systolic computation; Computer science; Design methodology; Emulation; Partitioning algorithms; Pins; Pipelines; Processor scheduling; Scheduling algorithm; Shape; Systolic arrays;
fLanguage :
English
Publisher :
ieee
Conference_Titel :
System Sciences, 1988. Vol.II. Software Track, Proceedings of the Twenty-First Annual Hawaii International Conference on
Conference_Location :
Kailua-Kona, HI, USA
Print_ISBN :
0-8186-0842-0
Type :
conf
DOI :
10.1109/HICSS.1988.11806
Filename :
11806
Link To Document :
بازگشت