我的工作广泛使用 Migliore、Martorana 和 Sciortino 的算法来查找所有可能的简单路径,即在图中没有多次遇到节点的路径,如:An Algorithm to find All Paths between two Nodes in图表. (虽然这个算法本质上是一种深度优先搜索并且本质上是直观的递归,但作者也提出了一个非递归的、基于堆栈的实现。)我想知道这样的算法是否可以在 GPU 上实现。目前,我正在努力在这个问题中看到任何真正的并行性。例如,监视和分派线程的成本可能会使协作图搜索(通过硬件线程)望而却步。或者,如果图形被分区并分配给单独的硬件线程进行搜索,则分而治之的策略可能会起作用。然而,人们必须弄清楚如何(1)对图进行分区(2)制定子任务和(3)结合分区上的搜索结果。
问问题
751 次
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 回答