Scalable Single Source Shortest Path Algorithms for Massively Parallel Systems
Scalable Single Source Shortest Path Algorithms for Massively Parallel Systems
复制标题
DOI：
10.1109/ipdps.2014.96
复制
发表时间：
2014-05
期刊：
影响因子：
--
通讯作者：
Venkatesan T. Chakaravarthy;Fabio Checconi;F. Petrini;Yogish Sabharwal
中科院分区：
文献类型：
--
作者：
Venkatesan T. Chakaravarthy;Fabio Checconi;F. Petrini;Yogish Sabharwal
在单源最短路径(SSSP)问题中，我们必须找到从一个源点v到图中所有其他顶点的最短路径。在本文中，我们介绍了一种新的并行算法，它是由Bellman-Ford算法和Delta-Step算法衍生出来的。我们使用了各种剪枝技术，如边分类和方向优化，以显著减少节点间的通信量，并提出了负载均衡策略来处理高阶顶点。大量的性能分析表明，我们的算法在无标度图和真实世界的图上都能很好地工作。在最大的测试配置中，一个在32,768个Blue gene/Q节点上有238个顶点和242个边的R-MAT图，我们已经实现了每秒3万亿条边的处理速度(TTEPS)，比最好的发布结果提高了四个数量级。
In the single-source shortest path (SSSP) problem, we have to find the shortest paths from a source vertex v to all other vertices in a graph. In this paper, we introduce a novel parallel algorithm, derived from the Bellman-Ford and Delta-stepping algorithms. We employ various pruning techniques, such as edge classification and direction-optimization, to dramatically reduce inter-node communication traffic, and we propose load balancing strategies to handle higher-degree vertices. The extensive performance analysis shows that our algorithms work well on scale-free and real-world graphs. In the largest tested configuration, an R-MAT graph with 238 vertices and 242 edges on 32,768 Blue Gene/Q nodes, we have achieved a processing rate of three Trillion Edges Per Second (TTEPS), a four orders of magnitude improvement over the best published results.