logo标签列表

CUDA FFT - 二的幂次方

c++cudaconvolution
3

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

拥有2的幂大小的意义何在？

1
将示例链接或显示相关代码可能会有所帮助。 - Chris Pitman
2个回答
8
我认为这是你的答案。它使用了不同的算法。

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

在解决类似问题时，需要注意cuFFT使用两种不同的算法来实现FFT。其中一种是Cooley-Tuckey方法，另一种是Bluestein算法。当维度只有2、3、5和7等质因数时（例如675 = 3 ^ 3 x 5 ^ 5），使用675 x 675比使用674 x 674或677 x 677要好得多，这是通过使用Cooley-Tuckey方法实现的。如果其中一个质因数是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共享内存
  • 是单个因子的幂（例如2的幂）
这些变换也是最准确的，因为所选FFT算法的数值稳定性。对于满足第一个条件但不满足第二个条件的变换，CUFFT使用更通用的混合基数FFT算法，这通常更慢且数值上不太准确。因此，如果可能，最好使用2或4的幂次方或其他小质数（例如3、5或7）的幂次方。此外，CUFFT中的2的幂次方FFT算法通过为不满足第一个条件的信号块化子变换来最大限度地利用共享内存。
3
只是为了给Ade的答案增加一些背景：一般来说，离散傅里叶变换需要进行大量的计算。N点的单维FFT需要进行N*N次乘法。FFT（快速傅里叶变换）之所以更快，是因为在N为2的幂的情况下，可以重写方程，使得你只需要N*log2N次乘法。
在大多数应用中，你并不关心精确的样本数量。所以你选择2的幂，以获得最佳性能。
三次幂或五次幂也可以工作，但2的幂是最快的，并且是最容易编写的算法，因此这些年来已经成为主导。
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接