Efficient Parallel Graph Exploration on Multi-Core CPU and GPU
Graphs are a fundamental data representation that have been used extensively in various domains. In graph-based applications, a systematic exploration of the graph such as a Breadth-First Search (BFS) often serves as a key component in the processing of their massive data sets. In this paper, the authors present a new method for implementing the parallel BFS algorithm on multi-core CPUs which exploits a fundamental property of randomly shaped real-world graph instances. By utilizing memory bandwidth more efficiently, their method shows improved performance over the current state-of-the-art implementation and increases its advantage as the size of the graph increases.