IMPLEMENTATION OF PARALLEL FFT ALGORITHMS ON DISTRIBUTED-MEMORY MACHINES WITH A MINIMUM OVERHEAD OF COMMUNICATION

We present in this paper methods for the many mono-dimensional and mul ti-dimensional FFT algorithms which minimize the communication overhea d. We describe the implementation of these algorithms on a hypercube a rchitecture. Moreover, we derive these implementations onto mesh and t orus topologies by using emulation results of hypercube communications on these topologies, We compute optimal sizes of blocks in order to o btain a maximal overlap of communications by computations, Experimenta l results on Intel iPSC/860 and Paragon, IBM SP1 and Gray T3D machines are given, which confirm the theoretical analysis.