This thesis details the implementation of Swing Modulo Scheduling, a Software Pipelining technique, that is both effective and efficient in terms of compile time and generated code. Software Pipelining aims to expose Instruction Level Parallelism in loops which tend to help scientific and graphical applications.
Modulo Scheduling is a category of algorithms that attempt to overlap iterations of single basic block loops and schedule instructions based upon a priority (derived from a set of heuristics). The approach used by Swing Modulo Scheduling is designed to achieve a highly optimized schedule, keeping register pressure low, and does both in a reasonable amount of compile time.
One drawback of Swing Modulo Scheduling, (and all Modulo Scheduling algorithms) is that they are missing opportunities for further Instruction Level Parallelism by only handling single basic block loops. This thesis details extensions to the Swing Modulo Scheduling algorithm to handle multiple basic block loops in the form of a superblock. A superblock is group of basic blocks that have a single entry and multiple exits. Extending Swing Modulo Scheduling to support these types of loops increases the number of loops Swing Modulo Scheduling can be applied to. In addition, it allows Modulo Scheduling to be performed on hot paths (also single entry, multiple exit), found with profile information to be optimized later offline or at runtime.
Our implementation of Swing Modulo Scheduling and extensions to the algorithm for superblock loops were evaluated and found to be both effective and efficient. For the original algorithm, benchmarks were transformed to have performance gains of 10-33%, while the extended algorithm increased benchmark performance from 7-22%.
An Implementation of Swing Modulo Scheduling with Extensions for Superblocks, Tanya M. Lattner.
Masters Thesis, Computer Science Dept., University of Illinois at Urbana-Champaign, June 2005.
The "book form" is useful if you plan to print this out. Print the file out double sided, fold it in half, and staple it in the middle of the page. It dramatically reduces the number of pages of paper used.
@MastersThesis{Lattner:MSThesis05,
author = {Tanya M. Lattner},
title = "{An Implementation of Swing Modulo Scheduling with Extensions for Superblocks}",
school = "{Computer Science Dept., University of Illinois at Urbana-Champaign}",
year = {2005},
address = {Urbana, IL},
month = {June},
note = {{\em See {\tt http://llvm.cs.uiuc.edu}.}}
}