.png){kind=icon}
.png){kind=icon}
Return
Scalable Single Source Shortest Path Algorithms for Massively Parallel Systems
.png){kind=icon}
OA
AI
DOI：10.1109/TPDS.2016.2634535.png)
.png){kind=icon}
.png){kind=icon}
Share.png){kind=icon}
Save
Abstract
En 中文
We consider the single-source shortest path (SSSP) problem: given an undirected graph with integer edge weights and a source vertex v, find the shortest paths from v to all other vertices. 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. These techniques are particularly effective on power-law graphs, as demonstrated by our extensive performance analysis. In the largest tested configuration, an R-MAT graph with 2(38) vertices and 2(42) 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.
Keywords:
Shortest path
parallel algorithm
delta stepping
graph 500 benchmark
distributed system
AI Summary
Key information extracted from the uploaded paper, including a brief overview, abstract, background, key highlights, visual analysis, and future outlook.
Journal
IF:
6
Papers:
5.2K
Citations:
1.1W