TY - JOUR
T1 - Wavesched
T2 - A novel scheduling technique for control-flow intensive designs
AU - Lakshminarayana, Ganesh
AU - Khouri, Kamal S.
AU - Jha, Niraj K.
N1 - Funding Information:
Manuscript received February 26, 1998; revised June 2, 1998. This work was supported in part by the National Science Foundation (NSF) under Grant MIP-9319269 and by Alternative System Concepts, Inc. under a small business innovative research (SBIR) contract from Air Force Rome Laboratories. This paper was recommended by Associate Editor R. Camposano. G. Lakshminarayana is with NEC CCRL, Princeton, NJ 08540 USA. K. S. Khouri and N. K. Jha are with Princeton University, Princeton, NJ 08544 USA. Publisher Item Identifier S 0278-0070(99)02967-X.
PY - 1999
Y1 - 1999
N2 - In this paper, we present a novel scheduling algorithm targeted toward minimizing the average execution time of control-flow intensive behavioral descriptions. Our algorithm uses a control/data flow graph model, which preserves the parallelism inherent in the application. It explores previously unexplored regions of the solution space by its ability to overlap the schedules of independent iterative constructs, whose bodies share resources. It also incorporates well known optimization techniques like loop unrolling in a natural fashion. This is made possible by a general loop-handling technique, which we have devised. Application of the algorithm to several common benchmarks demonstrates up to 4.8-fold improvement in expected schedule length over existing scheduling algorithms, without paying a price in terms of the best and worst case schedule lengths required to execute the behavioral description (in fact, frequently, the best/worst case schedule lengths are also better for our algorithm).
AB - In this paper, we present a novel scheduling algorithm targeted toward minimizing the average execution time of control-flow intensive behavioral descriptions. Our algorithm uses a control/data flow graph model, which preserves the parallelism inherent in the application. It explores previously unexplored regions of the solution space by its ability to overlap the schedules of independent iterative constructs, whose bodies share resources. It also incorporates well known optimization techniques like loop unrolling in a natural fashion. This is made possible by a general loop-handling technique, which we have devised. Application of the algorithm to several common benchmarks demonstrates up to 4.8-fold improvement in expected schedule length over existing scheduling algorithms, without paying a price in terms of the best and worst case schedule lengths required to execute the behavioral description (in fact, frequently, the best/worst case schedule lengths are also better for our algorithm).
UR - http://www.scopus.com/inward/record.url?scp=0032627685&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=0032627685&partnerID=8YFLogxK
U2 - 10.1109/43.759064
DO - 10.1109/43.759064
M3 - Article
AN - SCOPUS:0032627685
SN - 0278-0070
VL - 18
SP - 505
EP - 523
JO - IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems
JF - IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems
IS - 5
ER -