SYNTHESIZING SYSTOLIC ARRAYS FROM RECURRENCE EQUATIONS

We address the problem of synthesizing systolic arrays from recurrence equations. This problem has been studied by a number of researchers for the case where the dependencies in the recurrence are uniform. We first summarize this approach and present a number of results that make explicit the scope and limitations of such Uniform Recurrence Equations (UREs). To overcome the limitations we propose the class of Affine Recurrence Equations (AREs) which are a superset of UREs. In order to synthesize systolic arrays from such recurrences it is necessary to determine appropriate timing and allocation functions. We discuss techniques to determine such functions. We will also show that merely determining such functions is not enough to guarantee that the architecture is systolic. We therefore present a technique called data pipelining which enables us to derive systolic arrays from the ARE. © 1990.