Hypernode reduction modulo scheduling
Josep Llosa, Mateo Valero, Eduard Ayguadé, Antonio M. González · 1995
Software Pipelining is a loop scheduling technique that extracts parallelism from loops by overlapping the execution of several consecutive iterations. Prior scheduling research has focused on achieving minimal execution time, without regarding register requirements Unidirectional strategies (top-down or bottom-up) tend to stretch operand lifetimes because they schedule some operations too early/late. The paper presents a novel bidirectional 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 pre-ordering heuristic guarantees that, when an operation is selected to be scheduled into the current partial scheduling, there are only predecessors or successors of the operation that have been already scheduled. An operation will be schedul...