Scheduling FFT computation on SMP and multicore systems

ABSTRACT

Increased complexity of memory systems to ameliorate the gap between the speed of processors and memory has made it increasingly harder for compilers to optimize an arbitrary code within a palatable amount of time. With the emergence of multicore (CMP), multiprocessor (SMP) and hybrid shared memory multiprocessor architectures, achieving high e ciency is becoming even more challenging. To address the challenge to achieve high e ciency in performance critical applications, domain speci c frameworks have been developed that aid the compilers in scheduling the computations. We have developed a portable framework for the Fast Fourier Transform (FFT) that achieves high e ciency by automatically adapting to various architectural features. Adapting to parallel architectures by searching through all the combinations of schedules (plans) is an expensive task, even when the search is conducted in parallel. In this paper, we develop heuristics to simplify the generation of better schedules for parallel FFT computations on CMP/SMP systems. We evaluate the performance of OpenMP and PThreads implementations of FFT on a number of latest architectures. The performance of parallel FFT schedules is compared with that of the best plan generated for sequential FFT and the speedup for di erent number of processors is reported. In the end, we also present a performance comparison between the UHFFT and FFTW implementations.

REFERENCES

• 1: R. C. Agarwal , F. G. Gustavson , M. Zubair, A high performance parallel algorithm for 1-D FFT, Proceedings of the 1994 conference on Supercomputing, p.34-40, December 1994, Washington, D.C., United States
• 2: Ali, A., Johnsson, L., and Mirkovic, D. Empirical Auto-tuning Code Generator for FFT and Trignometric Transforms. In ODES: 5th Workshop on Optimizations for DSP and Embedded Systems, in conjunction with International Symposium on Code Generation and Optimization (CGO) (San Jose, CA, March 2007).
• 3: D. H. Bailey, FFTs in external or hierarchical memory, The Journal of Supercomputing, v.4 n.1, p.23-35, Mar. 1990 [doi>10.1007/BF00162341]
• 4: Cooley, J., and Tukey, J. An algorithm for the machine computation of complex fourier series. Mathematics of Computation 19 (1965), 297--301.
• 5: Franz Franchetti , Yevgen Voronenko , Markus Püschel, FFT program generation for shared memory: SMP and multicore, Proceedings of the 2006 ACM/IEEE conference on Supercomputing, November 11-17, 2006, Tampa, Florida [doi>10.1145/1188455.1188575]
• 6: Matteo Frigo, A fast Fourier transform compiler, Proceedings of the ACM SIGPLAN 1999 conference on Programming language design and implementation, p.169-180, May 01-04, 1999, Atlanta, Georgia, United States
• 7: Frigo, M., and Johnson, S. G. The design and implementation of FFTW3. Proceedings of the IEEE 93, 2 (2005), 216--231. special issue on "Program Generation, Optimization, and Platform Adaptation".
• 8: Charles Van Loan, Computational frameworks for the fast Fourier transform, Society for Industrial and Applied Mathematics, Philadelphia, PA, 1992
• 9: Dragan Mirkovic, Automatic Performance Tuning in the UHFFT Library, Proceedings of the International Conference on Computational Sciences-Part I, p.71-80, May 28-30, 2001
• 10: Dragan Mirković , Rishad Mahasoom , Lennart Johnsson, An adaptive software library for fast Fourier transforms, Proceedings of the 14th international conference on Supercomputing, p.215-224, May 08-11, 2000, Santa Fe, New Mexico, United States [doi>10.1145/335231.335252]
• 11: John L. Hennessy , David A. Patterson, Computer architecture: a quantitative approach, Morgan Kaufmann Publishers Inc., San Francisco, CA, 02
• 12: Puschel, M., Moura, J. M. F., Johnson, J., Padua, D., Veloso, M., Singer, B. W., Xiong, J., Franchetti, F., Gacic, A., Voronenko, Y., Chen, K., Johnson, R. W., and Rizzolo, N. SPIRAL: Code generation for DSP transforms. Proceedings of the IEEE, special issue on "Program Generation, Optimization, and Adaptation" 93, 2 (2005), 232--275.
• 13: Ping Tak Peter Tang, DFTI---a new interface for Fast Fourier Transform libraries, ACM Transactions on Mathematical Software (TOMS), v.31 n.4, p.475-507, December 2005 [doi>10.1145/1114268.1114271]
• 14: Temperton, C. Self-Sorting Mixed-Radix Fast Fourier Transforms. Journal of Computational Physics 52 (1983), 1--23.
• 15: Tolimieri, R., An, M., and Lu, C. Algorithms for discrete fourier transform and convolution. Springer-Verlag, 1997.

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.1 Numerical Algorithms and Problems

Additional Classification:
  D. Software
  D.1 PROGRAMMING TECHNIQUES
      D.1.3 Concurrent Programming

  G. Mathematics of Computing
  G.4 MATHEMATICAL SOFTWARE
      Subjects: Parallel and vector implementations

General Terms:
Algorithms, Design, Performance

Keywords:
automatic parallelization, automatic performance tuning, fast Fourier transform, multicore, shared memory