9

次の問題があります: GPU のツリー構造に基づいて、値の包括的スキャン (例:プレフィックスの合計) を計算する必要があります。これらのスキャンは、ルート ノード (トップダウン) またはリーフ ノード (ボトムアップ) から行われます。単純なチェーンの場合は簡単に処理できますが、ツリー構造のため並列化を効率的に実装するのはかなり困難です。

ツリーの例

たとえば、トップダウン インクルーシブ スキャンの後、(12)が保持(0)[op](6)[op](7)[op](8)[op](11)[op](12)され、ボトムアップ インクルーシブ スキャンの場合、(8)が保持されます(8)[op](9)[op](10)[op](11)[op](12)。ここ[op]で、 は指定されたバイナリ演算子 (行列の加算、乗算など) です。

また、次の点も考慮する必要があります。

  • 典型的なシナリオでは、異なるブランチの長さは長すぎないように (~10)、5 から 10 のブランチのようにする必要があります。そのため、これはブロック内で実行され、作業はスレッド間で分割されます。異なるブロックは、ノードの異なる値を処理するだけです。これは占有率に関して明らかに最適ではありませんが、これは後で取り組む問題に対する制約です。今のところ、命令レベルの並列処理に依存します。
  • グラフの構造は変更できない (実際のシステムを記述する) ため、バランスを取ることはできません (または(6)、新しいルートとして使用するなど、ツリーのルートを変更することによってのみ)。それにもかかわらず、典型的な木はバランスが崩れすぎてはいけません。
  • 私は現在、GPGPU に CUDA を使用しているため、この問題を解決できる CUDA 対応のテンプレート ライブラリを受け入れることができます。
  • ノード データは既にグローバル メモリにあり、結果は他の CUDA カーネルによって使用されるため、大きなボトルネックにならないようにこれを達成することが目的です。
  • 「サイクル」はありません。つまり、ブランチはツリーの下にマージできません。
  • ツリーの構造は固定され、初期化フェーズで設定されます。
  • 単一の二項演算は非常にコストがかかる場合があります (たとえば、多項式行列の乗算、つまり、各要素が特定の次数の多項式である)。

この場合、この問題を解決するための「最適な」データ構造 (ツリー構造の場合) と最適なアルゴリズム (包括的なスキャン/プレフィックスの合計の場合) は何でしょうか?

4

4 に答える 4

3

次の理由により、並列プレフィックススキャンはあなたのケースには適していないと思います。

並列プレフィックス スキャン アルゴリズムは の合計数を増やします。プレフィックス合計[op]のリンクでは、16 入力の並列プレフィックス スキャンには 26 が必要ですが、順次バージョンでは 15 しか必要ありません。並列アルゴリズムのパフォーマンスが向上するのは、十分なハードウェア リソースがあるという前提に基づいています。複数を並行して実行する。[op][op]

[op]並列プレフィックス スキャンを試す前に、コストを評価できます。

一方、ツリーのサイズは小さいので、ツリーを単純に 4 (リーフ ノードの数) の独立した単純なチェーンと見なし、カーネルの同時実行を使用して、これら 4 つのプレフィックス スキャン カーネルのパフォーマンスを向上させることができると思います。

0-1-2-3
0-4-5
0-6-7-8-9-10
0-6-7-8-11-12
于 2013-10-03T16:28:41.860 に答える
3

おそらく頭の悪いアイデアですが、2D マトリックスを取得するような方法で、値が 0 のノードをツリーに挿入すると想像してください。たとえば、この例では、5ノードの下に 3 つのゼロ値ノードがあります。次に、1 つのスレッドを使用して、マトリックスの各レベルを水平に移動します。トップダウンのプレフィックスの合計については、ツリーがその場所で持つことができる分岐の最大数によって各下位スレッドが遅延するように、スレッドをオフセットします。したがって、マトリックス上を走る斜めのエッジを持つ「波」が得られます。上位のスレッドはさらに進んでおり、それらのノードがさらに下位のスレッドによってさらに処理されるのに間に合うように計算します。ツリーが深いのと同じ数のスレッドが必要になります。

于 2013-10-03T14:48:41.670 に答える
0

Kepler GK110 アーキテクチャでは、動的並列処理と呼ばれるカーネルを再帰的に呼び出すことができると思います。したがって、ツリーの各ノードで値の合計を計算する必要がある場合は、動的並列処理が役立ちます。ただし、再帰の深さが制約になる場合があります。

于 2013-10-04T19:18:59.913 に答える
0

私の第一印象は、Eric が提案したのと同様に、ツリー ノードを 1 次元配列に編成できるということです。そして、その配列に対してセグメント化されたプレフィックス サム スキャン ( http://en.wikipedia.org/wiki/Segmented_scan ) を実行できます。

ツリー ノードを例として使用すると、1 次元配列は次のようになります。

0-1-2-3-0-4-5-0-6-7-8-9-10-0-6-7-8-11-12

そして、新しいリストがどこで始まるかを示すフラグの並列配列があります (リストとは、ルートで始まりリーフ ノードで終わるシーケンスを意味します)。

1-0-0-0-1-0-0-1-0-0-0-0- 0-1-0-0-0- 0- 0

ボトムアップの場合、次のように別のセグメント フラグ配列を作成できます。

0-0-0-1-0-0-1-0-0-0-0-0- 1-0-0-0-0- 0- 1

同じアルゴリズムを使用して逆の順序でトラバースします。

セグメント化されたプレフィックス スキャンを実装する方法については、私自身は実装していませんが、その方法について参考になる参考文献をいくつか見つけました: http://www.cs.cmu.edu/afs/cs/ cademic/class/15418-s12/www/lectures/24_algorithms.pdf およびhttp://www.cs.ucdavis.edu/research/tech-reports/2011/CSE-2011-4.pdf (23 ページを参照)

于 2013-10-04T20:57:36.377 に答える