- Rating
- 3
- Confidence
- 3
- Informativeness
- 2
- Presentation
- 3
- Soundness
- 2
Read review
Paper summary
The paper presents optimized SpMV optimizations implementations for different sparsity patterns and GPU architectures. The authors introduce SPARROW, ɑ 2-stɑge kernel generation framework inspired by human cognition: System 1 (based on intuition): sparsity-aware decision model: pairs ɑ multi scale Transformer encoder (different-sized occupancy patches) with ɑ global feature MLP (matrix dims, nnz, etc.) to rank an expert library of 22 SpMV strategy topologies. System 2 (feedback-guided tree search agent): takes the top-ranked strategy and iteratively refines parameters, thread mappings, code structure, correctness validation and execution profiling over ɑ search budget of 10 attempts. The evaluation is done on 291 SuiteSpɑrse matrices. SPARROW achieves 1.74x speedup over cuSPARSE on NVIDIA A-100 and 3.9x speedup over hipSpɑrse on Hygon DCU.
Critical strengths
SPARROW achieves higher speedup compared with existing expert-driven strategies and only hardware guided feedback search. By combining of offline-learned structural prior and hardware-in-the-loop search, it streamlines the search and reduces LLM context/search budget. It achieves good accuracy by encoding both local spatial occupancy patches across multiple grid granularities and global statistics. It achieves 87% compilation success rate vs. general coding agents like Codex (67%) by constraining the agent to expert-designed structured templates.
Critical weaknesses
While the results are promising, this study does not provide any insights on what kinds of sparsity patterns are conducive to what algorithmic strategies. For instance, how do unstructured vs. locally dense or power-law sparsity structures shift thread tile sizes, shared memory usage and load balancing?
The paper also does not provide any information on what are the strategies that were finally chosen for each type of hardware architecture. Are there any lessons learned that can be used to further optimize the search?
In many workloads, the sparsity changes is not known or changes during execution. The overhead of the proposed method is too high to be useful for such cases.
Questions for authors
Are the benefits listed here due to agentic search or due to sparsity-aware expert strategies? Can the agent recover from ɑ suboptimal initial strategy?
What is the chosen layout for SpMV processing? If there are different layouts, is the memory footprint and conversion overhead of specialized storage layouts considered?
How would SPARROW handle dynamic graphs or streamlining workloads where the sparsity pattern in not known apriori? System 2 search loop introduces significant compilation and profiling overhead. Will you then fallback to System 1?
The x axis of Figure 5 is the number of non-zeroes. What are the corresponding sparsity numbers? In other words, how would the figure change if the GFLOPS was plotted against density?
In Figure 5, how close are the SPARROW implementations to theoretical limits? Was a roofline analysis done here?
The compiled candidates are checked against reference SpMV using one deterministic input vector. Is one reference sufficient to check for correctness?
3 comments
Q1. Are the performance gains attributable to agentic search or sparsity-aware expert strategies? Can the agent recover from a suboptimal initial strategy?
- Q1.A benefits from agent search or sparsity-aware expert strategies?: As shown in Table.3 in our paper
| Agent Design | GFLOPS | Speedup* | fast1 | fast2 |
|---|---|---|---|---|
| Without sparsity-aware | 190.33 | 1.59× | 86% | 31% |
| Without agent | 134.59 | 1.13× | 62% | 14% |
| Sparsity-aware with Agent (GLM) | 207.38 | 1.74× | 90% | 40% |
Speedup is calculated against cuSPARSE.
The ablation study in this Table addresses this question, SPARROW outperforms both the expert-driven strategies and hardware-feedback-only search, demonstrating that the performance gains arise from the complementary contributions of sparsity-aware structural priors and hardware-guided agentic optimization, rather than from either component alone.
- Q1.B Can the agent recover from ɑ suboptimal initial strategy? Yes, the agent can recover because the LLM is not restricted to refining the initial strategy. When profiling indicates that a strategy has reached a performance plateau, the agent can explore alternative strategies. For example, for the boneS01 matrix, the agent initially explored a strategy assigning ten nonzeros to each thread. After several iterations without further performance improvement, it switched to an alternative strategy that processes eight rows per warp. The final implementation achieved a 50% performance improvement over the initial strategy.
Q2. What is the chosen layout for SpMV processing? If there are different layouts, is the memory footprint and conversion overhead of specialized storage layouts considered?
- Sparse matrix have many layout: CSR, COO, ELL, DIA. However SPARROW generates specific layouts and corresponding CUDA kernels for each matrix by employing a combination of techniques: sorting, partitioning into rows or non-zero elements, padding, interleaved storage, and the use of index metadata. which is not a known format but a specific NEW layout for this target matrix. This design philosophy is consistent with prior work such as AlphaSparse [1].
- We have consider the layout conversion overhead. When a selected strategy requires converting the input matrix into a specialized layout, the conversion cost is accounted for as preprocessing overhead.
Q3. How does SPARROW handle dynamic graphs or streaming workloads where sparsity is not known a priori?
If the sparsity pattern cannot be determined prior to execution, a set of predefined expert heuristics—characterized by conservative upper bounds and aggressive lower bounds—can be employed to initiate the optimization process.
Q4. How would Figure 5 change if GFLOPS were plotted against matrix density?
We agree that plotting performance against matrix density would provide a complementary perspective to the current analysis based on the number of nonzeros.
We have replaced a Fig.5 in revised version with a plot of GFLOPS against matrix density, defined as nnz/(m × n), to further illustrate how performance varies across matrices with different sparsity levels.
Q5. How close are SPARROW implementations to the theoretical performance limits?
Since SpMV is predominantly memory-bandwidth-bound, we conducted a bandwidth-based roofline analysis to evaluate the achieved performance relative to the corresponding theoretical upper bounds.
The roofline figure has been add to the revised version, in Appendix. Fig.8.
The results are summarized below: We define as the proportion of matrices that reach above of their peak value.
| Method | |||
|---|---|---|---|
| SPARROW | 70% | 32% | 9% |
| cuSPARSE | 19% | 0% | 0% |
Q6. Is a single deterministic input vector sufficient for correctness validation?
We agree that comparison against a reference SpMV implementation using a single deterministic input vector provides only limited empirical validation and cannot rule out indexing or reduction errors that may be masked by that particular input.
To strengthen correctness validation, we will employ multiple reproducible randomized input vectors. For the final selected kernels, we will perform more comprehensive validation using independent inputs and check output initialization across repeated kernel invocations.
In our current follow-up experiments, the kernels generated are all correct.
REFERENCES
[1]AlphaSparse:Z. Du, J. Li, Y. Wang, X. Li, G. Tan, N. Sun. AlphaSparse: Generating High Performance SpMV Codes Directly from Sparse Matrices. SC 2022. DOI: 10.1109/SC41404.2022.00071。
Thank you for doing the additional experiments. This has helped me understand your method better. My score is till 3.
W1. Understanding the relationship between sparsity patterns and optimization strategies.
In fact, there is no "golden rule" that can accurately predict the optimal optimization strategy for a given sparse pattern; this depends on both hardware characteristics and the properties of the sparse matrix. Sometimes, even similar sparse patterns may require different optimal strategies.
However, we did encounter some counterintuitive cases where the performance of expert-optimized operators degraded quite severely. As a representative example, consider the boyd1 matrix. Under the storage representation used in our experiments, it contains 93,279 rows and 652,246 nonzeros. Among these rows, 93,261 contain only one nonzero each, while the remaining 18 rows account for 85.70% of all nonzeros, with the longest row containing 93,261 nonzeros. This represents an extremely imbalanced mixture of short and long rows.
This example illustrates an important optimization principle: when a small number of exceptionally long rows dominate the computational workload, partitioning thread blocks by a fixed number of rows can lead to severe load imbalance. Allowing long rows to be distributed across multiple warps and blocks exposes additional parallelism across SMs and improves workload distribution.
The current challenge in optimizing spMV (sparse matrix-vector multiplication) is not a lack of mappings between sparse patterns and optimization strategies, but rather the instability of these mappings. A given matrix might require "Strategy A" when running on an A100 GPU, yet necessitate "Strategy B" on a BW100.
W2. Architecture-specific strategy selection and lessons for future search.
The optimal strategy depends on both the sparsity structure and hardware characteristics, such as warp/wavefront organization, memory hierarchy, and resource constraints. This is precisely why SPARROW combines a hardware-independent structural prior with hardware-in-the-loop optimization.
Our analysis reveals that the two GPUs exhibit common high-level strategy patterns, while the specific levels of work partitioning and parameter granularity need to be adapted to the target device. A common characteristic is that workloads are partitioned according to sparsity structures, with computation organized through a combination of data layouts, local accumulation, and segmented reduction. Two strategies frequently selected on both GPUs are thread-level column partitioning with local reduction and NNZ-based partitioning with bitmaps and warp-level segmented reduction. The differences are mainly manifested at two levels:
Consider the same matrix,
ASIC_100k. With the same strategy template and a fixed thread block size of 256, varying only the number of nonzeros (NNZs) processed per thread block yields the following results:These results demonstrate that the same workload granularities can exhibit opposite performance rankings on different devices, highlighting the importance of hardware-specific parameter tuning even when the same high-level optimization strategy is employed.
The lesson we learnt is that we can envision extending SPARROW with a persistent experience database that records successful strategies, sparsity characteristics, hardware configurations, and profiling results. Such a database could serve as long-term memory for the agent.
W3. Optimization overhead and applicability to dynamic sparsity.
We agree that SPARROW has limited applicability to workloads with frequently changing sparsity patterns, where the optimization overhead may outweigh the performance benefits. However, in many important SpMV applications, such as iterative solvers, algebraic multigrid (AMG), and preconditioned iterative methods, the sparsity pattern is typically available before repeated SpMV executions and remains unchanged across multiple iterations. In such scenarios, the one-time optimization cost can be amortized over sufficiently many SpMV operations. This assumption is also common in existing sparsity-aware optimization approaches, such as SparseZeta. Therefore, SPARROW targets an important class of workloads with reusable sparsity patterns rather than arbitrary dynamic sparsity.