《计算机工程与科学杂志》发表论文赏析

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

来源:计算机工程与科学杂志2022年第2期北京时间:

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

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

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

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

2022年2期其他文献查阅:

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

硅转接层高带宽存储互连通道信号完整性设计及仿真

一种基于Chiplet集成技术的超高阶路由器设计

一种CDC信号滑动窗口时序分析方法

基于聚合的FlowRadar网络数据采集加速模型设计

基于软件定义的WSNs非均匀分簇QoS路由算法

基于角色管理的实用拜占庭容错共识算法

基于深度学习的GPS轨迹去匿名研究

基于谱聚类的社交网络差分隐私保护算法研究

基于代理辅助多目标萤火虫算法的软件缺陷预测方法研究

基于模糊决策过程的模糊计算树逻辑模型检测

基于混合注意力机制的目标跟踪算法

基于特征聚类的大视差图像拼接算法

改进标签一致KSVD字典学习的人脸识别算法

WiFi环境下基于CGRU-ELM混合模型的手势识别

一种基于GN算法的动态图划分方法

用于人体检测的YOLOv3改进及压缩算法的研究

多源图像融合方法的研究综述

图自编码器推荐研究综述

区间值广义正交模糊Frank算子及群决策方法

基于混合反向学习策略的鲸鱼优化算法

几类带空转移的n元伪加权自动机的关系

基于密度和中心指标的Canopy二分K-均值算法优化

填文献完整题目 获取完整文献

填写需求
联系方式
注:学术顾问会在1小时内联系您,请留意!