Back to Search Start Over

Scalable Single Source Shortest Path Algorithms for Massively Parallel Systems.

Authors :
Chakaravarthy, Venkatesan T.
Checconi, Fabio
Murali, Prakash
Petrini, Fabrizio
Sabharwal, Yogish
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