Automatic Tuning of Discrete Fourier Transforms Driven by Analytical Modeling

Basilio Fraguela, Yevgen Voronenko and Markus Puschel

Analytical modeling has been used to estimate optimal values for parameters such as tile sizes in the context of loop nests. Nevertheless, important algorithms such as the discrete Fourier transform (DFT) present a search space with thousands of different implementations with very different complex access patterns and nesting and coding structures. As a result, all existing optimization systems for these codes resort to iterative compilation. Another reason for this is that algorithms like the DFT exhibit access patterns that behave in the physically-indexed caches of current processorsin a very different way to the virtually-indexed caches that all the cache models in the bibliography assume.Finally, hardware prefetchers have an important effect on the performance of these memory-demanding codes, a fact that has never been modeled. In this paper we present the firstanalytical model that can guide successfully the selection of high performance DFTs by taking into account all these facts.

Back to Program