Publications
Detailed Information
Compile-Time Scheduling and Assignment of Data-Flow Program Graphs with Data-Dependent Iteration
Cited 24 time in
Web of Science
Cited 38 time in Scopus
- Authors
- Issue Date
- 1991-11
- Citation
- IEEE Trans. Comput., vol. 40, pp.1225-1238, Nov. 1991
- Keywords
- Data flow ; data-dependent iteration ; parallel processors ; parallelizing compilers ; quasi-static scheduling ; scheduling
- Abstract
- Four scheduling strategies for dataflow graphs onto parallel processors are classified: (1) fully dynamic, (2) static-assignment, (3) self-timed, and (4) fully static. Scheduling techniques valid for strategies (2), (3), and (4) are proposed. The focus is on dataflow graphs representing data-dependent iteration. A known probability mass function for the number of cycles in the data-dependent iteration is assumed, and how a compile-time decision about assignment and/or ordering as well as timing can be made is shown. The criterion used is to minimize the expected total idle time caused by the iteration. In certain cases, this will also minimize the expected makespan of the schedule. How to determine the number of processors that should be assigned to the data-dependent iteration is shown. The method is illustrated with a practical programming example.
- ISSN
- 0018-9340
- Language
- English
- Files in This Item:
- There are no files associated with this item.
Item View & Download Count
Items in S-Space are protected by copyright, with all rights reserved, unless otherwise indicated.