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

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

近年来,图计算在诸多领域发挥着越来越重要的作用。连通分量算法是图计算的重要基础算法,可以应用于可达性查询、一致性检测等众多场景。面向大规模图遍历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.