FFT algorithms for SIMD parallel processing systems

Academic Article


  • SIMD (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. © 1986.
  • Authors

    Digital Object Identifier (doi)

    Author List

  • Jamieson LH; Mueller PT; Siegel HJ
  • Start Page

  • 48
  • End Page

  • 71
  • Volume

  • 3
  • Issue

  • 1