Multidimensional, Multiprocessor, Out-of-Core FFTs with Distributed Memory and Parallel Disks (Extended Abstract)

) Lauren M. Baptist Thomas H. Cormen # {lmb, thc}@cs.dartmouth.edu Dartmouth College Department of Computer Science Abstract We show how to compute multidimensional Fast Fourier Transforms (FFTs) on a multiprocessor system with distributed memory when problem sizes are so large that the data do not fit in the memory of the entire system. Instead, data reside on a parallel disk system and are brought into memory in sections. We use the Parallel Disk Model for implementation and analysis. Our method is a straightforward out-of-core variant of a wellknown method for in-core, multidimensional FFTs. It performs 1-dimensional FFT computations on each dimension in turn. This method is easy to generalize to any number of dimensions, and it also readily permits the individual dimensions to be of any sizes that are integer powers of 2. The key step is an out-of-core transpose operation that places the data along each dimension into contiguous positions on the parallel disk system so that the..