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

Gerez, Sabih H. and Heemstra de Groot, Sonia M. and Herrmann, Otto E. (1992) A Polynomial-Time Algorithm for the Computation of the Iteration-Period Bound in Recursive Data-Flow Graphs. IEEE Transactions on Circuits and Systems I: Fundamental theory and applications, 39 (1). pp. 49-52. ISSN 1057-7122

Preview

PDF
317Kb

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
Item Type:	Article
Copyright:	© 1992 IEEE
Faculty:	Electrical Engineering, Mathematics and Computer Science (EEMCS)
Research Group:	Computer Architecture for Embedded Systems (CAES)
Link to this item:	http://purl.utwente.nl/publications/14661
Official URL:	http://dx.doi.org/10.1109/81.109243
Export this item as:	BibTeX EndNote HTML Citation Reference Manager

Show download statistics for this publication

Repository Staff Only: item control page

Metis ID: 111725