Stage Scheduling: A Technique to Reduce the Register Requirements of a Modulo Schedule

Alexandre E. Eichenberger, Edward S. Davidson


Modulo scheduling is an efficient technique for exploiting instruction level parallelism in a variety of loops, resulting in high performance code but increased register requirements. We present a set of low computational complexity stage-scheduling heuristics that reduce the register requirements of a modulo schedule by shifting operations by multiples of II cycles. Measurements on a benchmark suite of 1298 loops from the Perfect Club, SPEC-89, and the Livermore Fortran Kernels shows that our best heuristic achieves on average 99% of the optimal decrease in register requirements.


Register-sensitive modulo scheduling, software, pipelining, loop scheduling, instruction level parallelism, VLIW, superscalar.

Talk Overheads (227835 bytes)