Technical Papers Archive

Accelerating SpGEMM Through Lightweight Clustering and Cache-Aware Accumulation


Authors: Shengle Lin, Chubo Liu, Yan Ding, Yikun Hu, and Wangdong Yang (College of Computer Science and Electronic Engineering, Hunan University; National Supercomputing Center in Changsha); Keqin Li (State University of New York, Department of Computer Science); and Kenli Li (College of Computer Science and Electronic Engineering, Hunan University; National Supercomputing Center in Changsha)

Abstract: Sparse matrix-matrix multiplication is one of the most crucial kernels in linear algebra solvers, graph analytics, and machine learning workloads. The clustered row-row style has emerged as a favorable SpGEMM workflow because of its potentially good parallelism. However, due to frequent data movement caused by irregular memory access, existing approaches often suffer from three issues: (1) workload imbalance and prohibitive preprocessing overhead, (2) unsatisfactory data locality, and (3) inefficient accumulation strategy.

To this end, we propose LeSpGEMM, a locality-enhanced SpGEMM algorithm. LeSpGEMM introduces a lightweight row-clustering method to improve spatial locality with near-linear complexity, and a cache-aware hybrid accumulation strategy to exploit data reuse across diverse sparse patterns. It further incorporates optimized kernels, including a SIMD-accelerated dense accumulator and an efficient hash-based accumulator. Experimental results on multiple platforms show that LeSpGEMM significantly outperforms six state-of-the-art implementations while maintaining low preprocessing overhead.



Presentation: file

Back to Technical Papers Archive Listing