cuda - CUDA fft - クーリー・テューキー、並列処理はどのように利用されていますか?

Question

FFT 実装がどのように機能するか ( Cooley-Tuckey アルゴリズム) を知っており、1D または 2D FFT をすばやく計算するための CUFFT CUDA ライブラリがあることも知っていますが、プロセスで CUDA 並列処理がどのように利用されているか知りたいです。

バタフライ計算と関係ありますか？（各スレッドがデータの一部を共有メモリにロードし、各スレッドが偶数項または奇数項を計算するようなものですか？）

Answer 1

彼らが Cooley-Tuckey アルゴリズムを使用しているとは思えません。なぜなら、そのインデックス順列フェーズが共有メモリ アーキテクチャにとってあまり便利ではないからです。さらに、このアルゴリズムは 2 のべき乗のメモリ ストライドで動作しますが、これもメモリの合体​​には適していません。ほとんどの場合、彼らは Stockham 自己ソート FFT の定式化を使用しています。たとえば、ベイリーのアルゴリズムです。

実装に関しては、あなたの言うとおりです。通常、大きな FFT を複数の小さな FFT に分割し、1 つのスレッド ブロック内に完全に収まるようにします。私の仕事では、128 スレッドのスレッド ブロックごとに 512 ポイントまたは 1024 ポイントの FFT (もちろん完全にアンロールされています) を使用しました。通常、大量のデータ転送が必要になるため、GPU で従来の基数 2 アルゴリズムを使用することはありません。代わりに、基数 8 または基数 16 のアルゴリズムを選択して、各スレッドが一度に 1 つの大きな「バタフライ」を実行するようにします。実装例については、Vasily Volkovページにアクセスするか、この「クラシック」ペーパーを確認することもできます。