cuda - CUDA fft -cooley tukey，如何利用并行性？

Question

我知道 FFT 实现是如何工作的（Cooley-Tukey 算法），并且我知道有一个 CUFFT CUDA 库可以快速计算 1D 或 2D FFT，但我想知道在此过程中如何利用 CUDA 并行性。

它与蝴蝶计算有关吗？（就像每个线程将部分数据加载到共享内存中，然后每个线程计算偶数项或奇数项？）

Answer 1

我不认为他们使用 Cooley-Tukey 算法，因为它的索引置换阶段使得共享内存架构不太方便。此外，该算法适用于内存步长的二次幂，这也不利于内存合并。他们很可能使用 Stockham 自排序 FFT 的一些公式：例如Bailey 算法。

与实现有关的，你是对的，通常将一个大的 FFT 拆分成几个较小的 FFT，它们完全适合一个线程块。在我的工作中，我使用 512 点或 1024 点 FFT（当然完全展开）每个线程块有 128 个线程。通常，由于需要大量数据传输，您不会在 GPU 上使用经典的 radix-2 算法。取而代之的是，选择 radix-8 甚至 radix-16 算法，以便每个线程一次执行一个大“蝴蝶”。例如实现，您还可以访问Vasily Volkov页面，或查看这篇“经典”论文。