Range-chart-guided iterative data-flow graph scheduling
Open Access
- 1 May 1992
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Circuits and Systems I: Regular Papers
- Vol. 39 (5) , 351-364
- https://doi.org/10.1109/81.139286
Abstract
An alternative method for the scheduling of iterative data-flow graphs is described. The method is based on the scheduling-range chart, which contains the information on the range within which each operation in the graph can be scheduled. The scheduling range is determined by considering the intraiteration and interiteration precedence relations. The goal is to find an optimal position within the scheduling range of each operation in such a way that some quality criteria (number of hardware resources, iteration period, latency, register lifetime) are optimized. A formal proof of the NP-completeness of the problem is given and two polynomial-time heuristics are introduced: fixed-rate (rate-optimal as a special case) scheduling where the number of hardware resources is optimized at the same time that a specific iteration period is guaranteed, and maximum-throughput scheduling with limited resources where the iteration period is optimized for a fixed number of processors. The algorithms are able to find optimal solutions for well-known benchmark exampleKeywords
This publication has 17 references indexed in Scilit:
- A topological sorting and loop cleansing algorithm for a constrained MIMD compiler of shift-invariant flow graphsPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2005
- Cyclo-static multiprocessor scheduling for the optimal realization of shift-invariant flow graphsPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2005
- Rate-optimal scheduling of recursive DSP algorithms based on the scheduling-range chartPublished by Institute of Electrical and Electronics Engineers (IEEE) ,1990
- Force-directed scheduling for the behavioral synthesis of ASICsIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 1989
- Scheduling Precedence Graphs in Systems with Interprocessor Communication TimesSIAM Journal on Computing, 1989
- Synchronous data flowProceedings of the IEEE, 1987
- SEHWA: A Program for Synthesis of PipelinesPublished by Institute of Electrical and Electronics Engineers (IEEE) ,1986
- The maximum sampling rate of digital filters under hardware speed constraintsIEEE Transactions on Circuits and Systems, 1981
- Local Microcode Compaction TechniquesACM Computing Surveys, 1980
- Optimal Scheduling Strategies in a Multiprocessor SystemIEEE Transactions on Computers, 1972