A Faster Breadth-First Search on Sparse Graphs

Abstract

Breadth-First Search (BFS) is a widely used graph processing algorithm with applications in many areas. State-of-the-art parallel BFS algorithms use a levelsynchronous approach which explores the graph level by level, with a synchronization barrier between each level. The level-synchronous approach works well for dense graphs, where each level is relatively large, but its synchronization requirements limit performance on sparse graphs. Unordered BFS algorithms instead explore graphs without the level constraint, thus removing the synchronization barrier, at the cost of potentially doing significantly more work to complete the traversal. We present an efficient unordered BFS algorithm for sparse high-diameter graphs. The algorithm schedules the traversal using a relaxed FIFO queue, i.e., a queue that is allowed to dequeue items other than the head, to improve queue throughput. Additionally, we introduce two novel optimizations for unordered BFS. On a shared memory system, our algorithm achieves speedups of 1.6-2.4 compared to the state-of-the-art level-synchronous algorithm on four sparse real-world graphs.