Rev 3 | 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> |