Subgraph Counting: Color Coding beyond Trees
Venkatesan T. Chakaravarthy, Michael Kapralov, et al.
IPDPS 2016
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, Michael Kapralov, et al.
IPDPS 2016
Jin-Yi Cai, Venkatesan T. Chakaravarthy
COCOON 2005
Venkatesan T. Chakaravarthy, Monu Kedia, et al.
HiPC 2012
Prakash Murali, Norbert M. Linke, et al.
ISCA 2019