Title: Synthesis of systolic algorithms and processor arrays
Abstract: A formal definition of a systolic array and a systolic algorithm is given. The design of a systolic array and the necessary input-output relations for a given computational problem include the design of an algorithm expressed in terms of a functional graph as an intermediate level. A discipline is introduced in the design process by identifying the features of a class of algorithms which can be embedded in systolic arrays. Cluster-homogeneous functional graphs with cluster-independent data dependences are shown to represent systolic algorithms. The proof of the theorem given is a realization procedure at the same time. The approach used is illustrated on the 1-D-convolution. The transformations used to obtain different designs are more general than those used elsewhere /4/ and have a larger field of application. The set of the linear 1-D systolic designs for the 1-D-convolution is shown to be enumerable and the different designs are grouped together in 7 classes and 42 groups (36 in case of symmetry in two of the classes). A minimal (in some sense) design can be given for each of the 42 groups. Eight of these designs, however, were given by H. T. Kung elsewhere /3/.
Publication Year: 1986
Publication Date: 1986-01-01
Language: en
Type: book-chapter
Indexed In: ['crossref']
Access and Citation
Cited By Count: 1
AI Researcher Chatbot
Get quick answers to your questions about the article from our AI researcher chatbot