%T Multiprocessor Out-of-Core FFTs with Distributed Memory and Parallel Disks
%A Thomas H. Cormen
%A Jake Wegmann
%A David M. Nicol
%R Technical Report PCS-TR97-303
%I Dartmouth College, Computer Science
%C Hanover, NH
%D January 1997
%U http://www.cs.dartmouth.edu/reports/TR97-303.ps.Z
%X
 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.
%Z
 Revised version appeared in IOPADS '97.