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) .