Subversion Repositories shark

Rev

Rev 2 | Details | Compare with Previous | Last modification | View Log | RSS feed

Rev Author Line No. Line
2 pj 1
<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 3.2//EN">
2
<html>
3
<head><title>
4
FFTW FAQ - Section 4
5
</title>
6
<link rev="made" href="mailto:fftw@theory.lcs.mit.edu">
7
<link rel="Contents" href="index.html">
8
<link rel="Start" href="index.html">
9
<link rel="Next" href="section5.html"><link rel="Previous" href="section3.html"><link rel="Bookmark" title="FFTW FAQ" href="index.html">
10
</head><body text="#000000" bgcolor="#FFFFFF"><h1>
11
FFTW FAQ - Section 4 <br>
12
Internals of FFTW
13
</h1>
14
 
15
<ul>
16
<li><a href="#howworks" rel=subdocument>Q4.1. How does FFTW work?</a>
17
<li><a href="#whyfast" rel=subdocument>Q4.2. Why is FFTW so fast?</a>
18
<li><a href="#wisdom" rel=subdocument>Q4.3. What is this <code>wisdom</code> thing?</a>
19
<li><a href="#whywisdom" rel=subdocument>Q4.4. Why do you use <code>wisdom</code>? I just wanted to save a plan.</a>
20
</ul><hr>
21
 
22
<h2><A name="howworks">
23
Question 4.1.  How does FFTW work?
24
</A></h2>
25
 
26
The innovation (if it can be so called) in FFTW consists in having an
27
interpreter execute the transform.  The program for the interpreter
28
(the <i>plan</i>) is computed at runtime according to the
29
characteristics of your machine/compiler.  This peculiar software
30
architecture allows FFTW to adapt itself to almost any machine.
31
 
32
<p>
33
For more details, see the paper &quot;The Fastest Fourier Transform in
34
the West&quot;, by M. Frigo and S. G. Johnson, available at
35
<A href="http://theory.lcs.mit.edu/~fftw/">the FFTW web page</A>.  See also &quot;FFTW: An Adaptive Software Architecture for the
36
FFT&quot;, in ICASSP '98.  
37
<h2><A name="whyfast">
38
Question 4.2.  Why is FFTW so fast?
39
</A></h2>
40
 
41
This is a complex question, and there is no simple answer.  In fact,
42
the authors do not fully know the answer, either.  In addition to many
43
small performance hacks throughout FFTW, there are three general
44
reasons for FFTW's speed.  
45
<ul>
46
<li>    FFTW uses an internal interpreter to adapt itself to
47
a machine.  See <A href="#howworks">Q4.1 `How does FFTW work?'</A>.  
48
<li>    FFTW uses a code generator to produce highly-optimized
49
routines for computing small transforms.
50
 
51
<li>    FFTW uses explicit divide-and-conquer to take advantage
52
of the memory hierarchy.  
53
</ul>
54
For more details on these three topics, see the paper &quot;The
55
Fastest Fourier Transform in the West&quot;, by M. Frigo and S. G. Johnson,
56
available at <A href="http://theory.lcs.mit.edu/~fftw/">the FFTW web page</A>.  
57
<h2><A name="wisdom">
58
Question 4.3.  What is this <code>wisdom</code> thing?
59
</A></h2>
60
 
61
<code>wisdom</code> is the name of the mechanism that FFTW uses to save
62
and restore plans.  Rather than just saving plans, FFTW remembers what
63
it learns about your machine, and becomes wiser and wiser as time
64
passes by.  You can save <code>wisdom</code> for later use.  
65
<h2><A name="whywisdom">
66
Question 4.4.  Why do you use <code>wisdom</code>? I just wanted to save a plan.
67
</A></h2>
68
 
69
<code>wisdom</code> could be implemented with less effort than a general
70
plan-saving mechanism would have required.  In addition,
71
<code>wisdom</code> provides additional benefits.  For example, if you
72
are planning transforms of size 1024, and later you want a transform
73
of size 2048, most of the calculations of the 1024 case can be reused.
74
 
75
<p>
76
In short, <code>wisdom</code> does more things with less effort, and seemed like The Right Thing to do.  <hr>
77
Next: <a href="section5.html" rel=precedes>Known bugs</a>.<br>
78
Back: <a href="section3.html" rev=precedes>Using FFTW</a>.<br>
79
<a href="index.html" rev=subdocument>Return to contents</a>.<p>
80
<address>
81
<A href="http://theory.lcs.mit.edu/~fftw/">Matteo Frigo and Steven G. Johnson</A> / <A href="mailto:fftw@theory.lcs.mit.edu">fftw@theory.lcs.mit.edu</A>
82
- 18 May 1999
83
</address><br>
84
Extracted from FFTW Frequently Asked Questions with Answers,
85
Copyright &copy; 1999 Massachusetts Institute of Technology.
86
</body></html>