0
$\begingroup$

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?

$\endgroup$
1
$\begingroup$

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

$\endgroup$
  • $\begingroup$ What about avoiding the recalculation of the Twiddle factor $W^k_N$ for these parallels FFT? Would this be something that cufftPlanMany handles? $\endgroup$ – Eduardo Reis Jan 18 at 18:23
  • 1
    $\begingroup$ these are typically not calculated on the fly, so there's no runtime overhead; generally, in GPUs, it's often not faster to have something centralized that all threads access compared to having a little more data locally that you might need to compute on the fly. $\endgroup$ – Marcus Müller Jan 18 at 18:25
  • $\begingroup$ I implemented their methodology, and the convolution on the frequency domain was slower than the one on spatial domain, I assumed it was due to the FFT of tensorflow. $\endgroup$ – Eduardo Reis Jan 18 at 18:25
  • 1
    $\begingroup$ there's many reasons why that might have been the case. Generally, I wouldn't blame tensorflow unless I have an in-depth analysis of where time is spent. $\endgroup$ – Marcus Müller Jan 18 at 18:27
  • $\begingroup$ Thanks for the clarification above regarding the Twiddle factor. I think that is worthy to be added to the answer. $\endgroup$ – Eduardo Reis Jan 18 at 18:28

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.