c++ - CUDA FFT——二的幂

Question

我正在查看 CUDA SDK 上的 FFT 示例，我想知道：当填充数据的一半是 2 的幂时，为什么 CUFFT 更快？（一半是因为在频域中一半是多余的）

拥有两个大小的力量有什么意义？

Answer 1

我想这就是你的答案。它使用不同的算法

http://forums.nvidia.com/index.php?showtopic=195094

“我一直在研究类似的问题。在 cuFFT 手册中，解释了 cuFFT 使用两种不同的算法来实现 FFT。一种是 Cooley-Tukey 方法，另一种是 Bluestein 算法。当维度具有主要因素时只有 2,3,5 和 7 例如 (675 = 3^3 x 5^5)，那么 675 x 675 的性能要比 674 x 674 或 677 x 677 好得多。这是使用 Cooley-Tukey 方法完成的。如果素数之一是除 2、3、5 或 7 以外的素数，则该数的 FFT 使用 Bluestein 方法实现。Bluestein 方法较慢，并且还存在一些精度损失。

来自手册：http: //developer.download.nvidia.com/compute/cuda/3_1/toolkit/docs/CUFFT_Library_3.1.pdf

CUFFT 库实现了几种 FFT 算法，每种算法都有不同的性能和精度。最佳性能路径对应于满足两个标准的变换大小：

• 适合 CUDA 的共享内存
• 是单因素的幂（例如，二的幂）

由于所选 FFT 算法的数值稳定性，这些变换也是最准确的。对于满足第一个标准但不满足第二个标准的变换大小，CUFFT 使用更通用的混合基数 FFT 算法，该算法通常速度较慢且数值精度较低。因此，如果可能，最好使用 2 或 4 的幂或其他小素数（例如，3、5 或 7）的幂的大小。此外，CUFFT 中的二次方 FFT 算法通过阻塞不满足第一个标准的信号的子变换来最大限度地利用共享内存。

Answer 2

只是为 Ade 的回答添加更多背景知识：

通常，离散傅里叶变换需要大量计算。N 个点的单维 FFT 需要 N*N 次乘法。FFT（快速傅立叶变换）更快，只是因为在 N 是 2 的幂的情况下，可以重写方程，这样您只需要 N * log2 N 次乘法。

在大多数应用程序中，您并不关心样本的确切数量。因此，您选择两个的幂，以获得最佳性能。

三或五的幂也可以，但二的幂是最快的，也是最容易编写的算法，因此多年来一直占主导地位。