The Scalability of FFT on Parallel Computers

Anshul Gupta, Vipin Kumar

Research output: Contribution to journalArticlepeer-review

72 Scopus citations

Abstract

In this paper we present the scalability analysis of parallel Fast Fourier Transform algorithm on mesh and hypercube connected multicomputers using the isoefficiency metric. The isoefficiency function of an algorithm architecture combination is defined as the rate at which the problem size should grow with the number of processors to maintain a fixed efficiency. On the hypercube architecture, a commonly used parallel FFT algorithm can obtain linearly increasing speedup with respect to the number of processors with only a moderate increase in problem size. But there is a limit on the achievable efficiency and this limit is determined by the ratio of CPU speed and communication bandwidth of the hypercube channels. Efficiencies higher than this threshold value can be obtained if the problem size is increased very rapidly. If the hardware supports cut-through routing, then this threshold can also be overcome by using an alternate less scalable parallel formulation. The scalability analysis for the mesh connected multicomputers reveals that FFT cannot make efficient use of large-scale mesh architectures unless the bandwidth of the communication channels is increased as a function of the number of processors. We also show that it is more cost-effective to implement the FFT algorithm on a hypercube rather than a mesh despite the fact that large scale meshes are cheaper to construct than large hypercubes. Although the scope of this paper is limited to the Cooley-Tukey FFT algorithm on a few classes of architectures, the methodology can be used to study the performance of various FFT algorithms on a variety of architectures such as SIMD hypercube and mesh architectures and shared memory architecture.

Original languageEnglish (US)
Pages (from-to)922-932
Number of pages11
JournalIEEE Transactions on Parallel and Distributed Systems
Volume4
Issue number8
DOIs
StatePublished - Aug 1993

Keywords

  • Communication overhead
  • Fast
  • Fourier Transform
  • efficiency
  • isoefficiency function
  • parallel architectures
  • parallel processing
  • scalability

Fingerprint Dive into the research topics of 'The Scalability of FFT on Parallel Computers'. Together they form a unique fingerprint.

Cite this