Discrete fourier transform on multicore
Authors:
- 23 October 2009
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Signal Processing Magazine
- Vol. 26 (6) , 90-102
Abstract
This article gives an overview on the techniques needed to implement the discrete Fourier transform (DFT) efficiently on current multicore systems. The focus is on Intel-compatible multicores, but we also discuss the IBM Cell and, briefly, graphics processing units (GPUs). The performance optimization is broken down into three key challenges: parallelization, vectorization, and memory hierarchy optimization. In each case, we use the Kronecker product formalism to formally derive the necessary algorithmic transformations based on a few hardware parameters. Further code-level optimizations are discussed. The rigorous nature of this framework enables the complete automation of the implementation task as shown by the program generator Spiral. Finally, we show and analyze DFT benchmarks of the fastest libraries available for the considered platforms.Keywords
This publication has 29 references indexed in Scilit:
- A survey of multicore processorsIEEE Signal Processing Magazine, 2009
- Formal datapath representation and manipulation for implementing DSP transforms2008
- Generating SIMD Vectorized Permutations2008
- How to Write Fast Numerical Code: A Small IntroductionLecture Notes in Computer Science, 2008
- Scheduling FFT computation on SMP and multicore systems2007
- An Implementation of Parallel 3-D FFT Using Short Vector SIMD Instructions on Clusters of PCsLecture Notes in Computer Science, 2006
- Short vector code generation for the discrete Fourier transform2004
- A SIMD vectorizing compiler for digital signal processing algorithms2002
- Multi-processor Performance on the Tera MTA1998
- A methodology for designing, modifying, and implementing Fourier transform algorithms on various architecturesCircuits, Systems, and Signal Processing, 1990