Data Centers

Parallel Breadth-First Search on Distributed Memory Systems

Download Now Date Added: Nov 2011
Format: PDF

Data-intensive, graph-based computations are pervasive in several scientific applications, and are known to be quite challenging to implement on distributed memory systems. In this paper, the authors explore the design space of parallel algorithms for Breadth-First Search (BFS), a key subroutine in several graph algorithms. They present two highly-tuned parallel approaches for BFS on large parallel systems: a level-synchronous strategy that relies on a simple vertex-based partitioning of the graph, and a two-dimensional sparse matrix partitioning-based approach that mitigates parallel communication overhead.