Gunrock: GPU Graph Analytics

# Gunrock: GPU Graph Analytics PPoPP'16 ###### tags: `GPUs` [paper](https://dl.acm.org/doi/pdf/10.1145/3108140) [slide2020](https://archive.fosdem.org/2020/schedule/event/graph_gunrock/attachments/slides/3674/export/events/attachments/graph_gunrock/slides/3674/Gunrock_FOSDEM.pdf) [slide2015](https://images.nvidia.com/events/sc15/pdfs/SC5139-gunrock-multi-gpu-processing-library.pdf) ## 1. Introduction * our data-centric model’s key abstraction is the frontier, a subset of the edges or vertices within the graph that is currently of interest. * All Gunrock operations are bulk-synchronous and manipulate this frontier, either by computing on values within it or by computing a new frontier from it. * Gunrock targets graph primitives that are iterative, convergent processes * benchmark * breadth-first search (BFS) * single-source shortest path (SSSP) * betweenness centrality (BC) * PageRank * connected components (CC) * triangle counting (TC) * goal * performance * programmability * role * gunrock * how * programmer * what * chalenge * managing irregularity in work distribution * method * load-balancing * work-efficiency strategies * contribution * data-centric abstraction * incorperate * kernel fusion * push-pull traversal * idempotent traversal * priority queues * simple and flexible APIs * GPU-specific optimization strategies * memory efficiency * load balancing * workload management  # 3. DATA-CENTRIC ABSTRACTION * most graph analytics tasks can be expressed as iterative convergent processes * ![](https://i.imgur.com/DG2Vd7m.png) * focusing on * others * sequencing steps of computation * we * manipulating a data structure(the frontier of vertices or edges) * support * we * node and edge frontiers * others * vertices only * gather-apply-scatter(PowerGraph) * message-passing (Pregel) * bulk-synchronous "steps" * between step * sequential * inside step * parallel * graph primitives ![](https://i.imgur.com/wQi1aZm.png) * advance * an irregularly-parallel operation * different vertices in a graph have different numbers of neighbors * vertices share neighbors * 4 kinds of advance * V-to-V, V-to-E, E-to-V, E-to-E * utilized for * visit each element in the current frontier while updating local values and/or accumulating global values * BFS distance updates * visit the node or edge neighbors of all the elements in the current frontier while updating source vertex, destination vertex, and/or edge values * distance updates in SSSP * generate edge frontiers from vertex frontiers or vice versa * BFS, SSSP, SALSA * pull values from all vertices 2 hops away by starting from an edge frontier, visiting all the neighbor edges, and returning the far-end vertices of these neighbor edges * filter * A filter operator generates a new frontier from the current frontier by choosing a subset of the current frontier based on programmer-specified criteria. Each input item maps to zero or one output item * Though filtering is an irregular operation, using parallel scan for efficient filtering is well-understood on GPUs * used for 1. split vertices or edges based on a filter * SSSP’s 2-bucket delta-stepping) 2. compact out filtered items to throw them away * duplicated vertices in BFS or edges where both end nodes belong to the same component in CC * segmented intersection * takes two input node frontiers with the same length, or an input edge frontier, and generates both the number of total intersections and the intersected node IDs as the new frontier * key operator in TC * compute * defines an operation on all elements (vertices or edges) in its input frontier * A programmer-specified compute operator can be used together with all three traversal operators * no order * potential data race(atomic ops) * regular * sssp ![](https://i.imgur.com/3cuWVfD.png) * computes the shortest path from a single node in a graph to every other node in the graph * iteration description * input frontier of active vertices (or a single vertex) initialized to a distance of zero * enumerates the sizes of the frontier’s neighbor list of edges and computes the length of the output frontier * redistributes the workload across parallel threads * each edge adds its weight to the distance value at its source value and, if appropriate, updates the distance value of its destination vertex * removes redundant vertex IDs * three Gunrock operators * advance * computes the list of edges connected to the current vertex frontier and (transparently) load-balances their execution * compute * update neighboring vertices with new distances * filter * generate the final output frontier by removing redundant nodes, optionally using a two-level priority queue, whose use enables delta-stepping --- ## 3.1 Alternative Abstractions * Gather-apply-scatter (GAS) abstraction * Message-passing * CPU strategies * Help’s primitives * Asynchronous execution --- * two parts * Above the traversal-compute abstraction is the application module * Under the abstraction are the utility functions, the implementation of operators used in traversal, and various optimization strategies * three components ![](https://i.imgur.com/298zc9b.png) Fig. 4. Gunrock’s Graph Operator and Functor APIs. The Operator APIs divide the whole workloads into load-balanced per-edge or per-node operations and fuse the kernel with a functor that defines one such operation. * problem * provides graph topology data and an algorithm-specific data management interface * functors * contain user-defined computation code and expose kernel fusion opportunities that we discuss below * enactor * serves as the entry point of the graph algorithm * specifies the computation as a series of graph operator kernel calls with user-defined kernel launching settings * implementation * a sequence of bulk-synchronous steps, specified within the enactor and implemented as kernels, that operate on frontiers * an enactor-only program would sacrifice a significant performance opportunity * leveraging producer-consumer locality between operations by integrating multiple operations into single GPU kernels * kernel fusion is absent from other programmable GPU graph libraries * data-centric programming model conclude: * allows more flexibility on the operations * vertex-centric * edge-centric * decouples a compute operator from traversal operators * allows an implementation that both leverages state of-the-art data-parallel primitives and enables various types of optimizations * code smaller in size and clearer, Problem class and kernel enactor are both template-based C++ code * eases the job of extending Gunrock’ single-GPU execution model to multiple GPUs # 4. EFFICIENT GRAPH OPERATOR DESIGN ![](https://i.imgur.com/7x1z2oW.png) --- ## 4.1 Advance ![](https://i.imgur.com/4rDBuM9.png) * vectorized device memory assignment and copy * parallel threads place dynamic data (neighbor lists with various lengths) within shared data structures (output frontier) 1. allocation part * given a list of allocation requirements for each input item (neighbor list size array computed from row offsets), we need the scatter offsets to write the output frontier * implementation * prefix-sum [reference](https://www.itread01.com/content/1548349563.html) 2. copy part * for the copy part, we need to load-balance parallel scatter writes with various lengths over a single launch * implementation * load balancing * course grain * fine grain * traversal direction * 5.1 * push-based advance * pull-based advance ## 4.2 Filter ![](https://i.imgur.com/Nsuv1QO.png) Fig. 8. Filter is based on compact, which uses either a global scan and scatter (for exact filtering) or a local scan and scatter after heuristics (for inexact filtering). * stream compaction operator * transforms a sparse representation of an array (input frontier) to a compact one (output frontier) * implementation * Merrill et al.’s filtering implementation * prefix-sum * local prefix-sums with various culling heuristics * byproduct * uniquification feature * 5.2 ## 4.3 Segmented Intersection ![](https://i.imgur.com/dKEYCLG.png) Fig. 9. Segmented intersection implementation that uses prefix-sum, compact, merge-based intersection, and reduction. 1. takes two input frontiers 2. computes the intersection of two neighbor lists 3. outputs the intersected items * for intersection computation on two large frontiers, a modified merge-path algorithm would achieve high performance because of its load balance * for segmented intersection, the workload per input item pair depends on the size of each item’s neighbor list 1. prefix-sum for pre-allocation 2. a series of load-balanced intersections according to a heuristic based on the sizes of the neighbor list pairs 3. a stream compaction to generate the output frontier, and a segmented reduction as well as a global reduction to compute segmented intersection counts and the global intersection count --- * High-performance segmented intersection requires a similar focus to high-performance graph traversal * divide the edge lists into two groups 1. small neighbor lists 2. one small and one large neighbor list * two kernels * Two-Small * one thread to compute the intersection of a node pair * Small-Large * starts a binary search for each node in the small neighbor list on the large neighbor list # 5. SYSTEM IMPLEMENTATION AND OPTIMIZATIONS * component in achieving high performence * right abstraction * optimized implementations of the primitives within the framework ## 5.1 Graph traversal throughput * major contributions 1. generalizing different types of workload-distribution 2. load-balance strategies * advance operators * Gunrock’s advance step generates an irregular workload ![](https://i.imgur.com/4KZv9nE.png) ![](https://i.imgur.com/wH2CXNA.png) * methods * Static Workload Mapping Strategy * cooperative process * load all the neighbor list offsets into shared memory, then use a block of threads to cooperatively process per-edge operations on the neighbor list * loop strip mining * split the neighbor list of a node so multiple threads within the same SIMD lane can achieve better utilization * Dynamic Grouping Workload Mapping Strategy * Merge-based Load-Balanced Partitioning Workload Mapping Strategy * Push vs. Pull Traversal * Two-Level Priority Queue ## 5.2 Synchronization throughput * the bottlenecks of synchronization throughput * concurrent discovery 1. visited parents 2. being-visited peers 3. concurrently discovered children. * contributes to most synchronization overhead when there is per-node computation * 5.1.4 * dependencies in parallel data-primitives * computation during traversal has a reduction (Pagerank, BC) and/or intersection (TC) step on each neighbor list * methods * Idempotent vs. non-idempotent operations 1. it will cause an advance step to generate an output frontier that has duplicated elements 2. it will cause any computation on the common neighbors to run multiple times * Idempotent * advance step will avoid(costly) atomic operations, repeat the computation multiple times, and output all redundant items to the output frontier * filter step has incorporated a series of inexpensive heuristics to reduce, but not eliminate, redundant entries in the output frontier * Atomic Avoidance Reduction Operations 1. reduce the atomic operations by hierarchical reduction and the efficient use of shared memory on the GPU or 2. assign several neighboring edges to one thread in our dynamic grouping strategy so that partial results within one thread can be accumulated without atomic operations ## 5.3 Kernel launch throughput * Fuse computation with graph operator * fuse regular computation steps together with more irregular steps like advance and filter by running a computation step (with regular parallelism) on the input or output of the irregularly-parallel step, all within the same kernel. * Fuse filter step with traversal operators * Several traversal-based graph primitives have a filter step immediately following an advance or neighborhood-reduction step. * Gunrock implements a fused single-kernel traversal operator that launches both advance and filter steps. * Such a fused kernel reduces the data movement between double-buffered input and output frontiers ## 5.4 Memory access throughput 1. coalesced memory access 2. effective use of the memory hierarchy 3. reducing scattered reads and writes * Our choice of graph data structure helps us achieve these goals * format * vertex-centric operations * compressed sparse row (CSR) * edge-centric operations * choose coordinate list (COO) * Gunrock represents all per-node and per-edge data as structure-of-array (SOA) data structures that allow coalesced memory accesses with minimal memory divergence * shared memory and local memory * In dynamic grouping workload mapping * local memory * In load-balanced partition workload mapping * shared memory * In filter operator * shared memory # 6. GRAPH APPLICATIONS ![](https://i.imgur.com/WNqeHfZ.png) * advance, filter, segmented intersection and compute steps can be composed to build new graph primitives with minimal extra work. * Breadth-First Search (BFS) * Single-Source Shortest Path * Betweenness Centrality * Connected Component Labeling * PageRank and Other Node Ranking Algorithms * Triangle Counting * Subgraph Matching # 7. PERFORMANCE CHARACTERIZATION ![](https://i.imgur.com/MZXQifz.png) All PageRank times are normalized to one iteration. Hardwired GPU implementations for each primitive are enterprise (BFS), delta-stepping SSSP, gpu_BC (BC), and conn (CC). OOM means out-of-memory. A missing data entry means either there is a runtime error, or the specific primitive for that library is not available. # 8. CONCLUSION * highly programmable * high-performance