high performance computing on graphics processing units: hgpu.org

The Fourier Transform is one of the most in uential mathematical equations of our time. The Discrete Fourier Transform (DFT) (which is equal to the Fourier Transform for signals with equally spaced samples) has been improved by a more efficient algorithm called the Fast Fourier Transform contributed by Cooley-Tukey[8] and Gentlemen-Sande[11]. Improvements since then have primarily been focused on hardware correspondence. The terms memory wall and power wall restrict CPUs from increasing their performance the way they have in the past. CPUs can only increase the number of cores, following the example of graphics cards and increasing parallelization. Developments like CUDA have made it possible to program GPUs the way one would a CPU. Publications on optimization of FFTs on GPUs have primarily been focused on overlapping data transfer and computation, and multi-dimensional FFTs. As a multi-dimensional FFT consists for 1-dimensional FFTs along each dimension, we focus on optimizing the 1-dimensional case and propose a method to run the FFT algorithm on multiple GPUs having minimized communication.