Show simple item record  

dc.contributor.advisorWitten, Ian H.
dc.contributor.advisorCree, Michael J.
dc.contributor.advisorPerrone, John A.
dc.contributor.authorBlake, Anthony Martin
dc.date.accessioned2012-06-21T03:24:42Z
dc.date.available2012-06-21T03:24:42Z
dc.date.issued2012
dc.identifier.citationBlake, A. M. (2012). Computing the fast Fourier transform on SIMD microprocessors (Thesis, Doctor of Philosophy (PhD)). University of Waikato, Hamilton, New Zealand. Retrieved from https://hdl.handle.net/10289/6417en
dc.identifier.urihttps://hdl.handle.net/10289/6417
dc.description.abstractThis 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 Trans- form”), 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).
dc.format.mimetypeapplication/pdf
dc.language.isoen
dc.publisherUniversity of Waikato
dc.rightsAll items in Research Commons are provided for private study and research purposes and are protected by copyright with all rights reserved unless otherwise indicated.
dc.subjectFourier transform
dc.subjectFFT
dc.subjectDFT
dc.titleComputing the fast Fourier transform on SIMD microprocessorsen
dc.typeThesis
thesis.degree.grantorUniversity of Waikato
thesis.degree.levelDoctoral
thesis.degree.nameDoctor of Philosophy (PhD)
dc.date.updated2012-06-18T06:26:52Z
pubs.place-of-publicationHamilton, New Zealanden_NZ


Files in this item

Thumbnail

This item appears in the following Collection(s)

Show simple item record