Source-linked AI summary
Gunrock: GPU Graph Analytics
Yangzihao Wang, Yuechao Pan, Andrew Davidson, Yuduo Wu, Carl Yang, Leyuan Wang, Muhammad Osama, Chenshan Yuan, Weitang Liu, Andy T. Riffel, John D. Owens
TL;DR
Irregular graph access and control flow, alongside GPU programming complexity, challenge the development of programmable high-performance graph libraries. Gunrock uses a high-level, frontier-focused model with integrated GPU optimizations. Its primitives are on par with hardwired implementations and faster than other programmable GPU graph libraries, while its current design targets a single GPU.
Problem
Method
Gunrock uses bulk-synchronous operations on vertex or edge frontiers and integrates load-balancing and work-efficiency strategies into this data-centric model.
Source: §1 · p. 2Results
Gunrock’s framework is on par with hardwired primitives and faster than any other programmable GPU graph library.
Source: §8.3 · p. 47Takeaways & Limitations
The paper shows that GPU graph analytics can be both simple and efficient with an appropriate high-level model and low-level optimizations.
Source: §8.3 · p. 47The current model is designed and optimized for a single GPU; multi-GPU work on one node exists, but larger machines remain unaddressed.
Source: §8.1 · p. 42
Abstract
from arXiv · showhide
For large-scale graph analytics on the GPU, the irregularity of data access and control flow, and the complexity of programming GPUs, have presented two significant challenges to 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 characterize the performance of various optimization strategies and evaluate Gunrock's overall performance on different GPU architectures on a wide range of graph primitives that span from traversal-based algorithms and ranking algorithms, to triangle counting and bipartite-graph-based algorithms. The results show that on a single GPU, Gunrock has on average at least an order of magnitude speedup over Boost and PowerGraph, comparable performance to the fastest GPU hardwired primitives and CPU shared-memory graph libraries such as Ligra and Galois, and better performance than any other GPU high-level graph library.
1 INTRODUCTION
Gunrock addresses the irregularity of graph processing on GPUs with a high-level, frontier-focused programming model. It combines that abstraction with GPU optimizations to balance programmability and performance.
1 INTRODUCTION
- Gunrock’s bulk-synchronous operations manipulate a frontier—the subset of vertices or edges currently participating in computation.Operations either compute on frontier values or generate a new frontier.Source: §1 · p. 2
- Graph irregularity in data access and control flow makes efficient GPU implementation challenging across traversal, ranking, connected-components, and triangle-counting primitives.The paper focuses on BFS, SSSP, BC, PageRank, CC, and TC.Source: §1 · p. 2
- Gunrock integrates load-balancing and work-efficiency strategies so programmers specify frontier operations rather than how work is distributed.The contribution includes kernel fusion, push-pull traversal, idempotent traversal, and priority queues.Source: §1 · p. 2
- Gunrock’s primitives achieve performance comparable to hardwired counterparts and significantly outperform previous programmable GPU abstractions.The paper also presents APIs for expressing a wide range of graph-processing primitives at a high level.Source: §1 · pp. 2–3
2 RELATED WORK
Related work spans CPU graph systems, specialized parallel algorithms, and high-level GPU frameworks. The paper contrasts their programming models and performance trade-offs with Gunrock’s design.
2 RELATED WORK
- The landscape includes CPU systems, distributed frameworks, hardwired GPU primitives, and high-level GPU models, each with distinct performance or programmability trade-offs.The discussion notes communication costs in distributed systems, implementation difficulty and limited generality for hardwired primitives, and performance overheads in high-level GPU frameworks.Source: §2 · p. 3
2.1 Single-node and Distributed CPU-based Systems
- CPU systems include BGL, Pregel-like message-passing, GraphLab and PowerGraph’s GAS model, and shared-memory systems such as Ligra and Galois.GraphLab supports asynchronous computation; PowerGraph uses vertex cuts for power-law graphs, while Galois requires users to generate active elements.Source: §2.1 · pp. 3–4
2.2 Specialized Parallel Graph Algorithms
- Specialized GPU work develops algorithm-specific strategies for BFS, connected components, betweenness centrality, SSSP, and triangle counting.Examples include adaptive load balancing and direction optimization for BFS, dynamic work selection for BC, and set intersections for triangle counting.Source: §2.2 · pp. 4–5
2.3 High-level GPU Programming Models
- Message-passing GPU frameworks include Medusa, Totem, and Frog, with trade-offs involving load balance, algorithm generality, or per-iteration edge visits.Medusa lacks fine-grained traversal load balancing; Totem’s API limits algorithm generality, while Frog requires visiting all edges each iteration.Source: §2.3 · pp. 5–6
- GAS-based GPU frameworks include VertexAPI2, MapGraph, and CuSha, which combine operator abstractions with different load-balancing strategies.The surveyed systems also include nvGRAPH, which expresses graph computation through semi-ring SpMV operations.Source: §2.3 · p. 6
- Gunrock is described as the only high-level GPU graph system supporting vertex- and edge-centric operations with runtime fine-grained load balancing and no input preprocessing.The paper frames its programming goals as high-level abstraction, flexibility across tasks, and alignment with GPU execution.Source: §2.3 · pp. 6–7
3 DATA-CENTRIC ABSTRACTION
Gunrock expresses iterative graph algorithms as bulk-synchronous operations on active vertex or edge frontiers, rather than primarily as sequences of computation steps. Its operators and APIs pair this abstraction with GPU-specific optimization opportunities and support comparisons with alternative graph-processing models.
3 DATA-CENTRIC ABSTRACTION
- Gunrock’s data-centric model manipulates active vertex or edge frontiers in bulk-synchronous steps, rather than focusing on sequencing computation.Individual operations within a step can run in parallel, and primitives are built from sequences of steps.Source: §3 · pp. 7–8
- Gunrock supports switching between vertex and edge frontiers, while Pregel and PowerGraph’s abstractions cannot support edge-centric operations or require heavy redundancy to do so.Source: §3 · pp. 7–8
- The four operators—advance, filter, segmented intersection, and compute—transform frontiers through traversal, selection, intersection, and per-item computation.Advance visits neighbors; filter selects or compacts items; segmented intersection supports triangle counting; compute applies programmer-defined operations across frontier elements.Source: §3 · pp. 8–9
- Unequal vertex degrees and shared neighbors make advance irregularly parallel, making efficient advance the most significant challenge of a GPU implementation.Source: §3 · p. 9
- In SSSP, advance distributes neighbor-edge work, compute updates distances, and filter forms the next frontier, optionally using a two-level priority queue for delta-stepping.The example assumes non-negative edge weights.Source: §3 · pp. 10–11
3.1 Alternative Abstractions
- Compared with GAS, Gunrock’s frontier operations accommodate direction-optimizing traversal and two-level priority queues; Pregel’s vertex-centric parallelism can load-balance poorly on uneven-degree graphs.Gunrock also supports direct communication and both push- and pull-based traversal.Source: §3.1 · p. 12
- Gunrock’s APIs expose fusion opportunities, which the authors identify as crucial for performance and absent from other programmable GPU graph libraries.The program structure separates problem data, user-defined functors, and an enactor that specifies graph-operator calls.Source: §3.1 · pp. 13–14
- The data-centric model supports flexible vertex- or edge-oriented operations, decouples computation from traversal, and is described as extensible to multi-GPU execution.The authors report that their multi-GPU framework uses the model with an unchanged core single-GPU implementation.Source: §3.1 · p. 14
4 EFFICIENT GRAPH OPERATOR DESIGN
The section describes advance, filter, and segmented-intersection implementations, emphasizing allocation and load balancing for irregular graph work.
4.2 Filter
- Filter compacts a sparse input frontier into an output frontier, using local prefix sums and culling heuristics that also provide uniquification.The figure contrasts exact filtering via global scan-and-scatter with inexact filtering via local scan-and-scatter after heuristics.Source: §4.2 · p. 15, Figure 8 · p. 17
4.1 Advance
- Advance handles variable neighbor-list sizes by splitting allocation from load-balanced scatter and choosing coarse- or fine-grained work mapping and push or pull traversal.Prefix-sum computes scatter offsets; coarse-grained strategies group lists by size, while fine-grained strategies rebalance work across threads.Source: §4.1 · p. 15, Figure 7 · p. 16
4.3 Segmented Intersection
- Segmented intersection preallocates with prefix-sum, groups neighbor-list pairs by size for two load-balanced kernels, then compacts results and reduces intersection counts.Two-Small handles two small lists; Small-Large searches each item in the small list against the large list, and is also used when both lists are large.Source: §4.3 · pp. 16–17
5 SYSTEM IMPLEMENTATION AND OPTIMIZATIONS
Gunrock combines a frontier-centered abstraction with GPU-specific optimizations to balance performance and programmability. Its implementation addresses irregular workloads across traversal, synchronization, kernel-launch, and memory-access throughput.
5 SYSTEM IMPLEMENTATION AND OPTIMIZATIONS
- Gunrock’s frontier-focused abstraction is designed to integrate alternative implementations and optimizations while hiding load-balancing and work-efficiency strategies from programmers.The section organizes these optimizations around traversal, synchronization, kernel-launch, and memory-access throughput.Source: §5 · pp. 17–18
5.1 Graph Traversal Throughput Optimizations
- Traversal mapping combines static per-vertex work, dynamic thread/warp/block grouping, and global load-balanced partitioning, with topology-based heuristics selecting among strategies.Dynamic grouping targets neighbor lists of different sizes; global partitioning adds overhead but increases throughput on scale-free graphs, and the hybrid switches by average degree and frontier size.Source: §5.1.1 · pp. 19–20, §5.1.2 · p. 20, §5.1.3 · p. 21
- Push-pull traversal maintains active and unvisited frontiers, enabling pull to visit unvisited vertices with visited predecessors and produce updated frontiers.Gunrock’s two-frontier design supports flexible traversal operations; the paper reports a large BFS speedup on scale-free graphs.Source: §5.1.4 · pp. 22–23
- Gunrock’s priority-queue strategy splits an output frontier into near and far slices, processing the near slice before updating the priority function for the far slice.The paper reports using this optimization only in SSSP.Source: §5.1.5 · pp. 23–24
5.2 Synchronization Throughput Optimization
- For idempotent operations, Gunrock avoids costly atomics by permitting repeated computation and uses filter heuristics to reduce, but not eliminate, duplicate frontier entries.For reductions, it also uses hierarchical reduction or groups neighboring edges so a thread can accumulate partial results without atomics.Source: §5.2.1 · p. 25, §5.2.2 · p. 25
5.3 Kernel Launch Throughput Optimization
- Gunrock fuses regular computation functors into graph-operator kernels and can fuse traversal with filtering to reduce kernel launches and movement between double-buffered frontiers.The fused traversal operator launches advance and filter in one kernel.Source: §5.3 · p. 25
5.4 Memory Access Throughput Optimization
- Gunrock uses CSR for vertex-centric operations and permits COO for edge-centric operations; its structure-of-arrays layout and GPU memory hierarchy support coalesced access.CSR also lets prefix-sum reorganize sparse, uneven workloads into dense, uniform ones.Source: §5.4 · pp. 25–26
6 GRAPH APPLICATIONS
Gunrock builds graph primitives by composing advance, filter, segmented-intersection, and compute steps. The section illustrates this approach across traversal, ranking, connectivity, triangle counting, and subgraph matching.
6.1 Breadth-First Search (BFS)
- Gunrock expresses BFS with advance and filter, using load balancing and push-pull traversal while idempotent advance and filter heuristics address concurrent vertex discovery.The implementation can record each vertex’s source distance and/or predecessor.Source: §6.1 · p. 27
6.2 Single-Source Shortest Path
- Gunrock implements SSSP with advance and filter, atomically relaxing distances and using a priority queue to reorganize the frontier after each iteration.Its implementation generalizes load-balanced traversal and priority-queue strategies used in a specialized SSSP implementation.Source: §6.2 · p. 27
6.3 Betweenness Centrality
- Gunrock’s BC implementation computes shortest-path counts in a forward phase, then traverses the BFS frontier backward to compute dependency scores.The authors had not yet considered task parallelism within Gunrock, viewing it as apparently limited to BC.Source: §6.3 · p. 28
6.4 Connected Component Labeling
- Gunrock labels connected components through repeated hooking on edge frontiers followed by pointer-jumping on vertex frontiers, stopping each phase when component IDs no longer change.Source: §6.4 · p. 28
6.5 PageRank and Other Node Ranking Algorithms
- Gunrock computes PageRank by advancing over a frontier containing all vertices, accumulating values with AtomicAdd, and filtering vertices whose values have converged.Source: §6.5 · pp. 28–29
6.6 Triangle Counting
- Gunrock’s triangle-counting implementation follows the forward algorithm, using advance, filter, and segmented intersection to count intersections between neighbor lists.Keeping one orientation of each undirected edge—from the higher-degree endpoint to the lower-degree endpoint—halves the edges processed.Source: §6.6 · p. 29
6.7 Subgraph Matching
- Gunrock’s subgraph-matching implementation filters candidate vertices by label and degree, collects candidate edges with advance and filter, then joins using set intersection.Source: §6.7 · pp. 29–30
7 PERFORMANCE CHARACTERIZATION
This section characterizes Gunrock’s performance across graph structures and workloads, including who-to-follow and triangle-counting implementations, and compares it with CPU and GPU graph libraries. It also examines how traversal load balancing and optimization choices affect results, including transparent triangle-counting optimizations built around a segmented intersection operator intended for reuse.
7.1 Performance Summary
- Gunrock’s BFS-based primitives perform relatively better on seven scale-free graphs than on two small-degree, large-diameter graphs, with load balancing cited as a key reason.Runtimes scale roughly linearly with graph size for BFS, whereas frontier atomic contention limits BC, SSSP, and PageRank scalability; CC scalability is affected by race conditions as power-law graphs grow.Source: §7.1 · p. 31, Table 8 · p. 36
7.2 vs. CPU Graph Libraries
- Gunrock achieves 6x–337x speedup on average over BGL and PowerGraph, performs comparably to Ligra on most tested primitives, and shows greater advantages on traversal-based than dense, regular primitives.The Ligra comparison uses a 2-CPU machine; the reported SSSP inconsistency reflects Gunrock’s delta-stepping versus Ligra’s Bellman-Ford, while BC differences on four scale-free graphs reflect Ligra’s pull traversal.Source: Table 6 · p. 33, §7.2 · pp. 33–34
7.3 vs. Hardwired GPU Implementations and GPU Libraries
- Against hardwired GPU implementations, Gunrock is comparable or better on BFS, BC, and SSSP, but 5x slower (geometric mean) on CC.Gunrock’s CC iteration processes full edge lists in both hooking and pointer-jumping phases; its application code is smaller and clearer than other GPU graph libraries.Source: Table 6 · p. 33, §7.3 · p. 34
- Gunrock’s geometric-mean speedups over MapGraph are 4.679 for BFS, 12.85 for SSSP, 3.076 for PageRank, and 5.69 for CC.Gunrock outperforms CuSha on BFS and SSSP and matches its PageRank performance without preprocessing; on direction-optimized BFS for soc-LiveJournal, it delivers 1.83x more MTEPS than Totem’s 2-CPU, 2-GPU configuration.Source: §7.3 · p. 35
7.4 Optimization Strategies Performance Analysis
- Idempotence and direction-optimized traversal generally improve on baseline BFS, but combining them can hurt, and idempotence can reduce performance on graphs with degree standard deviation below 5.On low-degree-variation graphs, avoiding atomics offers little gain while idempotence adds filtering work; in direction-optimized traversal, it also adds global accesses to the visited-status bitmask.Source: §7.4 · pp. 36–37, Figure 19 · p. 37
- On nine datasets, LB CULL outperforms LB and TWC in traversal tests, but TWC performs better on two mesh-like SSSP graphs.LB CULL adapts load balancing to input-frontier size and fuses kernels; the paper cautions that it cannot conclude this strategy is always best.Source: §7.4 · pp. 37–38, Figure 20 · p. 37
7.5 GPU Who-To-Follow Performance Analysis
- Against Cassovary, Gunrock achieves speedups of up to 1000x on Google Plus and 14x on the representative 2009 Twitter graph.As graph size doubles, total runtime increases by an average of 1.684x and Money runtime by 1.454x; the implementation performs linear O(m + n) work by processing each vertex and edge exactly once.Source: §7.5.1 · pp. 39–40, Table 11 · p. 40, §7.5.2 · p. 40
7.6 GPU Triangle Counting Performance Analysis
- Gunrock’s triangle-counting kernel achieves geometric-mean speedups of 2.51× over Green et al.’s CPU implementation and 4.03× over their GPU implementation.Filtering edge-list generation and reforming the induced subgraph reduce five-sixths of the workload, while dynamic grouping supports GPU utilization; overall performance is comparable to the fastest shared-memory CPU implementation.Source: §7.6 · p. 41
- The optimizations are transparent to Gunrock’s data-centric model and apply to a segmented intersection graph operator that may support other graph primitives.The authors note that the intersection kernel is not yet quite optimal.Source: §7.6 · p. 42
8 CONCLUSION
Gunrock’s data-centric programming model supports a programmable, high-performance GPU graph analytics system. The conclusion identifies limits in its current scope and outlines directions for extending its execution model, operators, primitives, and graph support.
8.1 Limitations
- Gunrock’s current model targets a single GPU and static graphs, does not support graphs exceeding GPU global memory, and lacks extensive compiler optimizations such as kernel fusion and AST generation.Source: §8.1 · p. 42
8.2 Future Work
- Future scaling work includes multi-node execution, out-of-core support, and streaming, which would require more significant changes than out-of-core support.Gunrock has been extended to multiple GPUs on one node, but larger machines remain unaddressed; its data-centric model is expected to map naturally to streaming with a frontier as an edge stream.Source: §8.1 · p. 42, §8.2.1 · p. 43
- Proposed execution-model directions include asynchronous updates that could accelerate convergence in SSSP, CC, PageRank, and label propagation, and task parallelism for workloads such as all-pairs shortest paths and betweenness centrality.Source: §8.2.1 · p. 43
- Gunrock’s future abstraction work includes higher-level framework or DSL support, additional backends, and a hierarchical operator framework combining shared components with specialized optimizations.The current interfaces are C/C++-friendly and callable from languages such as Python and Julia; candidate backends include GraphBLAS, VertexAPI2, and EmptyHeaded.Source: §8.2.2 · p. 44, §8.2.3 · p. 45
- Candidate operator and primitive extensions include neighborhood reduction, priority queues, sampling, supervertex formation, and graph algorithms spanning coloring, connectivity, traversal, subgraph matching, and machine learning.Source: §8.2.3 · p. 44, §8.2.4 · p. 45
- Future graph-data directions include mutable and matrix-form graphs, improved memory locality, and partial loading of vertex or edge information to support graph queries and network-analysis primitives.Source: §8.2.5 · p. 46
8.3 Summary
- The authors conclude that Gunrock’s frontier-focused model maps naturally to GPUs, balancing performance and flexibility while accommodating optimization strategies and new graph primitives.Source: §8.3 · p. 47
- Gunrock combines a general, straightforward-to-program graph framework with performance on par with hardwired primitives and faster than other programmable GPU graph libraries.New primitives take a few hundred lines of code and require minimal GPU programming knowledge.Source: §8.3 · p. 47