4

私の研究では、Migliore、Martorana、および Sciortino によるアルゴリズムを広範囲に使用して、考えられるすべての単純なパス (つまり、ノードが 2 回以上遭遇しないパス) をグラフ内で見つけます: An Algorithm to find All Paths between Two Nodes inグラフ. (このアルゴリズムは本質的に深さ優先検索であり、本質的に直感的に再帰的ですが、著者は非再帰的なスタックベースの実装も提示しています。) そのようなアルゴリズムを GPU に実装できるかどうか知りたいです。現時点では、この問題で実際の並列性を確認するのに苦労しています。たとえば、スレッドの監視とディスパッチのコストによって、(ハードウェア スレッドによる) 協調グラフ検索が非常に困難になる場合があります。あるいは、グラフが分割され、検索のために個々のハードウェア スレッドに割り当てられている場合、分割統治戦略が機能する可能性があります。ただし、(1) グラフを分割する方法、(2) サブタスクを定式化する方法、および (3) 分割での検索結果を結合する方法を理解する必要があります。

4

2 に答える 2

2

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

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); }
   }
}

path[endNode][i] // startNode から endNode への i 番目のパス

パーティショニング: ノード % から来ました 2
サブタスク: ノードから移動する場所を見つけます
結合: 共有メモリがありますよね?

于 2011-01-05T06:57:46.933 に答える
0

あなたの問題を GPU に簡単に移植して、より高速に実行できるとは思いません。ほとんどの GPU パワーを利用する GPU プログラム:

  • 数千のスレッドで構成されていますが、その数は一定です。新しいスレッドの生成や以前のスレッドの強制終了はありません。
  • 合体メモリアクセスを優先します。隣接するスレッドがメモリの完全に異なる領域にアクセスする場合 (そして通常はグラフ アルゴリズムがアクセスする場合) は遅くなります。
  • 再帰とスタックが好きではありません。最新の NVIDIA Fermi カードは関数呼び出しをサポートしており、スレッドはスタックを持つことができますが、スレッド数が多いため、スタックは非常に短くなります (または大量のメモリを消費します)。

効率的な GPU アルゴリズムがないとは言いませんが、既存のアルゴリズムを効率的なコードに変換する簡単な方法はないと思います。

于 2011-02-27T20:41:42.577 に答える