Topologically Adaptive Parallel Breadth-First Search on Multicore Processors

Free registration required

Executive Summary

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.

  • Format: PDF
  • Size: 630.6 KB