Good Heuristic Point Where Sending FFT to GPU is Computationally Worth It?

Question

This is a rather simple question, but I haven't found much posted within the last 5 years or so regarding a good rule of thumb for computing an FFT on the GPU vs the CPU. I know that most of the overhead of GPU-calculated FFTs is that you have to first write the data to a buffer and then transmit that data to the GPU, from the CPU, in order to compute the transform.

This implies naturally that GPU calculating of the FFT is more suited for larger FFT computations where the number of writes to the GPU is relatively small compared to the number of calculations performed by the GPU. But the issue then becomes knowing at what point that the FFT performs better on the CPU vs GPU. The best I've found is on the lines of "when you're computing larger FFTs", but that's a little relativistic to be particularly meaningful guideline for practitioners, especially considering that GPU technology has been accelerating so rapidly in the past few years.

I'm just looking for a more concrete estimate of at what point it becomes efficient to compute the transform on the GPU vs CPU (perhaps there's a benchmark somewhere out there?). Thanks in advance for any help you can provide.

Answer 1

I'm afraid there won't ever be a rule of thumb!

The reasons are manifold, mainly, that both the systems you're considering and the problems you're trying to solve vary across a very large range.

Problem-based aspects

You say you want to do an FFT – but that's always but half of what you actually want to do!

Need the FFT converted to it's abs², then mapped to colors, then displayed on a screen? Do it in the GPU, it's right where it belongs; fosphor does that, at an easy 200MS/s on capable PC/GPU combinations:

In that case, the size of the FFT doesn't even matter. Your data is going to be processed further on by the GPU, so do the FFT there.

On the other hand, you might want to do something that depends on a lot of checks on individual elements in the FFT, in the CPU? Possibly just one FFT, and then not many more?

In that case, your theoretical throughput doesn't help you at all. Just waiting for the data to get out of your CPU cache, back into coherent memory, so it can be DMA'ed to the GPU, where you then initiate an FFT (possibly wasting an interrupt/context switch on the way), just to wait till it's done, the GPU DMA'ed the data back to your main memory and you got it into your CPU's cache won't pay, even for medium sized FFTs.

So: this whole "high-latency math accelerator business" really only ever pays off if you can do something sensible while you wait. If you can't, there's a huge latency penalty.

System-based aspects

Ok, not going into too much detail here, but:

• DSP systems are either CPU or Memory-bandwidth limited
• If your GPU operation helps with CPU limititation, but puts additional data movement load on the memory interface, while in fact the rest of your system is memory-bandwidth limited, you're hurting yourself.
• Same applies the other way around: Maybe your algorithm (the FFT in your specific size of interest) is CPU limited, but your GPU acceleration leads to additional interrupts
• What is an FFT size that your CPU can do very well? That is probably defined by the sizes of it's L1 and L2 caches. A Xeon number-crunching CPU will have dozens of Megabytes of those, whereas an ARM running in a Jetson NVidia SoC will not.
• What is the FFT size your graphics card is good at? There's a humongous difference in numbers of parallel threads, their flexibility and memory bandwidth across cards.
• What is a metric for "good", at all? Just some strange ratio of throughput and latency, but maybe also energy and leaving the right kind of ressources free for other work?
• What is your CPU<->main memory interface? Is it a quad-channel DDR4 interface running at nearly 2GHz, or is it single-channel DDR?
• What is your GPU<->GPU memory interface?
• What is your GPU<->main memory interface?
• How well does your CPU<->GPU communication work for your specific use case?
• Is there a high load on e.g. the PCIe bus, for example, because the same PCIe switch has to handle the data flowing in and out of your high-rate system (eg. storage, but more likely, 10 Gigabit ethernet or video data)?

So, the answer probably won't be satisfactory, but it really is:

Somewhere above 64 bins, somewhere below 2²⁰ bins, for a single-precision FFT. It depends.