FFT algorithms for SIMD parallel processing systems
1986; Elsevier BV; Volume: 3; Issue: 1 Linguagem: Inglês
10.1016/0743-7315(86)90027-4
ISSN1096-0848
AutoresLeah H. Jamieson, Philip T. Mueller, Howard Jay Siegel,
Tópico(s)Embedded Systems Design Techniques
ResumoSIMD (single instruction stream - multiple data stream) algorithms for one- and two-dimensional discrete Fourier transforms are presented. Parallel structurings of algorithms for efficient computation for a variety of machine size/problem size combinations are presented and analyzed. Through these algorithms, techniques for exploiting relationships between problem size and machine size are demonstrated. The algorithms are evaluated in terms of the number of arithmetic operations and interprocessor data transfers required. The ability of various interconnection networks presented in the literature to perform the needed transfers is examined. It is shown that the efficiency of a particular data distribution/algorithm decomposition approach is a function of the machine-size/problem-size relationship.
Referência(s)