You are here

Small Discrete Fourier Transforms on Graphics Processors

Title: Small Discrete Fourier Transforms on Graphics Processors.
21 views
6 downloads
Name(s): Mitra, Sayantan, author
Srinivasan, Ashok, professor directing thesis
Yuan, Xin, committee member
Zhang, Zhenghao, committee member
Department of Computer Science, degree granting department
Florida State University, degree granting institution
Type of Resource: text
Genre: Text
Issuance: monographic
Date Issued: 2010
Publisher: Florida State University
Place of Publication: Tallahassee, Florida
Physical Form: computer
online resource
Extent: 1 online resource
Language(s): English
Abstract/Description: Efficient implementations of the Discrete Fourier Transform (DFT) for GPUs provide good performance with large data sizes, but are not competitive with CPU code for small data sizes. On the other hand, several applications require the use of a large number of DFTs on small data sizes. In fact, even algorithms for large data sizes use a divide-and-conquer approach, where eventually small DFTs need to be performed. In this thesis, it will be shown that the asymptotically slow matrix multiplication approach can yield better performance on GPUs than asymptotically faster algorithms, for small data, due to its regular memory access and computational patterns. Also discussed in this thesis are the effect of different optimization techniques, and the combination of the matrix multiplication algorithm with the mixed radix algorithm for 2-D and 3-D complex DFTs. This implementation performs up to 21 times faster than cuFFT on an NVIDIA GeForce 9800 GTX GPU and up to 5 times faster than FFTW on a CPU. Furthermore, this GPU implementation can accelerate the performance of a Quantum Monte Carlo application for which cuFFT is not effective. The primary contributions of this work lie in providing a GPU implementation that is efficient for small DFTs and in demonstrating the utility of the matrix multiplication approach.
Identifier: FSU_migr_etd-2373 (IID)
Submitted Note: A Thesis submitted to the Department of Computer Science in partial fulfillment of the requirements for the degree of Master of Science.
Degree Awarded: Summer Semester, 2010.
Date of Defense: June 1, 2010.
Keywords: Discrete Fourier Transform, DFT, GPU, CUDA
Bibliography Note: Includes bibliographical references.
Advisory Committee: Ashok Srinivasan, Professor Directing Thesis; Xin Yuan, Committee Member; Zhenghao Zhang, Committee Member.
Subject(s): Computer science
Persistent Link to This Record: http://purl.flvc.org/fsu/fd/FSU_migr_etd-2373
Owner Institution: FSU

Choose the citation style.
Mitra, S. (2010). Small Discrete Fourier Transforms on Graphics Processors. Retrieved from http://purl.flvc.org/fsu/fd/FSU_migr_etd-2373