Connexions

Sections
You are here: Home » Content » Computing the fast Fourier transform on SIMD microprocessors

About: Computing the fast Fourier transform on SIMD microprocessors

Collection type: Ph.D. thesis

Thesis by: Anthony Blake. E-mail the author

View the content: Computing the fast Fourier transform on SIMD microprocessors

Metadata

Name: Computing the fast Fourier transform on SIMD microprocessors
ID: col11438
Language: English (en)
Summary: This thesis describes how to compute the fast Fourier transform (FFT) of a power-of-two length signal on single-instruction, multiple-data (SIMD) microprocessors faster than or very close to the speed of state of the art libraries such as FFTW (``Fastest Fourier Transform in the West''), SPIRAL and Intel Integrated Performance Primitives (IPP). The conjugate-pair algorithm has advantages in terms of memory bandwidth, and three implementations of this algorithm, which incorporate latency and spatial locality optimizations, are automatically vectorized at the algorithm level of abstraction. Performance results on 2-way, 4-way and 8-way SIMD machines show that the performance scales much better than FFTW or SPIRAL. The implementations presented in this thesis are compiled into a high-performance FFT library called SFFT (``Streaming Fast Fourier Transform''), and benchmarked against FFTW, SPIRAL, Intel IPP and Apple Accelerate on sixteen x86 machines and two ARM NEON machines, and shown to be, in many cases, faster than these state of the art libraries, but without having to perform extensive machine specific calibration, thus demonstrating that there are good heuristics for predicting the performance of the FFT on SIMD microprocessors (i.e., the need for empirical optimization may be overstated).
Collection Subtype: Ph.D. thesis
Subject: Mathematics and Statistics, Science and Technology
Keywords: DFT, FFT, SIMD
License: Creative Commons Attribution License CC-BY 3.0
Authors: Anthony Blake (amb33@cs.waikato.ac.nz)
Copyright Holders: Anthony Blake (amb33@cs.waikato.ac.nz)
Maintainers: Anthony Blake (amb33@cs.waikato.ac.nz)
Latest version: 1.2 (history)
First publication date: Jun 20, 2012 9:02 pm GMT-5
Last revision to collection: Jul 15, 2012 8:36 pm GMT-5

Downloads

PDF: col11438_1.2.pdf PDF file, for viewing content offline and printing. Learn more.
EPUB: col11438_1.2.epub Electronic book format file, for viewing on mobile devices. Learn more.
Collection Structure XML: col11438_1.2_collection.xml XML that defines the structure of the collection. Cannot be reimported in the editing interface. Learn more.
Source Export ZIP: col11438_1.2_complete.zip The Collection Structure XML, plus the CNXML and included media files for each module in the collection. Cannot be reimported. Learn more.
Offline ZIP: col11438_1.2_offline.zip An offline HTML copy of the content. Also includes XML, included media files, and other support files. Learn more.

Version History

Version: 1.2 Jul 15, 2012 8:36 pm GMT-5 by Anthony Blake
Changes: 
Added appendices
Version: 1.1 Jul 15, 2012 5:28 pm GMT-5 by Anthony Blake
Changes: 
Initial commit

How to Reuse and Attribute This Content

If you derive a copy of this content using a Connexions account and publish your version, proper attribution of the original work will be automatically done for you.

If you reuse this work elsewhere, in order to comply with the attribution requirements of the license (CC-BY 3.0), you must include

  • the authors' names: Anthony Blake
  • the title of the work: Computing the fast Fourier transform on SIMD microprocessors
  • the Connexions URL where the work can be found: http://cnx.org/content/col11438/1.2/

See the citation section below for examples you can copy.

How to Cite and Attribute This Content

The following citation styles comply with the attribution requirements for the license (CC-BY 3.0) of this work:

American Chemical Society (ACS) Style Guide:

Blake, A. Computing the fast Fourier transform on SIMD microprocessors, Connexions Web site. http://cnx.org/content/col11438/1.2/, Jul 15, 2012.

American Medical Assocation (AMA) Manual of Style:

Blake A. Computing the fast Fourier transform on SIMD microprocessors [Connexions Web site]. July 15, 2012. Available at: http://cnx.org/content/col11438/1.2/.

American Psychological Assocation (APA) Publication Manual:

Blake, A. (2012, July 15). Computing the fast Fourier transform on SIMD microprocessors. Retrieved from the Connexions Web site: http://cnx.org/content/col11438/1.2/

Chicago Manual of Style (Bibliography):

Blake, Anthony. "Computing the fast Fourier transform on SIMD microprocessors." Connexions. July 15, 2012. http://cnx.org/content/col11438/1.2/.

Chicago Manual of Style (Note):

Anthony Blake, "Computing the fast Fourier transform on SIMD microprocessors," Connexions, July 15, 2012, http://cnx.org/content/col11438/1.2/.

Chicago Manual of Style (Reference, in Author-Date style):

Blake, A. 2012. Computing the fast Fourier transform on SIMD microprocessors. Connexions, July 15, 2012. http://cnx.org/content/col11438/1.2/.

Modern Languages Association (MLA) Style Manual:

Blake, Anthony. Computing the fast Fourier transform on SIMD microprocessors. Connexions. 15 July 2012 <http://cnx.org/content/col11438/1.2/>.