我在 MPI 中实现并行深度优先搜索算法的一半，我正在考虑尝试在 CUDA / OpenCL 中也这样做，只是为了好玩/出于好奇。该算法很简单，但并非微不足道。C 中的单核版本大约有 200 行代码。
GPGPU适合这种问题多少？
问问题
2939 次
1 回答
6
在 CUDA 中实现树搜索操作并不是那么简单。有一些论文，比如那个
- “在 GPU 上探索回溯范式的经验教训” http://dl.acm.org/citation.cfm?id=2033458
还有另一个相当简单的实现（在我看来不是一个大规模并行化的实现）
- “使用 CUDA 在 GPU 上加速大型图算法”Pawan Harish 和 PJ Narayanan
困难在于，树操作通常涉及决策，并根据决策采取不同的分支。因此，在不重叠和进行冗余操作的情况下大规模并行化操作是相当困难的。
有一些方法使用堆栈和队列实现来遍历树。
您可能会在这里找到类似的问题： 错误：CUDA 同步上的 BFS
于 2012-10-01T10:57:46.813 回答