Searching for a Parent Instead of Fighting Over Children: A Fast Breadth-First Search Implementation for Graph500
Title | Searching for a Parent Instead of Fighting Over Children: A Fast Breadth-First Search Implementation for Graph500 |
Publication Type | Technical Report |
Year of Publication | 2011 |
Authors | Beamer, S., Asanović K., & Patterson D. |
Other Numbers | 3452 |
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. |
URL | https://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 |