Communication efficient multi-processor FFT (Q1201720)

The main contribution of the paper are communication efficient multiprocessor algorithms for the Cooley-Tukey fast Fourier transform (FFT). The discussed algorithms are also efficient in the use of storage for twiddle factors and in the use of the bandwidth between each processor and its memory. The impact on performance of different data layouts is evaluated. Finally, results from implementations on the connection machine system CM-200 are presented.