Parallel Breadth-First Search on Distributed Memory Systems

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.

Provided by: Association for Computing Machinery Topic: Data Centers Date Added: Nov 2011 Format: PDF

Find By Topic