SIMA: Scalable Scratchpad-Based Index-Matching Hardware Accelerator for Sparse Linear Algebra

Sparse linear algebra kernels are becoming increasingly important in applications across the graph, machine learning, and high-performance computing domains. For compressed sparse data representations, index-matching is critical in these kernels due to time-consuming memory accesses. Exploiting parallelism for this operation is not trivial. State-of-the-art hardware supporting index-matching in SIMD/SIMT general-purpose accelerators based on Vector Processing Units or General-Purpose Graphic Processing Units architectures exhibits limited scalability. Moreover, alternative hash-based approaches do not leverage all the available parallelism. In this work, we propose SIMA, a S calable, scratchpad-based, I ndex- M atching hardware A ccelerator for sparse linear algebra in SIMD/SIMT general-purpose accelerators. SIMA follows a hash-based index-matching approach that provides a simple and scalable microarchitecture, while also leveraging both index and match parallelism, contrasting with the state of the art. SIMA combines a multi-banked scratchpad, that enables leveraging index parallelism with reduced area and power, with cache-like functionality that supports match parallelism. In addition, SIMA can also mitigate the impact of index collisions with a novel mechanism that leverages index misses. SIMA achieves savings of, at least, 94.08% and 72.65% for area and leakage power, respectively, when compared to the state-of-the-art. These improvements translate to an average speedup of at least 1.97 × across the different evaluated groups of real-world matrices and sparse kernels, with an average increase in energy efficiency of at least 6.91 ×. In addition, contrary to alternative hash-based approaches, SIMA can leverage all the available parallelism, outperforming all evaluated baselines when computing General Sparse Matrix-Sparse Matrix Multiplication (SpGEMM) with large matrices. Moreover, SIMA improves existing hash-based proposals by accommodating hardware-friendly hash functions, reducing index collisions and increasing memory utilization.