ITA Software's Technical Seminar Series

Talk Topic: Parallel Breadth-First Search
Tao B. Schardl, MIT CSAIL
June 2, 2010

Abstract

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 standard 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 employed in serial breadth-first search algorithms. For a variety of benchmark input graphs whose diameters are significantly smaller than the number of vertices — condition met by many real-world graphs — demonstrates good speedup with the number of processing cores.

Since PBFS employs a nonconstant-time “reducer” — a “hyperobject” 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 reducers. 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 diameter $D$ and bounded out-degree, this data-race-free version of PBFS algorithm runs in time $O((V+E)/P + D\lg^3(V/D))$ on $P$ processors, which means that it attains near-perfect linear speedup if $P \ll (V+E)/D\lg^3(V/D)$.

Bio

Tao B. Schardl is a Ph.D. candidate in the Department of Electrical Engineering and Computer Science at the Massachusetts Institute of Technology. He is a member MIT’s Computer Science and Artificial Intelligence Laboratory, and works in the Supertech group with Professor Charles Leiserson. His primary research is on developing parallel graph algorithms and parallel data structures. His previous research includes developing a work-efficient parallel breadth-first search algorithm and designing a theoretical framework for analyzing Cilk programs with nonconstant time reducer hyperobjects. Mr. Schardl received his Bachelor of Science in Computer Science and Electrical Engineering from MIT in 2009 and his Masters of Engineering in Computer Science and Electrical Engineering from MIT in 2010.