グラフ上の2つのノード間のすべての可能なパスのGPUベースの検索

Question

私の研究では、Migliore、Martorana、Sciortinoのアルゴリズムを幅広く使用して、すべての可能な単純なパスを見つけることができます。 An Algorithm to find All Paths between Two Nodes in a Graphに記載されているようなグラフである。 （このアルゴリズムは本質的には深さ優先検索であり、直感的に再帰的であるが、非再帰的なスタックベースの実装も提示する）。現時点では、私はこの問題の真の並列性を見るのに苦労しています。たとえば、スレッドを監視しディスパッチするコストは、（ハードウェアスレッドによる）協調グラフ検索を禁止する可能性があります。あるいは、グラフが分割され、検索のために個々のハードウェアスレッドに割り当てられている場合、分割征服戦略が機能する可能性があります。しかし、（1）グラフを分割する（2）サブタスクを定式化する、（3）検索結果をパーティションに結合する方法を理解する必要があります。

Answer 1

これは少し錆びています。ダイクストラはどうですか？

Boolean[] visited;    // [node] = true; 
Boolean[][] connected;   // [node][i] = node 
Vector<Vector<Integer>>[] path; // this should suck 
Integer startNode; 
Integer endNode; 
Queue queue0; //for thread 0 
Queue queue1; //for thread 1 

while (queue0.hasNext()) { 
    Integer node = queue.getNext(); 
    if visited[node] { 
     continue; 
    } else { 
     visited[node] = true; 
    } 

    for (nextNode: connected[node]) { 
     for (i) { 
     path[nextNode].append(path[node][i].clone().append(node)); 
     } 
     if (nextNode%2 == 0) { queue0.add(nextNode); } 
     if (nextNode%2 == 1) { queue1.add(nextNode); } 
    } 
} 

パスstartNode

パーティションからENDNODEする[ENDNODE] [i]は// i番目のパス：あなたが共有している：組み合わせノード
から行く場所を見つける：ノード％から2つの
サブタスクを来ましたメモリ、右？

Answer 2

あなたの問題はGPUでより速く実行できるように簡単に移植できるとは思いません。 GPUのパワーを最大限に活用するGPUプログラム：

• スレッドの数は分かりますが、それらの数は一定です。新しいスレッドの生成や以前のスレッドの強制終了はありません。
• 融合メモリアクセスを推奨します。隣接するスレッドがメモリの異なる領域に完全にアクセスすると（通常、グラフアルゴリズムでは）遅くなります。
• 回帰とのスタックが好きではありません。最新のNVIDIA Fermiカードは関数呼び出しをサポートしており、スレッドはスタックを持つことができますが、スレッド数が多いため、スタックは非常に短い（または多くのメモリを消費します）。私はないを行う

には、効率的なGPUのアルゴリズムが存在しないと言うが、私は、効率的なコードに既存のアルゴリズムを変換する簡単な方法がないことを信じています。