Communication efficient multi-processor FFT

DOI10.1016/0021-9991(92)90380-HMaRDI QIDQ1201720zbMATH OpenOpenAlexFDO

Authors S. Lennart Johnsson, Michel Jacquemin, Robert L. Krawitz

Publication date 17 January 1993

Published in Journal of Computational Physics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0021-9991(92)90380-h

zbMATH Keywords

Boolean cube networksefficient multiprocessor algorithmsfast Fourier transform

Mathematics Subject Classification ID

Numerical methods for discrete and fast Fourier transforms (65T50) Parallel numerical computation (65Y05) Numerical algorithms for specific classes of architectures (65Y10) Distributed algorithms (68W15)

Review text

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.

Recommendations

• Cooley-Tukey FFT on the Connection Machine
• Implementation of parallel FFT algorithms on distributed memory machines with a minimum overhead of communication
• Multiprocessor FFTs
• FFT algorithms and their adaptation to parallel processing
• FAST FOURIER TRANSFORM ALGORITHM DESIGN AND TRADEOFFS ON THE CM-2

Cites work

• Algorithms for Matrix Transposition on Boolean N-Cube Configured Ensemble Architectures
• scientific article; zbMATH DE number 3967873 (Why is no real title available?)
• scientific article; zbMATH DE number 3752234 (Why is no real title available?)
• scientific article; zbMATH DE number 3577138 (Why is no real title available?)
• Multiprocessor FFTs
• Optimum broadcasting and personalized communication in hypercubes
• Solving Tridiagonal Systems on Ensemble Architectures

Cited in

(8)

• Cooley-Tukey FFT on the Connection Machine
• A distributed memory algorithm for 3-D FFTs
• Congruent Number Theta Coefficients to 1012
• A highly efficient FFT using shared-memory multiplexing
• Multiprocessor FFTs
• Further Symmetries of in-Place FFTs
• Compression using efficient multicasting
• Minimizing Communication in the Multidimensional FFT

This page was built for publication: Communication efficient multi-processor FFT

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1201720)