Range Chart-Guided Iterative Data-Flow-Graph Scheduling

S.M. Heemstra de Groot, Sabih H. Gerez, O.E. Herrmann

    Research output: Contribution to journalArticleAcademicpeer-review

    68 Citations (Scopus)
    328 Downloads (Pure)


    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 examples
    Original languageUndefined
    Pages (from-to)351-364
    Number of pages14
    JournalIEEE transactions on circuits and systems
    Issue number5
    Publication statusPublished - 1992


    • METIS-111726
    • IR-14664

    Cite this