In this paper we discuss architecture-specific performance tuning for fast Fourier transforms (FFTs) implemented in the UHFFT library. The UHFFT library is an adaptive and portable software library for FFTs developed by the authors. We present the optimization methods used at different levels, starting with the algorithm selection used for the library code generation and ending with the actual implementation and specification of the appropriate compiler optimization options. We report on the performance results for several modern microprocessor architectures.
Get full access to this article
View all access options for this article.
References
1.
Cooley, J. W. and Tukey, J. W. 1965. An algorithm for the machine computation of complex Fourier series . Mathematics of Computation19: 297–301 .
2.
Duhamel, P. and Hollmann, H. 1984. Split radix FFT algorithms . Electronic Letters20: 14–16 .
3.
Duhamel, P. and Vetterli, M. 1990. Fast Fourier transforms: a tutorial review and a state of the art . Signal Processing19: 259–299 .
4.
Frigo, M. 1999. A fast Fourier transform compiler . In Proceedings of the 1999 ACM SIGPLAN Conference on Programming Language Design and Implementation, Atlanta, GA, May 1–4, pp. 169–180 .
5.
Frigo, M. and Johnson, S. G. 1997. The fastest Fourier transform in the West. Technical Report MIT-LCS-TR-728, MIT, Cambridge, MA .
6.
Frigo, M. and Johnson, S. G. 1998. FFTW: an adaptive software architecture for the FFT . In Proceedings of International Conference on Acoustics, Speech, and Signal Processing (ICASSP), Seattle, WA, May 12–15, Vol. 3, pp. 1381–1384 . See http://www.fftw.org.
7.
Gatlin, K. S. and Carter, L. 2001. Faster FFTs via architecturecognizance . In Proceedings of the 2000 International Conference on Parallel Architectures and Compilation Techniques (PACT’00), Philadelphia, PA, October 16–18, pp. 249–260 .
8.
Good, I. J. 1958. The interaction algorithm and practical Fourier analysis . Journal of the Royal Statistical Society, Series B20: 361–375 .
