High performance multi-dimensional (2D/3D) FFT-Shift implementation on Graphics Processing Units (GPUs)

Frequency domain analysis is one of the most common analysis techniques in signal and image processing. Fast Fourier Transform (FFT) is a well know tool used to perform such analysis by obtaining the frequency spectrum for time- or spatial-domain signals and vice versa. FFT-Shift is a subsequent operation used to handle the resulting arrays from this stage as it centers the DC component of the resulting array at the origin of the spectrum. The modern Graphics Processing Units (GPUs) can be easily exploited to efficiently execute this operation considering the Compute Unified Device Architecture (CUDA) technology that was released by NVIDIA. In this work, we present an efficient high performance implementation for two- and three-dimensional FFT-Shift on the GPU exploiting its highly parallel architecture relying on the CUDA platform. We use Fourier volume rendering as an example to demonstrate the significance of this proposed implementation. It achieves a speedup of 65X for the 2D case & 219X for the 3D case.