algorithm - FFT の FLOPS はいくつですか?

Question

FLOPS高速フーリエ変換 (FFT) が何回実行されるか知りたいです。

では、浮動小数点数の1次元配列がありN、この数値セットの FFT を計算したい場合、何FLOPS回実行する必要がありますか?

これは使用するアルゴリズムに依存することはわかっていますが、利用可能な最速のものはどうでしょうか?

また、FFT のスケーリングが のオーダーであることも知っていますがN*log(N)、これは私の質問には答えません。

Answer 1

それは実装に依存します。最速は必ずしも最小のFLOPや最大のFLOPSを意味するわけではありません。多くの場合、 FLOPを下げるのではなく、HWアーキテクチャを利用することによって速度が達成されます。実装が多すぎるため、実際のコードとアーキテクチャのない質問には答えられません。

私は通常、単一解像度の行列にFFTを何度も使用するため、事前計算Wされた行列の実装が好きなので、解像度ごとに複数回計算する必要はありません。これにより、再帰レイヤーごとのFLOPを大幅に削減できます。W

たとえば、この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

実際の入力/出力を使用する場合は、最初/最後の再帰レイヤーの値をさらに下げることができます。しかし、いくつかの操作は他の操作よりも複雑であるため、単純なFLOPカウントでは十分ではありません。また、速度に影響するのはFLOPだけではありません。

FLOPSを取得するにはtime [s] 、FFTを測定するだけです。

FLOPS = FLOP/time

Answer 2

FFTW ベンチマーク ページでフロップのパフォーマンスを見積もることができます。少し古くなっていますが、最も効果的な FFT 実装の結果が含まれています。

概算では3.0GHz Intel Xeon Core Duoで5000MFlops程度だそうです

Answer 3

「利用可能な最速」はプロセッサに大きく依存するだけでなく、私のテストではまったく異なるアルゴリズムを使用する可能性があります。しかし、ボグシンプルのフロップを数えました非再帰的なインプレース デシメーション イン タイム radix-2 FFT は、長さ 1024 の FFT の古い ACM アルゴリズムの教科書からそのまま取り出し、20480 の fmul と 30720 の fadd を取得しました (これは、事前に計算された回転因子テーブルを使用していました。したがって、超越関数の計算はフロップ カウントに含まれませんでした)。ただし、このコードでは、大量の整数配列インデックス計算、サイン テーブル ルックアップ、およびデータ移動が追加で使用され、おそらく FPU よりもはるかに多くの CPU サイクルが必要であることに注意してください。はるかに大きな FFT では、大量の追加データ キャッシュ ミスやその他のメモリ レイテンシ ペナルティも発生する可能性があります。そのような状況では、メモリ階層のレイテンシ ペナルティを減らす代わりに FLOP を追加することで、コードを高速化することができます。では、YMMV。