Computing the fast Fourier transform on SIMD microprocessors

Blake, Anthony Martin

Computing the fast Fourier transform on SIMD microprocessors

dc.contributor.advisor	Witten, Ian H.
dc.contributor.advisor	Cree, Michael J.
dc.contributor.advisor	Perrone, John A.
dc.contributor.author	Blake, Anthony Martin
dc.date.accessioned	2012-06-21T03:24:42Z
dc.date.available	2012-06-21T03:24:42Z
dc.date.issued	2012
dc.date.updated	2012-06-18T06:26:52Z
dc.description.abstract	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 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.mimetype	application/pdf
dc.identifier.citation	Blake, 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/6417	en
dc.identifier.uri	https://hdl.handle.net/10289/6417
dc.language.iso	en
dc.publisher	University of Waikato
dc.rights	All 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.subject	Fourier transform
dc.subject	FFT
dc.subject	DFT
dc.title	Computing the fast Fourier transform on SIMD microprocessors	en
dc.type	Thesis
pubs.place-of-publication	Hamilton, New Zealand	en_NZ
thesis.degree.grantor	University of Waikato
thesis.degree.level	Doctoral
thesis.degree.name	Doctor of Philosophy (PhD)