Previous | [1] | [2] | [3] | [4] | [5] |

Equivalent Transformations on Systolic Design

Represented by Generating Functions

**Young-Chang Hou and Jong-Chuang Tsay**

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.

REFERENCES

- Hou, Y. C. and Tsay, J. C., "An algebraic model for representing equivalent designs of systolic arrays," in
*Proc. Of ISMM International Symposium*, December 1988, Florida, pp. 163-166.

- Tsay, J. C. and Hou, Y. C., "On equivalent systolic designs of matrix multiplication and its algebraic respresentation," in
*Proc. Of International Computer Symposium*, December, 1988, Taiwan, pp. 247-252.

- Yuan, S.,
*An Algebraic Notation for the Design and Verification of Systolic Arrays*, M. S. Thesis, National Chiao Tung University, Hsinchu, R.O.C., June, 1987.