计算机科学 ›› 2022, Vol. 49 ›› Issue (6A): 594-600.doi: 10.11896/jsjkx.210400062

• 计算机网络 • 上一篇    下一篇

面向无尺度图的Δ-stepping算法改进策略

陈钧吾, 余华山   

  1. 北京大学计算机学院 北京 100871
  • 出版日期:2022-06-10 发布日期:2022-06-08
  • 通讯作者: 余华山(yuhs@pku.edu.cn)
  • 作者简介:(chenjw@pku.edu.cn)
  • 基金资助:
    国家重点研发计划(2018YFB0204100)

Strategies for Improving Δ-stepping Algorithm on Scale-free Graphs

CHEN Jun-wu, YU Hua-shan   

  1. School of Computer Science,Peking University,Beijing 100871,China
  • Online:2022-06-10 Published:2022-06-08
  • About author:CHEN Jun-wu,born in 1996,master candidate.His main research interests include parallel computing and so on.
    YU Hua-shan,born in 1971,Ph.D,associate professor.His main research inte-rest include parallel and distributed computing.
  • Supported by:
    National Key R&D Program of China(2018YFB0204100).

摘要: 单源最短路径问题是图算法理论中的经典问题,目的是在带权图上搜索一个源点到其他各个顶点的最短路径。Δ-stepping算法结合了经典Dijkstra算法和Bellman-Ford算法的优势,被广泛用于并行环境的单源最短路径计算。大规模网络的结构按照连接偏好机制演化,其顶点的度数分布呈显著的倾斜特征。基于大规模网络的倾斜性,提出了对Δ-stepping算法的两类改进策略。通过预处理计算任意两个顶点之间的距离上限,实现对边松弛操作的调度优化,提高单源最短路径计算的效率以及在并行环境中的伸缩性。首先,把权重超过所关联顶点之间距离上限值的边标记出来,在单源最短路径计算时,直接跳过这些边,从而减少计算过程中被松弛的边的数量。其次,利用顶点之间距离的上限值动态优化顶点的松弛顺序,只有一个顶点到源点的当前路径的长度不超过它们之间的距离上限值时,才松弛该顶点关联的边,从而减少这些边上的重复松弛操作。测试结果表明,与Graph500实现的Δ-stepping算法相比,改进后的算法在Graph500的基准测试图上有接近10倍的性能提升,在一些真实图上也有2.68~5.58倍的性能提升。

关键词: Δ-stepping算法, 大规模图, 性能优化, 最短路径

Abstract: The single-source shortest path problem is an important graph primitive.It computes the shortest paths in a weighted graph from a source vertex to every other vertex.Combining the classical Dijkstra's algorithm and Bellman-Ford's algorithm,Δ-stepping algorithm is used widely to complete SSSP computations in parallel settings.Due to the generic mechanism of preferential attachment,most large-scale networks are significantly skewed in the vertex degree distributions.This paper presents two strategies that utilize the skewness to improve the efficiency and scalability of Δ-stepping algorithm on large graphs.A preprocessing is executed on the input graph to compute an upper bound for the distance between every pair of vertices.The preprocessing results are used to reduce the redundant edge relaxations in Δ-stepping algorithm,so to improve the algorithm's efficiency and scalability in parallels settings.First,these upper bounds are used to reduce the relaxed edges.An edge is skippable in the SSSP computation when its weight is greater than upper bound of the distance between the connected vertices.Second,they are used to reduce relaxations repeated on the same edges.During the computation,a vertex is forbidden to be relaxed before its tentative distance to the source vertex has been updated to be less than the upper bound.Experimental results show that the improved algorithm on the Graph500 benchmark graphs provides nearly 10 ×performance improvement over its implementation on Graph500,and the performance improvement is between 2.68 and 5.58 on some real graphs.

Key words: Large-scale graph, Performance optimization, Shortest path, Δ-stepping algorithm

中图分类号: 

  • TP311
[1] BERTSEKAS D P.Network Optimization:Continuous and Discrete Models[J].Athena Scientific,1998(9):877-877.
[2] AHUJA R K,MAGNANTI T L,ORLIN J B,et al.Networkflows-theory,algorithms and applications[J].Journal of the Operational Research Society,1993,45(11):791-796.
[3] MEYER U,SANDERS P.Δ-stepping:A parallel single source shortest path algorithm[C]//Proceedings of Annual European Symposium on Algorithms(Esa'98).1998:393-404.
[4] MEYER U,SANDERS P.Δ-stepping:a parallelizable shortestpath algorithm[J].Journal of Algorithms,2003,49(1):114-152.
[5] BLELLOCH G E,GU Y,SUN Y,et al.Parallel shortest paths using radius stepping[C]//Proceedings of the 28th ACM Symposium on Parallelism in Algorithms and Architectures.2016:443-454.
[6] CHAKARAVARTHY V T,CHECCONI F,MURALI P,et al.Scalable single source shortest path algorithms for massively parallel systems[J].IEEE Transactions on Parallel and Distri-buted Systems,2016,28(7):2031-2045.
[7] BEAMER S,ASANOVIC K,PATTERSON D.Direction-opti-mizing breadth-first search[C]//Proceedings of the InternationalConference on High Performance Computing,Networking,Storage and Analysis(SC'12).IEEE,2012:1-10.
[8] DELLING D,GOLDBERG A V,NOWATZYK A,et al.PHAST:Hardware-accelerated shortest path trees[J].Journal of Parallel and Distributed Computing,2013,73(7):940-952.
[9] WATTS D J,STROGATZ S H.Collective dynamics of ‘small-world'networks[J].Nature,1998,393(6684):440-442.
[10] ALBERT-LASZLO B,ALBERT R.Emergence of Scaling inRandom Networks[J].Science,1999,286(5439):509-512.
[11] LESKOVEC J,CHAKRABARTI D,KLEINBERG J,et al.Kronecker graphs:an approach to modeling networks[J].arXiv:0812.4905v2,2009.
[12] MURPHY R C.WHEELER K B,BARRETT B W,et al.Introducing the graph 500[J].Cray User Group,2010,19:45-74.
[13] UENO K,SUZUMURA T.Highly scalable graph search for the Graph500 benchmark[C]//Proceedings of the 21st International Symposium on High-Performance Parallel and Distributed Computing.ACM,2012:149-160.
[14] ALBERT R,BARABÁSIA L.Statistical mechanics of complex networks[J/OL].https://journals.aps.org/rmp/abstract/10.1103/RevModPhys.74.47.
[1] 王永, 崔源.
基于四边形最优圈内最短路径的旅行商问题割边方法
Cutting Edge Method for Traveling Salesman Problem Based on the Shortest Paths in Optimal Cycles of Quadrilaterals
计算机科学, 2022, 49(6A): 199-205. https://doi.org/10.11896/jsjkx.210400065
[2] 鄂海红, 张田宇, 宋美娜.
基于Web的数据可视化图表渲染优化方法
Web-based Data Visualization Chart Rendering Optimization Method
计算机科学, 2021, 48(3): 119-123. https://doi.org/10.11896/jsjkx.200600038
[3] 张晓, 张思蒙, 石佳, 董聪, 李战怀.
Ceph分布式存储系统性能优化技术研究综述
Review on Performance Optimization of Ceph Distributed Storage System
计算机科学, 2021, 48(2): 1-12. https://doi.org/10.11896/jsjkx.201000149
[4] 赵晓薇, 朱小军, 韩周卿.
面向定位应用的无人机的悬停位置和飞行路径优化
Hover Location Selection and Flight Path Optimization for UAV for Localization Applications
计算机科学, 2021, 48(11): 345-355. https://doi.org/10.11896/jsjkx.201000105
[5] 徐江峰谭玉龙.
基于机器学习的HBase配置参数优化研究
Research on HBase Configuration Parameter Optimization Based on Machine Learning
计算机科学, 2020, 47(6A): 474-479. https://doi.org/10.11896/JsJkx.190900046
[6] 周建新, 张志鹏, 周宁.
基于CKSP的分段路由负载均衡技术
Load Balancing Technology of Segment Routing Based on CKSP
计算机科学, 2020, 47(4): 256-261. https://doi.org/10.11896/jsjkx.190500122
[7] 张彭奕, 宋杰.
区块链共识算法效能优化研究进展
Research Advance on Efficiency Optimization of Blockchain Consensus Algorithms
计算机科学, 2020, 47(12): 296-303. https://doi.org/10.11896/jsjkx.200700020
[8] 徐传福,王曦,刘舒,陈世钊,林玉.
基于Python的大规模高性能LBM多相流模拟
Large-scale High-performance Lattice Boltzmann Multi-phase Flow Simulations Based on Python
计算机科学, 2020, 47(1): 17-23. https://doi.org/10.11896/jsjkx.190500009
[9] 耿海军, 尹霞.
基于增量最短路径优先的域内高效路由保护算法
Efficient Intra-domain Routing Protection Algorithm Based on i-SPF
计算机科学, 2019, 46(8): 116-120. https://doi.org/10.11896/j.issn.1002-137X.2019.08.019
[10] 何霞, 汤一平, 王丽冉, 陈朋, 袁公萍.
基于Faster RCNNH的多任务分层图像检索技术
Multitask Hierarchical Image Retrieval Technology Based on Faster RCNNH
计算机科学, 2019, 46(3): 303-313. https://doi.org/10.11896/j.issn.1002-137X.2019.03.045
[11] 张凌浩, 桂盛霖, 穆逢君, 王胜.
基于后缀树的二进制可执行代码的克隆检测算法
Clone Detection Algorithm for Binary Executable Code with Suffix Tree
计算机科学, 2019, 46(10): 141-147. https://doi.org/10.11896/jsjkx.180801573
[12] 耿海军.
基于优化链路权值的域内路由保护方案
Intra-domain Routing Protection Scheme by Optimizing Link Weight
计算机科学, 2019, 46(1): 143-147. https://doi.org/10.11896/j.issn.1002-137X.2019.01.022
[13] 徐启泽, 韩文廷, 陈俊仕, 安虹.
众核平台上广度优先搜索算法的优化
Optimization of Breadth-first Search Algorithm Based on Many-core Platform
计算机科学, 2019, 46(1): 314-319. https://doi.org/10.11896/j.issn.1002-137X.2019.01.049
[14] 孙涛, 张俊星.
SDN性能优化技术研究综述
Review of SDN Performance Optimization Technology
计算机科学, 2018, 45(11A): 84-91.
[15] 满振祯,余世明,何德峰.
基于改进伊藤算法的最短路径网络路由优化算法
Shortest Path Network Routing Optimization Algorithm Based on Improved ITO Algorithm
计算机科学, 2017, 44(7): 215-220. https://doi.org/10.11896/j.issn.1002-137X.2017.07.038
Viewed
Full text


Abstract

Cited

  Shared   
  Discussed   
No Suggested Reading articles found!