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.
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.