HP Labs Technical Reports

Click here for full text: PDF

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

[Research] [News] [Tech Reports] [Palo Alto] [Bristol] [Japan] [Israel] [Site Map] [Home] [Hewlett-Packard]