Date Added: Feb 2010
Breadth-First Search (BFS) is a fundamental graph theory algorithm that is extensively used to abstract various challenging computational problems. Due to the fine-grained irregular memory accesses, parallelization of BFS can exhibit limited performance on cache-based systems. In this paper, the authors study the relationship between the topology of input graphs and the performance of BFS on multicore systems. They propose a model to estimate the scalability of BFS with respect to a given graph. Using this model, they propose a topologically adaptive parallel BFS algorithm on multicore systems. The proposed algorithm estimates scalability of each iteration of BFS with respect to the input graph at runtime.