GPGPU： '不規則な'変換を処理する効果的な方法は？定期的な変換で

Question

は、すべてのGPU-スレッドが例えば同じ時間複雑O.を有することが期待される：変換不規則で

for i=0 to 10: c[i] = a[i]*b[i] 

を、そうではない。ようなアレイをもたらす

for i=0 to len(arr) 
    for k=0 to random()%100 
     arr[i] += 1 

[2,50,32,77,1,5,66、...]各要素は、おおよその計算コストを示します。

GPGPUプログラミングは、「要素別の追加」、「行列乗算」、「畳み込み」などの通常の変換によく適しています。 しかし、不規則な変換はどうですか？ GPUスレッドを「うまく」配布する方法は？どのように '良い'カーネルを設計するのですか？共通の方法論はありますか？

Answer 1

ハードウェアがVegaでもVoltaでもない場合（どちらも項目ごとにほぼ独立したコマンド実行が可能です）、疑わしい作業をまとめてグループ化することをお勧めします。例えば、同じグループ内のすべてのアイテムは、ほぼ同じ量の作業ネイバーワークアイテムを有し、1次元（スキャンライン）ワークアイテムよりもバランスが取れているので、マンデルブロ画像ジェネレータ（アイテムごとに異なる作業量）世代（グループごとに異なる結果）。最後の繰り返しに応じて要素を並べ替えるか、空間グループを使用する必要があります。

最悪の場合、各計算ユニット（最大8,64,128,192コア）あたりの最大サイクル数が結果として決定され、より多くの計算単位でより高速になります。しかし、他のすべての作業項目は、それらの最大サイクルの後ろに隠され、CPUよりも効率的です。