An Efficient Data Parallel Implementation on Multicore/Multithreaded Systems: Part I - Compute the one-dimensional FFT

摘要

With the rise of multicore chips into the computing market coupled with the increases in hardware performance; have revolutionized the software industry where the software must be parallelized in order to benefit from the multicore/multithreaded architecture. This paper presents a high-performance parallel one-dimensional Fast Fourier Transform (FFT) algorithm for multicore systems. The proposed method is based on the formulation of the 1-D FFT (Size N), as a combination of p FFTs (size N/p). These p FFTs are distributed among the p cores on which each core will be performing an FFT of size N/p. These p partials FFTs are combined in parallel in order to obtain the required transform of size N. The analysis was performed on the Intel Parallel Composer Studio XE for a double precision 1D-FFT by revealing promising results and achieving a significant speedup with only 4 cores. One-dimensional (1-D) FFT parallel implementation on multicore/multithreaded are considered in this paper and two-dimensional (2-D) FFT in a companion paper, Part II.