Direction-Optimizing Breadth-First Search on CPU-GPU Heterogeneous Platforms

Breadth-First Search (BFS) is a basis for many graph traversal and analysis algorithms. In this paper, we present a direction-optimizing BFS implementation on CPU-GPU heterogeneous platforms to fully exploit the computing power of both the multi-core CPU and GPU. For each level of the BFS algorithm, we dynamically choose the best implementation from: a sequential top-down execution on CPU, a parallel top-down execution on CPU, and a cooperative bottom-up execution on CPU and GPU. By adapting to the runtime variability of vertex frontiers, such a hybrid approach provides the best performance for the exploration of each BFS level while avoiding poor worst case performance. Our implementation demonstrates speedups of 1.37 to 1.44 compared to the highest published performance for shared memory systems.