Fast and Efficient Parallel Breadth-First Search with Power-law Graph Transformation

In the big data era, graph computing is widely used to exploit the hidden value in real-world graphs in various scenarios such as social networks, knowledge graphs, web searching, and recommendation systems. However, the random memory accesses result in inefficient use of cache and the irregular degree distribution leads to substantial load imbalance. Breadth-First Search (BFS) is frequently utilized as a kernel for many important and complex graph algorithms. In this paper, we describe a preprocessing approach using Reverse Cuthill-Mckee (RCM) algorithm to improve data locality and demonstrate how to achieve an efficient load balancing for BFS. Computations on RCM-reordered graph data are also accelerated with SIMD executions. We evaluate the performance of the graph preprocessing approach on Kronecker graphs of the Graph500 benchmark and real-world graphs. Our BFS implementation on RCM-reordered graph data achieves 326.48 MTEPS/W (mega TEPS per watt) on an ARMv8 system, ranking 2nd on the Green Graph500 list in June 2020 (the 1st rank uses GPU acceleration).