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

摘要：

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

关键词：图计算、图遍历、连通分量算法、Graph500、捷径向量算法

所属期刊栏目：44

分类号：TP391.4(计算技术、计算机技术)

资助基金：国家数值风洞项目;国家自然科学基金;国家自然科学基金;国家自然科学基金;国家重点研发计划;湖南省自然科学基金;行分布处理实验室基金

在线出版日期：2022-03-29（万方平台首次上网日期，不代表论文的发表时间）

页数：共8页

页码：191-198