Go back to the benchmark results.
FFT Software Used
Note: Many of the publicly-available FFT subroutines are written in Fortran. These were converted to C via f2c for inclusion in the benchmark.
One-Dimensional Fourier Transforms
The following are the codes that were used in the one-dimensional benchmark, along with the abbreviations that are used for them in the performance graphs.
- cilk_fft: This FFT is a precursor to FFTW, written by Matteo Frigo (one of the FFTW authors). A major advantage of this code is that, on parallel machines with Cilk installed, it will get a linear speedup (it also runs on sequential machines with standard C compilers). This code is especially optimized for N's which are powers of two, although it works for any N.
- FFTW: The one-dimensional routines from the FFTW 1.1 package.
- We benchmarked two versions of this routine. The first one computes the optimal decomposition of the array by actually making timing measurements. The second version uses a heuristic and is labeled FFTW_ESTIMATE.
- CWP: A Prime Factor Algorithm (PFA) FFT implemenation from a C numerical library by the Colorado School of Mines. (More info here.) In some sense, this routine "cheats"--it requires that you give it an array size which it can transform quickly. Thus, it usually was running on a slightly larger array than the other codes. We ran two versions of CWP:
- CWP (min N): use the minimum allowable N greater than or equal to the N used by the rest of the FFTs.
- CWP (optimal N): use the optimal allowable N greater than or equal to the N used by the rest of the FFTs.
- ffts in C: A heavily inlined & optimized C FFT by Richard H. Krukar. (Here is his spartan home page.) This FFT can only handle N's which are powers of 2 (and no greater than 4096).
- mixfft: A mixed-radix C FFT written by Jens Jorgen Nielsen.
- GO: A Fortran
mixed-radix FFT from the GO (Golden
Oldies) library, by R. C. Singleton, Stanford Research Institute,
Sept. 1968. The same subroutine actually does N-dimensional FFTs. This
code is actually amazingly fast considering its age and N-dimensional
generality. (We used a version of the code that was converted from
Fortran via f2c. We also tried a version that had been
hand-translated, but this had only a negligible effect on the
performance.)
- FFTPACK: A well-known library of Fortran FFTs written by P. N. Swarztrauber, available at Netlib.
- NR: This is an FFT from Numerical Recipes in C. It only works for arrays whose sizes are powers of 2. (Not in the public domain.)
- GPFA: A Fortran FFT from "A Generalized Prime Factor FFT Algorithm For Any N = 2P3Q5R," by C. Temperton, J. Sci. Stat. Comp., May 1992.
- NAPACK: A Fortran FFT from the NAPACK package.
- fft2: A C FFT implementing the Cooley-Tukey algorithm, written by "Pjotr." (The full name of the author is unknown.)
- Mayer: A C FFT/FHT by R. Mayer. Can only handle N's that are powers of 2.
- Duhamel:
C code implementing a Duhamel-Holman split-radix FFT, written by D. Edelblute and modified by R. Mayer. (See Electronics
Letters, January 5, 1984.) Can only handle N's that are powers of
2.
- Beauregard: Yet another C FFT, this one by G. Beauregard. Can only handle N's that are powers of 2.
- ESSL: A highly optimized FFT for the RS/6000 only from IBM's ESSL library. (Not in the public domain.)
- SCILIB: A Cray-provided FFT from Cray's SCILIB library. This routine is highly vectorized on the C90. (Not in the public domain.)
- SUNPERF: The one-dimensional double-precision FFT from the
Sun Performance Library, optimized for the UltraSPARC. This code is
actually an optimized version of FFTPACK. (Not in the public domain.)
Three-Dimensional Fourier Transforms
The following are the codes that were used in the three-dimensional benchmark, along with the abbreviations that are used for them in the performance graphs.
- FFTWND: The multi-dimensional routines from the FFTW 1.1 package. We ran two different versions of this code: one for in-place and one for out-of-place transforms.
- GO: An N-dimensional Fortran mixed-radix FFT from the GO (Golden Oldies) library, by R. C. Singleton, Stanford Research Institute, Sept. 1968.
- PDA: Fortran FFT from the PDA (Public Domain Algorithms) library. The 1D FFTs it uses are based on FFTPACK at Netlib.
- NR: A multi-dimensional FFT in C from Numerical Recipes in C. This routine only works for arrays whose dimensions are powers of two. (Not in the public domain.)
- HARMD: Yet another public-domain N-dimensional Fortran FFT. This routine also only works for arrays whose dimensions are powers of two. (The author is unknown.)
- GPFA: A 3D Fortran FFT from "A Generalized Prime Factor FFT Algorithm For Any N = 2P3Q5R," by C. Temperton, J. Sci. Stat. Comp., May 1992.
- ESSL: A highly optimized 3D FFT for the RS/6000 only from IBM's ESSL library. (Not in the public domain.) Only the single-precision version of this routine was available to us, so we compared it separately to a single-precision version of FFTW. (Not in the public domain.)
- SCILIB: A Cray-provided 3D FFT from Cray's SCILIB library. This routine is highly vectorized on the C90. (Not in the public domain.)
Go back to the benchmark results.