A systematic method of synthesizing systolic arrays using a data dependence graph

Abstract With the recent development of VLSI technology, the systolic array is considered as practically realizable, where a large number of processors are placed on a chip to perform a parallel computation. the systolic array is a dedicated VLSI, which has a hardware structure depending on the algorithm. Consequently, a problem is how to design the systolic array corresponding to the given algorithm. This paper proposes an automatic synthesis for the systolic array using the dependence vector representing the data dependence. It is noted first that the systolic array is determined by the vector along the projection direction and the vector along the computation direction of the data dependence graph. the constraint for the forementioned two vectors is derived for the systolic graph. the constraint for the forementioned two vectors is derived for the systolic array to be realizable. Then using the constraint, the systolic array is derived systematically. A feature of the proposed method is that more than one systolic array corresponding to an algorithm can be constructed without a duplication. the systolic array in which processors operate in different ways, can also be derived. Finally, the proposed method is applied to the matrix multiplication, convolution and LD decomposition, indicating its usefulness.