Multiprocessor out-of-core FFTs with distributed memory and parallel disks

Thomas H. Cormen, Jake Wegmann, David M. Nicol

Research output: Contribution to conferencePaperpeer-review


This paper extends an earlier out-of-core Fast Fourier Transform (FFT) method for a uniprocessor with the Parallel Disk Model (PDM) to use multiple processors. Four out-of-core multiprocessor methods are examined. Operationally, these methods differ in the size of 'mini-butterfly' computed in memory and how the data are organized on the disks and in the distributed memory of the multiprocessor. The methods also perform differing amounts of I/O and communication. Two of them have the remarkable property that even though they are computing the FFT on a multiprocessor, all interprocessor communication occurs outside the mini-butterfly computations; communication that ordinarily occurs in a butterfly is folded into other data-movement operations. An analysis program shows that the two methods that use no butterfly communication usually use less communication overall than the other methods. The analysis program is fast enough that it can be invoked at run time to determine which of the four methods uses the least communication. One set of performance results on a small workstation cluster indicates that the methods without butterfly communication are approximately 9.5% faster. Moreover, they are much easier to implement.

Original languageEnglish (US)
Number of pages10
StatePublished - 1997
Externally publishedYes
EventProceedings of the 1997 5th Workshop on I/O in Parallel and Distributed Systems - San Jose, CA, USA
Duration: Nov 17 1997Nov 17 1997


OtherProceedings of the 1997 5th Workshop on I/O in Parallel and Distributed Systems
CitySan Jose, CA, USA

ASJC Scopus subject areas

  • Computer Science(all)


Dive into the research topics of 'Multiprocessor out-of-core FFTs with distributed memory and parallel disks'. Together they form a unique fingerprint.

Cite this