HP Labs Technical Reports
Click here for full text:
Spill-Free Parallel Scheduling of Precedence Graphs
Natarajan, Balas; Schlansker, Michael
Abstract: This paper concerns the problem of spill-free scheduling of acyclic precedence graphs on a processor with multiple functional units and a limited number of registers. The problem of minimizing the schedule length is well known to be computationally intractable. We present a heuristic for the problem, a general divide-and-conquer paradigm that converts any insensitive scheduling algorithm--one that is insensitive to register constraints--to one that respects register constraints. We estimate the goodness of the heuristic by relating its performance to that of the insensitive algorithm. We also present experimental results obtained by applying the heuristic to basic blocks from the SPEC benchmark programs, for several machine models.
Back to Index