Effective Scheduling of Directed Acyclic Graphs under Register Constraints

Balas Natarajan, Michael Schlansker


This paper concerns the problem of scheduling a directed acylic data dependency graph on a machine with multiple functional units with a limited number of registers, in the absence of spill. The problem of minimizing the schedule length is well known to be computationally difficult. We present a heuristic for the problem, as well as an estimate of the goodness of the approximation achieved by the heuristic for a restricted case where all the functional units are identical to one another, and the vertices of the graph are of unit duration. We also present experimental results obtained by running the algorithm on randomly chosen directed acyclic graphs, for various choices of the number of functional units and registers available.


Scheduling, register constraints, instruction level parallelism.

Talk Overheads (18427 bytes)