Cooley-Tukey FFT on the Connection Machine

DOI10.1016/0167-8191(92)90066-GMaRDI QIDQ1195705zbMATH OpenOpenAlexFDO

Authors S. Lennart Johnsson, Robert L. Krawitz

Publication date 19 January 1993

Published in Parallel Computing (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0167-8191(92)90066-g

zbMATH Keywords

connection machineCooley-Tukey fast Fourier transformimplementation featuresperformance data

Mathematics Subject Classification ID

Numerical methods for discrete and fast Fourier transforms (65T50) Numerical algorithms for specific classes of architectures (65Y10)

Review text

The objective of this paper is an efficient adaptation of the Cooley- Tukey fast Fourier transform (FFT) to multiprocessors interconnected by a Boolean cube network. The implementation is designed to make effective use of the communications bandwidth, the memory bandwidth, and the storage requirements with precomputed twiddle factors. The algorithms have been implemented on the connection machine systems CM-200 with 2048 floating-point processors. Performance data are provided for one- and two-dimensional FFT.

Recommendations

• Communication efficient multi-processor FFT
• Parallelization and Performance Analysis of the Cooley–Tukey FFT Algorithm for Shared-Memory Architectures
• FAST FOURIER TRANSFORM ALGORITHM DESIGN AND TRADEOFFS ON THE CM-2
• Two-dimensional FFT algorithms on hypercube and mesh machines
• Multiprocessor FFTs

Cited in

(12)

• Gray codes, fast Fourier transforms and hypercubes
• FFT algorithms and their adaptation to parallel processing
• Bluestein's FFT for arbitrary N on the hypercube
• Communication efficient multi-processor FFT
• A distributed memory algorithm for 3-D FFTs
• Convergence analysis of a \textit{periodic-like} waveform relaxation method for initial-value problems via the diagonalization technique
• Parallelization and Performance Analysis of the Cooley–Tukey FFT Algorithm for Shared-Memory Architectures
• scientific article; zbMATH DE number 820533 (Why is no real title available?)
• Multiprocessor FFTs
• Further Symmetries of in-Place FFTs
• A comparison of optimal FFTs on torus and hypercube multicomputers
• FFTs on mesh connected computers

This page was built for publication: Cooley-Tukey FFT on the Connection Machine

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