SC20 Is Everywhere We Are

SC20 Virtual Platform
Efficient Tiled Sparse Matrix Multiplication through Matrix Signatures
Event Type
Paper
Tags
Algorithms
Graph Algorithms
Linear Algebra
Registration Categories
TP
TimeThursday, 19 November 202011am - 11:30am EDT
LocationTrack 3
DescriptionTiling 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 Top Button