How to custom optimize cuFFT for a mini batch of multi-channel images?

Question

I am reading a paper, which has the following paragraph.

Current GPU implementations of the FFT such as cuFFT are designed to parallelize over individual transforms. This can be useful for computing a limited number of transforms on large inputs, but is not suitable for our task since we are performing many FFTs over relatively small inputs. Therefore, we developed a custom CUDA implementation of the Cooley-Tukey FFT algorithm which enabled us to parallelize over feature maps, minibatches and within each 2-D transform. Note that 2-D FFTs lend themselves naturally to parallelization since they can be decomposed into two sets of 1-D FFTs (one over rows and the other over columns), and each set can be done in parallel.

Unfortunately the paper doesn't bring further detail on this. As I could not get a feedback from the authors, I am asking the community,

How this implementation differs from the standard cuFFT implementation of the FFT?

The only thing that comes to my mind is that the standard cuFFT for images, when applied to a mini-batch, performs individual 2D FFT. Then, the only re-computation that could possible be avoided when considering a mini-batch of multi-channel images would be the re-calculation of the Twiddle factor $W_{N}^{k}$. Would there be another way to speed up a 2D FFT for this scenario?

Answer 1

I don't know if the paper is right, but what it claims is pretty clearly stated there:

• cuFFT uses many GPU processors in parallel to calculate one large FFT fast.
  It splits a complex problem in many smaller problems and solves them in parallel, and then combines the results to the solution to the complex problem.
• Their implementation goes and calculates many small transforms in parallel.
  It takes many small problems and solves them in parallel.

To be honest, that in isolation is not that cool, considering all they had to do is take a single-threaded FFT and tell CUDA to execute it on different data in parallel.

That trivial data parallelism is exactly what CUDA does for you. There were implementations of that even before Nvidia had a stable cuFFT out there. In fact, multiple parallel FFTs done on a GPU have been around longer than CUDA – it's the obvious algorithm to implement on a manycore thing like a GPU.

---

I doubt the authors are fully right in their claim that cuFFT can't calculate FFTs in parallel; cuFFT especially has a function cufftPlanMany which is used to calculate many FFTs at once.

To cite the cuFFT documentation:

where batch denotes the number of transforms that will be executed in parallel,

so, either that documentation is wrong, or the authors simply implemented something that was already built-in to cuFFT but which they ignored (maybe for good reason). Maybe that functionality wasn't there in 2013 (but I'm not willing to bet on that).