FFT有多少FLOPS？

Question

我想知道一次快速傅立叶变换(FFT)执行了多少次FLOPS。

因此，如果我有一个1维数组的N浮点数，我想要计算这组数字的FLOPS，需要执行多少次？

我知道这取决于使用的算法，但是最快的算法呢？

我也知道快速傅立叶变换的缩放是N*log(N)的量级，但这不能回答我的问题。

Answer 1

这取决于实现情况。最快并不意味着最低的FLOP或最高的FLOPS。这种速度通常是通过利用硬件架构而不是降低触发器来实现的。有太多的实现，所以你的问题没有实际的代码和架构是无法回答的。

我喜欢预先计算的快速傅立叶变换矩阵实现，因为我通常对单个分辨率矩阵使用 W 多次，因此不需要针对每个分辨率计算一次以上的W。这可以显著减少每个递归层的翻转。

例如，这个DFFTcc在每个迭代中有14个触发器，仅使用+,-,*操作。假设使用1DFFT case 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 input/output，你甚至可以降低first/last递归层的输入输出。但简单的触发器计数是不够的，因为一些操作比其他操作更复杂。而且触发器也不是影响速度的唯一因素。

现在，要获得FLOPS，只需测量 time [s] FFT所采用的：

FLOPS = FLOP/time

Answer 2

正如Spektre所强调的，实际的FLOPS (每秒浮点OPerations )取决于特定的硬件和实现，较高的FLOP (浮点OPeration)算法可能对应于较低的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 sums

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

如果乘法的排列不同，这些运算计数可能会改变，请参见Complex numbers product using only three multiplications。

同样的结果也适用于以频率基数2进行抽取的情况，如图所示

​

​

Answer 3

您可以在FFTW benchmark page上估计flops的性能。略显过时，但包含最有效的FFT实现的结果。

粗略估计3.0 GHz英特尔至强酷睿双核处理器的MFlops约为5000