Scott Beamer and Krste Asanović and David A. Patterson

EECS Department, University of California, Berkeley

Technical Report No. UCB/EECS-2011-117

November 15, 2011

http://www2.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},
    Year= {2011},
    Month= {Nov},
    Url= {http://www2.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://www2.eecs.berkeley.edu/Pubs/TechRpts/2011/EECS-2011-117.html
%F Beamer:EECS-2011-117