A Fast Fourier Transform Compiler

by Matteo Frigo.

In the ACM SIGPLAN'99 Conference on Programming Language Design and Implementation (PLDI), Atlanta, GA, USA
2009 Most Influential PLDI Paper Award (for 1999)
[Full text]


The FFTW library for computing the discrete Fourier transform (DFT) has gained a wide acceptance in both academia and industry, because it provides excellent performance on a variety of machines (even competitive with or faster than equivalent libraries supplied by vendors). In FFTW, most of the performance-critical code was generated automatically by a special-purpose compiler, called genfft, that outputs C code. Written in Objective Caml, genfft can produce DFT programs for any input length, and it can specialize the DFT program for the common case where the input data are real instead of complex. Unexpectedly, genfft ``discovered'' algorithms that were previously unknown, and it was able to reduce the arithmetic complexity of some other existing algorithms. This paper describes the internals of this special-purpose compiler in some detail, and it argues that a specialized compiler is a valuable tool.

This page maintained by: Matteo Frigo. Last updated: Sun Jun 21 09:29:38 2009