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

Sabih H. Gerez; Sonia M. Heemstra de Groot; Otto E. Herrmann

doi:10.1109/81.109243

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

Sabih H. Gerez, Sonia M. Heemstra de Groot, Otto E. Herrmann

Research output: Contribution to journal › Article › Academic › peer-review

26 Citations (Scopus)

146 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 language	English
Pages (from-to)	49-52
Number of pages	4
Journal	IEEE transactions on circuits and systems I: fundamental theory and applications
Volume	39
Issue number	1
DOIs	https://doi.org/10.1109/81.109243
Publication status	Published - 1992

Access to Document

10.1109/81.109243

Gerez1992polynomial-timeFinal published version, 318 KB

26 Citations
1 Report

A Polynomial-time algorithm for the computation of the iteration-period bound in recursive data-flow graphs
Gerez, S. H., Heemstra de Groot, S. M. & Herrmann, O. E., 1 Jan 1990, Enschede: Universiteit Twente EL/BSC.
Research output: Book/Report › Report › Professional

Cite this

@article{2ef7a2faa2f94a3b8b9425798d5dd1ad,

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

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",

author = "Gerez, {Sabih H.} and {Heemstra de Groot}, {Sonia M.} and Herrmann, {Otto E.}",

year = "1992",

doi = "10.1109/81.109243",

language = "English",

volume = "39",

pages = "49--52",

journal = "IEEE transactions on circuits and systems I: fundamental theory and applications",

issn = "1057-7122",

publisher = "IEEE",

number = "1",

}

A Polynomial-Time Algorithm for the Computation of the Iteration-Period Bound in Recursive Data-Flow Graphs. / Gerez, Sabih H.; Heemstra de Groot, Sonia M.; Herrmann, Otto E.
In: IEEE transactions on circuits and systems I: fundamental theory and applications, Vol. 39, No. 1, 1992, p. 49-52.

Research output: Contribution to journal › Article › Academic › peer-review

TY - JOUR

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

AU - Gerez, Sabih H.

AU - Heemstra de Groot, Sonia M.

AU - Herrmann, Otto E.

PY - 1992

Y1 - 1992

N2 - 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

AB - 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

U2 - 10.1109/81.109243

DO - 10.1109/81.109243

M3 - Article

SN - 1057-7122

VL - 39

SP - 49

EP - 52

JO - IEEE transactions on circuits and systems I: fundamental theory and applications

JF - IEEE transactions on circuits and systems I: fundamental theory and applications

IS - 1

ER -

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

Abstract

Access to Document

Fingerprint

Research output

A Polynomial-time algorithm for the computation of the iteration-period bound in recursive data-flow graphs

Cite this