Consider filtering square n*n images by square,separable m*m filters. What are the general computation time for the following approaches 1) FFT 2) by 2-D convolution 3) by two 1-D convolutions. (Capital letters to indicate implementation-dependent constants)

p.s what does it mean for a 2-D filter to be separable? what are the different and specific procedure of these three approaches?


That's a fairly broad brushed question. By 'general computation time' I presume that you mean how many floating point operations are performed by each of the three methods? Well, there's standard theoretical answers to that question which I don't know off the top of my head.

I don't think that matters because in my experience taking that theoretical number of operations and applying that to the theoretical GFLOPs score of the CPU in question won't get anywhere close to the real world runtime. The runtime of any particular algorithm depends on so many factors like CPU clock frequency, cache sizes, data sizes, and the cleverness of the library routine itself.

The library routine you use makes a huge difference. Some associates of mine once did some benchmarking on 1D FFTs on PowerPC with Altivec and found that the best (a proprietary library) was 30% faster than the next best, which was the open source FFTW. In our situation that was hugely significant. When you're building a system with tight real time and size requirements you gladly pay for a library that allows you to throw away one third of your hardware.

In general I've always ended up doing complex FFTs rather than convolution, they always seem to be a bit faster. Complex FFTs always seem a bit quicker than the real equivalent - seems to be to do with the data movements matching the cache behaviours a bit better. Of course that depends on pre computing the twiddle factors for the FFT beforehand.

In general I've found for big, cache busting data sets that clock speed doesn't matter a damn but memory speed does (so Intel i7 is really good for that).

For smaller data sets PowerPC has until very recently been king (a decent library + Altivec is way better than Intel's library + SSE, overcoming the clock rate difference). That was because Altivec's architecture allows you to do so many parts of the FFT all at once as well as featuring a fused multiply-add instruction.

However Intel have stepped up finally and given X86 a fused multiply-add, and AVX is 256 bits wide. So I suspect that Intel now win on the small scale too, what with Freescale being tardy in getting the latest PowerPC out the door (it looked good on paper, just for the moment).


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy