In thk paper a novel approach is presented to schedule iterative tasks on two-level pipelines under resource constraints, such that the executions of both high level iterations and low level operations are pipelined.Firs4 we limit the discussion to the case where none of the functional units is pipelined and pipelining is performed only at the global iteration level.Then we generalize it to the case where both global iterations and functional units are pipelined.We present the problem as an integer linear programming formulation and obtain the best solution which miniiizes the total execution time.Experimental resuhs show that the proposed algorithm produces optimal solutions for all the test cases we have tried within a few sewnds.

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.>