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

Analysis and optimization of the connected component algorithm for large-scale graph computing

作　　者：白皓 甘新标[1] 杨文祥 贾孟涵 涂旭平 张一鸣[1] 郭敏[1] 来乐 张意[4] 朱春平 BAI Hao;GAN Xin-biao;YANG Wen-xiang;JIA Meng-han;TU Xu-ping;ZHANG Yi-ming;GUO Min;LAI Le;ZHANG Yi;ZHU Chun-ping(College of Computer Science and Technology,National University of Defense Technology,Changsha 410073;Institute of Computational Aerodynamics,China Aerodynamics Research and Development Center,Mianyang 621000;College of Computer Science,Huanggang Normal University,Huanggang 438000;Troop 66061 of PLA,Beijing 100144,China)

机构地区：[1]国防科技大学计算机学院,湖南长沙410073 [2]中国空气动力研究与发展中心计算空气动力研究所,四川绵阳621000 [3]黄冈师范学院计算机学院,湖北黄冈438000 [4]中国人民解放军66061部队,北京100144

出　　处：《计算机工程与科学》2022年第2期191-198,共8页Computer Engineering & Science

基　　金：国家数值风洞项目(NNW2019ZT6-B21);国家自然科学基金(61772541,61872376,61932001);国家重点研发计划(2018YFB0204301);湖南省自然科学基金(2020JJ4669);并行分布处理实验室基金(6142110190206)。

摘　　要：近年来,图计算在诸多领域发挥着越来越重要的作用。连通分量算法是图计算的重要基础算法,可以应用于可达性查询、一致性检测等众多场景。面向大规模图遍历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倍。In recent years,graph computing has played an increasingly important role in many fields.The connected component algorithm is an important basic algorithm for graph computing,which can be applied to multiple scenarios such as reachability query.This paper is oriented to the large-scale graph traversal Graph500 standard test,and optimizes the connected component algorithm and data structure.The main innovations are as follows:(1)A shortcutting-vector algorithm is proposed for the union-find set,and the degree of coordination between the algorithm and the data structure is tested.(2)The multi-threaded iterative rotation algorithm is used to achieve the parallel acceleration of the algorithm.(3)The advantages and disadvantages of different implementation methods are compared from multiple dimensions.Based on the optimization method,the performance is evaluated and analyzed.When scale=25(including 225 vertices),the speedup ratio of the shortcutting-vector algorithm to the rank-merging algorithm based on two-dimensional vectors and linked lists is 1.38 times and 1.40 times,respectively.The speedup ratios of BFS and DFS are 4.76 times and 4.70 times respectively,and the space occupation is 4.1%~4.6%of the two algorithms.In addition,the speedup ratio of parallel to serial is 1.57 times.

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

分 类 号：TP391.4[自动化与计算机技术—计算机应用技术]