基于 GPU 搜索图上两个节点之间的所有可能路径

Question

我的工作广泛使用 Migliore、Martorana 和 Sciortino 的算法来查找所有可能的简单路径，即在图中没有多次遇到节点的路径，如下所示： 一种查找图中两个节点之间的所有路径的算法。 （虽然这个算法本质上是深度优先搜索并且本质上是直观的递归，但作者还提出了一种非递归的、基于堆栈的实现。）我想知道这样的算法是否可以在 GPU 上实现。目前我正在努力寻找这个问题中任何真正的并行性。例如，监视和分派线程的成本可能会使协作图搜索（通过硬件线程）变得令人望而却步。或者，如果对图进行分区并分配给各个硬件线程进行搜索，则分而治之的策略也可以发挥作用。然而，人们必须弄清楚如何（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); }
   }
}

path[endNode][i] // 从 startNode

分区到 endNode 的第 i 条路径：来自节点 % 2
子任务：找到从节点去的地方
结合：你们有共享内存，对吧？

Answer 2

我不认为你的问题可以轻松地移植到 GPU 上以使其执行速度更快。利用最多 GPU 能力的 GPU 程序：

• 由数千个线程组成，但线程数量是恒定的。不会产生新线程或杀死以前的线程。
• 更喜欢合并内存访问。如果相邻线程访问完全不同的内存区域（通常是图算法），速度将会很慢。
• 不喜欢递归和堆栈。最新的 NVIDIA Fermi 卡确实支持函数调用，并且线程可以拥有堆栈，但由于线程数量较多，堆栈非常短（或消耗大量内存）。

我并不是说不存在高效的 GPU 算法，但我相信没有直接的方法可以将现有算法转换为高效的代码。