Parallel Performance Project Research Paper

Research Paper

Stage Scheduling: A Technique to Reduce the Register Requirements of a Modulo Schedule
A. E. Eichenberger and E. S. Davidson
Proceedings of the 28th Annual International Symposium on Microarchitecture, pp 338-349, November 95.

Abstract

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 given modulo schedule by shifting operations by multiples of $II$ cycles. Measurements on a benchmark suite of 1289 loops from the Perfect Club, SPEC-89, and the Livermore Fortran Kernels shows that our best heuristic achieves on average 99% of the decrease in register requirements obtained by an optimal stage scheduler.