CUDA FFT - 两个功率

Question

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

有两个大小的功率工作的点是什么？

Answer 1

我认为这是你的答案。它使用不同的算法

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

“我一直在一个类似 问题。在CUFFT手册，它是 解释说CUFFT使用两种 不同的算法实现 的FFT的。一个是Cooley-Tuckey方法和另一种方法是Bluestein 算法。当维数为 的素因子仅为2,3,5和7时，例如 （675 = 3^3 x 5^5），则675 x 675 表现要好得多n说674 x 674或677 x 677.这是通过使用Cooley-Tuckey方法的 完成的。如果其中一个 的主要因素是其他 比2,3,5或7，那么使用Bluestein方法实现该 号码的FFT。 Bluestein方法 较慢，并且还有一些精度损失 。 “

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

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

• 适合CUDA的共享 内存
• 是单个因子 的权力（例如，二的幂）

这些 变换也是最准确 由于 选择FFT算法的数值稳定性。对于符合第一个标准 （但不是第二个）的尺寸的变换 ，CUFFT使用更一般的混合基FFT算法，其中 通常较慢并且在数字上较不准确。因此，如果可能的话，最好使用 两个或四个的幂或其他小的质数（例如三个，五个，或者三个，五个，或者七个）的幂。另外，CUFFT中的幂运算FFT算法通过对不符合第一标准的信号阻塞 子变换来使得共享存储器的最大使用为 。

Answer 2

只是为了多一点背景添加阿德的回答是：

一般来说，离散傅里叶变换是大量的运算。 N个点的单个维数FFT需要N * N次乘法。 FFT（快速傅立叶变换）速度更快，只是因为在N是2的幂的情况下，方程可以被重写，使得只需要N * log 2 N次乘法。

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

三或五的能力也可以工作，但是两个能力是最快的，并且是最简单的算法，所以这已经成为多年来的主导。