如何遍历并行的图形有2个或数处理

Question

我才能找到一些算法，可以使用2个或数处理遍历并行的图形没有一个进程步入的一个以前访问过的节点在互联网上搜索其他所以我可以加快整个图的总扫描任务，但我找不到任何东西。有什么算法可以帮助我平行地完成这样的任务吗？这值得么？

注： 数处理共享访问和tovisit节点

的相同内存谢谢

Answer 1

你可以试试消费者 - 生产者模型遍历图 - 但是从纯模型的一些修改：

• 读取和写入块队列中，而不是在一个时间元素，同时更新visited设置为块。它将为您节省同步时间 - 这将需要不那么频繁地完成。
• 当你做修改队列（和visited集） - 你应该做一些额外的工作，以确保你不会增加自设的最后检查发现已经访问过的数据。

注意，这种方法 - 你更然后可能会搜索某些顶点几次 - 但是你可以用频率队列和visited集更新约束它。

请问这值得吗？在这些事情中很难说 - 它依赖于很多东西（图形结构，大小，队列实现......）。

您应该运行一些测试，并尝试微调为“更新频率”的参数，并检查哪个是更好的经验。你应该使用statistical tools（wilcoxon test通常是事实上的标准），并确定一个比另一个更好。

Answer 2

除非时间大部分都花在实际穿越，你可以穿越在单个线程图形，并将每个节点上的工作排队等待多个进程并行处理。一旦你在队列中工作，你可以使用一个简单的生产者 - 消费者模型。