带状稀疏矩阵乘法及高效GPU实现

作者：刘丽; 陈长波

来源：计算机应用, 2023, 43(12): 3856-3867.

DOI：10.11772/j.issn.1001-9081.2022111720

• 带状稀疏矩阵
• 稀疏存储格式
• 稀疏矩阵乘法
• 图形处理单元
• 共享内存

稀疏-稠密矩阵乘法（SpMM）广泛应用于科学计算和深度学习等领域，提高它的效率具有重要意义。针对具有带状特征的一类稀疏矩阵，提出一种新的存储格式BRCV(Banded Row Column Value)以及基于此格式的SpMM算法和高效图形处理单元（GPU）实现。由于每个稀疏带可以包含多个稀疏块，所提格式可看成块稀疏矩阵格式的推广。相较于常用的CSR(Compressed Sparse Row)格式，BRCV格式通过避免稀疏带中列下标的冗余存储显著降低存储复杂度；同时，基于BRCV格式的SpMM的GPU实现通过同时复用稀疏和稠密矩阵的行更高效地利用GPU的共享内存，提升SpMM算法的计算效率。在两种不同GPU平台上针对随机生成的带状稀疏矩阵的实验结果显示，BRCV的性能不仅优于cuBLAS(CUDA Basic Linear Algebra Subroutines)，也优于基于CSR和块稀疏两种不同格式的cuSPARSE。其中，相较于基于CSR格式的cuSPARSE,BRCV的最高加速比分别为6.20和4.77。此外，将新的实现应用于图神经网络（GNN）中的SpMM算子的加速。在实际应用数据集上的测试结果表明，BRCV的性能优于cuBLAS和基于CSR格式的cuSPARSE，且在大多数情况下优于基于块稀疏格式的cuSPARSE。其中，相较于基于CSR格式的cuSPARSE,BRCV的最高加速比为4.47。以上结果表明BRCV可以有效提升SpMM的效率。

• 单位
  中国科学院重庆绿色智能技术研究院; 中国科学院大学