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 "The Fastest Fourier Transform in |
||
34 | the West", 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 "FFTW: An Adaptive Software Architecture for the |
||
36 | FFT", 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 "The |
||
55 | Fastest Fourier Transform in the West", 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 © 1999 Massachusetts Institute of Technology. |
||
86 | </body></html> |