  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).
