DocumentCode :
1392660
Title :
Scheduling data-flow graphs via retiming and unfolding
Author :
Chao, Liang-Fang ; Sha, Edwin Hsing-Mean
Author_Institution :
Dept. of Electr. Eng. & Comput. Eng., Iowa State Univ., Ames, IA, USA
Volume :
8
Issue :
12
fYear :
1997
fDate :
12/1/1997 12:00:00 AM
Firstpage :
1259
Lastpage :
1267
Abstract :
Loop scheduling is an important problem in parallel processing. The retiming technique reorganizes an iteration; the unfolding technique schedules several iterations together. We combine these two techniques to obtain a static schedule with a reduced average computation time per iteration. We first prove that the order of retiming and unfolding is immaterial for scheduling a data-flow graph (DFG). From this nice property, we present a polynomial-time algorithm on the original DFG, before unfolding, to find the minimum-rate static schedule for a given unfolding factor. For the case of a unit-time DFG, efficient checking and retiming algorithms are presented
Keywords :
computational complexity; data flow graphs; parallel programming; processor scheduling; checking; data-flow graphs; loop scheduling; polynomial-time algorithm; reduced average computation time; retiming; static schedule; unfolding; Chaos; Delay; Digital signal processing; High level synthesis; Iterative algorithms; Parallel processing; Polynomials; Processor scheduling; Scheduling algorithm; Very large scale integration;
fLanguage :
English
Journal_Title :
Parallel and Distributed Systems, IEEE Transactions on
Publisher :
ieee
ISSN :
1045-9219
Type :
jour
DOI :
10.1109/71.640018
Filename :
640018
Link To Document :
بازگشت