An adaptive software library for fast Fourier transforms

ABSTRACT

In this paper we present an adaptive and portable software library for the fast Fourier transform (FFT). The library consists of a number of composable blocks of code called codelets, each computing a part of the transform. The actual FFT algorithm used by the code is determined at run-time by selecting the fastest strategy among all possible strategies, given available codelets, for a given transform size. We also present an efficient automatic method of generating the library modules by using a special-purpose compiler. The code generator is written in C and it generates a library of C codelets. The code generator is shown to be flexible and extensible and the entire library can be generated in a matter of seconds. We have evaluated the library for performance on the IBM-SP2, SG1-2000, HP-Exemplar and Intel Pentium systems. We use the results from these evaluations to build performance models for the FFT library on different platforms. The library is shown to be portable, adaptive and efficient.

REFERENCES

• 1: J.C. Cooley and J.W. Tukey. An algorithm for the machine computation of complex fourier series. Math. Comp., 19:291-301, 1965.
• 2: M. Frigo , S. G. Johnson, The Fastest Fourier Transform in the West, Massachusetts Institute of Technology, Cambridge, MA, 1997
• 3: Charles Van Loan, Computational frameworks for the fast Fourier transform, Society for Industrial and Applied Mathematics, Philadelphia, PA, 1992
• 4: 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]
• 5: C. Temperton. A Note on Prime Factor FFT Algorithms. Journal of Computational Physics, 52:198-204, 1983.
• 6: C. M. Rader. Discrete fourier transforms when the number of data samples is prime. Proceedings of the IEEE, 56:1107-1108, 1968.
• 7: P. Duhamel and H. Hollmann. Split Radix FFT Algorithms. Electronic Letters, 20:14-16, 1984.
• 8: MIPS RIO000 Microprocessor. Users Manual. MIPS Technologies, Inc., 1996.
• 9: IBM. RS6000 Technical specification. http://www.rs6OOO.ibm.eom/, 1999.
• 10: Exemplar Programming Guide. Hewlett-Packaxd, Inc., 1997.
• 11: Intel Architecture Optimization. Reference Manual. Intel Corporation, 1999.
• 12: Rudolf Berrendorf and Heinz Ziegler. PCL: The Performance Counter Library. http://www.fz-juelich.de/zam/PCL/, 1999.

INDEX TERMS

Primary Classification:
  D. Software
  D.2 SOFTWARE ENGINEERING
      D.2.2 Design Tools and Techniques
          Subjects: Software libraries

Additional Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.4 Processors
          Subjects: Code generation; Optimization

  F. Theory of Computation
  F.4 MATHEMATICAL LOGIC AND FORMAL LANGUAGES
      F.4.1 Mathematical Logic
          Subjects: Computational logic

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