Superparallel FFTs

DOI10.1137/0914022MaRDI QIDQ5286354zbMATH OpenOpenAlexFDO

Authors Hans Munthe-Kaas

Publication date 29 June 1993

Published in SIAM Journal on Scientific Computing (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1137/0914022

zbMATH Keywords

fast Fourier transform algorithmsparallel computingSIMD computerssingle instruction multiple data machinessuperparallel algorithms

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)

Review text

Fast Fourier transform (FFT) algorithms based on the Cooley-Tukey approach [cf. \textit{J. W. Cooley} and \textit{J. W. Tukey}, Math. Comput. 19, 297-301 (1965; Zbl 0127.090)] are developed for single instruction multiple data (SIMD) machines. Any combination of FFT with powers of two as the periods and some alignment requirements for the initial data may be calculated. The algorithm solves multiple instances of similar problems with a degree of parallelism, therefore it is called superparallel in the sense of \textit{D. Parkinson} [Superparallel algorithms, in Supercomputing, NATO ASI series \(F\), Vol. 62, Springer-Verlag, Berlin, New York (1989)]. The degree of parallelism is proportional to \(\log_ 2m\), where \(m\) is the number of points in the largest subsystem. Unscrambling the results may be scheduled in parallel if necessary. An implementation for the SIMD machine MasPar with 16,384 processors is analysed.

Recommendations

• scientific article; zbMATH DE number 3997125
• scientific article; zbMATH DE number 1131691
• Parallel FFT algorithms for mimd computers
• A parallel FFT on an MIMD machine
• Ultrahigh-performance FFTs for the CRAY-2 and CRAY Y-MP supercomputers

Cited in

(3)

• Data-parallel numerical methods in a weather forecast model
• scientific article; zbMATH DE number 833641 (Why is no real title available?)
• Ultrahigh-performance FFTs for the CRAY-2 and CRAY Y-MP supercomputers

This page was built for publication: Superparallel FFTs

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