GPUs All Grown-Up: Fully Device-Driven SpMV Using GPU Work Graphs

Of course. Here is a peer review of the paper from the perspective of "The Guardian."

---

Review Form

Reviewer: The Guardian (Adversarial Skeptic)

Summary

The authors present a set of Sparse Matrix-Vector Multiplication (SpMV) implementations using a novel "Work Graphs" programming model on AMD GPUs. They claim this model, which enables fine-grained, on-device dynamic scheduling, significantly outperforms existing state-of-the-art library implementations from rocSPARSE. The primary claims are substantial performance speedups (up to 7.19x), drastically reduced memory overhead for auxiliary data structures, and simplified code complexity. While the reported performance numbers are impressive, the work's conclusions rest on a precarious methodological foundation due to the use of a non-standard, proprietary software and firmware stack, which introduces a critical confounding variable that undermines the central claims.

Strengths

1. Significant Reduction in Memory Overhead: The most compelling and defensible result is the drastic reduction in memory footprint for supporting data structures. Figure 7 clearly demonstrates that the Work Graphs approaches ("WG Fused," "WG Vanilla") have a small, fixed memory cost (~25-41 MiB), in stark contrast to rocSPARSE LRB ("RS Lrb"), whose memory requirement scales with the matrix dimensions to hundreds of megabytes. This is a clear and practical advantage.

2. Detailed Performance Analysis: The evaluation in Section 6 is thorough. The use of hardware performance counters (Figure 5) to investigate memory system utilization provides valuable low-level insight that supports the performance narrative (e.g., improved L0/L1 cache utilization). Furthermore, the breakdown of multi-iteration performance for "regular" versus "irregular" matrices (Figure 6b) shows a commendable level of detailed analysis.

3. Demonstration of a Potentially Powerful Model: The paper successfully demonstrates that a dataflow-driven, on-device scheduling model can, in principle, address the known inefficiencies of static, host-driven kernel launches for irregular workloads like SpMV. The concept of fusing preprocessing with computation for short rows in the "WG Fused" variant is a logical application of this model.

Weaknesses

1. Critical Methodological Flaw: Confounding Software Stacks: The entire comparison is fundamentally unsound. The authors compare their proposed method, built on a research compiler (AnyDSL) and a private, vendor-provided Platform Abstraction Library (PAL) with custom firmware (Section 5), against a baseline built on the public ROCm/HSA stack. It is impossible to isolate the performance impact of the Work Graphs model from the performance impact of the underlying software stack. The observed speedups could partially or wholly originate from lower dispatch overheads in PAL for this specific use case, different code generation from the AnyDSL compiler, or other unstated optimizations in the private software stack.

2. Insufficient Rebuttal of the Confounding Variable: The authors attempt to address the software stack discrepancy in Appendix A by porting the baseline LRB algorithm to their stack ("AD Lrb"). They show "AD Lrb" is slightly slower than "RS Lrb" and conclude their stack is at a disadvantage, thereby strengthening their claims. This reasoning is specious. It only shows their stack is not well-optimized for a sequence of traditional kernel launches. It is entirely plausible that the PAL stack is, conversely, highly optimized for launching a single, large, complex work graph, which is precisely what their proposed method does. The comparison remains apples-to-oranges.

3. Lack of Reproducibility: The work relies on custom AMD firmware, drivers, and libraries that are not publicly available (Section 5.1). As such, the results are completely irreproducible by the wider research community. This is a severe weakness for a paper submitted to an academic venue, as it prevents verification and extension of the work by others.

4. Failure to Isolate Performance Contributions: The "WG Fused" implementation, which provides the best results, conflates two distinct optimizations: (1) the dynamic scheduling of long rows via Work Graphs, and (2) kernel fusion for short rows processed directly within the binning node. The evaluation does not contain an ablation study to disentangle these effects. It is unclear how much of the 7.19x speedup comes from fusion (which can sometimes be implemented with other techniques) versus the novel scheduling capability itself.

Questions to Address In Rebuttal

1. How can the authors definitively prove that the reported performance gains are a direct result of the Work Graphs scheduling paradigm, and not an artifact of the fundamentally different and proprietary AnyDSL/PAL software stack having lower overheads for this workload pattern compared to the public ROCm/HSA stack?

2. The Appendix A comparison shows the AnyDSL/PAL stack is slower for a sequence of kernel launches. Could the authors provide microbenchmark data comparing the dispatch latency of a single, complex work graph via PAL versus the cumulative dispatch latency of a series of small kernels via HSA? This is critical to substantiating the claim that the stack is not the source of the speedup.

3. To properly attribute the performance gains of the "WG Fused" model, can the authors provide an ablation study? Specifically, a version must be evaluated that uses the Work Graph model to dispatch all rows to specialized downstream nodes (like "WG Vanilla") but uses the more efficient thread allocation logic of "WG Fused," thereby isolating the benefit of kernel fusion from the benefit of dynamic scheduling.

4. Given the complete reliance on a private and inaccessible software/firmware stack, what is the path forward for making this work reproducible? Can the authors commit to a timeline for a public release of the necessary components? Without a path to reproducibility, the work is more of a vendor whitepaper than a scientific contribution.

Of course. Here is a peer review of the paper from the perspective of "The Synthesizer."

---

Review Form:

Reviewer: The Synthesizer (Contextual Analyst)

Summary

This paper presents a novel approach to sparse matrix-vector multiplication (SpMV) that leverages the emerging "GPU Work Graphs" programming model to achieve a fully device-driven execution. The core contribution is the demonstration that both the traditionally host-managed preprocessing (binning rows by length) and the subsequent parallel computation can be unified into a single, dynamic dataflow graph that executes entirely on the GPU. This eliminates host-CPU interaction and allows for fine-grained, on-the-fly scheduling of workgroups to specialized compute kernels, leading to interleaved execution that improves cache locality and hardware utilization.

The authors implement and evaluate several variants of this approach, culminating in a "fused" version that processes short rows directly within the binning node and only offloads longer, more complex rows to downstream nodes. Their results, benchmarked across 59 sparse matrices, show significant performance improvements of up to 7.19x (mean 3.35x) over the state-of-the-art rocSPARSE LRB implementation for single-iteration SpMV. Furthermore, their methods remain competitive or superior to the highly-optimized CSR-Adaptive algorithm for a realistic number of repeated multiplications. The work also highlights significant secondary benefits, including a drastically reduced and fixed memory footprint for metadata and lower implementation complexity.

Strengths

The primary strength of this paper is its outstanding contextual significance. It serves as a compelling and timely case study for a paradigm shift in GPU computing—from a host-orchestrated, bulk-synchronous model to a more autonomous, dataflow-driven one.

1. Demonstration of a New Execution Model: SpMV is a perfect "poster child" for the limitations of traditional GPU programming. By successfully applying GPU Work Graphs to this notoriously irregular problem, the authors provide the community with a clear and powerful demonstration of what this new hardware capability enables. This work bridges the gap between an abstract hardware feature and a concrete, high-impact application, effectively showing how "GPUs are growing up."

2. Excellent Problem Framing and Context: The background section (Section 2, page 2) effectively situates Work Graphs within the history of GPU scheduling, drawing clear distinctions between this new model and prior art like CUDA/HIP Graphs (coarse-grained, static) and Dynamic Parallelism (kernel-level granularity). This contextualization is crucial for understanding why Work Graphs represent a fundamental step forward.

3. Holistic and Convincing Evaluation: The empirical evaluation is thorough and persuasive.

   • The performance gains are not merely incremental; they are substantial enough to command attention (Figure 4, page 10).
   • The analysis thoughtfully covers both single-iteration (Section 6.1) and multi-iteration (Section 6.2) scenarios, acknowledging the amortization trade-offs that dominate real-world use cases.
   • Crucially, the authors look beyond raw speed. The analysis of memory overhead (Figure 7, page 12) and implementation complexity (Table 3, page 12) paints a complete picture. The finding that the Work Graphs approach uses a fixed ~25 MiB of memory, versus a data-dependent footprint that scales to hundreds of megabytes for rocSPARSE LRB, is a powerful secondary result with practical implications for memory-constrained systems.

4. Enabling Future Research: This paper lays the groundwork for rethinking many other irregular algorithms on GPUs. The core concept—on-device classification and dynamic dispatch to specialized workers—is broadly applicable to graph analytics (e.g., processing nodes based on degree), particle methods (e.g., sorting interactions by distance), and adaptive mesh refinement. This work provides both the inspiration and a methodological template for future explorations in these areas.

Weaknesses

The weaknesses of this paper are largely related to the nascent state of the underlying technology rather than fundamental flaws in the research itself. However, they are important to acknowledge.

1. Limited Generality and Reproducibility: The work relies on a non-standard, vendor-specific toolchain (AnyDSL combined with a custom build of AMD's PAL) to access the Work Graphs feature. This is a significant barrier to reproducibility and adoption for the broader HPC community, which primarily operates within standardized frameworks like ROCm/HIP and CUDA. While the authors are transparent about this, it currently situates their work as a "proof of concept" rather than a readily deployable solution.

2. Single Architecture Study: The evaluation is performed on a single AMD RDNA3-based GPU. The remarkable performance gains are likely tied to the specific design of its Command Processor and its ability to manage the dataflow of records between nodes efficiently. It is unclear how these concepts and performance characteristics would translate to other architectures, such as NVIDIA's, which may have different hardware support for fine-grained, on-device scheduling (e.g., via Persistent Thread Blocks or other future mechanisms).

3. Potential Understatement of Broader Impact: While the paper is strong, its focus remains tightly on SpMV. It could benefit from a more explicit discussion of how the demonstrated principles could be generalized into a programming pattern or library abstraction for other irregular, data-driven problems. The paper proves that it works for SpMV but could do more to articulate how the pattern can be used elsewhere.

Questions to Address In Rebuttal

1. Path to Mainstream Adoption: Given the reliance on a custom toolchain, what do the authors see as the most viable path for integrating these device-driven techniques into mainstream HPC ecosystems? For instance, could the rocSPARSE library itself be evolved to use Work Graphs internally, abstracting the complexity from the user? Or would this require fundamental extensions to programming models like HIP, SYCL, or OpenCL?

2. Architectural Dependencies: Can the authors speculate on the key hardware features of the AMD Command Processor that are most critical to their success? For example, is it the size of the on-chip buffers for records, the latency of the scheduling logic, or the efficiency of the semaphore mechanism described in Section 2.5 (page 4)? Understanding this could help predict the viability of this approach on future or different hardware.

3. Generalizing the "Fused" Approach: The "fused" kernel (Section 4.2.3, page 7) is a clever optimization that processes simple work (short rows) immediately and only dispatches complex work. This pattern of "filter and dispatch" seems highly generalizable. Could the authors comment on its application to other domains? For example, in graph algorithms, could a "fused" node process low-degree vertices locally while dispatching high-degree vertices to parallel reduction kernels?

4. Comparison to a "Perfectly Tuned" General Kernel: The performance of RS General deteriorates on matrices with long rows due to thread divergence. Could a RS General-style kernel that is heavily optimized for a specific, narrow range of row lengths (e.g., 1-16) achieve similar performance to the "in-place" processing in the WG Fused binning node? This would help clarify if the performance gain comes from the fusion itself (eliminating record traffic) or simply from better specialization, which could theoretically be achieved in other ways.

Review Form

Reviewer: The Innovator (Novelty Specialist)

---

Summary

This paper presents a novel implementation of sparse matrix-vector multiplication (SpMV) on GPUs by leveraging the emerging "GPU Work Graphs" programming model. The authors' central claim is that this new model, which enables fully device-driven, fine-grained, dataflow-based scheduling, can overcome the limitations of traditional host-driven, coarse-grained SpMV algorithms. They propose several variants, including a direct translation of the state-of-the-art Logarithmic Radix Binning (LRB) approach and a more advanced "fused" version that combines preprocessing and computation for short rows within a single graph node. The work demonstrates that this new approach significantly outperforms established rocSPARSE implementations in single- and multi-iteration scenarios, while simultaneously reducing memory overhead and implementation complexity.

The core contribution is the mapping of the SpMV problem onto this new hardware-supported, fine-grained dataflow execution paradigm. While the components—SpMV optimization techniques and dynamic scheduling concepts—are not new in isolation, their synthesis through the Work Graphs abstraction is novel and demonstrates a fundamentally different, and more effective, way to structure this irregular workload on a GPU.

Strengths

1. Clear Novelty in Application and Synthesis: The primary strength of this paper is its novelty. While the authors correctly attribute the Work Graphs model to prior industry development (Section 2.4, page 3), its application to a canonical HPC problem like SpMV is, to my knowledge, the first of its kind in the academic literature. The novelty lies not in inventing a new SpMV algorithm from scratch, but in demonstrating how to effectively map an existing state-of-the-art approach (LRB) to a completely new, hardware-managed, fine-grained dataflow execution model.

2. Significant Delta Over Prior Art: The paper does an excellent job of differentiating its contribution from prior attempts at dynamic GPU execution.

   • vs. Persistent Threads (Section 2.2, page 3): This work replaces complex, manually-managed software queues with a hardware/firmware-managed dataflow mechanism. This is a significant step forward, abstracting away a major source of complexity and overhead.
   • vs. CUDA/HIP Graphs (Section 2.1, page 2): The proposed method moves beyond static, coarse-grained (kernel-level) dependency graphs. Work Graphs operate at the workgroup/thread level, allowing for dynamic, data-dependent scheduling and interleaving of different processing stages, which is impossible with traditional task graphs.
   • vs. Traditional On-Device LRB (Section 3, page 5): The standard LRB implementation (visualized in Listing 1) requires multiple distinct kernel launches and global synchronizations to pass data between the binning and processing stages. The authors' "Vanilla" and "Fused" Work Graph approaches (Listing 2) collapse this into a single graph launch where work items flow dynamically between nodes. This elimination of stop-the-world synchronization points and host interaction is a key conceptual advance.

3. The "Fused" Variant as an Algorithmic Novelty: The most novel contribution is the "Fused" implementation (Section 4.2.3, page 7). This is more than a simple translation of LRB; it is an algorithmic insight enabled by the Work Graphs model. By processing short rows directly within the binning node and only dispatching records for longer, more complex rows, the authors have effectively implemented a form of dynamic, on-the-fly kernel fusion. This demonstrates a sophisticated understanding of how to leverage the new programming model to co-locate dependent computations and improve data locality, which is a genuinely new technique in the context of SpMV.

Weaknesses

1. Novelty is Tied to a Nascent, Vendor-Specific Feature: The entire contribution hinges on the availability of the "Work Graphs" feature, which is currently not part of a standardized, cross-vendor compute API like OpenCL or CUDA (it is rooted in Direct3D 12). While the work is an excellent case study of the feature's potential, its novelty is tightly coupled to the adoption and standardization of this specific hardware capability. The paper could be strengthened by a brief discussion of the path to broader availability (e.g., through Vulkan or other APIs) to better frame the long-term relevance of this novel approach.

2. Potential for Hidden Complexity in Tuning: The "Fused" kernel introduces a new decision point: the threshold at which a row is no longer considered "short" and must be passed to a downstream node. This work appears to have pre-defined thresholds for "short," "vector-wave," and "long" rows. This risks trading one form of complexity (manual scheduling) for another (heuristic tuning). The novelty of the approach would be stronger if the authors discussed how these thresholds were determined and how sensitive the performance is to their values. Is it possible for the graph itself to dynamically adapt these thresholds? That would be a truly groundbreaking contribution.

Questions to Address In Rebuttal

1. The performance of the novel "Fused" approach (Section 4.2.3, page 7) depends on the classification of rows into "short" and "long." Could the authors elaborate on how the length thresholds for this classification were determined? Are these static, hard-coded values, or can they be tuned for different architectures or matrix characteristics? How much does performance degrade if suboptimal thresholds are chosen?

2. The paper's most significant conceptual leap is arguably the "Fused" kernel, not the direct "Vanilla" translation. Could the authors expand on why this type of dynamic kernel fusion is fundamentally infeasible or inefficient with prior art like persistent threads or CUDA Dynamic Parallelism? This would further sharpen the paper's core novel contribution.

3. Given that the novelty is tied to the Work Graphs feature, what is the authors' perspective on its potential for standardization across different GPU vendors and inclusion in more common HPC programming environments beyond the Direct3D-family of APIs?