A faster FFT in the Mid-West

FFT implementations today generally fall into two categories: Library generators (such as FFTW and Spiral) and specialized FFTs (such as prime95). Specialized FFTs have the obvious limitation of being specialized. However they are hand-tuned and generally offer superior performance. Library generators are generic and easier to port. But their performance is generally suboptimal. We describe in this paper an FFT library that was built while paying special attention to locality. The library achieves significantly better performance than FFTW, for long vectors. Unlike FFTW or Spiral, the recursive decomposition of the FFT is not created by a library generator; it is created by macro expansion that has a few selectable parameters. This provides an interface that can be more easily modified by users.

Name thesis:degree_name

M.S.

Level thesis:degree_level

Thesis

Discipline thesis:degree_discipline

Computer Science

Grantor

University of Illinois at Urbana-Champaign

Year dc:date

2013

Author dc:creator

• Yee, Alexander

Contributors dc:contributor

• Snir, Marc

• High Performance Computing (HPC)
• Fast Fourier Transform (FFT)
• Libraries

Statement dc:rights

• Copyright 2013 Alexander Yee

Language dc:language

en

Handle dc:identifier

http://hdl.handle.net/2142/44116

OAI identifier oai:identifier

oai:www.ideals.illinois.edu:2142/44116