Design of Fixed-Size Systolic Arrays
Yunho Kim, Kee-Young Yoo · Journal of Electrical Engineering and Information Science · 1999
This paper presents a method for designing fixed-size systolic arrays represented by the form of uniform recurrence equation. The method consists mainly of two phases: (ⅰ) partitioning a full-size systolic array based on the LPGS approach, and (ⅱ) scheduling initial input data for the fixed-size systolic array. The partitioning is done along the ray of the basis vectors of Array Partition Space (APS) defined in this paper. The result is to reduce the number of bands and the total execution time. In addition, we propose band dependence graph based on the dependence relationship among the bands. Based on the graph, the validity of partitioning is verified and the execution order of the bands is determined using the topological sorting. For practical design, a systematic scheduling method for the initial input data is also presented. To reduce the number of external buffers needed for the communications among the bands, so called Data Duplicate Input (DDI) mechanism for used variables is proposed.