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.

Unfortunately, due to a lack of locality, graph applications are often memory-bound on shared-memory systems or communication-bound on clusters. These bottlenecks leave much of the hardware idle, leading most graph algorithms to execute inefficiently on current platforms.

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:

Much of the ongoing work for the GAP project is designing hardware specialized for graph algorithms. Since most graph algorithms are memory-bound, much of this work is focused on memory system design rather than processor design.

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

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.