multithreading - 连通分量的并行算法

Question

我必须从已知的图形连通分量并行计算中找到最佳算法。

这里是我的数据和计算机架构的简要概述:

• 我可以访问一个包含数千个处理器(内存不共享，但我希望应该有单个节点中有足够的内存来评估我对整个节点的需求数据)。
• 我的图的边数与顶点数之比很小(大约 5)
• 我希望大多数连通分量都非常小(2-3 个顶点)
• 但是，将会有具有数百万个顶点的非常大的组件(甚至占总顶点数的 10%)。

我读过有关计算图的连通分量的并行算法。正如我所注意到的，其中一些基于序列化案例的经典 BFS 方法。老实说，我对这些算法的数量有点迷茫。谁能给我一些建议，哪种算法最适合我的目的？

Answer 1

Ligra对于单机多核实现，它要么是最先进的，要么接近它。它应该能够毫无问题地处理您的图表。

Connected Components at Scale via LocalContractions ，由我的同事 Jakub Łącki、Vahab Mirrokni 和 Michał Włodarczyk 编写，是 MapReduce 算法的最新技术水平(至少，据我所知)。我们已经在比您大一千倍的图表上使用它。