21

現在の GPU 実行とメモリ モデルは何らかの制限があります (メモリ制限、データ構造の制限、再帰なし...)。

グラフ理論の問題を GPU で実装することは実現可能だと思いますか? 例えば頂点カバー？支配セット？独立セット？マックスクリーク?...

GPU で分岐限定アルゴリズムを使用することも可能ですか? 再帰的バックトラック?

4

2 に答える 2

29

あなたはに興味があるでしょう

  1. 並列グラフアルゴリズムを使用したGPUの限界の調査

  2. CUDAを使用してGPUで大規模なグラフアルゴリズムを高速化します。

于 2010-03-12T08:22:43.807 に答える
5

これはあなたの質問に接していますが、ラティス上で「自己回避ウォーク」を列挙するための「再帰的」バックトラッキングアルゴリズムを実装しました (nb: ローカル変数を作成するオーバーヘッドを回避するために、スタックは CUDA カーネル内でシミュレートされました)一連の関数呼び出しに対して)。これを効率的に行うことは可能であるため、これをグラフ理論のコンテキストに適用できると確信しています。これは、Single Instruction Multiple Data (SIMD) パラダイム内でのバックトラッキングに関する一般的な議論を行ったトピックに関するセミナーへのリンクです。サイズが約 1MB の PDF ですhttp://bit.ly/9ForGS。

GPU のグラフ理論アルゴリズムに関する幅広い文献について知っているとは言いませんが、上記が少し役立つことを願っています。

(@TheMachineCharmer、リンクをありがとう。)

于 2010-03-15T11:32:42.913 に答える