Direction-Optimizing
Breadth-First Search

Scott Beamer, Aydın Buluç (LBL), David Patterson, Krste Asanović

Breadth-first search (BFS) is an important kernel used by many graph algorithms. It is only a traversal order, and depending on what is recorded, it can return connectivity, distance, or parenthood. Due to its simplicity and importance to graph workloads, it has been used as the first and main kernel in the Graph 500 competition.

A typical BFS implementation will examine every edge in a directed graph once (twice if undirected). Most of these edge examinations will fail because the other end of the edge has already been visited. The bottom-up approach can be drastically faster by checking many fewer edges. It is only advantageous when the frontier constitutes a large fraction of the graph, and this typically happens during the middle steps of a BFS on low-diameter graphs (such as social networks).

To get the best performance, we combine the novel bottom-up approach with the classical top-down approach. Since our hybrid switches approaches on a step-level granularity, and it uses each for when they are advantageous, it is called Direction-Optimizing BFS.

The direction-optimizing approach was conceived in time for the November 2011 Graph500 rankings, and it allowed a quad-socket Intel server to beat small clusters and specialized hardware such as the Cray XMT and the Convey HC-1. The algorithm was initially disclosed in a technical report [1] and later formally presented at Supercomputing 2012 [2].

We redesigned our algorithm to run on a cluster to perform BFS on larger graphs. Our implementation [3] is built on top of the CombBLAS framework.

Graph500 Finishes

Adoption of Direction-Optimizing Approach in Graph500

References

  1. "Searching for a Parent Instead of Fighting Over Children: A Fast Breadth-First Search Implementation for Graph500", Scott Beamer, Krste Asanović, and David Patterson, Technical Report UCB/EECS-2011-117, EECS Department, University of California, Berkeley, November 2011. TR
  2. "Direction-Optimizing Breadth-First Search", Scott Beamer, Krste Asanović, and David Patterson, International Conference on High Performance Computing, Networking, Storage and Analysis (SC), Salt Lake City, Utah, November 2012. ACM errata corrected
  3. "Distributed Memory Breadth-First Search Revisited: Enabling Bottom-Up Search", Scott Beamer, Aydın Buluç, Krste Asanović, and David Patterson, Workshop on Multithreaded Architectures and Applications (MTAAP), at the International Parallel & Distributed Processing Symposium (IPDPS), Boston, May 2013. IEEE
  4. "Direction-Optimizing Breadth-First Search", Scott Beamer, Krste Asanović, and David Patterson, Journal of Scientific Programming, 21(3-4), October 2013. IOS

GAP Project Home