Traditionally, software pipelining is applied either to the innermost loop of a given loop nest or from the innermost loop to outer loops. In this talk, we introduce a 3-step approach, called Single-dimension Software Pipelining (SSP), to software pipeline a loop nest at an arbitrary loop level.
The first step identifies the most profitable loop level for software pipelining in terms of initiation rate or data reuse potential. The second step simplifies the multi-dimensional data-dependence graph (DDG) into a 1-dimensional DDG and constructs a 1-dimensional schedule for the selected loop level. The third step derives a simple mapping function which specifies the schedule time for the operations of the multi-dimensional loop, based on the 1-dimensional schedule.
In the talk, we first introduce the above methodology, then the issues of code generation. We prove that SSP method is correct and at least as efficient as other modulo scheduling methods. Experimental results on a small number of loops show significant performance improvements over existing modulo scheduling methods.