Graph algorithms are becoming increasingly important, with applications covering a wide range of scales, from social network analysis on warehouse-scale computers to recognition tasks on mobile devices. The Berkeley Graph Algorithm Platform (GAP) Project spans the entire stack, and it aims to accelerate graph algorithms through software optimization and hardware acceleration. Some of the outcomes so far are:
- "Searching for a Parent Instead of Fighting Over Children: A Fast Breadth-First Search Implementation for Graph500", Scott Beamer, Krste Asanović, and David Patterson, Technical Report UCB/EECS-2011-117, EECS Department, University of California, Berkeley, November 2011. TR
- "Portable Parallel Performance from Sequential, Productive, Embedded Domain-Speciﬁc Languages", Shoaib Kamil, Derrick Coetzee, Scott Beamer, Henry Cook, Ekaterina Gonina, Jonathan Harper, Jeffrey Morlan, and Armando Fox, Symposium on Principles and Practice of Parallel Programming (PPoPP), New Orleans, Louisiana, February 2012. ACM
- "Direction-Optimizing Breadth-First Search", Scott Beamer, Krste Asanović, and David Patterson, International Conference on High Performance Computing, Networking, Storage and Analysis (SC), Salt Lake City, Utah, November 2012. ACM errata corrected
Best Student Paper Finalist
- "Distributed Memory Breadth-First Search Revisited: Enabling Bottom-Up Search", Scott Beamer, Aydın Buluç, Krste Asanović, and David Patterson, Workshop on Multithreaded Architectures and Applications (MTAAP), at the International Parallel & Distributed Processing Symposium (IPDPS), Boston, May 2013. IEEE
- "Direction-Optimizing Breadth-First Search", Scott Beamer, Krste Asanović, and David Patterson, Journal of Scientific Programming, 21(3-4), October 2013. IOS
- The GAP Benchmark Suite, Scott Beamer, Krste Asanović, and David Patterson, arXiv:1508.03619 [cs.DC], 2015. arXiv
- "Locality Exists in Graph Processing: Workload Characterization on an Ivy Bridge Server", Scott Beamer, Krste Asanović, and David Patterson, International Symposium on Workload Characterization (IISWC), Atlanta, October 2015. PDF IEEE
Best Paper Award
- "GAIL: The Graph Algorithm Iron Law", Scott Beamer, Krste Asanović, and David Patterson, Workshop on Irregular Applications: Architectures and Algorithms (IA^3), at the International Conference for High Performance Computing, Networking, Storage and Analysis (SC), Austin, November 2015. PDF ACM
- "Distributed-Memory Breadth-First Search on Massive Graphs", Aydın Buluç, Scott Beamer, Kamesh Madduri, Krste Asanović, and David Patterson, In D. Bader, editor, Parallel Graph Algorithms, CRC Press, Taylor-Francis, 2016 (in press). PDF site
- "Understanding and Improving Graph Algorithm Performance", Scott Beamer, Ph.D. Thesis, University of California Berkeley, September 2016. PDF TR
SPEC Kaivalya Dixit Distinguished Dissertation Award
- Reducing Pagerank Communication via Propagation Blocking, Scott Beamer, Krste Asanović, and David Patterson, International Parallel & Distributed Processing Symposium (IPDPS), Orlando, May 2017.
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 Nokia, NVIDIA, Oracle, and Samsung.
Research partially funded by DARPA Award Number HR0011-12-2-0016, the Center for Future Architecture Research, a member of STARnet, a Semiconductor Research Corporation program sponsored by MARCO and DARPA, and ASPIRE Lab industrial sponsors and affiliates Intel, Google, Huawei, Nokia, NVIDIA, Oracle, and Samsung. Any opinions, findings, conclusions, or recommendations in this paper are solely those of the authors and does not necessarily reflect the position or the policy of the sponsors.