Young-Chang Hou and Jong-Chuang Tsay
Institute of Computer Science and Information Engineering
National Chiao Tung University
Hsinchu, Taiwan 30050, Republic of China
In this paper, we propose a method for representing and transforming a systolic design. For representing a systolic design, the generating function [3, 11, 13] is used. The generating function can be used to describe the location, velocity, and moving path of a data item at any given time. Several generating functions can be grouped together to form a "systolic flow". When we use the systolic flow to represent a systolic design and apply a transformation matrix T on it, different generating functions which represent different but equivalent systolic designs of a given computation can be derived. We observe that the different elements in T play different transformation roles; hence, this gives us a guideline to select the elements in the transformation matrix.
Keywords: generating function, systolic array, equivalent transformation
Received October 17, 1988; revised July 28, 1989.
Communicated by Ferng-Ching Lin.