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

计算机工程与科学 ›› 2022, Vol. 44 ›› Issue (02): 191-198.

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

白皓1,4，甘新标1，杨文祥2,贾孟涵1，涂旭平3，张一鸣1，郭敏1，来乐1，张意4，朱春平4

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

收稿日期:2021-02-04 修回日期:2021-09-14 接受日期:2022-02-25 出版日期:2022-02-25 发布日期:2022-02-17
基金资助:
国家数值风洞项目(NNW2019ZT6-B21)；国家自然科学基金（61772541,61872376,61932001）;国家重点研发计划(2018YFB0204301)；湖南省自然科学基金(2020JJ4669)；并行分布处理实验室基金(6142110190206）

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

BAI Hao1,4,GAN Xin-biao1,YANG Wen-xiang2,JIA Meng-han1,TU Xu-ping3,ZHANG Yi-ming1,GUO Min1,LAI Le1,ZHANG Yi4,ZHU Chun-ping4#br#

#br#

（1.College of Computer Science and Technology,National University of Defense Technology,Changsha 410073;

2.Institute of Computational Aerodynamics,China Aerodynamics Research and Development Center,Mianyang 621000;

3.College of Computer Science,Huanggang Normal University,Huanggang 438000;

4.Troop 66061 of PLA，Beijing 100144,China）

Received:2021-02-04 Revised:2021-09-14 Accepted:2022-02-25 Online:2022-02-25 Published:2022-02-17

摘要/Abstract

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

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

Abstract: 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.

Key words: graph computing, graph traversal, connected component algorithm, Graph500, shortcutting-vector algorithm

白皓, 甘新标, 杨文祥, 贾孟涵, 涂旭平, 张一鸣, 郭敏, 来乐, 张意, 朱春平. 面向大规模图计算的连通分量算法分析与优化[J]. 计算机工程与科学, 2022, 44(02): 191-198.

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. Analysis and optimization of the connected component algorithm for large-scale graph computing[J]. Computer Engineering & Science, 2022, 44(02): 191-198.

参考文献［22］

［1］	Leskovec J,Kleinberg J,Faloutsos C.Graphs over time:Densification laws,shrinking diameters and possible explanations［C］∥Proc of the 11th ACM SIGKDD International Confe- rence on Knowledge Discovery and Data Mining,2005:177-187.
［2］	https://investor.fb.com/financials/?section=quarterlyearnings.
［3］	http://www.tencent.com/zh-cn/investors.html.
［4］	Zhang Y Z, Azad A, Buluc A.Parallel algorithms for finding connected components using linear algebra［J］.Journal of Parallel and Distributed Computing,2020,144:14-27.
［5］	https://graph500.org/.
［6］	Hopcroft J,Tarjan R.Algorithm 447:Efficient algorithms for graph manipulation［J］.Communications of the ACM,1973,16(6):372-378.
［7］	Reif J H. Depth-first search is inherently sequential［J］.Reif John H.,1985,20(5):229-234.
［8］	Hirschberg D S,Chandra A K,Sarwate D V.Computing connected components on parallel computers［J］.Communications of the ACM,1979,22(8):461-464.
［9］	Chin F Y L,Lam J,Chen I-N.Efficient parallel algorithms for some graph problems［J］.Communications of the ACM,1982,25(9):659-665.
［10］	Savage C,Ja’Ja’J.Fast,efficient parallel algorithms for some graph problems［J］.SIAM Journal on Computing,1981,10(4):682-691.
［11］	van Scoy F L. The parallel recognition of classes of graphs［J］.IEEE Transactions on Computers,1980,29 (7):563-570.
［12］	Peper F. Determining connected components in linear by a linear number of processor［J］.Information Processing Letters,1987,25(6):401-406.
［13］	Chen J K, Li J J,Lin Y J. Computing connected components of simple undirected graphs based on generalized rough sets［J］.Knowledge-Based Systems,2013,37:80-85.
［14］	Pedroche F, Rebollo M, Carrascosa C,et al.L-RCM:A method to detect connected components in undirected graphs by using the Laplacian matrix and the RCM algorithm［J］.
	arXiv:1206.5726,2012.
［15］	Kofman E,Marzorati D,Fernández J.Connected components in undirected set-based graphs［J］.arXiv:2008.04183,2020.
［16］	Sun Bin. Research on multi machine parallel algorithm for connected component problem［D］.Wuhan:Hubei University,2006.(in Chinese)
［17］	Zhang Y Z, Azad A,Hu Z J.FastSV:A distributed-memory connected component algorithm with fast convergence［J］.arXiv:1910.05971,2019.
［18］	Liu S C, Tarjan R E,Zhong P L.Connected components on a PRAM in log diameter time［C］∥
	Proc of the 32nd ACM Symposium on Parallelism in Algorithms and Architectures,2020:359-369.
［19］	Bentert M,Haag R,Hofer C,et al.Parameterized complexity of min-power asymmetric connectivity［J］.
	arXiv:2005.14620,2020.
［20］	Durgut R, Turaci T, Kutucu H.A heuristic algorithm to find rupture degree in graphs［J］. Turkish Journal of Electrical Engineering & Computer Sciences, 2019,27(5):3433-3441.
［21］	Wang Gui-ping, Wang Yan, Ren Jia-chen. Theory, implementation and application of graph algorithm［M］.Beijing:Peking University Press, 2011.(in Chinese)
［22］	Cormen T H, Leiserson C E, Rivest R L, et al. Introduction to algorithms［M］.Yin Jian-ping, Xu Yun, Wang Gang, et al, translation. Beijing:China Machine Press,
20	12.(in Chinese)
［23］	Tarjan R E, van Leeuwen J.Worst-case analysis of set union algorithms［J］.Journal of the ACM (JACM),1984,31(2):245-281.
［24］	Yao A C. On the expected performance of path compression algorithms［J］.SIAM Journal on Computing,1985,14(1):129-133.
［25］	Gabow H N,Tarjan R E. A linear-time algorithm for a special case of disjoint set union［J］.
	Journal of Computer and System Sciences,1985,30(2):209-221.
	附中文参考文献：
［16］	孙斌.连通分量问题的多机并行算法研究［D］.武汉:湖北大学,2006.
［21］	王贵平,王衍,任嘉辰.图论算法理论、实现和应用［M］.北京:北京大学出版社,2011.
［22］	Cormen T H,Leiserson C E,Rivest R L, 等.算法导论［M］.殷建平，徐云，王刚等译.北京:机械工业出版社,2012.

[1]	邹佩钢1,2，陈军1. 基于CombBLAS的同辈压力图聚类并行算法的设计与实现[J]. 计算机工程与科学, 2017, 39(03): 424-429.
[2]	衡冬冬,唐玉华,易晓东,刘向阳,周侗. 并行原型系统上BFS算法设计实现与测试分析[J]. 计算机工程与科学, 2017, 39(01): 27-34.