计算机工程与科学

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

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

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

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

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

来源：2022年第2期

《计算机工程与科学》期刊编辑部

查看计算机工程与科学杂志2022年第2期