SC20 Proceedings

The International Conference for High Performance Computing, Networking, Storage, and Analysis

Efficient Tiled Sparse Matrix Multiplication through Matrix Signatures

Authors: Sureyya Emre Kurt (University of Utah), Aravind Sukumaran-Rajam (Washington State University), Fabrice Rastello (French Institute for Research in Computer Science and Automation (INRIA)), and Ponnuswamy Sadayappan (University of Utah)

Abstract: Tiling is a key technique to reduce data movement in matrix computations. While tiling is well understood and widely used for dense matrix/tensor computations, effective tiling of sparse matrix computations remains a challenging problem. This paper proposes a novel method to efficiently summarize the impact of the sparsity structure of a matrix on achievable data reuse as a one-dimensional signature, which is then used to build an analytical cost model for tile size optimization for sparse matrix computations. The proposed model-driven approach to sparse tiling is evaluated on two key sparse matrix kernels; Sparse Matrix-Matrix Multiplication (SpMM) and Sampled Dense Dense Matrix Multiplication (SDDMM). Experimental results demonstrate that model-based tiled SpMM and SDDMM achieve high performance relative to the current state-of-the-art.

Back to Technical Papers Archive Listing