CUDA：還元または原子操作ですか？

Question

私は与えられた行列の最大値を計算することを含むCUDAカーネルを書いています。私は可能性を評価しています。

すべてのスレッドに共有メモリ内の値を格納させ、その後に削減アルゴリズムを使用して最大値を決定するようにします（pro：minimum divergence cons：共有メモリは2.0デバイスで48KBに制限されています） ）

読み込み操作と書き込み操作の両方があるため、アトミック操作を使用できませんでした。スレッドをsynchthreadsで同期できませんでした。

他のアイデアがあなたの心に浮かんでいますか？

Answer 1

これは、各ブロック内のCUDA

の削減を実行するための通常の方法で、

1）各スレッドのための共有メモリで実行されている換算値を保ちます。したがって、各スレッドは、グローバルメモリからの値をn（私は個人的には16と32の間の値）で読み込み、これらの値を更新します。

2）ブロック内で削減アルゴリズムを実行して、

この方法では、（スレッド数）* sizeof（datatye）バイト以上の共有メモリは必要ありません。

各ブロックは値が小さくなるため、最終値を取得するには2回目の削減パスを実行する必要があります。

たとえば、1ブロックあたり256スレッドを起動し、スレッドごとに16個の値を読み込んでいる場合は、ブロックあたり（256 * 16 = 4096）の要素を減らすことができます。

100万個の要素が与えられているので、最初のパスで250ブロック、2ブロック目で1ブロックだけを起動する必要があります。

この設定の要素数>（4096）^ 2の場合は、おそらく3回目のパスが必要です。

グローバルメモリの読み取りが合体するように注意する必要があります。グローバルメモリ書き込みを結合することはできませんが、これは実行する必要がある1つのパフォーマンスヒットです。

Answer 2

NVIDIAには縮小を行うCUDAデモがあります：hereです。デザインの背後にある動機を説明する白書があります。

Answer 3

また、CUDA 4.0の一部であるCUDA Thrust、またはhereの削減ルーチンを使用することもできます。

このライブラリは、nVidiaのエンジニアによって作成され、手作業で最適化されたコードと比較して優れています。私はグリッド/ブロックサイズのオートチューニングもあると思います。

生のデバイスポインタをラップすることで、自分のカーネルと簡単にインターフェイスすることができます。

これは厳密には統合の観点からのものです。理論については、tkerwinの答えを参照してください。

Answer 4

atomicAddファンクションも使用できますが、前述のアプローチよりもはるかに効率が悪いです。http://supercomputingblog.com/cuda/cuda-tutorial-4-atomic-operations/

Answer 5

私が見つけたthis documentは、CUDAでの並列削減の基本を学ぶのに非常に便利です。それは古くからのものなので、パフォーマンスをさらに向上させるための追加のトリックが必要です。

Answer 6

K20またはTitanをお持ちの場合は、動的並列処理をお勧めします。単一スレッドカーネルをランチすると＃ワーカーのカーネルスレッドがデータを生成し、＃item/first-round-reduction-factorスレッド結果が出るまで昼食をとってください。

Answer 7

実際に、あなたが記述した問題は、実際に行列に関する問題ではありません。入力データの2次元図は重要ではありません（行列データがメモリ内で連続してレイアウトされていると仮定します）。これは一連の値を減らしたものであり、すべての行列要素がメモリ内のどのような順序で表示されています。

行列表現がメモリ内で連続していると仮定すると、単純な縮小を行いたいだけです。そして、最近利用可能な最良の実装は、私が知る限り、nVIDIAのDuane Merillによる優れたlibcubです。 Hereは、デバイス全体の最大計算機能に関するドキュメントです。

ただし、行列が小さい場合を除き、ほとんどの計算では単にデータを読み取ってスレッド固有の最大値を更新するスレッドに過ぎないことに注意してください。スレッドが大規模な行列（またはむしろ大きなストライドスワス）の読み込みを完了したときにのみ、ブロックのレベルを下げるために、通常は共有メモリにローカル最大値を書き込みます。また、アトミックに関しては、おそらく多くの数のマトリックス要素の読み（すべてではないにしても何万という場合でも）のたびにatomicMax()コールを呼び出すことになります。