Efficient Tiled Sparse Matrix Multiplication through Matrix Signatures
Efficient Tiled Sparse Matrix Multiplication through Matrix Signatures
复制标题
DOI：
10.1109/sc41405.2020.00091
复制
发表时间：
2020-11
期刊：
影响因子：
--
通讯作者：
Süreyya Emre Kurt;Aravind Sukumaran-Rajam;F. Rastello;P. Sadayappan
中科院分区：
文献类型：
--
作者：
Süreyya Emre Kurt;Aravind Sukumaran-Rajam;F. Rastello;P. Sadayappan
平铺是减少矩阵计算中数据移动的关键技术。虽然平铺已被广泛理解并广泛用于密集矩阵/张量计算，但稀疏矩阵计算的有效平铺仍然是一个具有挑战性的问题。本文提出了一种新颖的方法，将矩阵的稀疏结构对可实现的数据重用的影响有效地总结为一维签名，然后用于构建稀疏矩阵计算的分块大小优化的分析成本模型。所提出的模型驱动的稀疏平铺方法在两个关键的稀疏矩阵内核上进行评估：稀疏矩阵-密集矩阵乘法（SpMM）和采样密集-密集矩阵乘法（SDDMM）。实验结果表明，基于模型的平铺 SpMM 和 SDMMM 相对于当前最先进的技术实现了高性能。
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 - Dense 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.