Untitled Document

A Comparison of Model-based and Empirical Optimization in FFTW

Project contact: Kamen Yotov

Description of project:

At a high level, the goal of this project is to do for the FFTW system what
the Yotov et al paper did for ATLAS.

Recall that the Yotov et al paper did the following. First, it explained how
ATLAS generated optimized MMM code, and listed the parameters that were used
to generate this code. Second, it explained how ATLAS searched for the values
of these parameters. Third, it gave an architectural model for determining
the values of these parameters. Finally, it compared the performance of the
codes generated by using the model and by using search.

In this project, we want to do a similar study for FFTW, a self-tuning system
for generating highly-tuned FFT codes for different architectures. This study
is important for the following reason. Empirical search can be used in two
ways: to choose between different implementations of a computation, and to
choose values for certain parameters. For the most part, ATLAS uses search
only to choose values for parameters (strictly speaking, the decision about
whether or not to copy the data in a tile into contiguous storage is an example
of “different implementations of a computation”).

In FFTW, the situation is
quite different: search is used extensively to choose between different implementations
of the basic FFT algorithm (Cooley-Tuckey, Gentleman-Sand etc.). Roughly speaking,
the FFT is a linear transform, so it can be represented as a matrix, and this
matrix
can be factorized in different ways to yield different FFT implementations.
In FFTW, search is used to choose between these different factorizations, which
results in a use of empirical optimization which is quite different in flavor
from the way in which it is used in ATLAS.

The objective of the project is figure out what decisions FFTW makes to generate
code, to develop models for making these decisions, and to evaluate the effectiveness
of these models.

What you need to do:

1. Download the FFTW system from the FFTW site and
   install it on your system. You may also want to look at the SPIRAL system
   from CMU.
2. Read the PLDI 99 paper on the FFTW system that is available on this site.
3. Figure out all the decisions that FFTW makes to generate tuned code.
4. Design architectural models that can be used to make these decisions.
5. Compare the effectiveness of using models to that of using search.

What you need to turn in:

Write a 10-12 page paper along the lines of the Yotov et al paper summarizing
your results. Make sure you save all your experimental data somewhere where
we have access to it.

Papers:

1. The FFTW site This site contains lots
   of useful material on FFTs.
2. The PLDI ’99
   paper on FFTW
3. The study of Yotov
   et al
4. The ATLAS site
5. SPIRAL is another
   self-tuning FFT package.