Improving Software Pipelining
with
Unroll-and-Jam and Memory Reuse Analysis



Chen Ding

Advisors:
Dr. Philip Sweany
Dr. Steve Carr


THESIS ABSTRACT



The high performance of today's microprocessors is achieved mainly by fast, multiple-issue hardware and optimizing compilers that together exploit the instruction-level parallelism (ILP) in programs. Software pipelining is a popular loop optimization technique in today's ILP compilers. However, four difficulties may prevent the optimal performance of software pipelining: insufficient parallelism in innermost loops, the memory bottleneck, hardware under-utilization due to uncertain memory latencies, and unnecessary recurrences due to the reuse of registers (false recurrences).

This research uses an outer-loop unrolling technique, unroll-and-jam, to solve the first and second problems. It shows, both in theory and experiment, that unroll-and-jam can solve the first problem by exploiting cross-loop parallelism in nested loops. Unroll-and-jam can also automatically remove memory bottleneck for loops. This research discovered that for 22 benchmark and kernel loops tested, a speed improvement of over 40\% is obtained by unroll-and-jam.

For solving the uncertain memory latencies, this research uses a compiler technique, memory reuse analysis. Using memory reuse analysis can significantly improve hardware utilization. For the experimental suite of 140 benchmark loops tested, using memory reuse analysis reduced register pressure by 10\% to 22\% compared to compiling the same loops assuming all memory acesses were cache misses.

False recurrences restrict the use of all available parallelism in loops. To date, the only method proposed to remove effect of the false recurrences requires additional hardware support for rotating register files. Compiler techniques such as modulo variable expansion \cite{Lam88a} are neither complete nor efficient for this purpose. This thesis proposes a new method that can eliminate the effect of false recurrence completely at a minimum register cost for conventional machines that do not contain rotating register files.



Download the thesis (pdf) or (compressed ps) .