MMSparse: 2D partitioning of sparse matrix based on mathematical morphology
MMSparse: 2D partitioning of sparse matrix based on mathematical morphology
复制标题
DOI：
10.1016/j.future.2020.02.076
复制
发表时间：
2020-07
期刊：
影响因子：
--
通讯作者：
Zhaonian Tan;Weixing Ji;Jianhua Gao;Yueyan Zhao;Akrem Benatia;Yizhuo Wang;Feng Shi
中科院分区：
文献类型：
--
作者：
Zhaonian Tan;Weixing Ji;Jianhua Gao;Yueyan Zhao;Akrem Benatia;Yizhuo Wang;Feng Shi
稀疏矩阵是任何有足够多的零的矩阵，利用它们是值得的。稀疏矩阵-向量乘法（SpMV）的计算效率受到稀疏矩阵中非零元素分布的显著影响，而传统的一维和二维分划方法无法充分利用这一点。本文提出了一种基于数学形态学理论的二维分划方法。利用一些基本的形态学变换，包括扩张、填充、打开和骨架化，将矩阵划分为密集和稀疏区域。这些密集区域根据其形态特征分为矩形、三角形和对角线。我们还提出了一种新的MMSparse（数学形态学稀疏）格式，该格式以最有效的格式存储每种类型的形状，而不是整个矩阵的一种格式。我们从SuiteSparse Matrix Collection中选取不同类型的矩阵，在NVIDIA GTX 1080Ti GPU上进行了一系列的实验。实验结果表明，我们的方法比cuSPARSE库内核的最佳性能平均提高2.47倍，比BCSR高2.54倍，比yaSpMV高1.48倍，比CSR5高1.85倍，比一维分区高1.35倍。
Sparse matrix is any matrix with enough zeros that it pays to take advantage of them. The computational efficiency of sparse matrix–vector multiplication (SpMV) is significantly influenced by the distribution of non-zero elements in sparse matrix, which is not fully exploited by traditional one-dimensional and two-dimensional partitioning approaches. In this paper, we present a novel two-dimensional partitioning method based on mathematical morphology theory. The matrix is partitioned into dense and sparse areas utilizing some basic morphological transformations, including dilatation, filling, opening, and skeletonization. These dense areas are classified as rectangle, triangle, and diagonal according to their morphological features. We also propose a new MMSparse (Mathematical Morphological Sparse) format that stores each type of shapes in the most efficient format instead of one format for an entire matrix. We select different types of matrices from the SuiteSparse Matrix Collection and conduct a series of experiments on NVIDIA GTX 1080Ti GPU. The experimental results show that our approach achieves average speedup 2.47x over the best performance of the cuSPARSE library kernel, 2.54x over BCSR, 1.48x over yaSpMV, 1.85x over CSR5, 1.35x over the one-dimensional partition.