On Thu, Apr 19, 2007 at 05:46:49PM -0400, Al Falloon wrote:
For us less knowledgable, what's fftw?
"Fastest Fourier Transform in the West." http://www.fftw.org/
Its cool, they use generative programming: an OCaml program generates "codlets" in C that can be composed and tuned to the specifics of your machine, then compiled into a blazingly fast FFT/DFT library.
But that's only the beginning of the coolness! fftw uses runtime timings to optimize each fourier transform based on the behavior of the computer on which it is being run--its cache, memory speed, CPU, etc. The result being that fftw using portable C can beat out most hand-optimized fftw libraries written in assembly! Steven (one of fftw's two authors) has done some incredible work on optimizations. The most unbelievable (to me) was that by eliminating negative constants from the generated code (using subtraction instead) they sped up the library on a particular architecture by some some significant margin (I think I recall 20%). -- David Roundy
Oleg has some related work http://okmij.org/ftp/Computation/Generative.html#framework "... The papers discuss in detail the generation of a straight-line C, Fortran, etc. code for the power-of-two FFT. The papers show that with the help of Abstract Interpretation we can exactly match the quality of code generated by the well-known system FFTW. The second paper demonstrates that our generated power-of-two FFT code has exactly the same number of floating-point operations as that in codelets of FFTW. The significant difference from FFTW is that we do not do any intensional code analysis ... " I don't know how useful this is. Alistair ***************************************************************** Confidentiality Note: The information contained in this message, and any attachments, may contain confidential and/or privileged material. It is intended solely for the person(s) or entity to which it is addressed. Any review, retransmission, dissemination, or taking of any action in reliance upon this information by persons or entities other than the intended recipient(s) is prohibited. If you received this in error, please contact the sender and delete the material from any computer. *****************************************************************