A Work-Efficient Parallel BreadthFirst Search Algorithm (or How to Cope with the Nondeterminism

We have developed a multithreaded implementation of breadth-first search (BFS) of a sparse graph using the Cilk++ extensions to C++. Our PBFS program on a single processor runs as quickly as a stan-dard C++ breadth-first search implementation. PBFS achieves high work-efficiency by using a novel implementation of a multiset data structure, called a “bag, ” in place of the FIFO queue usually em-ployed in serial breadth-first search algorithms. For a variety of benchmark input graphs whose diameters are significantly smaller than the number of vertices — a condition met by many real-world graphs — PBFS demonstrates near-perfect linear speedup in the number of processing cores, as long as the machine has sufficient memory bandwidth. Since PBFS employs a nonconstant-time “reducer ” — a “hyper-object ” feature of Cilk++ — the work inherent in a PBFS execution depends nondeterministically on how the underlying work-stealing scheduler load-balances the computation. We provide a general method for analyzing nondeterministic programs that use reduc-ers. PBFS also is nondeterministic in that it contains benign races which affect its performance but not its correctness. Fixing these races with mutual-exclusion locks slows down PBFS empirically, but it makes the algorithm amenable to analysis. In particular, we show that for a graph G = (V,E) with diameterD and bounded out-degree, this data-race-free version of PBFS algorithm runs in time O((V +E)/P+O(D lg3(V/D)) on P processors