S-Space College of Engineering/Engineering Practice School (공과대학/대학원) Dept. of Computer Science and Engineering (컴퓨터공학부) Journal Papers (저널논문_컴퓨터공학부)
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
- Issue Date
- IEEE Trans. Comput., vol. 40, pp.1225-1238, Nov. 1991
- Data flow ; data-dependent iteration ; parallel processors ; parallelizing compilers ; quasi-static scheduling ; scheduling
- 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.
- Files in This Item: There are no files associated with this item.
Items in S-Space are protected by copyright, with all rights reserved, unless otherwise indicated.