GPS: A Graph Processing System

Overview

In systems such as GPS and Pregel, the input graph (directed, possibly with values on edges) is distributed across machines and vertices send each other messages to perform a computation. Computation is divided into iterations called supersteps. Analogous to the map() and reduce() functions of the MapReduce framework, in each superstep a user-defined function called vertex.compute() is applied to each vertex in parallel. The user expresses the logic of the computation by implementing vertex.compute(). This design is based on Valiant's Bulk Synchronous Parallel model of computation. A detailed description can be found in the original Pregel paper.

There are five main differences between Pregel and GPS:

• GPS is open-source.
• GPS extends Pregel's API with a master.compute() function, which enables easy and efficient implementation of algorithms that are composed of multiple vertex-centric computations, combined with global computations.
• GPS has an optional dynamic repartitioning scheme, which reassigns vertices to different machines during graph computation to improve performance, based on observing communication patterns.
• GPS has an optimization called LALP that reduces the network I/O in when running certain algorithms on real-world graphs that have skewed degree distributions.
• GPS programs can be implemented using a higher-level domain specific language called Green-Marl, and automatically compiled into native GPS code. Green-Marl is a traditional imperative language with several graph-specific language constructs that enable intuitive and simple expression of complicated algorithms.

Using GPS we have studied the effects on system performance of different ways of partioning the graph, both before the graph computation starts and during the computation. A detailed description of GPS and our work on partitioning can be found in our online technical report.

Using our Green-Marl compiler, we were able to implement several algorithms such as Approximate Betweenness Centrality and Conductance, whose native GPS implmentations are very challenging. A detailed description of our work on the Green-Marl compiler can be found in our Green-Marl-to-GPS tech report. Details about Green-Marl can be found in the original Green-Marl paper.

We have been exploring how to solve some of the fundamental graph problems on Pregel-like systems, such as computing strongly connected components (SCC), or minimum spanning trees in large-scale graphs. A detailed description of our work on computing SCCs can be found here.

The GPS project is supported by the National Science Foundation (grant IIS-0904497), KAUST, and an Amazon Web Services Research Grant.

The GPS source code is available as open-source code under the BSD license. The source code can be found here. Here is the GPS documentation site containing information about how to download, set-up and run GPS as well as the GPS extensions to Pregel and the GPS API. Please join the user group stanfordgpsusers @ googlegroups.com for any questions/problems you might have in setting GPS up (the email group is public to everyone, you can join the group from Google Groups website).