High performance discrete Fourier transforms on graphics processors

Naga K. Govindaraju, Brandon Lloyd, Yuri Dotsenko, Burton Smith, John Manferdelli
Microsoft Corporation
In SC ’08: Proceedings of the 2008 ACM/IEEE conference on Supercomputing (2008), pp. 1-12.


   title={High performance discrete Fourier transforms on graphics processors},

   author={Govindaraju, N.K. and Lloyd, B. and Dotsenko, Y. and Smith, B. and Manferdelli, J.},

   booktitle={High Performance Computing, Networking, Storage and Analysis, 2008. SC 2008. International Conference for},





Download Download (PDF)   View View   Source Source   



We present novel algorithms for computing discrete Fourier transforms with high performance on GPUs. We present hierarchical, mixed radix FFT algorithms for both power-of-two and non-power-of-two sizes. Our hierarchical FFT algorithms efficiently exploit shared memory on GPUs using a Stockham formulation. We reduce the memory transpose overheads in hierarchical algorithms by combining the transposes into a block-based multi-FFT algorithm. For non-power-of-two sizes, we use a combination of mixed radix FFTs of small primes and Bluestein’s algorithm. We use modular arithmetic in Bluestein’s algorithm to improve the accuracy. We implemented our algorithms using the NVIDIA CUDA API and compared their performance with NVIDIA’s CUFFT library and an optimized CPU-implementation (Intel’s MKL) on a high-end quad-core CPU. On an NVIDIA GPU, we obtained performance of up to 300 GFlops, with typical performance improvements of 2–4x over CUFFT and 8–40x improvement over MKL for large sizes.
No votes yet.
Please wait...

* * *

* * *

HGPU group © 2010-2020 hgpu.org

All rights belong to the respective authors

Contact us: