Direction-Optimizing Breadth-First Search
Title | Direction-Optimizing Breadth-First Search |
Publication Type | Conference Paper |
Year of Publication | 2012 |
Authors | Beamer, S., Asanović K., & Patterson D. |
Other Numbers | 3338 |
Abstract | Breadth-First Search is an important kernel used bymany graph-processing applications. In many of these emergingapplications of BFS, such as analyzing social networks, theinput graphs are low-diameter and scale-free. We propose ahybrid approach that is advantageous for low-diameter graphs,which combines a conventional top-down algorithm along witha novel bottom-up algorithm. The bottom-up algorithm candramatically reduce the number of edges examined, which inturn accelerates the search as a whole. On a multi-socket server,our hybrid approach demonstrates speedups of 3.37.8 on a rangeof standard synthetic graphs and speedups of 2.44.6 on graphsfrom real social networks when compared to a strong baseline.We also typically double the performance of prior leading sharedmemory (multicore and GPU) implementations. |
Acknowledgment | Research supported by Microsoft (Award #024263) andIntel (Award #024894) funding and by matching funding byU.C. Discovery (Award #DIG07-10227). Additional supportcomes from Par Lab affiliates National Instruments, Nokia,NVIDIA, Oracle, and Samsung. Partially funded by DARPAAward HR0011-11-C-0100. |
URL | https://www.icsi.berkeley.edu/pubs/arch/directionoptimizing12.pdf |
Bibliographic Notes | Proceedings of the International Conference for High Performance Computing, Networking, Storage, and Analysis (SC12), Article No. 12, Salt Lake City, Utah |
Abbreviated Authors | S. Beamer, K. Asanovi?, and D. Patterson |
ICSI Research Group | Architecture |
ICSI Publication Type | Article in conference proceedings |