[Haskell-cafe] Re: fftw bindings

Bayley, Alistair Alistair_Bayley at invescoperpetual.co.uk
Fri Apr 20 05:44:47 EDT 2007

> 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

"... 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.

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.

More information about the Haskell-Cafe mailing list