Effective Scheduling of Directed Acyclic Graphs under Register Constraints
Balas Natarajan, Michael Schlansker
Abstract
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.
Keywords
Scheduling, register constraints, instruction level parallelism.
Talk
Overheads (18427 bytes)