Systolic multiplication - comparing two automatic systolic array design methods
Laura Ruff · 2009
Abstract. 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 [14], [15]), and a functional–based design method (see [6], [9], [10]). 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 tech-nique of space-time transformations. However, it also has some draw-backs. 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 in-ductive 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 (ac-cording to certain equations, which are general for function definitions