Static rate-optimal scheduling of iterative data-flow programs via optimum unfolding
- 1 January 1991
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Computers
- Vol. 40 (2) , 178-195
- https://doi.org/10.1109/12.73588
Abstract
Rate-optimal compile-time multiprocessor scheduling of iterative dataflow programs suitable for real-time signal processing applications is discussed. It is shown that recursions or loops in the programs lead to an inherent lower bound on the achievable iteration period, referred to as the iteration bound. A multiprocessor schedule is rate-optimal if the iteration period equals the iteration bound. Systematic unfolding of iterative dataflow programs is proposed, and properties of unfolded dataflow programs are studied. Unfolding increases the number of tasks in a program, unravels the hidden concurrently in iterative dataflow programs, and can reduce the iteration period. A special class of iterative dataflow programs, referred to as perfect-rate programs, is introduced. Each loop in these programs has a single register. Perfect-rate programs can always be scheduled rate optimally (requiring no retiming or unfolding transformation). It is also shown that unfolding any program by an optimum unfolding factor transforms any arbitrary program to an equivalent perfect-rate program, which can then be scheduled rate optimally. This optimum unfolding factor for any arbitrary program is the least common multiple of the number of registers (or delays) in all loops and is independent of the node execution times. An upper bound on the number of processors for rate-optimal scheduling is given.Keywords
This publication has 27 references indexed in Scilit:
- Nibble-serial arithmetic processor designs via unfoldingPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2003
- A systematic approach for design of digit-serial signal processing architecturesIEEE Transactions on Circuits and Systems, 1991
- The high-level synthesis of digital systemsProceedings of the IEEE, 1990
- Pipeline interleaving and parallelism in recursive digital filters. I. Pipelining using scattered look-ahead and decompositionIEEE Transactions on Acoustics, Speech, and Signal Processing, 1989
- Algorithm transformation techniques for concurrent processorsProceedings of the IEEE, 1989
- Concurrent cellular VLSI adaptive filter architecturesIEEE Transactions on Circuits and Systems, 1987
- Preemptive Scheduling Under Time and Resource ConstraintsIEEE Transactions on Computers, 1987
- Scheduling periodically occurring tasks on multiple processorsInformation Processing Letters, 1981
- Scheduling Algorithms for Multiprogramming in a Hard-Real-Time EnvironmentJournal of the ACM, 1973
- Parallel Sequencing and Assembly Line ProblemsOperations Research, 1961