Research

 
2007 MS Thesis

Master of Science Thesis

Rice University, Houston, TX, April, 2007

Tuning an Adaptive-Compilation Search Space with Loop Unrolling

Jeffrey A. Sandoval

This thesis demonstrates that careful selection of compiler transformations can improve the output and reduce the compile-time cost of adaptive compilation. Compiler effectiveness depends on the order of code transformations applied. Adaptive compilation, then, uses empirical search to tune the transformation sequence for each program. This method achieves higher performance than traditional compilers, but often requires large compilation times. Previous research reduces compilation time by tuning the search process. This thesis, instead, tunes the search space by adding a loop unroller, addressing a deficiency in our compiler. Despite increasing the search-space size, this change results in more effective and efficient searching. Averaged across nine benchmarks, the adaptive compiler produces code, more quickly, that is 10% faster. Unfortunately, implementing a loop unroller is non-trivial for our low-level intermediate language. Therefore, this thesis also contributes an algorithm for identifying and unrolling loops in the absence of high-level loop structures.

msthesis.pdf [596 KB]
 
2007 SMART Paper

First Workshop on Statistical and Machine learning approaches applied to ARchitectures and compilaTion (SMART'07)

Ghent, Belgium, January 28, 2007

Tuning an Adaptive Compiler

Keith D. Cooper, Tim Harvey, and Jeff Sandoval

Adaptive compilation is a technique for feedback-driven selection of program-specific or procedure-specific sequences of code optimizations. Adaptive compilers find effective compilation sequences using search, machine learning, genetic algorithms, and limited enumeration. A growing body of literature has established that no single sequence works well for all codes.

Active research in this area focuses on a number of problems, including finding better search techniques, understanding the search spaces, and reducing the cost of evaluating distinct sequences. This paper examines how the "best" sequences change when we add a new transformation to the search space. Specifically, we added a loop unroller to our pool of optimizations; it changed the "best" sequences and improved overall performance on a suite of benchmark codes.

2007-SMART.pdf [96 KB]
 

This poster and corresponding presentation received an Honorable Mention award in the 2006 LACSI Symposium Poster Competition

2006 LACSI Poster

LACSI Symposium 2006, Poster Session and Talk

Santa Fe, NM, October 17-19, 2006

Adaptive Compilation Insights into Compiler Implementation

Jeff Sandoval, Keith Cooper

Adaptive compilation has been shown to improve compiler effectiveness over traditional techniques. However, an equally important result of this research is increased understanding of the behavior of compilers. By ignoring assumptions about compiler optimizations, adaptive compilation research has offered unexpected insight into the improvement of our research compiler. This poster presents the addition of a new transformation to our compiler, prompted by surprising behavior from the adaptive compiler.

The adaptive compiler selects and orders transformations based on the specific context of each input code; this technique exploits the interaction between transformations, maximizing an objective function with a feedback directed compile-execute-adapt cycle. During our experiments, we noticed that the adaptive compiler often selected the loop-peel transformation multiple times in a single compilation sequence. Though our intended use of loop-peel was to prepare the code for loop-unswitching and Cytron-Lowry-Zadeck code motion, the adaptive compiler found a secondary, unintended use for loop-peel: reducing loop overhead. While each successive application of loop-peel can potentially reduce loop-overhead for a single iteration, a more powerful transformation, loop-unrolling, can reduce loop overhead for every iteration. The unexpected use of loop-peel, only observed because the adaptive compiler ignores assumptions about the behavior of transformations, led us to the writing of a loop-unroller pass to improve the efficiency and effectiveness of the adaptive compiler.

Adding a new pass to the adaptive compiler essentially enlarges the search space. This poster presents empirical results that demonstrate, because the opportunity for loop-unrolling often exists in our benchmarks, we are able to search this larger space just as effectively as without loop-unrolling. Considering two metrics for our search, quality of code produced and speed of search, we show that the adaptive compiler finds better solutions with the loop-unroller, and it finds similar quality solutions quicker. Even though adding another pass increases the size of the search space, our search techniques are actually more effective because they are able to take advantage of the existing opportunities for loop unrolling.

Poster.pdf [232 KB] | Poster.jpg [972 KB] | Presentation.pdf [900 KB]
 
2006 PLDI Poster

PLDI 2006, Poster Session

Ottawa, Canada, June 10-16, 2006

Adaptive Compilation Insights into Compiler Implementation

Jeff Sandoval, Keith D. Cooper

Adaptive compilation has been shown to improve compiler effectiveness over traditional techniques. However, an equally important result of this research is increased understanding of the behavior of compilers. By ignoring assumptions about compiler optimizations, adaptive compilation research has offered unexpected insight into the improvement of our research compiler. This poster presents the addition of a new transformation to our compiler, prompted by surprising behavior from the adaptive compiler.

The adaptive compiler selects and orders transformations based on the specific context of each input code; this technique exploits the interaction between transformations, maximizing an objective function with a feedback directed compile-execute-adapt cycle. During our experiments, we noticed that the adaptive compiler often selected the loop-peel transformation multiple times in a single compilation sequence. Though our intended use of loop-peel was to prepare the code for loop-unswitching and Cytron-Lowry-Zadeck code motion, the adaptive compiler found a secondary, unintended use for loop-peel: reducing loop overhead. While each successive application of loop-peel can potentially reduce loop-overhead for a single iteration, a more powerful transformation, loop-unrolling, can reduce loop overhead for every iteration. The unexpected use of loop-peel, only observed because the adaptive compiler ignores assumptions about the behavior of transformations, led us to the writing of a loop-unroller pass to improve the efficiency and effectiveness of the adaptive compiler. This poster will tell the story of this surprising discovery and show how the loop-unrolling pass changed the behavior of the adaptive compiler.

Poster.pdf [216 KB] | Poster.jpg [1420 KB]
 
2005 LACSI Poster

LACSI Symposium 2005, Poster Session

Santa Fe, NM, October 11-13, 2005

Improving Adaptive Compilation with Truncated Execution and Loop Unrolling

Jeff Sandoval, Keith D. Cooper, and Tim Harvey

Adaptive compilation uses artificial intelligence search techniques to select a sequence of compiler optimizations that maximizes an objective function, often performance. The payoff can be very high, resulting in up to 40% improvement over the default sequence of compiler passes. Unfortunately, these search methods require many iterations of a lengthy compile-execute-adapt feedback cycle, making adaptive compilation either unappealing or infeasible for many applications. This poster presents two different methods for reducing the cost of adaptive compilation.

The first approach, called truncated execution, shortens each iteration of the search by targeting an inefficiency in the execute stage. The inefficiency happens when the execution phase takes longer than the time of the best executable seen so far; there is no reason to finish this execution because it cannot improve the search results. Truncated execution enforces this cutoff, resulting in a more efficient execution stage.

The second method, adding a loop unroller optimization pass, attempts to improve the effectiveness of each iteration in the search. This has the potential to reduce the number of search iterations needed to find a good compilation sequence. Past experience shows that the loop-peel transformation often appears multiple times in good sequences because it reduces loop overhead. Loop unrolling also accomplishes this, but it affects every iteration of the loop instead of a single iteration. To perform loop unrolling at an arbitrary position in the compilation sequence, however, we must be able to unroll loops at the level of intermediate code. This poster presents the unique obstacles associated with detecting and unrolling loops when information about high-level loop constructs has been lost.

Poster.pdf [772 KB] | Poster.jpg [1380 KB]