GAP logo

Graph Algorithm
Platform

Scott Beamer   •   Aydın Buluç (LBL)
David Patterson   •   Krste Asanović

Overview

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:

direction-optimizing BFS GBSP GAP benchmark
Direction-Optimizing Breadth-First Search
fastest BFS for low-diameter graphs
Workload Characterization
identify graph processing bottlenecks
GAP Benchmark Suite
standardize evaluations with specification + reference code
GBSP Graph Algorithm Iron Law Real-world graph datasets
GBSP
graph DSL embedded in Python that achieves native performance
Graph Algorithm
Iron Law (GAIL)
understand graph performance tradeoffs
Real-world Graphs
links to graph datasets

Publications

  1. "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
  2. "Portable Parallel Performance from Sequential, Productive, Embedded Domain-Specific 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
  3. "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
  4. "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
  5. "Direction-Optimizing Breadth-First Search", Scott Beamer, Krste Asanović, and David Patterson, Journal of Scientific Programming, 21(3-4), October 2013. IOS
  6. The GAP Benchmark Suite, Scott Beamer, Krste Asanović, and David Patterson, arXiv:1508.03619 [cs.DC], 2015. arXiv
  7. "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
  8. "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
  9. "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
  10. "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
  11. Reducing Pagerank Communication via Propagation Blocking, Scott Beamer, Krste Asanović, and David Patterson, International Parallel & Distributed Processing Symposium (IPDPS), Orlando, May 2017. PDF
    Best Paper Award

Funding

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.