Two-step 1-D fast Fourier transform without inter-processor communications

Computing the 1-D fast Fourier transform (FFT) using the conventional six-step FFT on parallel computers requires intensive all-to-all communication due to the necessity of transposing an array three times. This all-to-all communication significantly reduces the performance of FFT in parallel systems. In this paper, we present a two-step parallel algorithm for implementing the 1-D FFT without inter-processor communication, at the expense of extra computation as opposed to the conventional six-step FFT. The advantage of the two-step FFT algorithm over its six-step counterpart becomes obvious in systems where the cost of computation is lower that of inter-processor communication. The 32-node Beowulf cluster is such a system with fast 2 GHz processors but relatively slow inter-processor communication by using 100 Mbit/s network switches. Our simulation results show that the two-step FFT algorithm without inter-processor communication outperforms the six-step 1-D FFT on this cluster