halide/Halide — pull request #363 by dsharletg (2014-07-07 23:54:20+00:00)
Title: FFT test

This is a test that implements an FFT in Halide (without extern functions). This has been mentioned/asked for a few times recently on the mailing list and elsewhere (@zvookin, @jrk). Thanks to Andrew for lots of help on this, especially the schedule! Here's an overview of what it does right now:

- The test performs a convolution via multiplication in the frequency domain of a simple box filter, it does this with both a complex transform and a real transform.
- Reports performance per the FFTW benchmarking methodology (http://www.fftw.org/speed/method.html)
- Current performance is ~75% of FFTW on my machine for complex transforms, ~50% of FFTW on my machine for real transforms.

This still needs a bit of work to get it up to par on performance with FFTW and some other improvements, but I think it is an interesting bit of code as is. I'm also stuck on some of the scheduling/optimization. If you are interested, any thoughts on how to schedule this better would be much appreciated. I think it would be pretty cool for Halide to beat FFTW, and I think we are close :) Current performance is within sniffing distance, and that's only when using a radix 2 transform! Higher radix transforms should be much more efficient, especially radix 4.