Dartmouth College Computer Science
Technical Report series
TR search TR listserv
|By author:||A B C D E F G H I J K L M N O P Q R S T U V W X Y Z|
|By number:||2017, 2016, 2015, 2014, 2013, 2012, 2011, 2010, 2009, 2008, 2007, 2006, 2005, 2004, 2003, 2002, 2001, 2000, 1999, 1998, 1997, 1996, 1995, 1994, 1993, 1992, 1991, 1990, 1989, 1988, 1987, 1986|
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.
Similar paper to appear in Parallel Computing.
Original version August 7, 1996;
revised September 6, 1996 and August 14, 1997.
Postscript for September 1996 version.)
Bibliographic citation for this report: [plain text] [BIB] [BibTeX] [Refer]
Or copy and paste:
Thomas H. Cormen and David M. Nicol, "Performing Out-of-Core FFTs on Parallel Disk Systems." Dartmouth Computer Science Technical Report PCS-TR96-294, August 1997.
Notify me about new tech reports.
Search the technical reports.
To receive paper copy of a report, by mail, send your address and the TR number to reports AT cs.dartmouth.edu
Copyright notice: The documents contained in this server are included by the contributing authors as a means to ensure timely dissemination of scholarly and technical work on a non-commercial basis. Copyright and all rights therein are maintained by the authors or by other copyright holders, notwithstanding that they have offered their works here electronically. It is understood that all persons copying this information will adhere to the terms and constraints invoked by each author's copyright. These works may not be reposted without the explicit permission of the copyright holder.
Technical reports collection maintained by David Kotz.