CUDA FFT - 两个幂

Question

我正在研究CUDA SDK上的FFT示例,我想知道:当填充数据的一半是2的幂时,为什么CUFFT要快得多？(因为频域中的一半是多余的)

拥有两种尺寸的力量有什么意义？

Answer 1

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

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

"我一直在研究类似的问题.在cuFFT手册中,解释说cuFFT使用两种不同的算法来实现FFT.一种是Cooley-Tuckey方法,另一种是Bluestein算法.当维度具有素数因子时只有2,3,5和7例如(675 = 3 ^ 3×5 ^ 5),那么675×675比674×674或677×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的共享内存
• 是单因素的幂(例如,2的幂)

由于所选FFT算法的数值稳定性,这些变换也是最准确的.对于满足第一个标准而非第二个标准的变换大小,CUFFT使用更通用的混合基FFT算法,该算法通常较慢且数值较少.因此,如果可能的话,最好使用2或4次幂的大小,或其他小质数(例如,3个,5个或7个)的大小.此外,CUFFT中的二次幂FFT算法通过阻止不满足第一标准的信号的子变换来最大限度地利用共享存储器.