我正在使用MPI实现并行深度优先搜索算法，目前已经完成了一半，同时考虑尝试使用CUDA / OpenCL也实现该算法，纯属出于兴趣和好奇。该算法简单但不是简单的问题，C语言单核版本大约有200行代码。
GPGPU技术在解决这种问题方面有多少适用性？
1个回答
6
树搜索操作在CUDA中实现并不简单。有一些论文，比如:
- "Lessons Learned from Exploring the Backtracking Paradigm on the GPU" http://dl.acm.org/citation.cfm?id=2033458
还有另一个相当简单的实现（在我看来并不是完全并行化的实现）
- "Accelerating Large Graph Algorithms on the GPU Using CUDA" Pawan Harish and P. J. Narayanan
困难在于，树操作通常涉及决策，根据不同的决策采取不同的分支。因此，在不重叠和进行冗余操作的情况下大规模并行化操作非常困难。
有一些方法使用堆栈和队列实现遍历树。
你可以在这里找到类似的问题： Error: BFS on CUDA Synchronization
- phoad
2
1困难在于，树操作通常涉及决策，并根据不同的决策采取不同的分支。@phoad - 我迫不及待地等待动态并行 :) - Mark Ebersole
有一些方法像“推测执行”。尽管它降低了并行度，但对于树生长和搜索算法可能是有益的。 - phoad
网页内容由stack overflow 提供, 点击上面的可以查看英文原文，
原文链接
原文链接