@TechReport{cormen:fft2-tr, author = {Thomas H. Cormen and Jake Wegmann and David M. Nicol}, title = {Multiprocessor Out-of-Core {FFTs} with Distributed Memory and Parallel Disks}, year = {1997}, number = {PCS-TR97-303}, institution = {Dept. of Computer Science, Dartmouth College}, copyright = {the authors}, later = {cormen:fft3}, URL = {https://digitalcommons.dartmouth.edu/cs_tr/143/}, keywords = {parallel I/O, out of core, scientific computing, FFT, pario-bib}, 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.}, comment = {Extends the work of cormen:fft.} }