Multiprocessor Out-of-Core FFTs with Distributed Memory and Parallel Disks

Dartmouth Technical Report PCS-TR97-303

	Thomas H. Cormen
	Jake Wegmann
	David M. Nicol

Date: January 1997

URL (compressed postscript): <http://www.cs.dartmouth.edu/reports/TR97-303.ps.Z> (156KB)

URL (PDF): <http://www.cs.dartmouth.edu/reports/TR97-303.pdf> (316KB)

Abstract:
 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.
 Performance results on a small workstation cluster indicate that
 except for unusual combinations of problem size and memory size, the
 methods that do not perform interprocessor communication during the
 mini-butterfly computations require approximately 86% of the time of
 those that do.  Moreover, the faster methods are much easier to
 implement.

Note:
 Revised version appeared in IOPADS '97.