c++ - CUDAFFT-2の累乗

Question

CUDA SDKのFFTの例を見ていて、疑問に思っています。パディングされたデータの半分が2の累乗であるのに、なぜCUFFTがはるかに高速なのですか？（周波数領域では半分が冗長であるため、半分）

2つのサイズの力で作業することのポイントは何ですか？

Answer 1

これがあなたの答えだと思います。さまざまなアルゴリズムを使用しています

http://forums.nvidia.com/index.php?showtopic=195094

「私は同様の問題に取り組んでいます。cuFFTマニュアルでは、cuFFTはFFTを実装するために2つの異なるアルゴリズムを使用すると説明されています。1つはCooley-Tuckey法で、もう1つはBluesteinアルゴリズムです。次元に素因数がある場合たった2、3、5、7の場合（675 = 3 ^ 3 x 5 ^ 5）、675 x 675は、たとえば674x674または677x677よりもはるかに優れたパフォーマンスを発揮します。これは、Cooley-Tuckey法を使用して行われます。素因数の1つが2、3、5、または7以外の素数である場合、その数のFFTはBluestein法を使用して実装されます。Bluestein法は低速であり、精度がいくらか低下します。」

マニュアルから： http： //developer.download.nvidia.com/compute/cuda/3_1/toolkit/docs/CUFFT_Library_3.1.pdf

CUFFTライブラリは、それぞれ異なるパフォーマンスと精度を持ついくつかのFFTアルゴリズムを実装しています。最高のパフォーマンスパスは、次の2つの基準を満たす変換サイズに対応します。

• CUDAの共有メモリに収まる
• 単一の要素の累乗です（たとえば、2の累乗）

これらの変換は、選択したFFTアルゴリズムの数値的安定性により、最も正確です。最初の基準を満たしているが2番目の基準を満たしていない変換サイズの場合、CUFFTは、通常は低速で数値の精度が低い、より一般的な混基FFTアルゴリズムを使用します。したがって、可能であれば、2または4の累乗、または他の小さな素数（3、5、または7など）の累乗のサイズを使用するのが最適です。さらに、CUFFTの2乗FFTアルゴリズムは、最初の基準を満たさない信号のサブ変換をブロックすることにより、共有メモリを最大限に活用します。

Answer 2

Adeの答えにもう少し背景を追加するだけです：

一般に、離散フーリエ変換は多くの計算です。Nポイントの単一次元FFTは、N*Nの乗算を取ります。FFT（高速フーリエ変換）は、Nが2の累乗である場合にのみ、N *log2Nの乗算のみが必要になるように方程式を書き直すことができるために高速になります。

ほとんどのアプリケーションでは、サンプルの正確な数は気にしません。したがって、最高のパフォーマンスを得るには、2の累乗を選択します。

3の累乗または5の累乗も機能しますが、2の累乗が最も速く、作成するのが最も簡単なアルゴリズムであるため、これは長年にわたって支配的になっています。