Close

Presentation

Improving SpGEMM Performance Through Reordering and Cluster-Wise Computation
DescriptionSparse Matrix-Matrix Multiplication (SpGEMM) is a key kernel in many scientific applications and graph workloads. SpGEMM is known to suffer from poor performance due to irregular memory access patterns. Gustavson's algorithm, a traditional approach for SpGEMM, involves row/column-wise operations, facing challenges with irregular accesses to the second matrix. Our research focuses on enhancing memory locality through matrix reordering and cluster-wise computation to address this issue.

In this study, we evaluate the effect of 10 different reordering algorithms on SpGEMM performance. Then, we introduce a novel method that employs cluster-wise SpGEMM, merging similar rows into clusters. Our findings show that matrix reordering can improve SpGEMM performance by up to 2.3×, and our cluster-wise approach can further enhance performance by up to 30%.