PaperlayerView exact revision on arXiv

Source-linked AI summary

Gunrock: A High-Performance Graph Processing Library on the GPU

Yangzihao Wang, Andrew Davidson, Yuechao Pan, Yuduo Wu, Andy Riffel, John D. Owens

arXiv:1501.05387v6cs.DC

TL;DR

GPU graph analytics is challenging because irregular graph structure complicates data access and control flow, while GPU programming is complex. Gunrock addresses this with a high-level, bulk-synchronous, frontier-based abstraction coupled with GPU optimizations, achieving performance comparable to hardwired primitives and outperforming prior programmable GPU abstractions. Five graph primitives were evaluated experimentally.

  • Problem

    Irregular graph data access and control flow, together with GPU programming complexity, challenge programmable high-performance graph libraries.

  • Method

    Gunrock uses a high-level, bulk-synchronous, data-centric abstraction centered on vertex or edge frontiers, with GPU primitives and optimizations such as kernel fusion.

  • Results

    Gunrock’s graph primitives achieve comparable performance to hardwired GPU counterparts and significantly outperform previous programmable GPU abstractions.

  • Takeaways & Limitations

    Gunrock provides a general, straightforward-to-program, and fast framework for developing graph primitives with minimal GPU programming knowledge.

  • Takeaways & Limitations

    Gunrock is implemented for single-GPU computation and graphs that fit into GPU memory; future work targets host memory, multi-GPU, and distributed scaling.

Abstract

from arXiv · show

For large-scale graph analytics on the GPU, the irregularity of data access and control flow, and the complexity of programming GPUs have been two significant challenges for developing a programmable high-performance graph library. "Gunrock", our graph-processing system designed specifically for the GPU, uses a high-level, bulk-synchronous, data-centric abstraction focused on operations on a vertex or edge frontier. Gunrock achieves a balance between performance and expressiveness by coupling high performance GPU computing primitives and optimization strategies with a high-level programming model that allows programmers to quickly develop new graph primitives with small code size and minimal GPU programming knowledge. We evaluate Gunrock on five key graph primitives and show that Gunrock has on average at least an order of magnitude speedup over Boost and PowerGraph, comparable performance to the fastest GPU hardwired primitives, and better performance than any other GPU high-level graph library.

1. Introduction

Gunrock addresses the difficulty of high-performance GPU graph analytics with a high-level, data-centric frontier abstraction and GPU-specific optimizations. Its APIs support expressive graph primitives while retaining performance comparable to hardwired implementations.

  • Gunrock centers programming on frontier operations rather than sequencing computation steps.
  • GPU graph analytics is difficult because graph data causes irregular data access and control flow.
  • Its data-centric abstraction incorporates kernel fusion, push-pull traversal, idempotent traversal, and priority queues.
  • Simple, flexible APIs express a wide range of graph processing primitives at a high level of abstraction.
  • Gunrock’s graph primitives achieve comparable performance to hardwired counterparts and significantly outperform previous programmable GPU abstractions.
  • The paper provides detailed experimental comparisons with several CPU and GPU implementations.

2. Related Work

Prior graph frameworks span CPU systems, hardwired GPU primitives, and high-level GPU models, each exposing trade-offs in scalability, programmability, generality, or performance. Gunrock is positioned against these limitations through a programmable GPU abstraction designed to retain high performance.

  • Single-node and Distributed CPU-based Systems: Single-node CPU systems are widely used but their serial or coarse-grained models suit GPUs poorly.
  • Single-node and Distributed CPU-based Systems: Distributed CPU systems improve scalability but incur substantial communication costs and remain poorly suited to GPUs.
  • GPU Hardwired Implementations: Hardwired GPU primitives deliver best-in-class performance but are difficult to program and generalize poorly across graph primitives.
  • High-level GPU Programming Models: High-level GPU frameworks often inherit CPU-oriented models and generally trail hardwired primitives because of framework overheads and limited primitive-specific optimization.
  • Single-node and Distributed CPU-based Systems: Pregel uses bulk synchronous parallelism with vertex-centric message passing, supporting scalability and fault tolerance.
  • Single-node and Distributed CPU-based Systems: Green-Marl hides complexity and provides graph-specific optimizations but does not support arbitrary vertex sets each iteration.
  • GPU Implementations and Libraries: GPU graph research includes adaptive load balancing for BFS and specialized representations or preprocessing for irregular memory access.

3. Background & Preliminaries

Graph processing operates on vertices, edges, and frontiers within GPU architectures built for massive parallelism. Efficient irregular graph computation requires memory-efficient data layouts, reduced divergence, and minimized scattered accesses.

  • A graph consists of vertices and edges, while vertex and edge frontiers represent subsets of those elements.
  • NVIDIA GPUs use massive parallelism, SIMT execution, kernels, and lockstep warps to achieve high throughput and hide memory latency.
  • Irregular GPU graph problems benefit from coalesced memory access, effective memory-hierarchy use, minimized warp divergence, and fewer scattered reads and writes.
  • Gunrock uses structure-of-array data structures and supports CSR or edge-list graph representations for coalesced access and operation-specific processing.

4. The Gunrock Abstraction and Implementation

Gunrock represents graph computation as bulk-synchronous operations over vertex or edge frontiers, combining flexible APIs with GPU-oriented optimizations for irregular workloads. Its implementation centers on advance and filter operators, kernel fusion, generalized load balancing, and frontier-based traversal alternatives.

  • 4.1 Gunrock’s Abstraction: Gunrock targets iterative convergent graph processes and treats the frontier of active vertices or edges as the central data structure.Programmers specify frontier manipulations rather than sequencing computation steps directly.
  • 4.1 Gunrock’s Abstraction: Gunrock supports both vertex and edge frontiers and can switch between them within one graph primitive, unlike vertex-focused GAS and Pregel abstractions.This flexibility allows a vertex frontier to generate a neighboring edge frontier directly.
  • 4.1 Gunrock’s Abstraction: Bulk-synchronous advance, filter, and compute steps manipulate frontiers while exposing parallel operations that avoid expensive fine-grained synchronization.Advance visits neighbors, whereas filter selects or compacts frontier elements according to programmer-specified criteria.
  • 4.3 Gunrock’s API and its Kernel-Fusion Optimization: Compile-time functor integration fuses regular computation with irregular advance and filter kernels, hiding implementation complexity while improving efficiency.Cond functors return booleans for filtering, while apply functors perform per-element computation.
  • 4.4 Workload Mapping and Load Balancing Details: Gunrock generalizes prior workload-distribution strategies into a generic advance operator and combines them with pull-based traversal.Its load-balancing strategies address irregular neighbor-list sizes and support both input- and output-oriented work grouping.
  • 4.5 Gunrock’s Optimizations: Pull traversal improves BFS by filtering unvisited vertices against predecessors in the current frontier, producing speedups of 1.52x on scale-free graphs and 1.28x on small-degree-large-diameter graphs.Gunrock converts the current frontier to a bitmap and uses advance to pull from valid predecessors.

5. Applications

Gunrock expresses several graph applications by composing frontier-based advance, filter, and compute operations, while extending the model to additional primitives and ranking algorithms.

  • Breadth-first search: BFS maps Merrill et al.’s expand and contract phases to Gunrock’s advance and filter operators, with idempotent traversal and discovery-reducing heuristics in the fastest implementation.The base implementation uses atomics to prevent concurrent discovery; the fastest version avoids them through idempotent advance.
  • Single-source shortest path: SSSP uses advance and filter iterations to relax distances with AtomicMin, while Gunrock generalizes load balancing and priority-queue optimizations from Davidson et al.The computation differs from BFS because edge relaxations retain minimal distance values.
  • Betweenness centrality: Betweenness centrality uses two phases: forward BFS-style accumulation of shortest-path counts, followed by backward traversal to compute dependency scores.Gunrock achieves competitive performance on scale-free graphs with the latest hardwired BC algorithm, while leaving task parallelism for future work.
  • Connected components: Connected components repeatedly applies edge-frontier filtering for hooking until component IDs stabilize, then uses vertex filtering for pointer-jumping.The hardwired comparison uses hooking and pointer-jumping, while Gunrock’s implementation expresses hooking with an edge-frontier filter.
  • PageRank: PageRank starts with all vertices, repeatedly advances to update rankings and filters converged vertices, using AtomicAdd operations.Iterations continue until all vertices have converged.
  • Other applications: Gunrock’s advance operator also supports bipartite ranking algorithms and has been used for Personalized PageRank, SALSA, and HITS, alongside other developing primitives.Additional work includes minimum spanning tree, maximal independent set, graph coloring, community detection, and graph matching.

6. Experiments & Results

Gunrock is evaluated across diverse graph datasets and primitives against CPU libraries, GPU frameworks, and hardwired GPU implementations. Its performance advantages are strongest on irregular graphs, while some optimizations depend on graph degree distribution.

  • Evaluation setup: Experiments used six real-world and generated undirected graphs spanning regular to scale-free topologies, with random SSSP edge weights from 1 to 64.The setup used an NVIDIA K40c GPU, and all results ignored data-transfer time.
  • Optimization sensitivity: Graphs with uniformly low degree exposed less parallelism and showed smaller gains over CPU-based methods.This qualifies the broader performance results across datasets.
  • CPU comparisons: Gunrock achieved 6x–337x average speedup over BGL and PowerGraph across all evaluated primitives.Performance was generally comparable to Ligra, while differences for SSSP and BC reflected algorithm and traversal choices.
  • GPU comparisons: Gunrock’s BFS, BC, and SSSP performance was comparable to or better than hardwired GPU implementations, but CC was 5x slower.The CC gap resulted from irregular control flow in hooking and pointer-jumping phases.
  • Performance factors: Gunrock’s performance advantage was attributed to integrated load-balanced traversal and a GPU-specific programming model.Its memory footprint matched Medusa and exceeded MapGraph, with data size α|E| + β|V|.
  • Optimization sensitivity: Optimization benefits varied with degree distribution: load-balanced traversal and direction-optimal traversal favored irregular social graphs, while Thread-Warp-CTA favored small-degree graphs.Degree distributions can guide strategy selection before computation begins.

7. Future Work

Future work targets graph settings and operations that remain difficult for Gunrock, including dynamic topology, neighborhood reductions, kernel fusion, and scaling beyond one GPU. These limitations define the main boundaries of the current system.

  • Evaluation context: Figure 7 compares execution-time speedups across six graph inputs and five libraries or hardwired algorithms, marking Gunrock wins with black dots.White dots indicate cases where Gunrock is slower.
  • Evaluation context: Figure 8 compares workload mapping, idempotent traversal, and forward versus direction-optimal traversal optimizations.The figure organizes three performance comparisons across these design choices.
  • Dynamic graphs: Gunrock’s generalized support for dynamic graphs that change topology during computation remains unsolved on GPUs.Existing primitives may modify topology internally, but generalized dynamic-graph support is still unresolved.
  • Operations: Neighborhood and global operations generally require less-efficient atomic operations, motivating a gather-reduce operator and frontier sampling.Sampling could support rough or seeded solutions for faster convergence.
  • Kernel fusion: Gunrock offers more kernel-fusion opportunities than GAS+GPU systems but does not match hardwired implementations, leaving fusion as its largest performance gap.The general problem remains unsolved.
  • Scalability: Gunrock currently supports only single-GPU computation for graphs that fit in GPU memory.Future scaling directions include host memory, multiple GPUs, and distributed multi-node systems.

8. Conclusions

Gunrock raises graph programming abstraction around GPU-aware frontier operations while retaining performance and flexibility. Its integrated optimizations support general, straightforward implementations that approach hardwired performance.

  • Conclusion: Gunrock’s frontier-focused, data-centric abstraction maps naturally to the GPU and provides both performance and programming flexibility.The abstraction centers graph computation on actively participating vertices or edges.
  • Conclusion: Integrated load balancing, direction-optimal traversal, and priority queues make Gunrock general, straightforward to program, and fast.New primitives require only a few hundred lines of code and minimal GPU programming knowledge.

A.1 Abstract

The artifact packages Gunrock’s current graph primitives and execution scripts for reproducing selected performance results. It also provides output files for validating those results.

  • Artifact contents: The artifact contains executables for Gunrock’s existing graph primitives and shell scripts for running them.These materials correspond to the latest GitHub version.
  • Artifact validation: The scripts support runtime and edge-throughput results from Table 3 and allow validation through generated text outputs.Users can run the test scripts and inspect the corresponding output files.

A.2.1 Check-list (artifact meta information) •

The artifact provides GPU graph-processing experiments, source code, datasets, runtime outputs, and execution details. It evaluates five graph primitives and reports runtime and/or edge throughput.

  • The evaluated graph primitives are breadth-first search, single-source shortest path, betweenness centrality, Pagerank, and connected component.
  • The program uses CUDA and C/C++ code compiled with gcc and nvcc using the -O3 flag.Host code uses gcc 4.8.4, while device code uses nvcc 7.0.27.
  • The artifact uses CUDA executables and publicly available matrix market files in an Ubuntu 12.04 environment with CUDA and GPU Computing SDK installed.
  • Experiments run on any GPU with compute capability ≥3.0, with an NVIDIA K40c GPU recommended, and report runtime and/or edge throughput.
  • The experiment workflow is to clone the project, download datasets, run test scripts, and observe the results.

A.2.2 How delivered

Gunrock is delivered as an open-source GPU graph-processing library with documented source code, build instructions, datasets, and experiment scripts. Users build the library, generate executables, run five graph primitives, and inspect per-dataset results.

  • Gunrock is an Apache 2.0 open-source library hosted on Github with code, API specifications, build instructions, and design documentation.
  • Gunrock requires an NVIDIA GPU with compute capability no less than 3.0, Boost, and CUDA version no less than 5.5.It has been tested on Ubuntu 12.04/14.04 and is expected to run correctly under other Linux distributions.
  • Datasets are publicly available or generated with standard graph-generation software, and users can obtain them through scripts after building Gunrock.The artifact also provides a generated rgg dataset and invites users to try other datasets or generate rgg/R-M graphs.
  • Users follow Github build instructions, clone the repository with its submodules, install Boost and CUDA, and compile Gunrock with CMake and make.The executables are built under gunrock_build/bin and the shared library under gunrock_build/lib.
  • Running the dataset and test scripts downloads the six paper datasets, executes five graph primitives, and stores results in output text files organized under BFS, SSSP, BC, PR, and CC directories.
  • BFS and SSSP report runtime and edge throughput, whereas BC, Pagerank, and CC report runtime only.
Loading 1501.05387v6…