Overview
This project, funded by the National Science Foundation's
ITR Program (grant number CCR-0205303) and the Los Alamos
Computer Science Institute, is exploring
fundamental issues that relate to the structure and effectiveness
of optimizing compilers.
Specifically, we are developing the technology needed to build,
deploy, and use adaptive optimizing compilers -- compilers that
change their behavior in response to the application being compiled,
the target machine for the compilation, and the user's objective
function for the code (runtime speed, code space, or other measurable property).
The research program divides, roughly, into two thrusts:
- algorithms to find effective compiler configurations for a specific
program, target, and objective function, and
- work on how to structure compilers in ways that make them suitable
for use with an adaptive controller.
The vision of the project is captured in this
early talk and in the
text of the proposal
Algorithms for Adaptation
The prototype adaptive compiler that we have built selects
a set of optimizations and an order in which to apply them.
It tries to find a sequence (selection + order) that minimizes
the given objective function.
From a mathematical perspective, the compiler is looking for
a minimizer (either local or global) inside a complex discrete
space.
We have performed a series of experiments to help us understand
and characterize these search spaces.
A typical space includes fifteen possible transformations; if we
allow the compiler to choose a sequence of ten passes, the space
contains 576,650,390,625 sequences (15 to the 10th power).
The graph to the right shows a tiny subset of one such space:
sequences of length four drawn from a set of five optimizations (625
points) for the MediaBench code ADPCM-C.
As you can see, the space is neither smooth nor convex.
(No consistent reordering of the data helps, either.)
These two talks show detailes results on the search space,
beyond what appears in the papers:
Keith's keynote talk at CGO 2004
(see particulary slides 23ff) and Keith's
recent lecture in Pitt's distinguished
lecture series.
We have designed a number of algorithms that appear to perform
well in these search spaces. Our current work is focused on
scaling up the experiments to demonstrate the efficacy of these
algorithms.
Building Compilers That Can Adapt
To build a functioning adaptive compiler requires more than a good
search algorithm.
The compiler must expose "knobs and controls" that let the adapive
controller change the compiler's behavior in productive ways.
Our prototype compiler, which we are using to develop search algorithms,
has a set of 16 optimization passes and an interface that lets the
controller string together the passes in arbitrary orders. (It can
also specify command-line parameters to each pass.)
We have tried to reorder passes in a couple of open-source compilers
without success.
Design decisions that lie at the heart of those compilers make them
difficult to reorder.
To study the issues of structure and parameterization, we are conducting
a number of studies.
- We performed a series of experiments using adaptive control of
command-line options to improve the performance of numerical
linear algebra codes. We were able to achieve ATLAS-like results
through automatic adaptation at the compiler level; this result
offers the promise of a system that makes ATLAS-class performance
available across a large class of applications. (See paper in 2003
LACSI Symposium, below)
- We are experimenting with control of inline substitution, with the
goal of understanding what makes a good parameterization for
adaptive control. (Too often, compilers provide command-line flags
that are not particularly useful for adaptive control.) This subproject
will produce a source-to-source inliner that uses adaptation to discover
program-specific inlining criteria.
- We are experimenting with compilation order in the LLVM compiler system
(V. Adve at UIUC). This project should demonstrate that the ideas from
our work can apply in a compiler not of our own construction. We are
gaining additional insight into what properties make adaptation easy
and what properties make adaptation hard.
Publications
We have published a few papers on this work, with more in the pipeline.
Some of these predate the ITR funding; earlier work was funded by Jose
Munoz at DARPA and by Andy White of LANL through the
Los Alamos
Computer Science Institute (LACSI).
- K.D. Cooper, P.J. Schielke, and D. Subramanian,
"
Optimizing for Reduced Code Space Using Genetic Algorithms,"
Proceedings of the 1999 ACM SIGPLAN Workshop on Languages, Compilers,
and Tools for Embedded Systems, Atlanta, GA, USA, May 1999.
Also SIGPLAN Notices 34(7), pages 1-9.
This paper started it all. It describes our experiments using a genetic
algorithm to find optimization sequences that generate compact code.
Funded by DARPA, it began our work in this arena.
- K.D. Cooper, D. Subramanian, and L. Torczon,
"Adaptive Optimizing
Compilers for the 21st Century", 2001 LACSI Symposium,
October 2001, Santa Fe, NM, USA.
(Proceedings distributed electronically.)
A version also appeared in Journal of Supercomputing 23(1),
August 2002, pages 7-22.
This paper laid our our vision on adaptive compilation.
Here is corresponding talk.
- K.D. Cooper and T. Waterman,
"Investigating Adaptive Compilation using the MIPSPro
Compiler," 2003 LACSI Symposium, Santa Fe, NM, USA, October 2003.
(Proceedings distributed electronically.)
A version also appeared in
Journal of High-Performance Computing Applications, 19(4),
2005, pages 423-431.
This paper describes our experiments with command-line control of
blocking for linear algebra codes (specifically, DGEMM).
- This technical report
presents an analysis of the search spaces
in which the compiler operates. It is currently unpublished.
- L. Almagor, K.D. Cooper, T.J. Harvey, S.W. Reeves, D. Subramanian,
L. Torczon, and T. Waterman,
"
Finding Effective Compilation Sequences,"
Proceedings of the 2004 ACM SIGPLAN/SIGBED Conference on Languages
Compilers, and Tools for Embedded Systems", Washington, DC, USA,
June 2004. Also, SIGPLAN Notices 39(7), pages 231-239.
This paper describes both the enumeration and exploration experiments
we have
done to date (at least, through Spring 2004). It provides a prelimianry
basis for understanding the efficacy of greedy methods, genetic
algorithms, hill climbers, and random probing.
- K.D. Cooper, A. Grosul, T.J. Harvey, S.W. Reeves, D. Subramanian,
L. Torczon, and T. Waterman, "
Exploring the Structure of the Space of Compilation Sequences
Using Randomized Search Algorithms," 2004 LACSI
Symposium, October 2004, Santa Fe, NM, USA.
(Proceedings distributed electronically.)
A version also appeared in Journal of Supercomputing 36(2), May
2006, pages 135-151.
- This paper, "Searching for Compilation
Sequences," is a preliminary version that was submitted
for publication. It discusses the merits of three search techniques
and shows the apparent superiority of randomized, impatient hillclimbers
for finding sequences of low-level scalar optimizations. It will not
appear in print, although the material is being folded into a journal
submission.
- K.D. Cooper, A. Grosul, T.J. Harvey, S. Reeves, D. Subramanian, L. Torczon,
and T. Waterman, "
ACME: Adaptive Compilation Made
Efficient," Proceedings of the 2005 ACM SIGPLAN/SIGBED Conference on
Languages, Compilers, and Tools for Embedded Systems, Chicago, IL, June
2005. Also SIGPLAN Notices 40(7), pages 69-77.
This paper describes two facets of the ACME tool: its user interface
and its facility for virtual execution.
- K.D. Cooper, T.J. Harvey, and J. Sandoval, "Tuning an Adaptive Compiler"
Proceedings of the First Workshop on Statistical and Machine Learning
Approaches Applied to Architectures and Compilation (SMART 07),
Ghent, Belgium, January 2007.
- K.D. Cooper, Y. Guo and D. Subramanian, "An Effective Local Search
Algorithm for an Adaptive Compiler,"
Proceedings of the First Workshop on Statistical and Machine Learning
Approaches Applied to Architectures and Compilation (SMART 07),
Ghent, Belgium, January 2007.
- K.D. Cooper, T.J. Harvey, and D.M. Peixotto, "Chow and Hennessy versus
Chaitin-Briggs Register Allocation: Using Adaptive Compilation to Fairly
Compare Algorithms,"
Proceedings of the Second Workshop on Statistical and Machine Learning
Approaches Applied to Architectures and Compilation (SMART 08),
Goteberg, Sweden, January 2008.
- K.D. Cooper, T.J. Harvey, and T. Waterman, "An Adaptive Strategy for
Inline Substitution," Proceedings of the 2008 International Conference
on Compiler Construction (CC 2008), March 2008.
Standard Disclaimers
The results of this work do not, in any way, represent official opinions
or positions of the government agencies that fund this work, particulary
the National Science Foundation and the Department of Energy.
This page is maintained by Keith D. Cooper.
He is a poor email correspondent, but can be reached
as keith at the mail domain rice.edu.
