Synthesizing systolic arrays from recurrence equations (Q749184)

The paper in its first part summarizes results on synthesizing systolic arrays from recurrence relations of special form as follows \(f(p)=g(f(p+\omega_ 1),f(p+\omega_ 2)...f(p+\omega_ k))\), where p and \(\omega_ i\) for \(i=1,2,...,k\) are constant n-dimensional vectors with integer coordinates. Although earlier results show a certain equivalence between systolic arrays and such systems of equations in the sense that timing and allocation functions can always be constructed, the authors feel that a generalization leads to easier derivation of the systolic architecture. Their generalization starts with the equation \(f(p)=g(f(A_ 1p+\omega_ 1)\), \(f(A_ 2p+\omega_ 2),...,f(A_ kp+\omega_ k))\), where \(A_ i\) are constant \(n\times n\) matrices. The construction of timing and allocation functions is described, and a pipelining theorem is formulated. This theorem imposes some restrictions on the matrices \(A_ i\). The results lead to the proposal of a synthesis procedure for systolic arrays.