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

TitleSearching for a Parent Instead of Fighting Over Children: A Fast Breadth-First Search Implementation for Graph500
Publication TypeTechnical Report
Year of Publication2011
AuthorsBeamer, S., Asanović K., & Patterson D.
Other Numbers3452
Abstract

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

Acknowledgment

The authors would like to thank Intel for their hardware donations which enabled this work andJason Reidy and Henry Gabb for providing access. Research supported by Microsoft (Award#024263) and Intel (Award #024894) funding and by matching funding by U.C. Discovery(Award #DIG07-10227). Additional support comes from Par Lab affiliates National Instruments,Nokia, NVIDIA, Oracle, and Samsung.

URLhttps://www.icsi.berkeley.edu/pubs/arch/ICSI_searchingforaparent11.pdf
Bibliographic Notes

Technical Report UCB/EECS-2011-117, EECS Department, University of California, Berkeley

Abbreviated Authors

S. Beamer, K. Asanovi?, and D. Patterson

ICSI Research Group

Architecture

ICSI Publication Type

Technical Report