PaperlayerView exact revision on arXiv

Source-linked AI summary

Rethinking Sparse Formats for RISC-V: A Hierarchical Approach to High-Performance SpMV

Anna Pirova, Anastasia Vodeneeva, Konstantin Kovalev, Alexander Ustinov, Maksim Zagriadskov, Daniil Litvyakov, Arthur Kulik, Evgeny Kozinov, Valentin Volokitin, Iosif Meyerov

arXiv:2609.11352v1cs.DCcs.PF

TL;DR

Efficient SpMV remains challenging because sparse rows can underuse vector registers, irregular accesses impair cache use, and parallel work can be imbalanced. The paper implements nine formats in RVVLASparse and proposes HCSR, which partitions matrices into CSR and COO blocks. HCSR delivers an average 1.6× speedup over the best CSR implementation.

  • Problem

    CSR SpMV can underuse vector registers on highly sparse matrices, incur cache misses from irregular accesses, and suffer parallel load imbalance.

    Source: §3.2 · p. 3

  • Method

    The paper implements SpMV for nine sparse formats in RVVLASparse and proposes HCSR, which partitions matrices into CSR and COO blocks.

    Source: §1 · p. 2

  • Results

    HCSR achieves an average speedup of 1.6× compared with the best CSR implementation.

    Source: §6 · p. 20

  • Takeaways & Limitations

    HCSR improves memory-access efficiency for a wide range of sparse matrices.

    Source: §6 · p. 20

    Automatic format selection remains an auxiliary tool that gives a fairly good, but not the best, solution, and simple selection rules are not yet available.

    Source: §5.2 · p. 20

Abstract

from arXiv · show

The sparse matrix-vector multiplication (SpMV) algorithm is a fundamental computational kernel of linear algebra and serves as a building block for numerous applications, primarily iterative solvers for systems of linear equations used in scientific and engineering simulations. This paper compares vectorized implementations of the SpMV algorithm across eight established sparse matrix storage formats and proposes a novel modification of the CSR format, Hierarchical CSR (HCSR), which enhances SpMV performance on RISC-V processors. Our SpMV implementations utilize RVV 1.0 intrinsics and are publicly available as an open-source C++ library named RVVLASparse. Computational experiments conducted on SpacemiT K1 and K3 RISC-V boards demonstrate that selecting an appropriate matrix storage format accelerates SpMV computations by an average of 1.6x, while the proposed HCSR format achieves the shortest execution time among all considered formats across a broad class of sparse matrices.

1. Introduction

SpMV is a key kernel in iterative sparse-system solvers, but existing formats and implementations are not well adapted to RISC-V. The paper introduces HCSR and RVVLASparse, compares formats across RISC-V processors, and examines factors affecting format selection.

1. Introduction

  • Existing CPU sparse-linear-algebra libraries often use classic formats that fail to exploit modern SIMD fully and are not adapted for RISC-V; nonstandard formats are often standalone rather than integrated into solvers.Source: §1 · pp. 1–2
  • HCSR partitions matrices into CSR and COO blocks to improve memory-subsystem efficiency.Source: §1 · p. 2
  • 1.6x average SpMV performance improvement on RISC-V CPUs with HCSR versus scalar and typical vectorized CSR implementations.The comparison is against scalar and typical vectorized implementations for CSR.Source: §1 · p. 2
  • The paper compares SpMV performance across storage formats on two generations of RISC-V processors.Source: §1 · p. 2
  • The work examines format hyperparameter tunability and identifies sparse-matrix characteristics that influence format selection.Source: §1 · p. 2
  • RVVLASparse implements SpMV for nine sparse data structures and is released as publicly available open-source software.Source: §1 · p. 2

2. Related Work

Related work covers classical sparse formats and their modifications for vectorization, cache locality, and structured matrices. It also surveys automatic format selection and RISC-V SpMV implementations.

2. Related Work

  • CSR, CCS, and COO remain widely used general-purpose formats, while many later variants target SIMD-capable x86 processors and GPUs.Source: §2 · p. 2
  • CSR-derived formats group nonzeros into blocks or lanes to improve vector use and cache locality; other variants target regular matrix structures or combine formats.Examples include CSR5, CSR2, CVR, CSX, VBFS, BCSR, and hybrid formats such as HYB.Source: §2 · p. 2
  • Custom sparse formats are often standalone implementations, and integrating them into third-party solver packages can require substantial engineering effort.Source: §2 · p. 2
  • Prior automatic format-selection work includes decision trees, CNNs applied to matrix images, and methods that generate machine-designed formats and algorithms.The paper adapts ideas from WISE for selection based on matrix structure.Source: §2 · pp. 2–3
  • A related RISC-V study compared vectorized CSR, SELL-p, and JDS, reporting its best performance with SELL-p.Source: §2 · p. 3

3. SpMV Algorithm for Various Matrix Storage Formats

This section describes RVV 1.0 and OpenMP SpMV implementations across nine storage formats, including HCSR, and explains how storage layouts shape vectorized computation. It details HCSR’s two-level sparse-block hierarchy, its block-type-based kernel selection, and its scope for the RISC-V processors studied.

3.1. Sparse matrix-vector multiplication

  • The implementations cover nine formats in single and double precision using RVV 1.0 intrinsics and OpenMP.The formats are CSR, Sell-C-σ, CSR2, CSR5, CVR, VHCC, VNEC, LAV, and HCSR; the discussion focuses on the highest-performing formats and HCSR.Source: §3.1 · p. 3

3.2. CSR Format

  • CSR vectorization can underuse registers on highly sparse rows, while irregular accesses to b cause cache misses and poor reuse; parallel execution can also suffer load imbalance.The passage notes that dedicated load-balancing strategies can address the latter issue.Source: §3.2 · p. 3

3.3. Sell-C-σ Format

  • Sell-C-σ sorts rows within slices, groups them into chunks, and pads chunks to uniform row lengths; its column-wise layout enables contiguous matrix loads and avoids reductions.These properties can improve performance over vectorized CSR for some matrices.Source: §3.3 · p. 3

3.4. CSR5 Format

  • CSR5 [19] stores nonzeros in fixed-size dense tiles whose column-wise layout assigns each SIMD lane a column; tile descriptors encode row starts, offsets, and empty rows.Tile width ω corresponds to vector-register length, while tile height σ is tuned experimentally.Source: §3.4 · p. 5
  • For CSR5 tiles spanning multiple rows, the algorithm classifies row segments as red, green, or blue, storing completed results and combining partial sums for rows crossing tile columns.Green segments end within a column, red segments are carried forward, and blue segments require prefix-sum combination with prior partial results.Source: §3.4 · p. 6
  • CSR5 [19] also corrects partial results at thread boundaries; RVV slide, mask, and bitwise operations can reduce instruction count, while LMUL must be chosen carefully.With static OpenMP scheduling, threads combine contributions to the first row in their assigned row segments using a calibrator array.Source: §3.4 · p. 6

3.5. HCSR Format

  • HCSR partitions the matrix into fixed R × C blocks, storing each nonempty block in CSR when pblock > pfix and otherwise in COO, with pfix equal to average nonzeros per row.The nonempty block structure, including empty-block information, is itself stored in CSR.Source: §3.5 · pp. 6, 8
  • HCSR SpMV traverses nonempty block rows in parallel and multiplies each block by its corresponding segment of b, improving vector-access locality over CSR.Its five arrays encode shared values and column indices, row metadata, block type, and offsets.Source: §3.5 · p. 8
  • For each HCSR block, the implementation computes its parameters and selects a CSR or COO kernel; COO uses a scalar implementation because its vectorized version performed worse experimentally.The CSR kernel follows vectorized CSR SpMV, with changes to vector register length and multiplication of y by β.Source: §3.5 · p. 8
  • HCSR combines standard sparse formats in a two-level block scheme that can improve cache efficiency; recursive extension is possible, but this paper uses two levels.The authors state that two levels suffice for their RISC-V processors.Source: §3.5 · p. 8

4. Experimental Results

Across the tested SpacemiT K1 and K3 systems, SpMV performance varies with storage format, precision, and core count. HCSR is especially competitive in multicore runs, while the discussion relates performance differences to memory bandwidth and processor architecture.

4.1. Experimental Setup

  • Experiments used SpacemiT K1 and K3 boards; K3 measurements used only its X100 high-performance cores.The K1 system used a Banana Pi BPI-F3 board; the K3 system also includes A100 AI cores, which were not used.Source: §4.1 · p. 8

4.2. Benchmark Suite

  • The benchmark used 121 SuiteSparse matrices spanning 0.5K–8.39M rows, with tuned format parameters and single- and eight-core runs in both precisions.Speedups were calculated relative to scalar CSR, with matrices ordered by increasing fill-in in the heatmaps.Source: §4.2 · pp. 8–9

4.3.1. SpacemiT K1

  • On K1, Sell-C-σ led single-core results at 1.5× over CSR on 107 matrices; CSR5/VHCC averaged 1.6× gains on rectangular and denser matrices.In single precision, Sell-C-σ also led most single-core matrices at 1.5×, while HCSR averaged 1.7× over CSR on eight cores.Source: §4.3.1 · p. 9
  • On K1, CSR2 and LAV averaged slowdowns of 34% and 20% versus CSR, although LAV gained 25% on denser single-core matrices.CVR and VNEC were near scalar CSR on one core but averaged 10% faster in parallel.Source: §4.3.1 · p. 9

4.4. Discussion

  • K3 reduced average SpMV time versus K1 alongside STREAM bandwidth rising from 6.9 to 19.9 GB/s; K3 also uses an out-of-order X100 core.The paper attributes the performance gain to architectural changes, including faster memory and out-of-order execution.Source: §4.3.2 · p. 10, §4.4 · pp. 11–12

4.3.2. SpacemiT K3

  • On K3, vectorized CSR, CSR5, Sell-C-σ, and HCSR averaged 1.7×–2.2× over scalar CSR on one core; vectorized CSR, CSR5, and HCSR averaged 1.5×–2.1× on eight.The absolute SpMV time fell by an average of 3× in double precision and 2× in single precision versus K1; selected single-core cases fell by up to 18×.Source: §4.3.2 · p. 10

4.4. Discussion

  • For the examined workload, compute units stalled about 95% of the time, while HCSR showed a cache-friendly pattern and a significant DRAM-bandwidth advantage.The effective-bandwidth estimate assumes at least 20 bytes loaded per nonzero; CSR used almost 70% of peak DRAM bandwidth and Sell-C-σ approached peak for the matrix studied.Source: §4.4 · p. 12

4.3.1. SpacemiT K1

  • On K1, HCSR is fastest on 80 of 121 matrices across formats, averaging 1.6× speedup over scalar CSR on 8 cores.The reported HCSR gains are especially substantial for rectangular and Kronecker matrices.Source: §4.3.1 · p. 9, Figure 9 · p. 13

5. Machine learning-based automatic format selection

Because SpMV performance depends on matrix structure and processor, the paper evaluates automatic format selection from matrix features. A regression model gives substantial average speedups, but sensitivity to training data and complex feature relationships limit reliable rule-based selection.

5.1. Model and feature selection

  • Random forest and gradient-boosted decision-tree classifiers choose formats directly, while regressors predict each format’s execution-time ratio to CSR and choose the lowest.The study implements automatic selection based on matrix portraits, adapting ideas from WISE.Source: §5.1 · p. 14
  • Feature vectors combine matrix dimensions and nonzero counts with distributions across rows, columns, tiles, and blocks, plus locality-related measurements.Distribution statistics include mean, variance, standard deviation, extrema, nonzero count, Gini index, and p-ratio; features are computed over approximately 2048 segments along each matrix dimension.Source: §5.1 · pp. 14–15
  • Models were trained on measurements from K1 and K3 using SuiteSparse and R-MAT matrices, then tested only on SuiteSparse matrices.The training dataset was a random 80% sample of the entire dataset.Source: §5.1 · p. 15

5.2. Experimental Results

  • 1.4×–1.5× average speedup on K1 and 1.7× on K3 result from model-selected formats; many matrices reach 2.0×–6.0×.Figures 15 and 16 compare selected-format speedup with the best of experiments on eight-core K1 and K3.Source: §5.2 · pp. 15–16, Figure 15 · p. 19, Figure 16 · p. 19
  • Tuning kept maximum LUB within 1.2–1.4 in all cases, but models remained sensitive to small changes in experimental results.When large gaps occurred, HCSR was selected although another format was optimal.Source: §5.2 · p. 16
  • Feature importance is often distributed across several weakly weighted features, and CSR5, CVR, and VNEC share feature patterns associated with irregular matrices.For the first pattern, each of three or more important features can have importance below 0.1.Source: §5.2 · p. 19
  • SELL-C-σ performs best when row nonzero counts have a small spread, while VHCC favors irregular matrices and also depends on row distributions and cache locality.For SELL-C-σ, the paper associates this pattern with low variance, a Gini index close to 1, and a p-ratio close to 0.5.Source: §5.2 · p. 19
  • HCSR’s important features differ by precision: p-ratio matters for double precision, while locality matters more for single precision on both boards.The authors suggest similar memory subsystems and a bottleneck when switching precision may explain this pattern.Source: §5.2 · pp. 19–20

6. Conclusion

The conclusion presents HCSR as a simple format intended to improve memory access for a wide range of sparse matrices. It also reports support for nine formats and automatic selection, while noting that selecting a suitable format takes significant engineering effort.

6. Conclusion

  • HCSR improves memory access efficiency for a wide range of sparse matrices while retaining advantages of standard formats.The authors report an average 1.6× speedup over the best CSR implementation.Source: §6 · p. 20
  • RVVLASparse supports nine popular SpMV formats and enables performance comparisons on SpacemiT K1 and K3.The authors report severalfold acceleration on K3 associated with its out-of-order processor, unlike their dense-matrix results.Source: §6 · p. 20
  • Automatic models can select formats from matrix structure, but choosing the most suitable format requires significant engineering effort.The study also identifies structural properties that influence format suitability.Source: §6 · p. 20
  • Future work will extend supported sparse operations and integrate the library into iterative solvers for sparse linear systems.Source: §6 · p. 20

Appendix A. Test matrices

Appendix A lists test-matrix characteristics, with the table continuing across pages. Its visible headings include matrix identifiers and names, dimensions, nonzero counts, nonzeros per row, and fill-in.

Appendix A. Test matrices

Loading 2609.11352v1…