Chernoskutov M.A.  

Methods for High Performance Graph Processing

Graph algorithms are common “building blocks” of many complex real-world applications, for instance, network analysis, data enrichment applications, bioinformatics, city planning, etc.
In general, graph algorithms are typical “data intensive” problem [1]. It means that parallel graph processing applications characterized by two important drawbacks [2,3]:
• workload imbalance amongst computational threads;
• large number of data transfers between computational processes.
The object of presented study are two methods which designed to address these drawbacks and to speedup the parallel graph traversal:
• reducing workload imbalance on computational threads (based on the fine-grained parallelization of edge array processing in CSR data structure);
• data transfer optimization (based on fused top-down and bottom-up graph traversal and using of bitmask, which synchronized between computational processes and stores information about vertices in the graph).
These methods allows to accelerate the parallel traversal of big graphs with skewed degree distribution (which have millions of vertices and edges). Thus, it used for development of the custom implementation of Graph500 benchmark (which based on the parallel breadth-first search on large graphs). Testing was carried out on the "Uran" supercomputer located at Institute of Mathematics and Mechanics, Ural Branch Russian Academy of Science (428th place in Top500, June list, 2013). We conduct experiments on graphs with 2^23, 2^24, 2^25 vertices. These graphs are not directed and have average degree 16. In all experiments, custom implementation significantly (more than two times) outperforms its non-optimized counterpart. These methods also applicable to other types of graph algorithms (for instance, single source shortest path).
References
[1]M.E.J. Newman, The structure and function of complex networks. SIAM Review 45, 167-256 (2003).
[2] B. Hendrickson, J.W. Berry, Graph analysis with high-performance computing, Computing in Science and Engineering, vol. 10, no. 2, pp. 14-19, 2008.
[3] A. Lumsdaine, D. Gregor, B. Hendrickson, J.W. Berry, Challenges in Parallel Graph Processing. Parallel Processing Letters 17, 2007, 5-20.