Software pipelining: a comparison and improvement
Reese B. Jones, Vicki H. Allan · International Symposium on Microarchitecture · 1990
Software pipelining can significantly increase the execution rate of loops. Each of the four major software pipelining algorithms takes a different approach to software pipelining. This paper discusses each method and explores some of the similarities and differences among the methods.On loops consisting of a single basic block, the Perfect Pipelining Algorithm [1] is the only software pipelining algorithm that currently achieves time optimality, in the absence of resource constraints. A technique for unrolling the loop before pipelining is presented as an improvement to software pipelining, as it can allow Lam's algorithm [2] to achieve time optimality for these restricted loops. Unrolling has an advantage over Perfect Pipelining because it can reduce the code space required for the software pipeline.