Abstract
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).
Degree
thesis:*- Grantor dc:publisher.institution
- University of Waikato
- Year dc:date.issued
- 2012
Author and committee
dc:creator, dc:contributor.*- Author dc:creator
-
- Blake, Anthony Martin
- Advisors dc:contributor.advisor
-
- Witten, Ian H.
- Cree, Michael J.
- Perrone, John A.
Subjects
dc:subject × 3Rights
dc:rights- Statement 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.