HisOrder: A Historical Frontier-Aware Graph Reordering for Efficient BFS

The efficiency of Breadth-first Search (BFS) is predominantly constrained by its poor locality and severe load imbalance. The former primarily arises from random accesses to neighbors of active vertices (a.k.a frontiers), while the latter is caused by skewed distribution of edge traversals among CPU cores. Graph reordering aims to improve data locality by contiguously placing vertices that are likely to be consecutively accessed, and can potentially enhance the load balance by distributing more balanced workloads to CPU cores. Prior graph reordering methods generally adopt static structural metrics like vertex degree and graph community to explore the vertex locality. However, the data access patterns and load distribution of BFS are intrinsically contingent upon the frontiers generated at runtime, which can vary significantly across different inputs and iterations. To this end, we propose a frontier-based locality feature vector that is capable to characterize the locality of the frontiers in BFS requests. With this feature vector, we propose a graph reordering method named HisOrder, which uses history of multiple BFS requests to construct a feature vector and explore the locality of vertices with K-Means. Furthermore, HisOrder finetunes the vertex order for balancing workloads among CPU cores by predicting runtime computing intensity using the learned frontier distribution. To enhance the efficiency of HisOrder, we eliminate redundant distance computations in K-means, thereby achieving a significant acceleration. Based on evaluation on four small-world graph datasets, HisOrder achieves an average performance improvement of 1.20× with reasonable overhead, and consistently surpasses the state-of-the-art graph reordering.