Parallel implementation of 1-D fast Fourier transform without inter-processor communications

摘要

Computing 1-D fast Fourier transform (FFT) using the classical 4-step FFT on parallel computers requires intensive all-to-all communication. This all-to-all communication significantly reduces the performance of FFT. In this paper, we present the no-communication algorithm that is a parallel algorithm for 1-D FFT without inter-processors communication. The advantage of this algorithm is the absence of all-to-all communication between processors. The disadvantage of this algorithm is the extra computation compared to the classical 4-step FFT. The no-communication algorithm has been implemented and tested in 8-node symmetric multiprocessors (SMP). The results show that the no-communication algorithm performs better than the 4-step FFT for relatively small data sizes. However, 4-step FFT algorithm performs better than the no-communication for relatively large data sizes.