FFT with fftw3 about cimg

[dtschump]

To me, the main advantage of using fftw3 is mostly that you can work with any image size you want. You are not forced to deal with images with a 2^N size along all the axes. This is really nice, and the 'CImg-only' implementation of the FFTW does not allow that unfortunately.
Also, the CImg implementation does not (yet) use any of the OpenMP feature, so it compute the FFT with a single thread. That is something I may change in the future anyway.
As the FFTW3 implementation is probably a lot more complex than mine, I'm not surprised the timing are a bit slower for small images. If I add the OpenMP directive to the current CImg-only implementation of the FFT, no doubts we'll be even faster.

[dtschump]

Well, I've done some quick tests, including OpenMP directives to the CImg-native implementation of the FFTW. We do not gain much except for quite big images (a few ms for images >6000x6000).
I'm not sure it's worth the overhead.

[uxhub]

I agree for free prime size of arrays. But, I read on fftw webpage "FFTW," which stands for the somewhat whimsical title of "Fastest Fourier Transform in the West." So I thought FFTW was the fastest implementation (and so parallel) I can find (on cpu).
If a single thread CImg-only implementation is quicker for 512^3 3D-image... I don't see the point.

Strange that you can't gain much time with open directives in cimg implementation since FFT is fully parallelizable, no ? (I think about the cufft performance, the cuda fft library for gpu).

[dtschump]

Yes, this is fully parallelizable, but the operations involved in the XYZ loops are so simple that parallelizing the loops using OpenMP is only valid for very large dimensions, otherwise the cost of creating, running the threads and waiting for them is higher than the gain you get.
That's the point with most parallelized operations using OpenMP. In CImg, we have some conditions on the minimal size of the image data before OpenMP is actually used.

[uxhub]

Yes I understand. Could I test your openmp directives for cimg-fft for higher 3-dimensions data ?
fftw takes the advantage over the cimg-fft at 1024x1024x1024, so your new directives may be relevant at this point.
Well, I'm curious to know how gpu implementation could be more efficient in this case since gpu card can't load much memory and so process small blocks....

[dtschump]

The difference between OpenMP and GPU parallelization is that with OpenMP you often parallelize outer loops that run for many iterations, while I see GPU code more as parallelization of 'inner' operations. But I may be wrong, I'm not a GPU expert.

[dtschump]

Also, to force OpenMP to be used in the FFTW, just add the directive :

#pragma omp parallel for collapse(2)

in file CImg.h, function static void CImg<T>::FFT(..) just before the loops

 cimg_forYZC(real,y,z,c) { ... } (for the x-axis, and so one for the other axes).

[uxhub]

Ok I will have a try.

But, I don't understand why you want to put openmp directives in the FFTW call in cimg.h code since FFTW procedure are already parallelized.
Don't you want to parallelize native cimg-FFT implementation instead ?

edit: as you said, no gain and even worth performance with openmp directives in fftw call
edit2: fftw provides n-dimensional transform call (http://www.fftw.org/parallel/parallel-fftw.html), when cimg calls 1d transforms. Is there performance gain to expect with the n-dimensional functions ?

[dtschump]

Using OpenMP in FFTW-based implementation is useless of course, I didn't say you should try this :)
OpenMP directives should be added to the CImg-native part only to have sense.
For your edit2 : I've no idea if this the 2d transform is faster than calling multiple 1d transform in fftw.

[uxhub]

Sorry I miss read. And I made an huge error this morning by measuring cpu time instead of real time...

So I compare here times for cimg only, cimg-openmp and cimg-fftw, and the results make sense this time. However, it could be nice to keep the openmp directives in cimg implementation... ;)

Thank you for your attention

CIMG ONLY
[64x64x64]      total: 0.059459
[128x128x128] total: 0.343971
[256x256x256] total: 7.162
[512x512x512] total: 74.3901
[1024x1024x1024] total: 886.168

CIMG + OPENMP
[64x64x64] total: 0.144665
[128x128x128] total: 0.147838
[256x256x256] total: 3.05347
[512x512x512] total: 23.5586
[1024x1024x1024] total: 236.439

CIMG + FFTW
[64x64x64] total: 0.0278749
[128x128x128] total: 0.231559
[256x256x256] total: 2.73878
[512x512x512] total: 21.415
[1024x1024x1024] total: 152.021