G.M. Megson
University of Newcastle upon Tyne. 1993
A method for the synthesis of so-called regular arrays from iterative algorithms with a certain class of non-linear data dependencies is considered. A general mapping theorem for index functions with integral valued non-linear components of recurrence subscripts is proposed. The technique is demonstrated by deriving two systolic arrays for the cyclic elimination algorithm applied to a set of N first-order linear recurrences. The first requires O(N) processors and employs non-stationary data flow. The second uses O(N2) cells and some stationary data. Both designs compute in O(N + Log2N) steps which allowing for the regular nature of the architecture is close to optimal.