A polynomial time algorithm for the computation of the iteration-period bound in recursive data flow graphs
- 1 January 1992
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Circuits and Systems I: Regular Papers
- Vol. 39 (1) , 49-52
- https://doi.org/10.1109/81.109243
Abstract
Rate-optimal scheduling of iterative data-flow graphs requires the computation of the iteration period bound. According to the formal definition, the total computational delay in each directed loop in the graph has to be calculated in order to determine that bound. As the number of loops cannot be expressed as a polynomial function of the number of modes in the graph, this definition cannot be the basis of an efficient algorithm. A polynomial-time algorithm for the computation of the iteration period bound based on longest path matrices and their multiplications is presenteKeywords
This publication has 7 references indexed in Scilit:
- Fast multiprocessor realizations of digital filtersPublished 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
- Static rate-optimal scheduling of iterative data-flow programs via optimum unfoldingIEEE Transactions on Computers, 1991
- Rate-optimal scheduling of recursive DSP algorithms based on the scheduling-range chartPublished by Institute of Electrical and Electronics Engineers (IEEE) ,1990
- Algorithm transformation techniques for concurrent processorsProceedings of the IEEE, 1989
- Static Scheduling of Synchronous Data Flow Programs for Digital Signal ProcessingIEEE Transactions on Computers, 1987
- The maximum sampling rate of digital filters under hardware speed constraintsIEEE Transactions on Circuits and Systems, 1981