Systolic multiplication – comparing two automatic systolic array design methods.

*(English)*Zbl 1190.68006Summary: This paper provides a comparison between two automatic systolic array design methods: the so-called space-time transformation methodology (a unifying approach to the design of VLSI algorithms), and a functional-based design method. The advantages (and possible disadvantages) of each method are pointed out by representative case studies (variants of systolic arrays generated with both design methods).

Many algorithms were already parallelised using the efficient technique of space-time transformations. However, it also has some drawbacks. It may be hard to formulate the problem to be solved in the form of a system of uniform recurrence equations, which is the usual starting point for this method. On the other hand, the space-time transformation method depends heavily on finding an affine timing function, which can also lead to complex computations.

The functional-based method exploits the similarity between the inductive structure of a systolic array and the inductive decomposition of the argument by a functional program. Although it is less general in the sense that it generates systolic arrays with certain properties, its most significant advantage is that it needs to investigate the behaviour of only the first processor of the systolic array, while other methods (as the space-time transformation method, too) must work with an array of processors. Moreover, the method is based on rewriting of terms (according to certain equations, which are general for function definitions and systolic arrays), thus the resulting systolic algorithm is certified to be correct, and the method itself is relatively easy to automatize.

Many algorithms were already parallelised using the efficient technique of space-time transformations. However, it also has some drawbacks. It may be hard to formulate the problem to be solved in the form of a system of uniform recurrence equations, which is the usual starting point for this method. On the other hand, the space-time transformation method depends heavily on finding an affine timing function, which can also lead to complex computations.

The functional-based method exploits the similarity between the inductive structure of a systolic array and the inductive decomposition of the argument by a functional program. Although it is less general in the sense that it generates systolic arrays with certain properties, its most significant advantage is that it needs to investigate the behaviour of only the first processor of the systolic array, while other methods (as the space-time transformation method, too) must work with an array of processors. Moreover, the method is based on rewriting of terms (according to certain equations, which are general for function definitions and systolic arrays), thus the resulting systolic algorithm is certified to be correct, and the method itself is relatively easy to automatize.