Code generators for automatic tuning of numerical kernels: experiences with FFTW

Abstract. Achieving peak performance in important numerical kernels such as dense matrix multiply or sparse-matrix vector multiplication usu-ally requires extensive, machine-dependent tuning by hand. In response, a number automatic tuning systems have been developed which typi-cally operate by (1) generating multiple implementations of a kernel, and (2) empirically selecting an optimal implementation. One such sys-tem is FFTW (Fastest Fourier Transform in the West) for the discrete Fourier transform. In this paper, we review FFTW's inner workings with an emphasis on its code generator, and report on our empirical evalua-tion of the system on two dierent hardware and compiler platforms. We then describe a number of our own extensions to the FFTW code genera-tor that compute ecient discrete cosine transforms and show promising speed-ups over a vendor-tuned library. We also comment on current op-portunities to develop tuning systems in the spirit of FFTW for other widely-used kernels.