Accession Number : ADA321329

Title :   Performing Out-of-Core FFTS on Parallel Disk Systems.

Descriptive Note : Contract rept.,

Corporate Author : INSTITUTE FOR COMPUTER APPLICATIONS IN SCIENCE AND ENGINEERING HAMPTON VA

Personal Author(s) : Cormen, Thomas H. ; Nicol, David M.

PDF Url : ADA321329

Report Date : DEC 1996

Pagination or Media Count : 16

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 input output 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.

Descriptors :   *PARALLEL PROCESSORS, *FAST FOURIER TRANSFORMS, *DISKS, ALGORITHMS, INPUT, OPTIMIZATION, COMPUTATIONS, MODELS, COSTS, MEMORY DEVICES, INTERNAL, INPUT OUTPUT DEVICES, MAGNETIC CORES.

Subject Categories : Numerical Mathematics
      Computer Hardware

Distribution Statement : APPROVED FOR PUBLIC RELEASE