Parallel power-of-two FFTs on hypercubes
Mahn-Ling Woo, Rosemary Anne Renaut · 1991
Theoretical analysis of ordered power-of-two Fast Fourier transforms (P02FFT) demonstrates that the most eficient algorithms for hypercube architectures may not always use nearest-neighbor communication.The ordered P02FFT which uses nearest-neighbor (distance 1) communication, requires d inter-processor communications for r/2 ~d and 2d -lr/2] interprocessor communications for r/2 < d, where 2" = N.In this paper we show that an ordered P02FFT can be obtained with just d inierprocessor communications for any r if the restriction that all communications are distance one is removed.This new algorithm uses [r/2~distance one and d -~r/2] distance two interprocessor communications.Packets of size N/2d~1 are transmitted in both of the ordered P02FFT algorithms.The time complexity of both the distance one and distance two algorithms is discussed.