CUDA FFT - 2的幂

我正在研究CUDA SDK上的FFT示例,我想知道:当填充数据的一半是2的幂时,为什么CUFFT要快得多? (因为频域中的一半是多余的) 拥有两种尺寸的力量有什么意义?     
已邀请:
我想这是你的答案。它使用不同的算法 http://forums.nvidia.com/index.php?showtopic=195094   “我一直在研究类似的问题   问题。在cuFFT手册中,它是   解释说cuFFT使用两个   不同的算法实现   FFT。一个是Cooley-Tuckey   方法和另一个是Bluestein   算法。当尺寸有   主要因素只有2,3,5和7,例如   (675 = 3 ^ 3×5 ^ 5),然后是675 x 675   表现比说674好得多   x 674或677 x 677.这是使用完成的   Cooley-Tuckey方法。如果其中之一   主要因素是其他主要因素   比2,3,5或7,那么FFT   数字是使用。实现的   布鲁斯坦方法。布鲁斯坦方法   比较慢,也有一些   精确损失。 “ 从手册:http://developer.download.nvidia.com/compute/cuda/3_1/toolkit/docs/CUFFT_Library_3.1.pdf   CUFFT库实现了几个   FFT算法,每个都有不同的   性能和准确性。最好的   性能路径对应   变换大小满足两个   标准:         适合CUDA的共享   记忆   是单一因素的力量   (例如,两个权力)         这些   变换也是最准确的   由于数字的稳定性   选择FFT算法。为了变换   符合第一个标准的尺寸   但不是第二,CUFFT使用更多   一般混合基FFT算法   通常较慢且数字较少   准确。因此,如果可能的话   最好使用权力的大小   两个或四个,或其他小的权力   素数(例如,三,五或   七)。另外,二者的力量   CUFFT中的FFT算法最大化   通过阻止使用共享内存   不转换信号的子转换   符合第一个标准。     
只是为Ade的回答添加更多背景: 通常,离散傅里叶变换是很多计算。 N点的单维度FFT采用N * N次乘法。 FFT(快速傅立叶变换)更快,因为在N为2的幂的情况下,可以重写等式,使得仅需要N * log2 N次乘法。 在大多数应用程序中,您不关心样本的确切数量。因此,您选择2的幂,以获得最佳性能。 三个或五个的功率也可以工作,但是两个的功率是最快的,并且是最容易编写的算法,因此多年来已成为主导。     

要回复问题请先登录注册