A Case Study of Complex Graph Analysis in Distributed Memory: Implementation and Optimization

In recent years, a large number of graph processing frameworks have been introduced, with their goal to simplify analysis of real-world graphs on commodity hardware. Additionally, the Graph500 benchmark has motivated extensive optimization of fundamental graph computations such as breadth-first search and shortest paths on leading high-performance computing systems. The purpose of this current work is to bridge the gap between these two research areas: we introduce a methodology for graph processing that is simple to implement, and yet offers high performance when scaling up from a single compute node up to several thousand nodes. We develop a compact and efficient graph representation, implement several graph analytics, and describe a number of optimizations that can be applied to these analytics. We test our implementations on the 2012 Web Data Commons hyperlink graph with 3.56 billion vertices and 128.7 billion edges, and perform scalability studies up to 4096 nodes of the Blue Waters supercomputer. On 256 nodes of Blue Waters, we demonstrate execution of six graph analytics on this large hyperlink graph in about 20 minutes.