A Polynomial-Time Algorithm for the Computation of the Iteration-Period Bound in Recursive Data-Flow Graphs

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

    Research output: Contribution to journalArticleAcademicpeer-review

    22 Citations (Scopus)
    69 Downloads (Pure)

    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 presented
    Original languageUndefined
    Pages (from-to)49-52
    Number of pages4
    JournalIEEE transactions on circuits and systems I: fundamental theory and applications
    Volume0
    Issue number1
    DOIs
    Publication statusPublished - 1992

    Keywords

    • IR-14661
    • METIS-111725

    Cite this