Parallelization of Two- and Three-Dimensional Fast Fourier Transforms

Abstract

Large computational programs employing multi-dimensional spectral techniques for numerical modeling or image processing rely heavily on the use of Fast Fourier Transforms (FFTs). This report describes work performed to port Numeric Algorithms Group, Ltd. (NAG) two-dimensional and three-dimensional FFTs to the IBM SP-l distributed parallel computing platform to transform arrays of almost any dimension upon many processors, while achieving significant speed-up factors. A description of the parallelization strategies used, observed performance, and conclusions derived is provided. The parallel FFT performance achieved is significant in that it allows for flexible, portable, and robust use of spectral and image processing codes across arbitrary arrays of processors. This further allows for more basic scientific research and production computing with greater flexibility than before. The work described by this report indicates that there is a great potential in implementing flexible and efficient FFTs that can meet the ever-increasing demands of future image and digital signal processing systems.

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Feb 01, 2001
Accession Number
ADA388664

Entities

People

  • Paul Bennett

Organizations

  • University of New Mexico

Tags

Communities of Interest

  • Energy and Power Technologies

DTIC Thesaurus Topics

  • Air Force
  • Air Force Research Laboratories
  • Algorithms
  • Computations
  • Computer Programming
  • Computer Programs
  • Computers
  • Differential Equations
  • Digital Signal Processing
  • Fast Fourier Transforms
  • Government Procurement
  • Governments
  • Image Processing
  • New Mexico
  • Signal Processing
  • Three Dimensional
  • Two Dimensional

Fields of Study

  • Engineering

Readers

  • Computer Vision.
  • Parallel and Distributed Computing.