Iterative Modulo Scheduling: A Practical Approach to Software Pipelining

Modulo scheduling serves as a framework for defining algorithms that facilitate software pipelining of innermost loops. This framework establishes a set of constraints essential for achieving a legal modulo schedule. Various algorithms and heuristics can be developed within this framework, yet limited work has been conducted to evaluate and compare these alternatives. The perception that modulo scheduling is computationally expensive and challenging to implement has hindered its adoption in product compilers. The report introduces iterative modulo scheduling, a practical algorithm adept at handling realistic machine models. It characterizes the algorithm based on the quality of generated schedules and the computational costs involved. The significance of this framework lies in its potential to enhance instruction-level parallelism (ILP) by optimizing the scheduling of operations across loop iterations, thereby improving overall performance.

Various techniques exist within the realm of modulo scheduling. One prominent method is the unroll-before-scheduling approach, which involves unrolling the loop multiple times before applying a global acyclic scheduling algorithm. This technique allows for overlapping iterations but introduces a scheduling barrier at the back-edge. The performance degradation associated with this method can be mitigated by increasing the extent of unrolling, albeit at the cost of increased code size and scheduling effort. Another method, software pipelining, eliminates scheduling barriers by moving instructions across the back-edge of the loop. This approach requires careful replication and unification of operations as they traverse splits and merges in the control flow graph. The challenge lies in determining which operations to move and in which direction, as excessive code motion can lead to increased register pressure and diminished performance.

The schedule-then-move approach focuses on creating a schedule that maximizes performance while identifying implicit code motions. One method within this approach is unroll-while-scheduling, which simultaneously unrolls and schedules the loop until a repetitive portion of the schedule is reached. This requires maintaining the state of the scheduling process, including knowledge of active iterations and allocated resources. The engineering challenges associated with this method have yet to be fully addressed, although strategies such as the Petri net approach offer potential solutions. By concentrating on generating effective schedules without scheduling barriers, this approach can yield superior results, particularly in loops with control flow. The framework of modulo scheduling specifies constraints necessary for achieving a legal schedule, ensuring that no intra- or inter-iteration dependencies are violated.

The practical applications of iterative modulo scheduling are significant in the context of modern compiler design. By optimizing the scheduling of loop iterations, this framework enhances the efficiency of instruction execution, thereby improving overall program performance. The ability to handle realistic machine models makes this approach particularly valuable in real-world scenarios. The report emphasizes the importance of understanding the constraints and objectives of modulo scheduling, such as the initiation interval (II), which governs the timing of successive iterations. With appropriate hardware support, the potential for minimal code expansion further underscores the efficiency of this scheduling method. The insights gained from this report contribute to the ongoing development of advanced scheduling techniques, ultimately benefiting compiler optimization and software performance.