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 foccused on memory system design rather than processor design.
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.