Improving software pipelining with unroll-and-jam

ii The high performance of today’s microprocessors is achieved mainly by fast, multipleissuing 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 bottlenecks for loops. This research discovered that for 22 benchmark and kernel loops tested, a speed improvement of over 50 % is obtained by unroll-and-jam. For solving the uncertain memory latencies, this research uses a compiler technique