# Searching for a Parent Instead of Fighting Over Children: A Fast Breadth-First Search Implementation for Graph500

### Scott Beamer, Krste AsanoviÄ‡ and David A. Patterson

###
EECS Department

University of California, Berkeley

Technical Report No. UCB/EECS-2011-117

November 15, 2011

### http://www.eecs.berkeley.edu/Pubs/TechRpts/2011/EECS-2011-117.pdf

This report provides a summary of an efficient breadth-first search implementation that is advantageous for social networks. This implementation uses a hybrid approach, combining a conventional top-down algorithm along with a novel bottom-up algorithm. The bottom-up algorithm can dramatically reduce the number of edges examined, which in turn accelerates the search as a whole. This hybrid approach is used to make a fast implementation for the Graph500 Benchmark [2], achieving 5.1 GTEPs at scale=28 (256M vertices with 4B undirected edges) on a quad-socket 40-core Intel Xeon compute node. It ranks 19th out of 50 on the November 2011 Graph500 Rankings.

BibTeX citation:

@techreport{Beamer:EECS-2011-117, Author = {Beamer, Scott and AsanoviÄ‡, Krste and Patterson, David A.}, Title = {Searching for a Parent Instead of Fighting Over Children: A Fast Breadth-First Search Implementation for Graph500}, Institution = {EECS Department, University of California, Berkeley}, Year = {2011}, Month = {Nov}, URL = {http://www.eecs.berkeley.edu/Pubs/TechRpts/2011/EECS-2011-117.html}, Number = {UCB/EECS-2011-117}, Abstract = {This report provides a summary of an efficient breadth-first search implementation that is advantageous for social networks. This implementation uses a hybrid approach, combining a conventional top-down algorithm along with a novel bottom-up algorithm. The bottom-up algorithm can dramatically reduce the number of edges examined, which in turn accelerates the search as a whole. This hybrid approach is used to make a fast implementation for the Graph500 Benchmark [2], achieving 5.1 GTEPs at scale=28 (256M vertices with 4B undirected edges) on a quad-socket 40-core Intel Xeon compute node. It ranks 19th out of 50 on the November 2011 Graph500 Rankings.} }

EndNote citation:

%0 Report %A Beamer, Scott %A AsanoviÄ‡, Krste %A Patterson, David A. %T Searching for a Parent Instead of Fighting Over Children: A Fast Breadth-First Search Implementation for Graph500 %I EECS Department, University of California, Berkeley %D 2011 %8 November 15 %@ UCB/EECS-2011-117 %U http://www.eecs.berkeley.edu/Pubs/TechRpts/2011/EECS-2011-117.html %F Beamer:EECS-2011-117