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

Journal of Inforamtion Science and Engineering, Vol.5 No.3, pp.229-250 (July 1989)
Equivalent Transformations on Systolic Design
Represented by Generating Functions

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.

REFERENCES

  1. 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.
  1. 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.
  1. 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.