SpMV speed improves with hierarchical sparse storage on RISC-V
Rethinking Sparse Formats for RISC-V: A Hierarchical Approach to High-Performance SpMV
Distributed, Parallel, and Cluster ComputingPerformance
Summary
Multiplying big sparse matrices by vectors quickly is important for many science and engineering problems. The authors tested different ways to store these sparse matrices on RISC-V processors and created a new method called Hierarchical CSR (HCSR). Their new approach makes the multiplication faster than older methods on RISC-V boards. They also shared their code openly for others to use.
What this means in practice
- •For software engineers: Optimize scientific computing applications on RISC-V by using HCSR to speed up sparse matrix-vector multiplication.
- •For hardware developers: Design RISC-V accelerators and boards optimized for hierarchical sparse matrix formats to boost linear algebra operations.
Authors
Anna Pirova, Anastasia Vodeneeva, Konstantin Kovalev, Alexander Ustinov, Maksim Zagriadskov, Daniil Litvyakov, Arthur Kulik, Evgeny Kozinov, Valentin Volokitin, Iosif Meyerov
Abstract
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.