Combining Model-based and Empirical Optimization
Project contact:
Kamen Yotov
Description of project:
The goal of this project is to evaluate the
utility of combining model-based optimization with empirical optimization
in restructuring
compilers.
As we discussed in class, most compilers use models of the memory
hierarchy to determine key transformation parameters like tile
sizes. These models are usually very simple, and they may ignore
features of the memory hierarchy such as cache
associativity. Therefore, the values of transformation parameters
determined by the use of these models can be sub-optimal. Systems
like ATLAS and PhiPAC use search techniques to determine these parameters,
but search
times can be very large even for optimizing code for a single level
of the memory hierarchy.
In this project, we will investigate intelligent search techniques
to reduce search time. For example, we can use model-based optimization
to determine transformation parameters, and perform limited search
around those values. This has two two advantages. The first is
that
installation time for library generators can be reduced. The second
is that more extensive optimization may be possible; for example,
we
might be able to optimize for several levels of the memory hierarchy
simultaneously if the search time for each level is reduced to
a manageable amount.
What you need to do:
- Download and install ATLAS on your computer.
Instrument it as described in the Yotov et al paper to determine
how much time
is spent in each phase of installation. Figure out which machines
you
want to
perform your studies on.
- Read the Yotov et al paper and determine which parameters you
want to optimize. You should base your choices on two considerations.
You should focus on parameters for which search takes a
long time. Also,
you need to have an effective strategy for reducing that
search
time. We suggest you start with tile size determination, and
then consider
other parameters.
- Read papers on algorithms for tile size selection, and figure
out which ones are most promising. Implement and evaluate those.
- Replace the search for tile size in ATLAS with your algorithm,
and evaluate performance on a variety of architectures.
- Figure out what kind of intelligence search you want to do.
A simple possibility is a greedy strategy in which you
continue searching along a direction as long as you get better
performance. You can also try more complex strategies like simulated
annealing. Evaluate your search strategies according to (i)
how
good
a job they do in finding transformation parameter values,
and (ii) how
long they take to find these values.
What you need to turn in:
- You should turn in a 10-12 page paper along the lines of the
Yotov et al paper, replacing the model-based optimization
with your model+empirical strategy. This does not mean regurgitating
all
the
text of that paper - use it as a rough model
for how to write
a paper in this area, and then write your own.
- Document and turn in your experimental data. Our project has
established a standard format for saving
experimental data so that it can be used by other people. Use that
format.
Some papers to start with:
- McKinley
et al paper on tile-size selection
- Chame
et al paper on tile-size selection
- Tseng
et al paper comparing tile-size selection algorithms
- Yotov et al
- ATLAS
reference
- PhiPAC
reference