我想知道FLOPS快速傅里叶变换 (FFT) 执行了多少次。
所以，如果我有一个浮点数的1维数组，N并且我想计算这组数字的 FFT，FLOPS需要执行多少？
我知道这取决于使用的算法，但最快的可用算法呢？
我也知道 FFT 的缩放是顺序的，N*log(N)但这不能回答我的问题。
问问题
4583 次
4 回答
3
这取决于实施。最快的不一定意味着最低的FLOP或最高的FLOPS。速度通常是通过利用硬件架构而不是降低FLOP来实现的。那里有太多的实现，所以没有实际代码和架构的问题是无法回答的。
我喜欢预先计算W的矩阵实现，因为我通常多次对单分辨率矩阵使用FFTW ，因此每个分辨率不需要计算超过一次。这可以显着减少每个递归层的FLOP 。
例如，这个DFFTcc每次迭代仅使用操作有 14次FLOP+,-,*。如果我没有犯任何愚蠢的错误，假设1D FFT案例并使用基本数据类型：N=8
FLOP = 8*14 + (4+4)*14 +(2+2+2+2+2)*14 +(1+1+1+1+1+1+1+1)*2 = 14*N*log2(N) + 2*N = 352
如果您使用 Real 输入/输出，您甚至可以降低第一个/最后一个递归层的值。但是简单的FLOP计数是不够的，因为某些操作比其他操作更复杂。FLOP也不是唯一影响速度的因素。
现在要获得FLOPS，只需测量FFTtime [s]所需 的时间：
FLOPS = FLOP/time
于 2016-10-14T08:21:38.337 回答
1
正如 Spektre 所强调的那样，实际FLOPS（每秒浮点操作数）取决于特定的硬件和实现，而更高的FLOP（浮点操作）算法可能对应于更低的FLOPS实现，因为有了这样的实现，您可以更有效地利用硬件。
如果要计算时间抽取基数2方法的浮点运算次数，可以参考下图：
让N要变换的序列的长度。有多个log2N阶段，每个阶段都包含N/2蝴蝶。然后让我们考虑通用蝴蝶：
让我们将通用蝴蝶的输出重写为
E(i + 1) = E(i) + W * O(i)
O(i + 1) = E(i) - W * O(i)
因此，蝴蝶涉及一个复数乘法和两个复数加法。在用实部和虚部重写上述方程时，我们有
real(E(i + 1)) = real(E(i)) + (real(W) * real(O(i)) - imag(W) * imag(O(i)))
imag(E(i + 1)) = imag(E(i)) + (real(W) * imag(O(i)) + imag(W) * real(O(i)))
real(O(i + 1)) = real(O(i)) - (real(W) * real(O(i)) - imag(W) * imag(O(i)))
imag(O(i + 1)) = imag(O(i)) - (real(W) * imag(O(i)) + imag(W) * real(O(i)))
因此，我们有
4 次乘法
real(W) * real(O(i)),
imag(W) * imag(O(i)),
real(W) * imag(O(i)),
imag(W) * real(O(i)).
6个总和
real(W) * real(O(i)) – imag(W) * imag(O(i)) (1)
real(W) * imag(O(i)) + imag(W) * real(O(i)) (2)
real(E(i)) + eqn.1
imag(E(i)) + eqn.2
real(E(i)) – eqn.1
imag(E(i)) – eqn.2
因此，时间抽取基数2方法的运算次数为
2N * log2(N) multiplications
3N * log2(N) additions
如果乘法的排列方式不同，这些运算计数可能会发生变化，请参阅仅使用三个乘法的复数乘积。
相同的结果适用于频率基数抽取2的情况，见图
于 2017-02-15T22:18:33.363 回答
0
“可用的最快”不仅非常依赖于处理器，而且可能使用我的测试完全不同的算法。但我把失败数算得一塌糊涂非递归就地抽取时间基数 2 FFT 取自旧 ACM 算法教科书，FFT 长度为 1024，得到 20480 fmuls 和 30720 fadds（这是使用预先计算的旋转因子表，因此超越函数计算不包括在翻牌计数中）。但请注意，此代码还使用了大量整数数组索引计算、正弦表查找和数据移动，这可能比 FPU 占用更多的 CPU 周期。更大的 FFT 可能还会导致大量额外的数据缓存未命中和其他内存延迟损失。在这种情况下，可以通过添加更多 FLOP 来加快代码速度，以换取减少内存层次延迟损失。所以，YMMV。
于 2016-10-15T01:12:15.627 回答
0
您可以在FFTW 基准页面上估计 flops-performance 。稍微过时，但包含最有效的 FFT 实现的结果。
对于 3.0 GHz Intel Xeon Core Duo，粗略估计约为 5000 MFlops
于 2016-10-14T08:00:44.337 回答