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

Question

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

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

Answer 1

我认为他们没有使用 Cooley-Tuckey 算法，因为它的索引排列阶段使其对于共享内存架构来说不太方便。此外，该算法适用于两倍的内存步幅，这也不利于内存合并。他们很可能使用 Stockham 自排序 FFT 的某种公式:例如 Bailey's algorithm .

关于实现，你是对的，通常会将一个大的 FFT 分成几个较小的 FFT，这些较小的 FFT 完全适合一个线程 block 。在 my work ，我对每个具有 128 个线程的线程 block 使用了 512 点或 1024 点 FFT(当然是完全展开的)。通常，由于需要大量数据传输，您不会在 GPU 上使用经典的 radix-2 算法。相反，我们选择 radix-8 甚至 radix-16 算法，以便每个线程一次执行一只大“蝴蝶”。如需示例实现，您还可以访问Vasily Volkov页面，或查看this “经典”论文。