This project is funded by the NSF ITR program and by Texas
ATP. Project members are:
Keith Cooper , Linda
Torczon and Devika
Subramanian .
The context
At design time, the compiler writer selects a set of optimizations and
an order in which to apply them. These choices have a direct impact
on the quality of code that the compiler can generate. Making good
choices is difficult for several reasons. The sheer number of
transformations that have been described in the literature is
daunting. The relationship between features of the input program and
improvements (or degradations) produced by a transformation is not
formally characterized. The interactions between these
transformations are poorly understood.
The question
Can we build an adaptive compiler that changes its selection of
transformations and its application order based on the input program,
the performance characteristics of the target machine, and an explicit
objective function? Such a compiler would sample the space of
transformation sequences in a randomized manner, learning a model
of the impact of various sequences on a given program, and
adapting its sampling based on the learned model.
Preliminary Results on fmin
We have built such a compiler. It has allowed us to explore the impact
of transformation selection and ordering on the code that the compiler
produces, and to characterize the search space in which the adaptive
compiler operates. We present our results on a benchmark program
called fmin . We chose fmin a 150 line Fortran program
with a complex control-flow graph and forty-four basic blocks. It
displays interesting behavior from an optimization standpoint and is
small enough to study exhaustively.
- Given a pool of optimizations and an objective function for a
program, what is the number and distribution of sequences that
minimize that function for the program? The distribution of run times
of the optimized fmin program when run through all possible
optimization sequences of length 10 drawn from a pool of 5
optimizations is here.
- What fraction of the local minima of the objective function are
within 10% of the global minimum? 10% of the sequences are within 10%
of the best solution for fmin .
- How are these ``good'' minima distributed in the space? That is,
what is the probability that a good minimum can be found by a search
algorithm guided purely by the local (discrete) gradient of the
objective function? This figure
shows the final values achieved by a hill climber from 100,000
random starts. 94.97% of the solutions found by the hill climber are
within 10% of the global minimum.
- Further, what is the effective diameter of the space of
optimizations? By that we mean, how many steps will a local search
algorithm need on average before settling into a local minimum?
Here is the figure which
shows the average number of steps needed by a hill climber to find a
good solution in this space.
- Is there a decision rule that can distinguish sequences that lead
to a good local minimum from ones that do not? Can such a decision
rule be learned from the sampled sequences? Can we relate the decision
rule to properties of the program being optimized? We have trained
decision tree classifiers, SVMs and HMMs to characterize sequences
that yield good optimizations for fmin versus those that
don't. Details are in our technical
report .
Publications
- ACME: adaptive compilation made efficient , LACSI Symposium 2005.
- Exploring the structure of compilation sequences using randomized search algorithms, LACSI Symposium, 2004.
- Adaptive optimizing
compilers for the 21st century, Journal of Supercomputing,
23(1),7:22, 2002. Here's the talk
at the LACSI symposium (with K. Cooper and L. Torczon).
- Compilation order matters , Technical Report, January 2002, Rice University (with K. Cooper, L. Torczon and
T. Harvey).
- Optimizing for reduced code
space using genetic algorithms, ACM SIGPLAN Workshop on Languages,
Compilers, and Tools for Embedded Systems (LCTES), Atlanta, GA, 1999,
will appear as an issue of SIGPLAN Notices) (with P. Schielke and
K. D. Cooper).
- An experimental
evaluation of list scheduling, Technical report, September 1998,
Rice University (with K. Cooper and P. Schielke).
Talks