Sparse Stream Semantic Registers: A Lightweight ISA Extension Accelerating General Sparse Linear Algebra
Open access
Date
2023-12Type
- Journal Article
ETH Bibliography
yes
Altmetrics
Abstract
Sparse linear algebra is crucial in many application domains, but challenging to handle efficiently in both software and hardware, with one- and two-sided operand sparsity handled with distinct approaches. In this work, we enhance an existing memorystreaming RISC-V ISA extension to accelerate both one- and two-sided operand sparsity on widespread sparse tensor formats like compressed sparse row (CSR) and compressed sparse fiber (CSF) by accelerating the underlying operations of streaming indirection, intersection, and union. Our extensions enable single-core speedups over an optimized RISC-V baseline of up to 7.0×, 7.7 × , and 9.8 × on sparse-dense multiply, sparse-sparse multiply, and sparse-sparse addition, respectively, and peak FPU utilizations of up to 80% on sparse-dense problems. On an eight-core cluster, sparse-dense and sparse-sparse matrix-vector multiply using real-world matrices are up to 4.9× and 5.9× faster and up to 2.9× and 3.0× more energy efficient. We explore further applications for our extensions, such as stencil codes and graph pattern matching. Compared to recent CPU, GPU, and accelerator approaches, our extensions enable higher flexibility on data representation, degree of sparsity, and dataflow at a minimal hardware footprint, adding only 1.8% in area to a compute cluster. A cluster with our extensions running CSR matrix-vector multiplication achieves 9.9× and 1.7× higher peak floating-point utilizations than recent highly optimized sparse data structures and libraries for CPU and GPU, respectively, even when accounting for off-chip main memory (HBM) and on-chip interconnect latency and bandwidth effects. Show more
Permanent link
https://doi.org/10.3929/ethz-b-000636014Publication status
publishedExternal links
Journal / series
IEEE Transactions on Parallel and Distributed SystemsVolume
Pages / Article No.
Publisher
IEEESubject
Computer architecture; Hardware acceleration; Linear algebra; Sparse computation; Sparse tensorsOrganisational unit
02636 - Institut für Integrierte Systeme / Integrated Systems Laboratory03996 - Benini, Luca / Benini, Luca
Funding
101034126 - Pilot using Independent Local & Open Technologies (EC)
101036168 - European Processor Initiative (EPI) SGA2 (EC)
More
Show all metadata
ETH Bibliography
yes
Altmetrics