Hypernode Reduction Modulo Scheduling
Josep Llosa, Mateo Valero, Eduard Ayguade, Antonio Gonzalez
Software Pipelining is a loop scheduling technique that extracts
parallelism from loops by overlapping the execution of several
consecutive iterations. Most prior scheduling research has focused on
achieving minimum execution time, without regarding register requirements.
Most strategies tend to stretch operand lifetimes because they
schedule some operations too early or too late.
The paper presents a novel strategy that simultaneously
schedules some operations late and other operations early,
minimizing all the stretchable dependencies and therefore reducing the
registers required by the loop.
The key of this strategy is a pre-ordering phase that selects the order
in which the operations will be scheduled.
The results show that the method described in this
paper performs better than other heuristic methods and almost as well as a
linear programming method but requiring much less time to produce the
Keywords: Instruction Scheduling, Loop Scheduling, Software
Pipelining, Register Allocation, Register Spilling.
Overheads (202865 bytes)