Programming Model

This page describes the programming model we use in Gunrock.

Gunrock targets graph computations that are generally expressed as “iterative convergent processes”. By “iterative,” we mean operations that may require running a series of steps repeatedly; by “convergent,” we mean that these iterations allow us to approach the correct answer and terminate when that answer is reached. Many graph-computation programming models target a similar goal.

Many of these programming models focus on sequencing steps of computation. Gunrock differs from these programming models in its focus on manipulating a data structure. We call this data structure a frontier of vertices or edges. The frontier represents the subset of vertices or edges that is actively participating in the computation. Gunrock operators input one or more frontiers and output one or more frontiers.

Generically, graph operations can often be expressed via a push abstraction (graph elements “push” local private updates into a shared state) or a pull abstraction (graph elements “pull” updates into their local private state) (Besta et al. publication on push-vs.-pull, HPDC ‘17). Gunrock’s programming model supports both of these abstractions. (For instance, Gunrock’s direction-optimized Breadth-First Search (BFS) and PageRank (PR) support both push and pull BFS phases. Mini-Gunrock supports pull-based BFS and PR.) Push-based approaches may or may not require synchronization (such as atomics) for correct operation; this depends on the primitive. Gunrock’s idempotence optimization (within its BFS implementation) is an example of a push-based primitive that does not require atomics.