Graphs are fundamental data structures for modeling social interactions, computer networks, and physical simulations. Graph analytic libraries provide optimized primitives and application programming interfaces (APIs) for performing computation on large-scale graph datasets. This paper describes Gunrock, a high-performance graph analytic library for general-purpose graph operations using graphic processing units (GPUs). Gunrock improves programmability by enabling developers to describe common graph analytic workloads using four primitive operations. In addition, the authors describe optimized implementations for each primitive on commodity GPUs.

Several implementations of large-scale graph analytic libraries are already available for single-node and distributed central processing unit (CPU) systems such as Boost, Pregel, GiGraph, and GraphLab. More recently, several efficient implementations of fundamental graph applications such as breadth-first search, connected components, and triangle counting have been developed for GPUs. Section 2 provides an excellent survey of graph analytic libraries.

Whereas previous approaches have modeled graph operations using a series of synchronized computations, the novelty of this work lies in the fact that such operations are performed using progressive updates to a data structure that consists of nodes or edges (referred to as a frontier). Unlike previous approaches that only perform vertex-centric computations, Gunrock allows operations on vertices or edges. The framework provides four primitives for expressing common graph analytic operations: advance, filter, segmented intersection, and compute. The authors illustrate these operations with an example, single-source shortest path, and compare the implementation with existing CPU-based and GPU-based graph analytic frameworks (section 3). An important issue addressed here is the efficient mapping of irregular operations on GPUs. Several strategies are described, including coarse-grained load balancing, dynamic grouping, and adjusting traversal direction.

The Gunrock graph analytic model suits a broad class of graph analytic algorithms as demonstrated by experiments performed on real-world datasets. An open-source version of the library is available for popular GPU platforms.