Back to Search
Start Over
Scalable Single Source Shortest Path Algorithms for Massively Parallel Systems.
- Source :
-
IEEE Transactions on Parallel & Distributed Systems . Jul2017, Vol. 28 Issue 7, p2031-2045. 15p. - Publication Year :
- 2017
-
Abstract
- We consider the single-source shortest path (SSSP) problem: given an undirected graph with integer edge weights and a source vertex v<alternatives> <inline-graphic xlink:href="chakaravarthy-ieq1-2634535.gif"/></alternatives>, find the shortest paths from v<alternatives> <inline-graphic xlink:href="chakaravarthy-ieq2-2634535.gif"/></alternatives> 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 <alternatives><inline-graphic xlink:href="chakaravarthy-ieq3-2634535.gif"/></alternatives> vertices and 2^42<alternatives> <inline-graphic xlink:href="chakaravarthy-ieq4-2634535.gif"/></alternatives> 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. [ABSTRACT FROM AUTHOR]
Details
- Language :
- English
- ISSN :
- 10459219
- Volume :
- 28
- Issue :
- 7
- Database :
- Academic Search Index
- Journal :
- IEEE Transactions on Parallel & Distributed Systems
- Publication Type :
- Academic Journal
- Accession number :
- 123588169
- Full Text :
- https://doi.org/10.1109/TPDS.2016.2634535