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

Question

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

它与蝶形计算有关吗？(类似于每个线程将部分数据加载到共享内存中，然后每个线程计算一个偶数项或奇数项？)

Answer 1

我不认为他们使用Cooley-Tuckey算法，因为它的索引排列阶段使其在共享内存体系结构中不是很方便。此外，该算法适用于2的幂内存步长，这也不利于内存合并。最有可能的是他们使用了一些斯托克汉姆自排序快速傅立叶变换的公式:例如Bailey's algorithm。

关于实现的问题，你是对的，通常人们会将一个大的FFT分成几个较小的FFT，它们完全适合一个线程块。在my work中，我使用了512或1024点的FFT(当然是完全展开的)，每个线程块有128个线程。通常，由于需要进行大量数据传输，因此不能在GPU上使用经典的基数-2算法。取而代之的是，人们选择基数-8甚至基数-16算法，以便每个线程一次执行一个大的“蝶形”。例如实现，你也可以访问Vasily Volkov页面，或者查看this的“经典”论文。