algorithm - 如何与 2 或 n 个进程并行遍历图

Question

我正在互联网上搜索，以找到一些可以使用 2 个或 n 个进程并行遍历图的算法，而无需一个进程进入另一个进程先前访问过的节点，这样我就可以加快整个图的总扫描任务，但我什么也找不到。有没有什么算法可以帮助我并行完成这样的任务？这值得么？

注意：n 个进程共享访问和访问节点的相同内存

谢谢你

Answer 1

除非大部分时间花在实际遍历上，否则您可以在单个线程上遍历图形，并将每个节点的工作排队，以便从多个进程并行处理。在队列中完成工作后，您可以使用简单的生产者-消费者模型。

Answer 2

您可以尝试使用消费者-生产者模型来遍历图形 - 但对纯模型进行了一些修改：

• 以块为单位读取和写入队列，而不是一次一个元素，也visited以块为单位更新集合。它将为您节省同步时间 - 这将需要减少频率。
• 当您确实修改队列（并visited设置）时 - 您应该做一些额外的工作以确保您不添加自上次检查该集合以来已经访问过的数据。

请注意，使用这种方法 - 您更有可能搜索一些顶点几次 - 但您可以将其与队列和visited集合的更新频率绑定。

值得吗？在这些事情上很难说——它取决于很多事情（图结构、大小、队列实现……）。

您应该运行一些测试并尝试微调“更新频率”的参数，并根据经验检查哪个更好。您应该使用统计工具（wilcoxon 测试通常是这方面的事实标准）并确定一个是否比另一个更好。