面向大规模图计算的连通分量算法分析与优化

作者：白皓; 甘新标^*; 杨文祥; 贾孟涵; 涂旭平; 张一鸣; 郭敏; 来乐; 张意; 朱春平

来源：计算机工程与科学, 2022, 44(02): 191-198.

• 图计算
• 图遍历
• 连通分量算法
• Graph500
• 捷径向量算法

近年来,图计算在诸多领域发挥着越来越重要的作用。连通分量算法是图计算的重要基础算法,可以应用于可达性查询、一致性检测等众多场景。面向大规模图遍历Graph500标准测试,对连通分量算法进行了算法和数据结构优化。主要有以下创新:(1)对并查集提出了捷径向量算法,并测试了算法和数据结构的配合程度;(2)利用多线程迭代轮转对算法实现并行加速;(3)从多个维度比较了不同实现方法的优缺点。基于优化方法,对性能进行了评估分析,当scale=25(包含2~(25)个节点)时,捷径向量算法对基于二维向量和链表的按秩合并算法的加速比分别是1.38倍和1.40倍,对BFS和DFS的加速比分别为4.76倍和4.70倍,且空间占用为该2个算法的4.1%～4.6%,此外,并行对串行的加速比为1.57倍。

• 单位
  中国空气动力研究与发展中心; 黄冈师范学院; 国防科技大学