The speedup and efficiency of 3-D FFT on distributed memory MIMD systems

The author analyzes a 3-D FFT (fast Fourier transform) algorithm for a distributed memory MIMD (multiple-instruction multiple-data) system. It is shown that the communication complexity limits the efficiency even under ideal conditions. The efficiency for the optimal speedup is η_opt=0.5. Actual applications which experience load imbalance, duplication of work, and blocking are even less efficient. Therefore the speedup with P processing elements, S(P)=η×P, is disappointingly low. Moreover, the 3-D FFT algorithm is not susceptible to massive parallelization, and the optimal number of PEs is rather low even for large problem size and fast communication. A strategy to reduce the communication complexity is presented