私はMPIで並列深さ優先検索アルゴリズムを実装する途中で、CUDA / OpenCLでもそれをやろうと考えています.楽しみ/好奇心から。アルゴリズムは単純ですが、自明ではありません。C のシングルコア バージョンは、約 200 行のコードです。
GPGPU はこの種の問題にどのくらい適していますか?
質問する
2939 次
1 に答える
6
ツリー検索操作は、CUDA で実装するにはそれほど単純ではありません。みたいな紙もあります
- 「GPU でのバックトラッキング パラダイムの調査から学んだ教訓」http://dl.acm.org/citation.cfm?id=2033458
そして、別のかなり単純な実装 (私の意見では、大規模な並列化された実装ではありません)
- 「CUDA を使用した GPU での大規模なグラフ アルゴリズムの高速化」Pawan Harish および PJ Narayanan
難しいのは、ツリーの操作には一般に意思決定が含まれ、決定に従って異なる分岐が行われるという事実から来ています。そのため、オーバーラップせずに操作を大規模に並列化し、冗長な操作を作成することは非常に困難です。
スタックとキューの実装を使用してツリーをトラバースするアプローチがいくつかあります。
ここで同様の質問を見つけることができます: Error: BFS on CUDA Synchronization
于 2012-10-01T10:57:46.813 に答える