On the scalability of FFT on parallel computers

Publisher Website
Google Scholar
Abstract
In this paper, we present the scalability analysis of parall el Fast Fourier Transform algorithm on mesh and hypercube connected multicomputers,using the isoefficiencymetric. 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 hyp ercube architecture, a commonly used parallel FFT algorithm can obtain linearly increasing spee dup with respect to the number,of processors with only a moderate increase in problem,size. But there is a l imit 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 thres hold can also be overcome by using an alternate less scalable parallel formulation. The scalability analysis f or 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. This work was supported by IST/SDIO through the Army Research Office grant # 28408-MA-SDI to the University of Minnesota

This publication has 8 references indexed in Scilit: