A fast Fourier transform compiler

ABSTRACT

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.

REFERENCES

• ACT90: Myoung An , James W. Cooley , Richard Tolimieri, Factorization method for crystallographic Fourier transforms, Advances in Applied Mathematics, v.11 n.3, p.358-371, Sep. 1990 [doi>10.1016/0196-8858(90)90014-P]
• ASU86: Alfred V. Aho , Ravi Sethi , Jeffrey D. Ullman, Compilers: principles, techniques, and tools, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1986
• AV88: Alok Aggarwal , Jeffrey,S. Vitter, The input/output complexity of sorting and related problems, Communications of the ACM, v.31 n.9, p.1116-1127, Sept. 1988 [doi>10.1145/48529.48535]
• BFJ+96: Robert D. Blumofe , Matteo Frigo , Christopher F. Joerg , Charles E. Leiserson , Keith H. Randall, An analysis of dag-consistent distributed shared-memory algorithms, Proceedings of the eighth annual ACM symposium on Parallel algorithms and architectures, p.297-308, June 24-26, 1996, Padua, Italy [doi>10.1145/237502.237574]
• CO75: R.E. Crochiere and A. V. Oppenheim. Analysis of linear digital networks. Proceedings of the IEEE, 63:581-595, April 1975.
• CT65: J.W. Cooley and J. W. 'Ihkey. An algorithm for the machine computation of the complex Fourier series. Mathematics of Computation, 19:297-301, April 1965.
• DV90: P. Duhamel , M. Vetterli, Fast fourier transforms: a tutorial review and a state of the art, Signal Processing, v.19 n.4, p.259-299, April 1990 [doi>10.1016/0165-1684(90)90158-U]
• FJ: Matteo Frigo and Steven G. Johnson. The FFTW web page. http://theory, lcs .air. edu/'fftw.
• FJ97: M. Frigo , S. G. Johnson, The Fastest Fourier Transform in the West, Massachusetts Institute of Technology, Cambridge, MA, 1997
• FJ98: Matteo Frigo and Steven G. Johnson. FFTW: An adaptive software architecture for the FFT, In Proceedings of the IEEE International Conference on Acoustics, Speech, and Signal Processing, volume 3, pages 1381- 1384, Seattle, WA, May 1998.
• FLR98: Matteo Frigo , Charles E. Leiserson , Keith H. Randall, The implementation of the Cilk-5 multithreaded language, Proceedings of the ACM SIGPLAN 1998 conference on Programming language design and implementation, p.212-223, June 17-19, 1998, Montreal, Quebec, Canada
• GHSJ96: S. K. S. Gupta , C.-H. Huang , P. Sadayappan , R. W. Johnson, A framework for generating distributed-memory parallel programs for block recursive algorithms, Journal of Parallel and Distributed Computing, v.34 n.2, p.137-153, May 1, 1996 [doi>10.1006/jpdc.1996.0051]
• HK81: Hong Jia-Wei , H. T. Kung, I/O complexity: The red-blue pebble game, Proceedings of the thirteenth annual ACM symposium on Theory of computing, p.326-333, May 11-13, 1981, Milwaukee, Wisconsin, United States [doi>10.1145/800076.802486]
• HV92: P.H. Hartel and W. G. Vree. Arrays in a lazy functional language---a case study: the fast Fourier transform. In G. Hains and L. M. R. Mullin, editors, Arrays, functional languages, and parallel systems (ATABLE), pages 52-66, June 1992.
• JB83: H.W. Johnson and C. S. Bums. The design of optimal DFT algorithms using dynamic programming. IEEE Transactions on Acoustics, Speech and Signal Processing, 31:378-387, April 1983.
• Knu98: Donald E. Knuth, The art of computer programming, volume 2 (3rd ed.): seminumerical algorithms, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1997
• Kul95: Joanna L. Kulik. Implementing compiler optimizations using parallel graph reduction. Master's thesis, Massachussets Institute of Technology, February 1995.
• Ler98: Xavier Leroy. The Objective Carol system release 2.00. Institut National de Recherche en Informatique at Automatique (INRIA), August 1998.
• Mar76: J.A. Maruhn. FOURGEN: a fast Fourier transform program generator. Computer Physics Communications, 12:147-162, 1976.
• Muc97: Steven S. Muchnick, Advanced compiler design and implementation, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1998
• OS89: Alan V. Oppenheim , Ronald W. Schafer, Discrete-time signal processing, Prentice-Hall, Inc., Upper Saddle River, NJ, 1989
• Par92: Will Partain, The nofib Benchmark Suite of Haskell Programs, Proceedings of the 1992 Glasgow Workshop on Functional Programming, p.195-202, July 06-08, 1992
• PT87: F. Perez and T. Takaoka. A prime factor FF'T algorithm implementation using a program generation technique. IEEE Transactions on Acoustics, Speech and Signal Processing, 35(8): 1221-1223, August 1987.
• Rad68: C.M. Rader. Discrete Fourier transforms when the number of data samples is prime. Proc. of the IEEE, 56:1107-1108, June 1968.
• SB96: i. Selesnick and C. S. Burrus. Automatic generation of prime length FFr programs. IEEE Transactions on Signal Processing, pages 14-24, January 1996.
• SJHB87: H. V. Sorensen, D. L. Jones, M. T. Heideman, and C. S. Burrus. Real-valued fast Fourier transform algorithms. IEEE Transactions on Acoustics, Speech, and Signal Processing, ASSP-35(6):849-863, June 1987.
• TAL97: Richard Tolimieri, Myoung An, and Chao Lu. Algorithms for Discrete Fourier Transform and Convolution. Springer Verlag, 1997.
• Vel95: Todd Veldhuizen, Using C++ template metaprograms, C++ gems, SIGS Publications, Inc., New York, NY, 1996
• VS94a: J.S. Vitter and E. A. M. Shriver. Optimal algorithms for parallel memory I: Two-level memories. Algorithmica, 12(2-3):110-147, 1994. double special issue on Large- Scale Memories.
• VS94b: J.S. Vitter and E. A. M. Shriver. Optimal algorithms for parallel memory II: Hierarchical multilevel memories. Algorithrnica, 12(2-3):148-169, 1994. double special issue on Large-Scale Memories.
• Wad97: Philip Wadler, How to declare an imperative, ACM Computing Surveys (CSUR), v.29 n.3, p.240-263, Sept. 1997 [doi>10.1145/262009.262011]
• Win78: S. Winograd. On computing the discrete Fourier transform. Mathematics of Computation, 32(1):175-199, January 1978.

INDEX TERMS

Primary Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.4 Processors
          Subjects: Compilers

Additional Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.1 Numerical Algorithms and Problems
          Subjects: Computation of transforms (e.g., fast Fourier transform)

General Terms:
Algorithms, Design, Languages, Measurement, Performance, Theory