PARALLEL IMPLEMENTATIONS OF 1-D FAST FOURIER TRANSFORM WITHOUT INTERPROCESSOR COMMUNICATION

摘要

Computing 1-D Fast Fourier Transform (FFT) using the conventional 4-step FFT on parallel computers requires intensive all-to-all communication, which can adversely affect the performance of FFT. In this paper, we present 2-step-no-communication and 3-step-no-communication algorithms, which are parallel algorithms for 1-D FFT without interprocessor communication. One of the main advantages of these algorithms is the absence of all-to-all communication between processors, albeit at the expense of increased computation compared to the conventional 4-step FFT. If the cost of extra computation required by the 2-step-no-communication and the 3-step-no-communication algorithms is more than offset by the cost of all-to-all communication in the 4-step FFT, then these two no-communication algorithms will outperform the 4-step FFT algorithm. We test the 2-step-no-communication and the 3-step-no-communication algorithms in two parallel systems (a 32-node Beowulf cluster and 8-node symmetric multiprocessors), with varying costs of all-to-all communication and computation. The experimental results show that the no-communication algorithms perform better than the 4-step FFT in the SMP only for relatively small data sizes, but the no-communication algorithms outperform the 4-step FFT in the Beowulf cluster for all data sizes tested.