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://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},
    Institution = {EECS Department, University of California, Berkeley},
    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