Pith. sign in

REVIEW 3 major objections 4 minor 86 references

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

T0 review · 3 major / 4 minor · reviewed 2026-08-14 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read Sparse linear algebra reaches parity with hand-tuned GPU graph codes

desk verdict A credible engineering contribution that shows GraphBLAS on GPU can be competitive; the headline performance claims are overstated and inconsistent across sections. read the letter →

arxiv 1908.01407 v5 pith:6P3SJ7VW submitted 2019-08-04 cs.DC cs.MS

Carl Yang , Aydin Buluc , John D. Owens This is my paper · ORCID
classification cs.DCcs.MS
keywords GraphBLASGPUframeworklinearalgebradirectionoptimizationsparsematrix-vectormultiplicationmaskingloadbalancingalgorithms
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

The paper argues that the GraphBLAS model—graph algorithms written as sparse linear algebra operations—can be made fast enough on GPUs to compete with hand-tuned native graph code, rather than remaining a convenience interface that pays a large performance tax. It presents GraphBLAST, an open-source single-GPU implementation, and reports that on five standard algorithms it is at least an order of magnitude faster than earlier GraphBLAS implementations, comparable to the fastest hardwired GPU primitives and to the strongest CPU and GPU frameworks on scale-free graphs, and faster than the remaining GPU graph frameworks tested. The argument is carried by three design principles: exploiting input sparsity by automatically choosing between sparse-vector and dense-vector matrix-vector multiplication (push versus pull), exploiting output sparsity by reading the mask before the multiply, and load-balancing irregular work with merge-based and row-split kernels. If these results are representative, a programmer can write BFS in 22 lines and receive near-hardwired performance, which would remove the usual productivity-versus-performance tradeoff in graph analytics. The paper itself lists multi-GPU scaling, kernel fusion, asynchronous execution, and matrix-matrix direction optimization as unaddressed limitations.

What carries the argument

The central object is the masked sparse matrix-vector multiply $y \leftarrow (A^T x) .* m$ (equivalently $y = A^T x .* \lnot v$ in BFS), where $A$ is the graph's adjacency matrix, $x$ is the current frontier, and $m$ is a mask of output locations to keep or discard. This one operation is implemented by two interchangeable kernels: SpMSpV, a push traversal whose work scales with the number of nonzeros in $x$, and SpMV, a pull traversal whose work scales with the size of the typically unvisited mask; a cost model chooses between them so the user never specifies direction. The same output-sparsity idea appears in masked sparse matrix-matrix multiplication $C = (A B) .* M$, where reading $M$ first avoids materializing the large intermediate product and makes triangle counting memory-efficient. Load-balancing kernels built from segmented scans, merge-based decomposition, and row splits keep these routines efficient on skewed degree distributions.

What would settle it

Run GraphBLAST on a family of low-diameter regular graphs (for example a two-dimensional grid or a road network) while instrumenting each BFS and CC iteration to record the true number of frontier neighbors and the true number of unvisited vertices; if the fixed switch point of one tenth of all edges misfires whenever actual values differ from the average-degree approximation, the resulting slowdown (the paper reports up to 107.7x on connected components versus a hand-tuned GPU kernel) can be traced to the cost model and would be reduced by an adaptive estimate.

Watch

Extended reading notes

Core claim

The central claim, stated on the paper's own terms, is that a linear-algebra-based graph framework can match state-of-the-art native frameworks and hardwired kernels on a GPU while keeping the GraphBLAS programming model. Concretely, GraphBLAST computes graph traversals as one masked sparse linear algebra step, $y \leftarrow (A^T x) .* \lnot m$, and the backend decides on every call whether to run the push form (SpMSpV, work proportional to the nonzeros in the frontier $x$) or the pull form (SpMV, work proportional to the unvisited set $m$), using a cost model with a fixed switch threshold of one tenth of the graph's edges. The paper reports geometric-mean speedups of $43.51\times$ (with $1268\times$ peak) over a multi-threaded CPU GraphBLAS implementation on scale-free graphs, a $31.8\times$ geomean speedup over the earlier GPU GraphBLAS implementation on BFS, parity with the strongest CPU and GPU frameworks on BFS, SSSP, and PR with the main exceptions on road networks, and wins over other GPU frameworks, alongside a severalfold reduction in lines of application code.

Load-bearing premise

Section 9 states that scaling to multiple GPUs or nodes, kernel fusion, asynchronous execution, and direction optimization for matrix-matrix multiplication remain open; the performance claim itself rests on the push/pull cost model assuming the frontier's neighbor count is average degree times frontier size and unvisited vertices are nearly all vertices, with a fixed switch point of one tenth of all edges, so road networks with small regular degrees can choose the wrong direction and slow dramatically.

Editorial extensions

If this is right

  • A GraphBLAS interface can be the performance path rather than a prototype path: the paper's measurements put BFS, SSSP, and PR on scale-free graphs at or above the speed of the leading native GPU and shared-memory frameworks, with the framework doing the optimization work automatically.
  • Programmers can stop writing push and pull variants: because direction is chosen from sparsity inside the matrix-vector multiply, BFS and SSSP code stays direction-agnostic, and the same backend also selects between the sparse-vector and dense-vector forms for repeated PageRank iterations.
  • Masking an operation before computing it can save an order of magnitude in memory and runtime whenever the output is sparse; the paper's masked sparse matrix-matrix multiply speeds up triangle counting by 13 to 79 times compared with computing the product first.
  • The algorithmic family covered is wide: BFS, SSSP, PageRank, connected components, and triangle counting all reduce to few-line compositions of matrix-vector and matrix-matrix operations with masks, confirming that the five standard workloads stress different parts of the framework as intended.
  • Because GraphBLAST implements the GraphBLAS API with minor C++ template differences, graph algorithms written against the open standard should map onto it with little change, making the performance work reusable across a growing set of GraphBLAS programs.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • A testable improvement suggested by the paper's own road-network failures is to replace the fixed one-tenth-of-edges switch threshold with a cheap, data-dependent estimate of the current frontier's neighbor count; if the estimate tracked the true value on low-diameter regular graphs, the reported 4.88x slowdowns versus a CPU framework on BFS and 107.7x slowdown on connected components should large
  • The automatic push-pull logic for matrix-vector multiplication has a natural matrix-matrix analogue: the right-hand factor's column sparsity plays the role of the input vector's sparsity, so a direction-optimizing switch between sparse matrix-dense matrix and sparse matrix-sparse matrix multiplication could yield batched betweenness centrality and all-pairs shortest paths with the same user-side s
  • On newer GPU generations the paper's push phase, built on radix-sorted multiway merge, improves less than the competition's frontier-deduplication heuristics; substituting a deduplication kernel inside the sparse-matrix sparse-vector multiply is a plausible way to recover BFS parity without breaking the linear-algebra interface.
Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

3 major / 4 minor

Summary. The paper presents GraphBLAST, an open-source, single-GPU implementation of the GraphBLAS linear-algebra-based graph framework. It identifies three design principles: exploiting input sparsity through automatic push/pull direction optimization, exploiting output sparsity through fused masking, and GPU-specific considerations such as load balancing and avoiding CPU-to-GPU copies. The authors evaluate five graph algorithms (BFS, SSSP, PageRank, connected components, triangle counting) on a range of scale-free and mesh-like graphs, comparing against CPU frameworks (SuiteSparse, Galois, Ligra), GPU frameworks (Gunrock, CuSha, MapGraph, GBTL), and hardwired GPU implementations. The headline claims are order-of-magnitude speedups over previous GraphBLAS implementations and comparable or better performance than state-of-the-art general graph frameworks.

Significance. If the qualified version of the claims holds, this is a significant systems contribution: it demonstrates that a linear-algebra-based graph framework on GPUs can be competitive with specialized graph frameworks while drastically reducing application code size, and it provides an open-source reference implementation. The experimental coverage is broad, spanning multiple algorithms, datasets, and baselines, and the paper includes a useful discussion of load-balancing and sparsity-exploitation techniques. The key weakness is that the abstract and conclusion overstate the results: the paper's own tables show Gunrock ahead of GraphBLAST on BFS, CC, and TC geomeans, and the speedup numbers against SuiteSparse are reported inconsistently across sections. These issues are fixable with careful qualification, but they currently undermine the central claim as written.

major comments (3)
  1. [Abstract; §8.3; Table 13] The abstract's claim that GraphBLAST has 'better performance than any other GPU graph framework' is contradicted by the paper's own evaluation. Section 8.3 reports that Gunrock is 11.8%, 14.8%, and 11.1% faster in the geometric mean on BFS, CC, and TC, respectively, and Table 13 shows GraphBLAST is 3.13× slower than Gunrock on BFS and 4.00× slower on CC on the Titan V. The claim should be narrowed to the specific algorithms and graph types where the data support it, for example 'comparable to Gunrock on BFS/CC/TC and faster on SSSP/PR on scale-free graphs.' As written, the headline claim is not supportable from the manuscript's own tables.
  2. [Section 1; §8.2; §9] The reported speedups over SuiteSparse GraphBLAS are inconsistent across the paper. Section 1 states '43.51× geomean ... and 1268× peak over SuiteSparse GraphBLAS for multi-threaded CPUs'; Section 8.2 states 'geomean 27.9× (1268× peak) on all algorithms and geomean 43.51× ... on scale-free graphs'; and Section 9 states '36× geomean 892× peak over SuiteSparse GraphBLAS (sequential CPU).' These numbers differ not only in magnitude but also in the described baseline configuration (multi-threaded vs. sequential). The authors must reconcile these figures and clearly define the dataset subset and CPU configuration for every headline number, otherwise the reader cannot verify the central performance claim.
  3. [§4.3.1; §8.2; Table 13] The direction-optimization cost model relies on two assumptions—that |E_f| can be approximated as d|V_f| and that |V_u| can be approximated as |V|—leading to a fixed push/pull threshold of |E|/10. This threshold is a heuristic with no sensitivity analysis, and the paper's own results show that the approximation fails badly on road-network graphs: Section 8.2 reports a 4.88× slowdown versus Ligra on road-network BFS, and Table 13 reports GraphBLAST being 0.10× and 0.0044× of Gunrock's speed on road-network BFS and CC, respectively. The authors should either provide evidence that the threshold is robust across graph types or explicitly restrict the performance claims to scale-free graphs where the cost model is intended to apply.
minor comments (4)
  1. [§3.3] There is a typo in 'on ther other hand' that should be corrected to 'on the other hand.'
  2. [§2.1.1; §7.5] Several references are left as unresolved placeholders: 'STINGER [? ]', 'Kineograph [? ]', 'Aspen [? ]', 'Terrace [? ]' in Section 2.1.1, and '[33?]' in Section 7.5. These need to be completed before publication.
  3. [§8; Table 12] The measurement section states that Gunrock and GraphBLAST tests were run 10 times and averaged, but no variance or standard deviation is reported. Since several comparisons are close (e.g., the 11–15% geomean differences in Section 8.3), reporting variance or per-run distributions would make the comparability claims more credible.
  4. [Table 12] The note 'All PageRank times are normalized to one iteration' is helpful, but it should be clarified whether the corresponding edge-throughput numbers are also normalized per iteration; otherwise the PR throughput values may be misinterpreted.

Circularity Check

0 steps flagged · score 0.0 of 10

No circularity: GraphBLAST's performance claims are validated against external baselines; tuned heuristics are engineering choices, not fitted predictions.

full rationale

This is a systems and performance paper rather than a derivation paper, and I find no step in which a claimed result is equivalent to its inputs by construction. The core claims are measured performance comparisons against external baselines (Ligra, Gunrock, SuiteSparse, GBTL, and hardwired GPU implementations) on standard datasets, which is the correct independent test. The design principles (exploiting input and output sparsity, load balancing) are engineering contributions; they are motivated by microbenchmarks (Figures 6-9) but are not 'derived' from those benchmarks in a circular sense. The direction-optimization threshold |E|/10 (Table 9) and the SpMM cutoff nnz/M < 9.35 (Section 6.3.3) are empirically tuned heuristics, not fitted parameters masquerading as predictions; the paper reports performance on held-out datasets, not on the tuning data. The paper does cite the authors' earlier work for implementation components (SpMSpV [82], push-pull GraphBLAS [81], SpMM [80]), but these are code-lineage references, not load-bearing derivations: the current paper measures the resulting framework against outside systems, and no cited 'uniqueness theorem' or self-referential formal result is used to forbid alternatives. The skeptical observation that the abstract's 'better performance than any other GPU graph framework' is contradicted by the paper's own Tables 12-13 is a benchmarking-validity and claim-calibration concern, not a circularity concern; it does not make a derivation equivalent to its input. I therefore find no significant circularity.

Assumptions & free parameters 2 free parameters · 3 assumptions · 0 invented entities

The central performance claim is an engineering result, so the free parameters are empirical system thresholds rather than scientific constants. The domain assumptions are explicitly stated approximations in the direction-optimization cost model. No new physical or mathematical entities are introduced.

free parameters (2)
  • Direction-optimization threshold = |E|/10
    Used in the cost model to switch between push (SpMSpV) and pull (SpMV) in mxv. Chosen empirically; the paper compares with Ligra's |E|/20 and Gunrock's |E|/1000 (Table 9).
  • SpMM algorithm-selection threshold = nnz/M < 9.35
    Selects between merge-based and row-split SpMM, tuned using 157 SuiteSparse matrices; the authors note it does not capture all cases (Section 6.3.3).
assumptions (3)
  • domain assumption Frontier neighbor count can be approximated as d times the frontier size, i.e., |E_f| ≈ d|V_f|.
    Section 4.3.1: avoids prefix-sum overhead. If inaccurate, direction optimization picks a suboptimal push/pull direction.
  • domain assumption Unvisited vertex count can be approximated as all vertices, i.e., |V_u| ≈ |V|.
    Section 4.3.1: avoids an extra kernel launch to count the mask. Reasonable on scale-free graphs where the switch happens early.
  • domain assumption ModernGPU primitives (IntervalExpand, IntervalGather, ReduceByKey, segmented scan) provide efficient GPU building blocks.
    Section 6.3: load-balanced kernels depend on these primitives; if they are unavailable or slow on other GPUs, the performance claims may not transfer.

how reviews work

0 comments
Cite this review

Pith. "Pith review of GraphBLAST: A High-Performance Linear Algebra-based Graph Framework on the GPU." pith.science (2026). https://pith.science/paper/6P3SJ7VW

@misc{pith2026190801407,
  author       = {Pith},
  title        = {Pith review of: GraphBLAST: A High-Performance Linear Algebra-based Graph Framework on the GPU},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/6P3SJ7VW}},
  note         = {Machine review of arXiv:1908.01407}
}
read the original abstract

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.

Figures

Figures reproduced from arXiv: 1908.01407 by the authors.

Figure 1
Figure 1. Mismatch between existing frameworks targeting high-level languages and hardware accelerators. [PITH_FULL_IMAGE:figures/full_fig_p002_1.png] view at source ↗
Figure 2
Figure 2. The adjacency matrix A is one representation of graph 𝐺 = (𝑉 , 𝐸) with its set of vertices 𝑉 and set of edges 𝐸. The matrix-vector multiply A Tx is one representation of the BFS graph traversal where the sparse vector x represents the current active frontier of vertices. 3 GRAPHBLAS CONCEPTS The following section introduces GraphBLAS’s model of computation. A full treatment of Graph￾BLAS is beyond the scope of this … view at source ↗
Figure 3
Figure 3. Calling the operation mxv (matrix-vector multiply) performs w = Au. ∗ mask over the Semiring op. The template parameters can be used to do compile-time type-checking. Info is an error type that is returned according to the C API specification [17]. accum is an optional parameter for controlling whether the output of the calculation overwrites w or whether it is accumulated to w. The Descriptor can be used to control… view at source ↗
Figures from the paper (11 more)
Figure 4
Figure 4. Figure 4: Decomposition of key GraphBLAS operations. Note that vxm is the same as mxv and setting the [PITH_FULL_IMAGE:figures/full_fig_p013_4.png]
Figure 5
Figure 5. Figure 5: Running example of breadth-first-search from source node 1. Currently, we are on level 2 and trying [PITH_FULL_IMAGE:figures/full_fig_p015_5.png]
Figure 6
Figure 6. Figure 6: Comparison of SpMV and SpMSpV. Matrix Input Vector Output Vector Operation Mask Complexity Sparsity (A) Sparsity (x) Sparsity (m) GEMV no 𝑂(𝑀𝑁) SpMV (pull) no 𝑂(𝑑𝑀) SpMSpV (push) no 𝑂(𝑑 𝑛𝑛𝑧(x)) GEMV yes 𝑂(𝑁 𝑛𝑛𝑧(m)) SpMV (pull) yes 𝑂(𝑑 𝑛𝑛𝑧(m)) SpMSpV (push) yes 𝑂(𝑑 𝑛𝑛𝑧(…
Figure 7
Figure 7. Figure 7: Comparison with and without fused mask. mxm first mask first Dataset Nonzeroes Runtime (s) Nonzeroes Runtime (s) Memory savings Speedup coAuthorsCiteseer 2.03M 458.3 814K 5.96 2.49× 76.9× coPapersDBLP 81.3M 3869 15.2M 78.66 5.35× 13.2× road_central 29.0M 3254 16.9M 246…
Figure 8
Figure 8. Figure 8: The three parallelizations for CSR SpMV and SpMM on matrix [PITH_FULL_IMAGE:figures/full_fig_p026_8.png]
Figure 9
Figure 9. Figure 9: Microbenchmark showing performance of the merge-based algorithm compared against the row-split [PITH_FULL_IMAGE:figures/full_fig_p027_9.png]
Figure 10
Figure 10. Figure 10: Operation flowchart for different algorithms expressed in GraphBLAS. A loop indicates a while-loop [PITH_FULL_IMAGE:figures/full_fig_p028_10.png]
Figure 11
Figure 11. Figure 11: Speedup of GraphBLAST over seven other graph processing libraries/hardwired algorithms on [PITH_FULL_IMAGE:figures/full_fig_p034_11.png]
Figure 12
Figure 12. Figure 12: Runtime breakdown of GraphBLAST and Gunrock migrating from K40c to Titan V GPU for BFS, [PITH_FULL_IMAGE:figures/full_fig_p036_12.png]
Figure 13
Figure 13. Figure 13: Design of GraphBLAST: Completed and planned components, and how open standard GraphBLAS [PITH_FULL_IMAGE:figures/full_fig_p038_13.png]
Figure 14
Figure 14. Figure 14: Data points from GraphBLAST and points representative of the state-of-the-art in distributed BFS. [PITH_FULL_IMAGE:figures/full_fig_p040_14.png]

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

86 extracted references · 79 canonical work pages

  1. [1]

    Better size estimation for sparse matrix products

    Rasmus Resen Amossen, Andrea Campagna, and Rasmus Pagh. Better size estimation for sparse matrix products. Lecture Notes in Computer Science , pages 406–419, 2010

    2010

  2. [2]

    Parallel triangle counting and enumeration using matrix algebra

    Ariful Azad, Aydin Buluç, and John Gilbert. Parallel triangle counting and enumeration using matrix algebra. In 2015 IEEE International Parallel and Distributed Processing Symposium Workshop , pages 804–811. IEEE, May 2015

    2015

  3. [3]

    Fayoumi, Reza Nouri, Seyed-Mehdi-Reza Beheshti, Ahmed Barnawi, and Sherif Sakr

    Omar Batarfi, Radwa El Shawi, Ayman G. Fayoumi, Reza Nouri, Seyed-Mehdi-Reza Beheshti, Ahmed Barnawi, and Sherif Sakr. Large scale graph processing systems: survey and an experimental evaluation. Cluster Computing , 18(3):1189–1213, July 2015

    2015

  4. [4]

    Modern GPU library

    Sean Baxter. Modern GPU library. https://moderngpu.github.io/, 2016

    2016

  5. [5]

    Bayer and E

    R. Bayer and E. M. McCreight. Organization and maintenance of large ordered indexes. Acta Informatica, 1(3):173–189, 1972

    1972

  6. [6]

    Understanding and Improving Graph Algorithm Performance

    Scott Beamer. Understanding and Improving Graph Algorithm Performance . PhD thesis, University of California, Berkeley, Fall 2016

    2016

  7. [7]

    Direction-optimizing breadth-first search

    Scott Beamer, Krste Asanović, and David Patterson. Direction-optimizing breadth-first search. In Proceedings of the International Conference for High Performance Computing, Networking, Storage and Analysis , SC ’12, pages 12:1–12:10, November 2012

    work page 2012

  8. [8]

    Reducing PageRank communication via propagation blocking

    Scott Beamer, Krste Asanović, and David Patterson. Reducing PageRank communication via propagation blocking. In IEEE International Parallel and Distributed Processing Symposium (IPDPS) , pages 820–831, May 2017

    work page 2017

Show all 86 references
  1. [9]

    Implementing sparse matrix-vector multiplication on throughput-oriented processors

    Nathan Bell and Michael Garland. Implementing sparse matrix-vector multiplication on throughput-oriented processors. In Proceedings of the 2009 ACM/IEEE Conference on Supercomputing , SC ’09, pages 18:1–18:11, November 2009

    2009

  2. [10]

    Thrust: A productivity-oriented library for CUDA

    Nathan Bell and Jared Hoberock. Thrust: A productivity-oriented library for CUDA. In GPU Computing Gems Jade Edition, pages 359–371. Elsevier, 2012

    2012

  3. [11]

    To push or to pull: On reducing communication and synchronization in graph computations

    Maciej Besta, Michał Podstawski, Linus Groner, Edgar Solomonik, and Torsten Hoefler. To push or to pull: On reducing communication and synchronization in graph computations. In Proceedings of the 26th International Symposium on High-Performance Parallel and Distributed Computi...

    2017

  4. [12]

    High performance exact triangle counting on GPUs

    Mauro Bisson and Massimiliano Fatica. High performance exact triangle counting on GPUs. IEEE Transactions on Parallel and Distributed Systems , 28(12):3501–3510, December 2017

    2017

  5. [13]

    Blelloch

    Guy E. Blelloch. Prefix sums and their applications. Technical Report CMU-CS-90-190, School of Computer Science, Carnegie Mellon University, November 1990. http://www.cs.cmu.edu/~scandal/papers/CMU-CS-90-190.html

    1990

  6. [14]

    Mattson, Scott McMillan, and José E

    Benjamin Brock, Aydin Buluç, Timothy G. Mattson, Scott McMillan, and José E. Moreira. A roadmap for the GraphBLAS C++ API. In 2020 IEEE International Parallel and Distributed Processing Symposium Workshops (IPDPSW) , pages 219–222. IEEE, May 2020

    2020

  7. [15]

    The Combinatorial BLAS: design, implementation, and applications

    Aydın Buluç and John R Gilbert. The Combinatorial BLAS: design, implementation, and applications. The International Journal of High Performance Computing Applications , 25(4):496–509, November 2011

    2011

  8. [16]

    Parallel breadth-first search on distributed memory systems

    Aydın Buluç and Kamesh Madduri. Parallel breadth-first search on distributed memory systems. In Proceedings of the International Conference for High Performance Computing, Networking, Storage and Analysis , SC ’11. ACM Press, November 2011

    2011

  9. [17]

    The GraphBLAS C API Specification , November 2017

    Aydin Buluc, Timothy Mattson, Scott McMillan, Jose Moreira, and Carl Yang. The GraphBLAS C API Specification , November 2017. Rev. 1.1. http://graphblas.org/index.php/C_language_API

    2017

  10. [18]

    Design of the GraphBLAS API for C

    Aydın Buluç, Timothy Mattson, Scott McMillan, Jose Moreira, and Carl Yang. Design of the GraphBLAS API for C. In IEEE International Parallel and Distributed Processing Symposium Workshops (IPDPSW) , May 2017

    2017

  11. [19]

    Federico Busato, Oded Green, Nicola Bombieri, and David A. Bader. Hornet: An efficient data structure for dynamic sparse graphs and matrices on GPUs. In 2018 IEEE High Performance extreme Computing Conference (HPEC) . IEEE, September 2018

    2018

  12. [20]

    One trillion edges: Graph processing at Facebook-scale

    Avery Ching, Sergey Edunov, Maja Kabiljo, Dionysios Logothetis, and Sambavi Muthukrishnan. One trillion edges: Graph processing at Facebook-scale. Proceedings of the VLDB Endowment , 8(12):1804–1815, August 2015

    2015

  13. [21]

    Structure prediction and computation of sparse matrix products

    Edith Cohen. Structure prediction and computation of sparse matrix products. Journal of Combinatorial Optimization , 2(4):307–332, 1998

    1998

  14. [22]

    Graph twiddling in a MapReduce world

    Jonathan Cohen. Graph twiddling in a MapReduce world. Computing in Science & Engineering , 11(4):29–41, July 2009. ACM Trans. Math. Softw., Vol. 1, No. 1, Article 1. Publication date: January 2021. GraphBLAST: A High-Performance Linear Algebra-based Graph Framework on the GPU 1:43

    2009

  15. [23]

    Cusp: Generic parallel algorithms for sparse matrix and graph computations, 2014

    Steven Dalton, Nathan Bell, Luke Olson, and Michael Garland. Cusp: Generic parallel algorithms for sparse matrix and graph computations, 2014. Version 0.5.0. http://cusplibrary.github.io/

    2014

  16. [24]

    Optimizing sparse matrix-matrix multiplication for the GPU

    Steven Dalton, Luke Olson, and Nathan Bell. Optimizing sparse matrix-matrix multiplication for the GPU. ACM Transactions on Mathematical Software (TOMS) , 41(4):25:1–25:20, August 2015

    2015

  17. [25]

    Andrew Davidson, Sean Baxter, Michael Garland, and John D. Owens. Work-efficient parallel GPU methods for single-source shortest paths. In Proceedings of the 28th IEEE International Parallel and Distributed Processing Symposium , IPDPS 2014, pages 349–359, May 2014

    2014

  18. [26]

    Timothy A. Davis. Algorithm 1000: SuiteSparse:GraphBLAS: Graph algorithms in the language of sparse linear algebra. ACM Transactions on Mathematical Software , 45(4):1–25, December 2019

    2019

  19. [27]

    Davis and Yifan Hu

    Timothy A. Davis and Yifan Hu. The University of Florida sparse matrix collection. ACM Transactions on Mathematical Software (TOMS), 38(1):1:1–1:25, November 2011

    2011

  20. [28]

    MapReduce: simplified data processing on large clusters

    Jeffrey Dean and Sanjay Ghemawat. MapReduce: simplified data processing on large clusters. Communications of the ACM, 51(1):107–113, January 2008

    2008

  21. [29]

    Engineering route planning algorithms

    Daniel Delling, Peter Sanders, Dominik Schultes, and Dorothea Wagner. Engineering route planning algorithms. In Jürgen Lerner, Dorothea Wagner, and Katharina A. Zweig, editors,Algorithmics of Large and Complex Networks , volume 5515 of Lecture Notes in Computer Science , pages...

    2009

  22. [30]

    A survey of parallel graph processing frameworks

    Niels Doekemeijer and Ana Lucia Varbanescu. A survey of parallel graph processing frameworks. Technical Report PDS-2014-003, Delft University of Technology, 2014

    2014

  23. [31]

    Joe Eaton. nvGRAPH. https://docs.nvidia.com/cuda/nvgraph/index.html, 2016. Accessed: 2018-01-18

    2016

  24. [32]

    Sparse matrix-vector multiplication on GPGPUs

    Salvatore Filippone, Valeria Cardellini, Davide Barbieri, and Alessandro Fanfarillo. Sparse matrix-vector multiplication on GPGPUs. ACM Transactions on Mathematical Software (TOMS) , 43(4):30:1–30:49, March 2017

    2017

  25. [33]

    James Fox, Oded Green, Kasimir Gabert, Xiaojing An, and David A. Bader. Fast and adaptive list intersections on the GPU. 2018 IEEE High Performance Extreme Computing Conference (HPEC) , September 2018

    2018

  26. [34]

    MapGraph: A high level API for fast development of high performance graph analytics on GPUs

    Zhisong Fu, Michael Personick, and Bryan Thompson. MapGraph: A high level API for fast development of high performance graph analytics on GPUs. In Proceedings of the Workshop on GRAph Data Management Experiences and Systems, GRADES ’14, pages 2:1–2:6, June 2014

    2014

  27. [35]

    Extreme scale de novo metagenome assembly

    Evangelos Georganas, Rob Egan, Steven Hofmeyr, Eugene Goltsman, Bill Arndt, Andrew Tritt, Aydin Buluç, Leonid Oliker, and Katherine Yelick. Extreme scale de novo metagenome assembly. In Proceedings of the International Conference for High Performance Computing, Networking, Sto...

    2018

  28. [36]

    Gleich, L

    D. Gleich, L. Zhukov, and P. Berkhin. Fast parallel PageRank: a linear system approach. Technical Report YRL-2004-038, Yahoo! Research, 2004

    2004

  29. [37]

    Gonzalez, Yucheng Low, Haijie Gu, Danny Bickson, and Carlos Guestrin

    Joseph E. Gonzalez, Yucheng Low, Haijie Gu, Danny Bickson, and Carlos Guestrin. PowerGraph: Distributed graph- parallel computation on natural graphs. In Proceedings of the USENIX Conference on Operating Systems Design and Implementation (OSDI), OSDI ’12, pages 17–30. USENIX A...

    2012

  30. [38]

    Gustavson

    Fred G. Gustavson. Two fast algorithms for sparse matrices: Multiplication and permuted transposition. ACM Transactions on Mathematical Software (TOMS) , 4(3):250–269, September 1978

    1978

  31. [39]

    An experimental comparison of Pregel-like graph processing systems

    Minyang Han, Khuzaima Daudjee, Khaled Ammar, M Tamer Özsu, Xingfang Wang, and Tianqi Jin. An experimental comparison of Pregel-like graph processing systems. Proceedings of the VLDB Endowment , 7(12):1047–1058, August 2014

    2014

  32. [40]

    Harris, K

    Charles R. Harris, K. Jarrod Millman, Stéfan J. van der Walt, Ralf Gommers, Pauli Virtanen, David Cournapeau, Eric Wieser, Julian Taylor, Sebastian Berg, Nathaniel J. Smith, Robert Kern, Matti Picus, Stephan Hoyer, Marten H. van Kerkwijk, Matthew Brett, Allan Haldane, Jaime Fe...

    2020

  33. [41]

    Junction tree variational autoencoder for molecular graph generation

    Wengong Jin, Regina Barzilay, and Tommi Jaakkola. Junction tree variational autoencoder for molecular graph generation. In Jennifer Dy and Andreas Krause, editors, Proceedings of the 35th International Conference on Machine Learning, volume 80 of Proceedings of Machine Learnin...

    2018

  34. [42]

    Owens, Yuechao Pan, Leyuan Wang, Xiaoyun Wang, and Carl Yang

    Ben Johnson, Weitang Liu, Agnieszka Łupińska, Muhammad Osama, John D. Owens, Yuechao Pan, Leyuan Wang, Xiaoyun Wang, and Carl Yang. HIVE year 1 report: Executive summary. https://gunrock.github.io/docs/hive_year1_ summary.html, November 2018

    2018

  35. [43]

    Johnson and Catherine C

    David S. Johnson and Catherine C. McGeoch, editors. Network Flows and Matching: First DIMACS Implementation Challenge, volume 12. American Mathematical Society, 1993

    1993

  36. [44]

    Adaptive methods for the computation of PageRank

    Sepandar Kamvar, Taher Haveliwala, and Gene Golub. Adaptive methods for the computation of PageRank. Linear Algebra and its Applications , 386:51–65, July 2004. Special Issue on the Conference on the Numerical Solution of Markov Chains 2003. ACM Trans. Math. Softw., Vol. 1, No...

    2004

  37. [45]

    R. Karp, C. Schindelhauer, S. Shenker, and B. Vöcking. Randomized rumor spreading. In Proceedings of the 41st Annual Symposium on Foundations of Computer Science , pages 565–574, November 2000

    2000

  38. [46]

    Owens, Carl Yang, Marcin Zalewski, and Timothy Mattson

    Jeremy Kepner, Peter Aaltonen, David Bader, Aydın Buluç, Franz Franchetti, John Gilbert, Dylan Hutchison, Manoj Kumar, Andrew Lumsdaine, Henning Meyerhenke, Scott McMillan, Jose Moreira, John D. Owens, Carl Yang, Marcin Zalewski, and Timothy Mattson. Mathematical foundations o...

    2016

  39. [47]

    Farzad Khorasani, Keval Vora, Rajiv Gupta, and Laxmi N. Bhuyan. CuSha: Vertex-centric graph processing on GPUs. In Proceedings of the 23rd International Symposium on High-performance Parallel and Distributed Computing , HPDC ’14, pages 239–252, June 2014

    2014

  40. [48]

    Michael Kircher and Prashant Jain. Pooling. In Alan O’Callaghan, Jutta Eckstein, and Christa Schwanninger, editors, Proceedings of the 7th European Conference on Pattern Languages of Programms , EuroPLoP 2002, pages 497–510. UVK—Universitätsverlag Konstanz, July 2002

    2002

  41. [49]

    GraphChi: Large-scale graph computation on just a PC

    Aapo Kyrola, Guy Blelloch, and Carlos Guestrin. GraphChi: Large-scale graph computation on just a PC. InProceedings of the USENIX Conference on Operating Systems Design and Implementation (OSDI) , OSDI ’12, pages 31–46, Berkeley, CA, USA, 2012. USENIX Association

    2012

  42. [50]

    Gráfok és mátrixok (graphs and matrices)

    Dénes Kőnig. Gráfok és mátrixok (graphs and matrices). Matematikai és Fizikai Lapok , 38:116–119, 1931. English translation by Gábor Szárnyas, Sept. 2020, https://arxiv.org/abs/2009.03780

    1931 arXiv

  43. [51]

    Howie Huang

    Hang Liu and H. Howie Huang. Enterprise: Breadth-first graph traversal on GPUs. In Proceedings of the International Conference for High Performance Computing, Networking, Storage and Analysis , SC ’15, pages 68:1–68:12, November 2015

    2015

  44. [52]

    Austern, Aart J

    Grzegorz Malewicz, Matthew H. Austern, Aart J. C. Bik, James C. Dehnert, Ilan Horn, Naty Leiser, and Grzegorz Czajkowski. Pregel: A system for large-scale graph processing. In Proceedings of the 2010 ACM SIGMOD International Conference on Management of Data , SIGMOD ’10, pages...

    2010

  45. [53]

    Mattson, Carl Yang, Scott McMillan, Aydin Buluç, and José E

    Timothy G. Mattson, Carl Yang, Scott McMillan, Aydin Buluç, and José E. Moreira. GraphBLAS C API: Ideas for future versions of the specification. In IEEE High Performance Extreme Computing Conference (HPEC) , September 2017

    2017

  46. [54]

    Thinking like a vertex: A survey of vertex-centric frameworks for large-scale distributed graph processing

    Robert Ryan McCune, Tim Weninger, and Greg Madey. Thinking like a vertex: A survey of vertex-centric frameworks for large-scale distributed graph processing. ACM Computing Surveys, 48(2):1–39, November 2015

    2015

  47. [55]

    Adam McLaughlin and David A. Bader. Scalable and high performance betweenness centrality on the GPU. In Proceedings of the International Conference for High Performance Computing, Networking, Storage and Analysis , SC ’14, pages 572–583. IEEE, November 2014

    2014

  48. [56]

    Merge-based parallel sparse matrix-vector multiplication

    Duane Merrill and Michael Garland. Merge-based parallel sparse matrix-vector multiplication. In Proceedings of the International Conference for High Performance Computing, Networking, Storage and Analysis , SC ’16, pages 678–689, November 2016

    2016

  49. [57]

    Scalable GPU graph traversal

    Duane Merrill, Michael Garland, and Andrew Grimshaw. Scalable GPU graph traversal. In Proceedings of the ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming (PPoPP) , PPoPP ’12, pages 117–128, February 2012

    2012

  50. [58]

    IBM GraphBLAS

    Jose Moreira and Bill Horn. IBM GraphBLAS. http://github.com/IBM/ibmgraphblas, 2018

    2018

  51. [59]

    A lightweight infrastructure for graph analytics

    Donald Nguyen, Andrew Lenharth, and Keshav Pingali. A lightweight infrastructure for graph analytics. InProceedings of the Twenty-Fourth ACM Symposium on Operating Systems Principles (SOSP ’13), pages 456–471. ACM Press, November 2013

    2013

  52. [60]

    Muhammad Osama, Minh Truong, Carl Yang, Aydın Buluç, and John D. Owens. Graph coloring on the GPU. In Proceedings of the Workshop on Graphs, Architectures, Programming, and Learning , GrAPL 2019, pages 231–240, May 2019

    2019

  53. [61]

    RAPIDS: Open GPU data science

    Josh Patterson. RAPIDS: Open GPU data science. https://rapids.ai/, 2018

    2018

  54. [62]

    Roger Pearce, Maya Gokhale, and Nancy M. Amato. Faster parallel traversal of scale free graphs at extreme scale with vertex delegates. In Proceedings of the International Conference for High Performance Computing, Networking, Storage and Analysis, SC ’14, pages 549–559. IEEE, ...

    2014

  55. [63]

    Priest, and Geoffrey Sanders

    Roger Pearce, Trevor Steil, Benjamin W. Priest, and Geoffrey Sanders. One quadrillion triangles queried on one million processors. In 2019 IEEE High Performance Extreme Computing Conference (HPEC) . IEEE, September 2019

    2019

  56. [64]

    Ryan Rossi and Nesreen K. Ahmed. The network data repository with interactive graph analytics and visualization. In Proceedings of the Twenty-Ninth AAAI Conference on Artificial Intelligence , pages 4292–4293, January 2015

    2015

  57. [65]

    X-Stream: Edge-centric graph processing using streaming partitions

    Amitabha Roy, Ivo Mihailovic, and Willy Zwaenepoel. X-Stream: Edge-centric graph processing using streaming partitions. In Proceedings of the Twenty-Fourth ACM Symposium on Operating Systems Principles - SOSP ’13 , pages 472–488. ACM Press, November 2013

    2013

  58. [66]

    GraphChallenge.org: Raising the bar on graph analytic performance

    Siddharth Samsi, Vijay Gadepally, Michael Hurley, Michael Jones, Edward Kao, Sanjeev Mohindra, Paul Monticciolo, Albert Reuther, Steven Smith, William Song, Diane Staheli, and Jeremy Kepner. GraphChallenge.org: Raising the bar on graph analytic performance. In 2018 IEEE High P...

    2018

  59. [67]

    Shubhabrata Sengupta, Mark Harris, Michael Garland, and John D. Owens. Efficient parallel scan algorithms for many-core GPUs. In Jakub Kurzak, David A. Bader, and Jack Dongarra, editors,Scientific Computing with Multicore and Accelerators, Chapman & Hall/CRC Computational Scie...

    2011

  60. [68]

    Shubhabrata Sengupta, Mark Harris, Yao Zhang, and John D. Owens. Scan primitives for GPU computing. InProceedings of the 22nd ACM SIGGRAPH/EUROGRAPHICS Symposium on Graphics Hardware , GH ’07, pages 97–106, August 2007

    2007

  61. [69]

    Seshadhri, Ali Pinar, and Tamara G

    C. Seshadhri, Ali Pinar, and Tamara G. Kolda. An in-depth study of stochastic Kronecker graphs. In 2011 IEEE 11th International Conference on Data Mining , pages 587–596. IEEE, December 2011

    2011

  62. [70]

    Graph processing on GPUs: A survey

    Xuanhua Shi, Zhigao Zheng, Yongluan Zhou, Hai Jin, Ligang He, Bo Liu, and Qiang-Sheng Hua. Graph processing on GPUs: A survey. ACM Computing Surveys, 50(6):1–35, January 2018

    2018

  63. [71]

    An 𝑂(log 𝑛) parallel connectivity algorithm

    Yossi Shiloach and Uzi Vishkin. An 𝑂(log 𝑛) parallel connectivity algorithm. Journal of Algorithms, 3(1):57–67, March 1982

    1982

  64. [72]

    Blelloch

    Julian Shun and Guy E. Blelloch. Ligra: a lightweight graph processing framework for shared memory. In Proceedings of the 18th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming , PPoPP ’13, pages 135–146, February 2013

    2013

  65. [73]

    Multicore triangle computations without tuning

    Julian Shun and Kanat Tangwongsan. Multicore triangle computations without tuning. In 2015 IEEE 31st International Conference on Data Engineering , pages 149–160. IEEE, April 2015

    2015

  66. [74]

    Slota, Sivasankaran Rajamanickam, and Kamesh Madduri

    George M. Slota, Sivasankaran Rajamanickam, and Kamesh Madduri. BFS and coloring-based parallel algorithms for strongly connected components and related problems. In 2014 IEEE 28th International Parallel and Distributed Processing Symposium. IEEE, May 2014

    2014

  67. [75]

    A fast GPU algorithm for graph connectivity

    Jyothish Soman, Kothapalli Kishore, and P J Narayanan. A fast GPU algorithm for graph connectivity. In 2010 IEEE International Symposium on Parallel and Distributed Processing, Workshops and Phd Forum (IPDPSW) . IEEE, April 2010

    2010

  68. [76]

    GraphMat: High performance graph analytics made productive

    Narayanan Sundaram, Nadathur Satish, Md Mostofa Ali Patwary, Subramanya R Dulloor, Michael J Anderson, Satya Gau- tam Vadlamudi, Dipankar Das, and Pradeep Dubey. GraphMat: High performance graph analytics made productive. Proceedings of the VLDB Endowment (VLDB) , 8(11):1214–1...

    2015

  69. [77]

    Leyuan Wang, Yangzihao Wang, Carl Yang, and John D. Owens. A comparative study on exact triangle counting algorithms on the GPU. In Proceedings of the 1st High Performance Graph Processing Workshop , HPGP ’16, pages 1–8, May 2016

    2016

  70. [78]

    Riffel, and John D

    Yangzihao Wang, Yuechao Pan, Andrew Davidson, Yuduo Wu, Carl Yang, Leyuan Wang, Muhammad Osama, Chenshan Yuan, Weitang Liu, Andy T. Riffel, and John D. Owens. Gunrock: GPU graph analytics. ACM Transactions on Parallel Computing (TOPC), 4(1):3:1–3:49, August 2017

    2017

  71. [79]

    Wolf, Mehmet Deveci, Jonathan W

    Michael M. Wolf, Mehmet Deveci, Jonathan W. Berry, Simon D. Hammond, and Sivasankaran Rajamanickam. Fast linear algebra-based triangle counting with KokkosKernels. In IEEE High Performance Extreme Computing Conference (HPEC). IEEE, September 2017

    2017

  72. [80]

    Carl Yang, Aydın Buluç, and John D. Owens. Design principles for sparse matrix multiplication on the GPU. In Marco Aldinucci, Luca Padovani, and Massimo Torquati, editors, Proceedings of the IEEE International European Conference on Parallel and Distributed Computing (Euro-Par...

    2018

  73. [81]

    Carl Yang, Aydın Buluç, and John D. Owens. Implementing push-pull efficiently in GraphBLAS. In Proceedings of the International Conference on Parallel Processing , ICPP 2018, pages 89:1–89:11, August 2018

    2018

  74. [82]

    Carl Yang, Yangzihao Wang, and John D. Owens. Fast sparse matrix and sparse vector multiplication algorithm on the GPU. In Graph Algorithms Building Blocks , GABB 2015, pages 841–847, May 2015

    2015

  75. [83]

    Understanding the overheads of launching CUDA kernels

    Lingqi Zhang, Mohamed Wahib, and Satoshi Matsuoka. Understanding the overheads of launching CUDA kernels. In Proceedings of the International Conference on Parallel Processing, Poster Session , ICPP 2019, August 2019

    2019

  76. [84]

    GBTL-CUDA: Graph algorithms and primitives for GPUs

    Peter Zhang, Marcin Zalewski, Andrew Lumsdaine, Samantha Misurda, and Scott McMillan. GBTL-CUDA: Graph algorithms and primitives for GPUs. In IEEE International Parallel and Distributed Processing Symposium Workshops (IPDPSW), pages 912–920. IEEE, May 2016

    2016

  77. [85]

    Parallel algorithms for finding connected components using linear algebra

    Yongzhe Zhang, Ariful Azad, and Aydın Buluç. Parallel algorithms for finding connected components using linear algebra. Journal of Parallel and Distributed Computing , 144:14–27, October 2020

    2020

  78. [86]

    -maxiters

    Yongzhe Zhang, Ariful Azad, and Zhenjiang Hu. FastSV: A distributed-memory connected component algorithm with fast convergence. In Proceedings of the SIAM Conference on Parallel Processing for Scientific Computing , PP20, pages 46–57. SIAM, February 2020. A LINES OF CODE For t...

    2020

Pith tools

Reviewed August 14, 2026 · model on record in the stance chip above.