SHERP

Compile-Time Scheduling and Assignment of Data-Flow Program Graphs with Data-Dependent Iteration

Cited 23 time in webofscience Cited 36 time in scopus
Authors
Ha, Soonhoi; Lee, Edward A.
Issue Date
1991-11
Publisher
Institute of Electrical and Electronics Engineers (IEEE)
Citation
IEEE Trans. Comput., vol. 40, pp.1225-1238, Nov. 1991
Keywords
Data flowdata-dependent iterationparallel processorsparallelizing compilersquasi-static schedulingscheduling
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
URI
http://hdl.handle.net/10371/7556
DOI
https://doi.org/10.1109/12.102826
Files in This Item:
There are no files associated with this item.
Appears in Collections:
College of Engineering/Engineering Practice School (공과대학/대학원)Dept. of Computer Science and Engineering (컴퓨터공학부)Journal Papers (저널논문_컴퓨터공학부)
  • mendeley

Items in S-Space are protected by copyright, with all rights reserved, unless otherwise indicated.

Browse