PaperlayerView exact revision on arXiv

Source-linked AI summary

GraphBLAST: A High-Performance Linear Algebra-based Graph Framework on the GPU

Carl Yang, Aydin Buluc, John D. Owens

arXiv:1908.01407v5cs.DCcs.MS

TL;DR

GraphBLAS offers linear-algebra building blocks for graph algorithms, but parallel-hardware programming presents a mismatch with the high-level languages users and designers prefer. GraphBLAST applies sparsity-aware and GPU-specific design principles; on five scale-free algorithms, it reports speedups over CPU and GPU graph frameworks.

  • Problem

    Parallel graph programming presents a mismatch between preferred high-level languages and the languages used for parallel hardware.

    Source: §1 · p. 2

  • Method

    GraphBLAST applies input-sparsity selection, output-sparsity masking, and GPU design choices including copy avoidance, generalized semirings, and load-balancing.

    Source: §9 · p. 39

  • Results

    On five scale-free graph algorithms, GraphBLAST achieved 2.31× geomean (10.97× peak) and 1.14× (5.24× peak) speed-up over CPU and GPU graph frameworks.

    Source: §1 · p. 4

  • Takeaways & Limitations

    The authors regard high performance on a single GPU as a prerequisite toward scalability, which their work does not address across multiple GPUs or nodes.

    Source: §9 · p. 39

    GraphBLAST is demonstrated at single-GPU scale; scaling across multiple GPUs or nodes is not addressed.

    Source: §9 · p. 39

Abstract

from arXiv · show

High-performance implementations of graph algorithms are challenging to implement on new parallel hardware such as GPUs because of three challenges: (1) the difficulty of coming up with graph building blocks, (2) load imbalance on parallel hardware, and (3) graph problems having low arithmetic intensity. To address some of these challenges, GraphBLAS is an innovative, on-going effort by the graph analytics community to propose building blocks based on sparse linear algebra, which will allow graph algorithms to be expressed in a performant, succinct, composable and portable manner. In this paper, we examine the performance challenges of a linear-algebra-based approach to building graph frameworks and describe new design principles for overcoming these bottlenecks. Among the new design principles is exploiting input sparsity, which allows users to write graph algorithms without specifying push and pull direction. Exploiting output sparsity allows users to tell the backend which values of the output in a single vectorized computation they do not want computed. Load-balancing is an important feature for balancing work amongst parallel workers. We describe the important load-balancing features for handling graphs with different characteristics. The design principles described in this paper have been implemented in "GraphBLAST", the first high-performance linear algebra-based graph framework on NVIDIA GPUs that is open-source. The results show that on a single GPU, GraphBLAST has on average at least an order of magnitude speedup over previous GraphBLAS implementations SuiteSparse and GBTL, comparable performance to the fastest GPU hardwired primitives and shared-memory graph frameworks Ligra and Gunrock, and better performance than any other GPU graph framework, while offering a simpler and more concise programming model.

1 INTRODUCTION

GraphBLAS offers linear-algebra building blocks for concise graph algorithms, but high-performance GPU implementations must address programming-model mismatch, load imbalance, and memory-bound work. GraphBLAST applies sparsity-aware and GPU-specific design principles and reports speedups over prior graph frameworks.

1 INTRODUCTION

  • GraphBLAS proposes linear-algebra building blocks to support concise graph algorithms, while high-level language preferences remain mismatched with parallel-hardware programming languages.GraphBLAS aims for portability, concise expression, high performance, and scalability; the paper notes that high performance on small scales must first be demonstrated.Source: §1 · p. 2
  • GraphBLAS had lacked high-performance GPU implementations, and GBTL was an order of magnitude slower than state-of-the-art GPU graph frameworks.The paper frames its work as addressing the performance gap while retaining a linear-algebra-based interface.Source: §1 · pp. 2–3
  • Graph problems require parallelization at large scale, while irregular memory access makes load-balancing difficult and low compute-to-memory ratios make many graph workloads memory-bound.The introduction notes that graphs may contain billions of vertices and edges.Source: §1 · pp. 2–3
  • The evaluation compares GraphBLAST with CPU and GPU graph frameworks and hand-tuned GPU implementations across BFS, SSSP, PageRank, connected components, and triangle counting.The compared systems include Ligra, Gunrock, CuSha, Galois, Mapgraph, GBTL, SuiteSparse, and problem-specific GPU implementations.Source: §1 · p. 3
  • Its design principles exploit input sparsity, output sparsity through masking, and GPU-specific considerations including avoiding CPU-to-GPU copies, generalized semirings, and load-balancing.Input sparsity selects between algorithms suited to sparse or dense input vectors; masking lets users indicate which output indices need not be computed.Source: §1 · p. 4
  • GraphBLAST reports 43.51× geomean and 1268× peak over SuiteSparse GraphBLAS for multi-threaded CPUs, plus 2.31× geomean (10.97× peak) and 1.14× (5.24× peak) speed-up over CPU and GPU frameworks.The latter comparison covers five graph algorithms on scale-free graphs.Source: §1 · p. 4

2 BACKGROUND & MOTIVATION

The section surveys vertex-centric, edge-centric, and linear-algebra-based graph frameworks, then examines GPU implementation challenges and systems that motivate GraphBLAST. It connects graph traversal to linear algebra through adjacency-matrix operations.

2.1.1 Vertex-centric.

  • Vertex-centric systems range from Pregel’s message-passing supersteps to GAS frameworks that address power-law load imbalance through vertex cuts or edge grouping.MapGraph combines load-balanced search with dynamic workload grouping; CuSha uses G-Shard preprocessing and concatenated windows, while HavoqGT uses vertex delegates for high-degree vertices.Source: §2.1.1 · p. 5

2.1.2 Edge-centric.

  • X-Stream’s edge-centric model streams unordered edge lists, exploiting sequential edge access even though vertex updates remain random-access.The cited work motivates this design by the superior sequential-access performance of memory and storage media over random access.Source: §2.1.2 · pp. 5–6

2.1.3 Linear algebra-based.

  • Linear-algebra frameworks express traversal as matrix-vector products; CombBLAS supplies semiring primitives, while GraphMat exposes a vertex-centric interface that converts programs to sparse matrix-vector multiplication.SuiteSparse is GraphBLAS-compliant, and GBTL is a GPU framework focused on programming-language research and separation of interface from backend.Source: §2.1.3 · p. 6

2.1.4 Implementation challenges on GPUs.

  • GPU graph frameworks contend with variable per-vertex work, limited work to occupy the GPU, kernel-launch and synchronization costs, and missed fusion opportunities.Load-balancing methods must trade their own cost against performance benefits; modular frameworks may also miss producer-consumer locality available to fused kernels.Source: §2.1.4 · pp. 6–7

2.2 Previous systems

  • Gunrock combines vertex- and edge-centric operations with runtime load balancing without preprocessing, but its optimization breadth increases application-code complexity.The stated design aim is to move more optimization work to the backend while retaining GraphBLAS’s compact interface and state-of-the-art performance.Source: §2.2.1 · p. 7

2.2.1 Gunrock.

  • Ligra generalizes direction-optimized BFS to graph-traversal algorithms but does not support multi-source traversals, which GraphBLAST expresses as sparse BLAS 3 operations.Source: §2.2.2 · p. 7

2.3 Graph traversal vs. matrix-vector multiply

  • An adjacency matrix represents the graph, and multiplying its transpose by a sparse vector represents a BFS step from the active frontier.For triangle counting, a masked product of the lower triangle and its transpose checks whether two-hop paths close into triangles while avoiding redundant paths.Source: §2.3 · p. 7, Figure 2 · p. 8

3 GRAPHBLAS CONCEPTS

GraphBLAS combines algebraic objects with programming constructs and operations to express graph computation. GraphBLAST illustrates the model with BFS and describes its C++ interface choices.

3.1 Abstract algebraic constructs

  • GraphBLAST represents graphs with matrices and active vertices with vectors, while semirings define edge/vertex computation and monoids provide a single associative operation with an identity.The MinPlus semiring illustrates shortest paths: addition combines path lengths and minimum selects the shortest; infinity represents unreachability.Source: §3.1.1 · p. 9, §3.1.2 · p. 9, §3.1.3 · p. 10

3.2 Programing constructs

  • Masks restrict which output indices are written, and descriptors can modify operations, including transposing a matrix or complementing a mask.A mask value of zero suppresses the corresponding output; its structural complement reverses that behavior.Source: §3.2.1 · p. 11, §3.2.2 · p. 11, Figure 3 · p. 12

3.3 Operation

  • The core mxm, mxv, and vxm operations account empirically for over 90% of graph-algorithm runtime; mxv and vxm traverse from one active-node set, while mxm handles multiple sets.For mxv, the semiring combines edge and active-node values and reduces intermediate results; an optional mask filters outputs.Source: §3.3 · pp. 11–12, Figure 3 · p. 12, Figure 4 · p. 13

3.4 Running example

  • BFS is expressed as a matrix-vector traversal followed by an elementwise product with the complement of the visited vector, yielding the next frontier.The running example advances from frontier vertices 0, 2, and 3, filters visited vertices 2 and 5, and retains 4 and 7.Source: §3.4 · p. 13, Figure 5 · p. 15
  • 64 loads and stores for dense GEMV fall to 20 for sparse-matrix SpMV in the 8-by-8 example, with input- and output-vector sparsity offering further potential reductions.The sparse-matrix count follows its 20 nonzeroes.Source: §3 · p. 9, §3.4 · p. 13

3.5 Code example

  • The BFS code marks visited vertices by level, traverses the current frontier while excluding visited vertices, and stops when the next frontier is empty.The example uses a Boolean semiring for traversal and a plus monoid to count active frontier entries.Source: §3.5 · pp. 13–14

3.6 Differences with GraphBLAS C API standard

  • GraphBLAST uses C++ templates and functors, compile-time type checking, and a header-only library, and omits some C API behaviors that users can compose from simpler operations.For example, users can clear an output before an operation to reproduce replace behavior, or follow an operation with elementwise addition or multiplication to accumulate results.Source: §3.6 · pp. 15–16

4 EXPLOITING INPUT SPARSITY (DIRECTION-OPTIMIZATION)

GraphBLAST exploits input-vector sparsity to select between SpMSpV and SpMV without requiring users to choose a traversal direction. The section describes the implementation, its storage choices, and the assumptions used by its direction criteria.

4 EXPLOITING INPUT SPARSITY (DIRECTION-OPTIMIZATION)

  • GraphBLAST automatically selects SpMSpV or SpMV from mxv parameters, extending generalized direction optimization to a GraphBLAS framework without requiring graph-algorithm semantics.The authors state this could reveal push-pull-like optimizations beyond graph processing.Source: §4 · p. 17, §4.4 · p. 21

4.1 Two roads to matrix-vector multiplication

  • SpMSpV exploits input-vector sparsity, whereas SpMV has cost independent of that sparsity; the former suits sparse active frontiers and the latter remains constant as vector sparsity changes.The section relates SpMSpV to push and SpMV to pull.Source: §4.1 · p. 17, §4.2 · p. 19, §4.3.2 · p. 20
  • 20 loads and stores for SpMV fall to 8 for SpMSpV in the example when input-vector sparsity is exploited.SpMSpV motivates storing the vector as sparse indices and values.Source: §4.1 · p. 17

4.2 Related work

  • Earlier GraphBLAS implementations GBTL and SuiteSparse lack generalized direction optimization, while GraphBLAST is the first to extend it to GraphBLAS-based frameworks.The authors say this omission contributes to those implementations trailing state-of-the-art graph frameworks.Source: §4.2 · p. 19

4.3 Implementation

  • For mxv, an empirical cost model chooses whichever of SpMV and SpMSpV is expected to use fewer memory accesses.Both routines are needed for efficient graph-framework mxv.Source: §4.3 · p. 19, §4.3.1 · p. 19

4.3.3 Matrix and Vector storage format.

  • GraphBLAST supports CSR and CSC matrices and both dense and sparse vectors, letting the backend switch vector formats while users may choose initial storage formats.Users can save memory by storing only one matrix representation, at the cost of performance.Source: §4.3 · p. 19, §4.3.3 · pp. 20–21

4.3.1 Direction optimization.

  • The direction criteria approximate frontier-neighbor counts from frontier size and average degree, and approximate unvisited vertices as all vertices because counting them adds GPU-kernel overhead.The latter assumption is described as reasonable for scale-free graphs, where the optimal push-to-pull switch occurs early.Source: §4.3.1 · p. 20
  • SpMSpV performance varies with input-vector sparsity, while SpMV performance is constant; the stated complexities are O(d nnz(x)) and O(dM), respectively.The SpMV cost is independent of input-vector sparsity; SpMSpV incorporates the vector’s nonzero count.Source: §4.3.2 · p. 20

5 EXPLOITING OUTPUT SPARSITY (MASKING)

GraphBLAST treats masking as output sparsity: users identify output indices they do not need, giving the backend an opportunity to fuse masking with computation. The section examines when accessing masks early can reduce work or memory use.

5 EXPLOITING OUTPUT SPARSITY (MASKING)

  • Masking lets users specify which output indices they need and can enable kernel fusion or fewer computations when the backend exploits that output sparsity.The paper describes masking both as a fused elementwise operation and as a way to declare output values unnecessary before computation.Source: §5 · p. 21, §5.1 · p. 21

5.1 Motivation and applications of masking

  • Masks can exclude already visited BFS vertices, keep SSSP active vectors sparse, skip converged PageRank vertices, or restrict triangle counting to existing edges.For triangle counting, the mask filters candidate wedges to those whose endpoint edge exists; the described algorithm is not optimal.Source: §5.1 · pp. 21–22

5.2 Microbenchmarks

  • Masked SpMV scales with mask-vector sparsity, but masked SpMSpV is unchanged because this implementation applies the mask after SpMSpV; mask lookup cannot asymptotically reduce matrix loads and stores there.The authors note binary search into the mask might reduce multiway-merge operations, but not asymptotic matrix access counts.Source: §5.2 · p. 22, Figure 7 · p. 23
  • 20 loads and stores for standard SpMV fall to 10 when the mask is checked first and only rows with nonzero mask entries are multiplied.This is the running example’s comparison of post-computation masking with accessing the mask ahead of multiplication.Source: §5.2 · p. 22, Figure 7 · p. 23

5.3 Masking insights

  • For masked mxv, accessing the mask first is preferred when input-vector nonzeros exceed a threshold; for mxm, it can avoid an order-of-magnitude output-nonzero blow-up and an order of magnitude of computation.The mask bounds where output nonzeros can occur, allowing only corresponding rows and columns to be loaded for dot products.Source: §5.3 · pp. 23–24

6 GPU IMPLEMENTATION

GraphBLAST keeps GPU data canonical and uses templated operators, then combines sparse primitives with workload-aware load balancing. Its implementations adapt algorithms to matrix and vector sparsity, while masked computation avoids unnecessary output work.

6.1 Memory management

  • GraphBLAST keeps a canonical GPU copy and marks the CPU copy stale after GPU mutations, copying data back only when an external operation needs it.A memory pool reuses allocated GPU memory for temporary operations.Source: §6.1 · p. 24

6.2 Operators

  • C++ templates and functors avoid maintaining code-generation tools while supporting GraphBLAS’s large cross product of semiring types and operations.The three semiring-taking methods require 1,459 operators even without user-defined types.Source: §6.2 · pp. 24–25

6.3 Implementation of key primitives and load balancing

  • Load balancing distributes work across GPU threads, warps, and blocks; GraphBLAST uses different strategies for SpMSpV, SpMV, SpMM, and masked SpGEMM.The strategies are multiple kernels for SpMSpV, merge-based for SpMV, merge-based and row split for SpMM, and row split for masked SpGEMM.Source: §6.3 · p. 25

6.3.1 SpMSpV.

  • SpMSpV expands work only for nonzero input-vector entries, then sorts contributions and reduces matching indices to form the output.Its work is O(flops(A, x)) with O(lg(flops(A, x))) depth; the temporary workspace is smaller than the input matrix unless the vector is dense.Source: §6.3.1 · p. 25

6.3.2 SpMV.

  • For SpMV, GraphBLAST uses ModernGPU’s nonzero-split merge-based implementation because the pathological empty-row case where merge path helps rarely occurs in practice.Nonzero-split assigns equal numbers of nonzeros per processor and uses a binary search on row offsets to find the starting row.Source: §6.3.2 · p. 25
  • The merge-based SpMV algorithm outperforms row-split SpMV across two types of load imbalance, though row-split wins in two configurations.The two configurations favoring row split are 512 and 2048.Source: §6.3.2 · p. 26, Figure 8 · p. 26

6.3.3 SpMM.

  • For SpMM, GraphBLAST selects merge-based processing when mean row length is below 9.35 and row split otherwise.The threshold comes from benchmarking and experiments on 157 SuiteSparse matrices; the authors did not encounter matrices with mean row length above 524,288.Source: §6.3.3 · p. 26

6.3.4 Masked SpGEMM.

  • 13–79× faster, direct masked SpGEMM also uses significantly less memory than computing SpGEMM first and applying the mask afterward.The direct implementation computes only entries selected by the mask.Source: §6.3.4 · p. 27

7 GRAPH ALGORITHMS

GraphBLAST expresses five commonly evaluated graph algorithms as compositions of GraphBLAS operations. The implementations draw on masking, sparsity, direction selection, and load balancing, with distinct algorithmic choices for each problem.

7.1 Breadth-first-search

  • BFS maps frontier expansion to masked Boolean-semiring mxv, with load balancing, direction optimization, early exit, structure-only operations, and operand reuse.The stated worst-case work is O(nnz(A)) and depth is O(D · log d_max).Source: §7.1 · pp. 28–29

7.2 Single-source shortest-path

  • SSSP uses adaptive Bellman-Ford with automatic generalized direction optimization and filters active vertices that did not improve their stored distances.It avoids priority queues; worst-case work is O(|E||V|), while each iteration has O(log d_max) depth.Source: §7.2 · p. 29

7.3 PageRank

  • PageRank uses merge-based load balancing and chooses SpMV when repeated multiplication has a vector that does not become sparser.Each iteration has O(ẽ) work and O(lg ẽ) depth, where ẽ counts the matrix nonzeros touched and can be below nnz(A) when vertices have converged.Source: §7.3 · p. 30

7.4 Connected components

  • Connected components uses FastSV with sparsification and new assign and extract variants that avoid otherwise-needed CPU–GPU transfers.Unlike LACC, FastSV does not guarantee an O(log |V|) worst-case iteration bound; GraphBLAST reports worst-case O(|E||V|) time and O(|V|) depth.Source: §7.4 · p. 31

7.5 Triangle counting

  • Triangle counting computes a masked product of the lower-triangular adjacency matrix with its transpose, then reduces the result to a scalar.For masked multiplication, GraphBLAST uses repeated binary searches from the shorter list into the longer list, trading a marginal average work factor of log d for more parallelism.Source: §7.5 · p. 31

8 EXPERIMENTAL RESULTS

GraphBLAST is evaluated across graph types and against CPU libraries, GPU frameworks, and hardwired implementations. Results vary by algorithm and graph: it is competitive with leading GPU frameworks in several cases, while road networks and some algorithms expose performance gaps.

8 EXPERIMENTAL RESULTS

  • The evaluation covers nine datasets for overall performance and five additional datasets for triangle counting, with runtime and TEPS as metrics.All experiments use a Tesla K40c; results exclude disk-to-memory and CPU-to-GPU transfer time.Source: §8 · pp. 31–32, Table 11 · p. 32, Table 12 · p. 33

8.1 Performance summary

  • GraphBLAST’s traversal-based BFS and SSSP perform better on scale-free graphs than on small-degree, large-diameter graphs, where overhead and lower parallelism constrain gains.The authors cite merge-based load-balancing overhead and a kernel launch per iteration; asynchronous approaches remain an open problem for non-BFS solutions.Source: §8.1 · p. 34

8.2 Comparison with CPU graph frameworks

  • Against CPU frameworks, GraphBLAST is 43.51× faster than SuiteSparse on scale-free graphs and 2.6× faster than Galois across all algorithms.Compared with Ligra, it is generally comparable on most tested algorithms, but is slower on road networks for BFS and SSSP and 2.80× slower for TC.Source: §8.2 · p. 35

8.3 Comparison with GPU graph frameworks and GPU hardwired

  • GraphBLAST is comparable or faster than hardwired GPU implementations on BFS, SSSP, and PR depending on dataset, but is 3.1× slower on CC for scale-free graphs and 107.7× slower on road networks.The authors connect the CC gap to pointer-jumping and kernel-launch overhead, especially on high-diameter road networks.Source: §8.3 · p. 35
  • GraphBLAST is 8.40× faster than CuSha and 3.97× faster than MapGraph in geomean, with the speedups attributed to direction optimization.CuSha performs the equivalent of pull traversal, while MapGraph is push-only.Source: §8.3 · p. 35
  • Against Gunrock, GraphBLAST is comparable on BFS, CC, and TC (Gunrock is 11.8%, 14.8%, and 11.1% faster in geomean, respectively), 1.1× faster on SSSP (1.53× peak), and achieves 2.39× PR speedup (5.24× peak).For PR, GraphBLAST uses generalized direction optimization to select SpMV, while Gunrock uses push-based advance.Source: §8.3 · pp. 35–36

8.4 Comparison with Gunrock on latest GPU architecture

  • On Titan V, GraphBLAST is 2.90× faster than Gunrock for PR, but has a 3.13× slowdown for BFS and a 4.00× slowdown for CC.For SSSP excluding road networks, GraphBLAST is 1.08× faster; including them, it is 0.48× slower.Source: §8.4 · p. 36, Table 13 · p. 37

8.5 Comparison with GraphBLAS-like framework on GPU

  • GraphBLAST is 31.8× faster than GBTL for BFS in the geomean, with 58.5× peak speedup.The authors attribute the difference to memory management, a specialized mxv, sparsity exploitation, and load balancing.Source: §8.5 · pp. 37–38, Table 14 · p. 38

9 CONCLUSION

GraphBLAST applies input sparsity, masking, and GPU-aware design principles to GraphBLAS, and reports speedups over SuiteSparse, Ligra, and Gunrock. The conclusion also identifies limits in scaling, kernel fusion, asynchronous execution, and matrix-matrix direction optimization.

9 CONCLUSION

  • 36× geomean and 892× peak over SuiteSparse GraphBLAS; GraphBLAST reports 2.14× geomean over Ligra and 1.01× over Gunrock on five graph algorithms.The corresponding reported peaks are 10.97× over Ligra and 5.24× over Gunrock.Source: §9 · p. 39
  • GraphBLAST’s design principles are input-sparsity direction optimization, output-sparsity masking, and GPU-aware support for avoiding copies, generalized semirings, and load balancing.GraphBLAST supports many algorithms, but inherently sequential algorithms such as depth-first search and priority-queue algorithms such as Dijkstra’s do not map efficiently to GraphBLAS.Source: §9 · p. 39
  • GraphBLAST demonstrates effectiveness on one GPU, but does not address scaling across multiple GPUs or nodes.The paper identifies multi-GPU and multi-node scalability as a main limitation.Source: §9 · p. 39
  • The tested datasets fit within 12 GB, while GPU memory limits scale-up and CPU-backed graph storage is likely noncompetitive against data fitting in GPU memory.The paper attributes the likely disadvantage of CPU backing storage to low CPU–GPU bandwidth and irregular graph-data access.Source: §9 · p. 39
  • Scale-free graphs are difficult to partition for multi-node execution, and faster GPU node computation can increase sensitivity to inter-node communication latency.The paper contrasts this with road-network-like graphs, which partition more readily and entail tractable communication.Source: §9 · p. 39
  • Blocking-mode triangle counting requires a matrix-matrix multiply followed by a reduce, writing the intermediate result to main memory before reading it again.The paper presents kernel fusion as an open problem and notes that runtime-dependent graph workloads and load balancing complicate automatically generated kernels.Source: §9 · pp. 40–41
  • An asynchronous execution model could address kernel-launch overhead on road networks, but the paper leaves graph-type detection and integration with GraphBLAS’s bulk-synchronous model open.The detection challenge is distinguishing graphs that need thousands of traversal iterations from those needing tens.Source: §9 · p. 41
  • Direction optimization currently applies only to matrix-vector multiplication; the paper proposes extending it to matrix-matrix multiplication for batched traversals and related applications.The proposed analogue switches between SpMM and SpGEMM, with output-size estimates potentially informing algorithm choice.Source: §9 · p. 41

A LINES OF CODE

The lines-of-code comparison counts algorithm-specific code and uses formatting and counting tools to make the comparison fair. Ligra is the non-GraphBLAS framework used for comparison because it has the fewest lines for all five algorithms.

A LINES OF CODE

  • The comparison counts only code specific to each algorithm and assumes each framework’s graph data is already in its preferred format.The authors manually remove include and namespace statements before counting.Source: A LINES OF CODE · p. 45
  • The authors use clang-format and cloc to reduce differences caused by formatting conventions and count lines of code.They remove include and namespace statements before formatting and counting.Source: A LINES OF CODE · pp. 45–46
  • Ligra is the non-GraphBLAS comparison framework because it has the fewest lines of code for all five algorithms.Source: A LINES OF CODE · p. 46

A.1 Breadth-first-search

The GraphBLAST BFS code initializes a frontier vector with the source, repeatedly computes an output, and continues while the reduction reports successors. The accompanying comparison presents GraphBLAST and Ligra BFS code.

A.1 Breadth-first-search

  • GraphBLAST initializes q1 with the source index and a value of 1, then uses q1 as the initial frontier.Source: §A.1 · p. 46
  • Each BFS iteration applies vxm with a logical-or-and semiring, toggles the mask descriptor, and reduces q1 to count successors.The loop continues while succ is greater than zero.Source: §A.1 · p. 46
  • The appendix shows GraphBLAST’s vector-and-matrix BFS alongside Ligra’s frontier-based edgeMap implementation.Source: §A.1 · p. 46

A.2 Single-source shortest-path

The GraphBLAST SSSP code initializes a source vector and an infinity-valued vector, then iterates vector-matrix and element-wise operations. The appendix compares it with Ligra’s frontier-based SSSP implementation.

A.2 Single-source shortest-path

  • GraphBLAST initializes the source vector with value 0 and creates a zero vector filled with the maximum float value.Source: §A.2 · p. 47
  • Each iteration applies vxm with a minimum-plus semiring, then uses eWiseAdd and eWiseMult before reducing w to count successors.Source: §A.2 · p. 47
  • The appendix presents Ligra’s SSSP as a frontier loop that calls edgeMap and then vertexMap.Source: §A.2 · p. 47

A.3 PageRank

The PageRank code initializes a probability vector uniformly and iterates sparse vector–matrix and elementwise operations until an error threshold or iteration limit is reached.

A.3 PageRank

  • The PageRank vector is initialized uniformly to 1/A_nrows.The code fills p with 1.f / A_nrows.Source: §A.3 · p. 48
  • Iterations continue while error exceeds eps and the iteration limit has not been reached.The loop uses the condition error > eps and iter <= max_niter_.Source: §A.3 · p. 48
  • Each iteration applies a vector–matrix operation, elementwise vector operations, and a reduction to compute error.The snippets show vxm, eWiseAdd, eWiseMult, and reduce operations within the iteration.Source: §A.3 · p. 48
  • The code includes a GraphBLAST PageRank implementation alongside a Ligra implementation for comparison.The algorithm caption identifies the left code as GraphBLAST and the right code as Ligra.Source: §A.3 · p. 48

A.4 Connected components

The connected-components code iteratively updates parent and grandparent vectors, tracks changes, and continues processing an active vertex set.

A.4 Connected components

  • The code initializes the parent vector with ascending vertex indices and duplicates it into working vectors.It also allocates vectors for grandparent and minimum-neighbor-parent values.Source: §A.4 · p. 49
  • Each iteration computes minimum neighbor-parent values from the grandparent vector and updates the parent vector.The code uses mxv and elementwise operations with minimum-selection semirings.Source: §A.4 · p. 49
  • The algorithm compares temporary and current grandparent vectors, reduces the difference vector, and uses the result to control iteration.The code forms a not-equal difference vector and reduces it to succ.Source: §A.4 · p. 49
  • The Ligra code processes active vertices with edgeMap, then filters all vertices to form the next output set.The algorithm caption labels the left code GraphBLAST and the right code Ligra.Source: §A.4 · p. 49

A.5 Triangle counting

The triangle-counting code includes a GraphBLAST matrix-based calculation and a common-neighbor counting routine over sorted adjacency lists.

A.5 Triangle counting

  • GraphBLAST multiplies the adjacency matrix by itself and reduces the resulting matrix to obtain ntris.The shown operations use a plus-times semiring followed by a plus-monoid reduction.Source: §A.5 · p. 50
  • The common-neighbor routine walks two neighbor lists using indices and compares neighbor values.The code sorts each vertex's outgoing neighbors before the edge traversal and common-neighbor counting.Source: §A.5 · p. 50
  • The counting function adds common-neighbor counts for one endpoint when s > d.The update is shown in both ordinary and atomic variants.Source: §A.4 · p. 49, §A.5 · p. 50
  • The algorithm caption identifies GraphBLAST code on the left and Ligra code on the right.The supplied caption labels the code examples but does not report a performance comparison.Source: §A.5 · p. 50
Loading 1908.01407v5…