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.