Range Chart-Guided Iterative Data-Flow-Graph Scheduling

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

doi:10.1109/81.139286

Range Chart-Guided Iterative Data-Flow-Graph Scheduling

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

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

68 Citations (Scopus)

240 Downloads (Pure)

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

Original language	Undefined
Pages (from-to)	351-364
Number of pages	14
Journal	IEEE transactions on circuits and systems
Volume	0
Issue number	5
DOIs	https://doi.org/10.1109/81.139286
Publication status	Published - 1992

Keywords

METIS-111726
IR-14664

Access to Document

10.1109/81.139286

00139286

Cite this

@article{74bf38cc255841c9aaad38dd78407d8e,

title = "Range Chart-Guided Iterative Data-Flow-Graph Scheduling",

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

keywords = "METIS-111726, IR-14664",

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

year = "1992",

doi = "10.1109/81.139286",

language = "Undefined",

volume = "0",

pages = "351--364",

journal = "IEEE transactions on circuits and systems",

issn = "0098-4094",

publisher = "IEEE",

number = "5",

}

TY - JOUR

T1 - Range Chart-Guided Iterative Data-Flow-Graph Scheduling

AU - Heemstra de Groot, S.M.

AU - Gerez, Sabih H.

AU - Herrmann, O.E.

PY - 1992

Y1 - 1992

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

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

KW - METIS-111726

KW - IR-14664

U2 - 10.1109/81.139286

DO - 10.1109/81.139286

M3 - Article

VL - 0

SP - 351

EP - 364

JO - IEEE transactions on circuits and systems

JF - IEEE transactions on circuits and systems

SN - 0098-4094

IS - 5

ER -