Range Chart-Guided Iterative Data-Flow-Graph Scheduling

Heemstra de Groot, Sonia M. and Gerez, Sabih H. and Herrmann, Otto E. (1992) Range Chart-Guided Iterative Data-Flow-Graph Scheduling. IEEE Transactions on Circuits and Systems I: Fundamental theory and applications, 39 (5). pp. 351-364. ISSN 1057-7122

Preview

PDF
1280Kb

Abstract:	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
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/14664
Official URL:	http://dx.doi.org/10.1109/81.139286
Export this item as:	BibTeX EndNote HTML Citation Reference Manager

Show download statistics for this publication

Repository Staff Only: item control page

Metis ID: 111726