BIB-VERSION:: CS-TR-v2.0 ID:: ncstrl.dartmouthcs//TR96-294 ENTRY:: August 09, 1996 ORGANIZATION:: Dartmouth College, Computer Science TITLE:: Performing Out-of-Core FFTs on Parallel Disk Systems TYPE:: Technical Report (paper) REVISION:: 3 AUTHOR:: Cormen, Thomas H. AUTHOR:: Nicol, David M. DATE:: August 1997 RETRIEVAL:: For a paper copy, email RETRIEVAL:: For a paper copy, write to Technical Report Librarian Department of Computer Science Dartmouth College 6211 Sudikoff Laboratory Hanover, NH 03755-3510 USA RETRIEVAL:: Compressed Postscript at http://www.cs.dartmouth.edu/reports/TR96-294.ps.Z RETRIEVAL:: PDF at http://www.cs.dartmouth.edu/reports/TR96-294.pdf ABSTRACT:: The Fast Fourier Transform (FFT) plays a key role in many areas of computational science and engineering. Although most one-dimensional FFT problems can be solved entirely in main memory, some important classes of applications require out-of-core techniques. For these, use of parallel I/O systems can improve performance considerably. This paper shows how to perform one-dimensional FFTs using a parallel disk system with independent disk accesses. We present both analytical and experimental results for performing out-of-core FFTs in two ways: using traditional virtual memory with demand paging, and using a provably asymptotically optimal algorithm for the Parallel Disk Model (PDM) of Vitter and Shriver. When run on a DEC 2100 server with a large memory and eight parallel disks, the optimal algorithm for the PDM runs up to 144.7 times faster than in-core methods under demand paging. Moreover, even including I/O costs, the normalized times for the optimal PDM algorithm are competitive, or better than, those for in-core methods even when they run entirely in memory. NOTE:: Similar paper to appear in Parallel Computing. Original version August 7, 1996; revised September 6, 1996 and August 14, 1997. (Compressed Postscript for September 1996 version.) END:: ncstrl.dartmouthcs//TR96-294