A delay distribution methodology for the optimal systolic synthesis of linear recurrence algorithms

A systematic methodology based on the concept of delay distribution to optimize the systolic scheduling of data flow graphs, which represent one-dimensional linear recurrence algorithms (LRAs) is introduced. Step-by-step examples are given to illustrate the procedure. It is shown that this procedure produces optimally scheduled data flow graphs (DFGs) for VLSI systolic implementation. The goal is to transform the DFG of a linear recurrence algorithm into an optimal form for VLSI systolic implementation. Considerable improvements have been achieved over previous works. Comparisons are made between the authors´ and previous designs on the examples of infinite impulse response (IIR) filters and finite impulse response (FIR) filters. Finally, a generalization of the procedure to N-dimensional linear recurrence algorithms is given, using the one-dimensional case as its basis