FFT有多少FLOPS？ [英] How many FLOPS for FFT?

问题描述

我想知道快速傅里叶变换（FFT）可以执行多少 FLOPS 。

I would like to know how many FLOPS a Fast Fourier Transform (FFT) performs.

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

So, if I have a 1 dimensional array of N float numbers and I would like to calculate the FFT of this set of numbers, how many FLOPS need to be performed?

我知道这取决于所使用的算法，但是那又如何呢？

I know that this depends on the used algorithm, but what about the fastest available?

我还知道FFT的缩放比例约为 N * log（N）但这不能回答我的问题。

I also know that the scaling of a FFT is of the order of N*log(N) but this would not answer my question.

推荐答案

这取决于实现。最快不一定意味着最低 FLOP 或最高 FLOPS 。通常通过利用 HW 体系结构而不是降低 FLOP 来实现速度。有太多的实现，因此您的问题没有实际的代码和体系结构是无法回答的。

That depends on implementation. Fastest does not necessary mean lowest FLOP nor highest FLOPS. The speed is often achieved by exploiting HW architecture rather than lowering FLOP. There are too many implementations out there so your question without actual code and architecture is unanswerable.

我喜欢预先计算的 W 矩阵实现，因为我通常对单个分辨率矩阵多次使用 FFT ，因此每个分辨率只需计算一次 W 即可。这样可以大大减少每个递归层的 FLOP 。

I like precomputed W matrix implementations as I usually use FFT for single resolution matrices many times so no need to compute W more then once per resolution. That can cut down FLOP per recursion layer significantly.

例如 DFFTcc 每个迭代仅使用 +，-，* 个运算具有14个 FLOP 。假设一维FFT 情况为 N = 8 并使用基本数据类型（如果我没有犯任何愚蠢的错误的话）：

For example this DFFTcc has 14 FLOP per iteration using only +,-,* operations. Assuming 1D FFT case N=8 and using basic data-type if I did not make any silly mistake:

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 并不是唯一影响速度的因素。

If you use Real input/output you can even lower that for first/last recursion layer. But simple FLOP count is not enough as some operations are more complicated then others. And also FLOP are not the only thing that affect speed.

现在要获得 FLOPS ，只需测量时间[s] FFT 需要：

Now to get the FLOPS just measure time [s] the FFT takes:

FLOPS = FLOP/time

这篇关于FFT有多少FLOPS？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！