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

Author

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

Author_Institution

Fac. of Electr. Eng., Twente Univ., Enschede, Netherlands

Volume

39

Issue

1

fYear

1992

fDate

1/1/1992 12:00:00 AM

Firstpage

49

Lastpage

52

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

Keywords

iterative methods; parallel algorithms; parallel processing; polynomials; directed loop; iteration-period bound; longest path matrices; polynomial time algorithm; rate-optimal scheduling; recursive data flow graphs; total computational delay; Circuits; Concurrent computing; Data flow computing; Delay; Digital signal processing; Iterative algorithms; Parallel processing; Polynomials; Processor scheduling; Scheduling algorithm;

fLanguage

English

Journal_Title

Circuits and Systems I: Fundamental Theory and Applications, IEEE Transactions on

Publisher

ieee

ISSN

1057-7122

Type

jour

DOI

10.1109/81.109243

Filename

109243