|
cannam@127
|
1 <!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 3.2//EN">
|
|
cannam@127
|
2 <html>
|
|
cannam@127
|
3 <head><title>
|
|
cannam@127
|
4 FFTW FAQ - Section 4
|
|
cannam@127
|
5 </title>
|
|
cannam@127
|
6 <link rev="made" href="mailto:fftw@fftw.org">
|
|
cannam@127
|
7 <link rel="Contents" href="index.html">
|
|
cannam@127
|
8 <link rel="Start" href="index.html">
|
|
cannam@127
|
9 <link rel="Next" href="section5.html"><link rel="Previous" href="section3.html"><link rel="Bookmark" title="FFTW FAQ" href="index.html">
|
|
cannam@127
|
10 </head><body text="#000000" bgcolor="#FFFFFF"><h1>
|
|
cannam@127
|
11 FFTW FAQ - Section 4 <br>
|
|
cannam@127
|
12 Internals of FFTW
|
|
cannam@127
|
13 </h1>
|
|
cannam@127
|
14
|
|
cannam@127
|
15 <ul>
|
|
cannam@127
|
16 <li><a href="#howworks" rel=subdocument>Q4.1. How does FFTW work?</a>
|
|
cannam@127
|
17 <li><a href="#whyfast" rel=subdocument>Q4.2. Why is FFTW so fast?</a>
|
|
cannam@127
|
18 </ul><hr>
|
|
cannam@127
|
19
|
|
cannam@127
|
20 <h2><A name="howworks">
|
|
cannam@127
|
21 Question 4.1. How does FFTW work?
|
|
cannam@127
|
22 </A></h2>
|
|
cannam@127
|
23
|
|
cannam@127
|
24 The innovation (if it can be so called) in FFTW consists in having a
|
|
cannam@127
|
25 variety of composable <i>solvers</i>, representing different FFT algorithms and implementation strategies, whose combination into a
|
|
cannam@127
|
26 particular <i>plan</i> for a given size can be determined at runtime according to the characteristics of your machine/compiler.
|
|
cannam@127
|
27 This peculiar software architecture allows FFTW to adapt itself to
|
|
cannam@127
|
28 almost any machine.
|
|
cannam@127
|
29 <p>
|
|
cannam@127
|
30 For more details (albeit somewhat outdated), see the paper "FFTW:
|
|
cannam@127
|
31 An Adaptive Software Architecture for the FFT", by M. Frigo and
|
|
cannam@127
|
32 S. G. Johnson, <i>Proc. ICASSP</i> 3, 1381 (1998), also available at <A href="http://www.fftw.org">the FFTW web page</A>.
|
|
cannam@127
|
33 <h2><A name="whyfast">
|
|
cannam@127
|
34 Question 4.2. Why is FFTW so fast?
|
|
cannam@127
|
35 </A></h2>
|
|
cannam@127
|
36
|
|
cannam@127
|
37 This is a complex question, and there is no simple answer. In fact,
|
|
cannam@127
|
38 the authors do not fully know the answer, either. In addition to many
|
|
cannam@127
|
39 small performance hacks throughout FFTW, there are three general
|
|
cannam@127
|
40 reasons for FFTW's speed.
|
|
cannam@127
|
41 <ul>
|
|
cannam@127
|
42 <li> FFTW uses a variety of FFT algorithms and implementation styles
|
|
cannam@127
|
43 that can be arbitrarily composed to adapt itself to
|
|
cannam@127
|
44 a machine. See <A href="#howworks">Q4.1 `How does FFTW work?'</A>.
|
|
cannam@127
|
45 <li> FFTW uses a code generator to produce highly-optimized
|
|
cannam@127
|
46 routines for computing small transforms.
|
|
cannam@127
|
47
|
|
cannam@127
|
48 <li> FFTW uses explicit divide-and-conquer to take advantage
|
|
cannam@127
|
49 of the memory hierarchy.
|
|
cannam@127
|
50 </ul>
|
|
cannam@127
|
51 For more details (albeit somewhat outdated), see the paper "FFTW:
|
|
cannam@127
|
52 An Adaptive Software Architecture for the FFT", by M. Frigo and
|
|
cannam@127
|
53 S. G. Johnson, <i>Proc. ICASSP</i> 3, 1381 (1998), available along with other references at
|
|
cannam@127
|
54 <A href="http://www.fftw.org">the FFTW web page</A>. <hr>
|
|
cannam@127
|
55 Next: <a href="section5.html" rel=precedes>Known bugs</a>.<br>
|
|
cannam@127
|
56 Back: <a href="section3.html" rev=precedes>Using FFTW</a>.<br>
|
|
cannam@127
|
57 <a href="index.html" rev=subdocument>Return to contents</a>.<p>
|
|
cannam@127
|
58 <address>
|
|
cannam@127
|
59 <A href="http://www.fftw.org">Matteo Frigo and Steven G. Johnson</A> / <A href="mailto:fftw@fftw.org">fftw@fftw.org</A>
|
|
cannam@127
|
60 - 30 July 2016
|
|
cannam@127
|
61 </address><br>
|
|
cannam@127
|
62 Extracted from FFTW Frequently Asked Questions with Answers,
|
|
cannam@127
|
63 Copyright © 2016 Matteo Frigo and Massachusetts Institute of Technology.
|
|
cannam@127
|
64 </body></html>
|
