21

当前的 GPU 执行和内存模型在某种程度上受到限制（内存限制、数据结构限制、无递归......）。

您认为在 GPU 上实现图论问题是否可行？例如，顶点覆盖？主导集？独立集？最大派系？...

在 GPU 上使用分支定界算法是否也可行？递归回溯？

4

2 回答 2

29

你会感兴趣的

  1. 使用并行图算法探索 GPU 的极限

  2. 使用 CUDA 在 GPU 上加速大型图算法。

于 2010-03-12T08:22:43.807 回答
5

这与您的问题切线相关，但我已经实现了一个“递归”回溯算法，用于枚举格上的“自我避免行走”（nb：堆栈是在 CUDA 内核中模拟的，以避免创建局部变量的开销对于一大堆函数调用）。可以有效地做到这一点，所以我相信这可以适应图论的背景。这是一个关于该主题的研讨会的链接，我在其中对单指令多数据 (SIMD) 范式中的回溯进行了一些一般性讨论；这是一个大小约为 1MB 的 pdf http://bit.ly/9ForGS。

我并不声称了解有关 GPU 上的图论算法的更广泛的文献，但希望以上内容有所帮助。

（@TheMachineCharmer，感谢您的链接。）

于 2010-03-15T11:32:42.913 回答