Abstract:
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 paper, we propose a three-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. We prove
that the SSP method is correct and at least as efficient as other
modulo scheduling methods.