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. Warehouse-scale computers run graph algorithms that reason about vast amounts of data, with applications including analytics and recommendation systems. On mobile clients, graph algorithms are important components of recognition and machine-learning applications.

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:

Other Useful Links:

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
  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. "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

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.