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:

  1. 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.
  2. 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.
  3. Read papers on algorithms for tile size selection, and figure out which ones are most promising. Implement and evaluate those.
  4. Replace the search for tile size in ATLAS with your algorithm, and evaluate performance on a variety of architectures.
  5. 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:

  1. 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.
  2. 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:

  1. McKinley et al paper on tile-size selection
  2. Chame et al paper on tile-size selection
  3. Tseng et al paper comparing tile-size selection algorithms
  4. Yotov et al
  5. ATLAS reference
  6. PhiPAC reference