Venkatesan T. Chakaravarthy, Vinayaka Pandit, et al.
IPDPS 2010
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 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.
Venkatesan T. Chakaravarthy, Vinayaka Pandit, et al.
IPDPS 2010
Tommaso Cucinotta, Fabio Checconi, et al.
Transactions on Embedded Computing Systems
Xinyu Que, Fabio Checconi, et al.
IPDPS 2015
Sonika Arora, Archita Agarwal, et al.
HiPC 2014