基于GPU对角稀疏矩阵向量乘法的动态划分算法

来源：计算机应用杂志2024年第11期北京时间：

作者：涂进兴, 李志雄, 黄建强

单位：1.青海大学 计算机技术与应用学院，西宁 810016；2.青海省智能计算与应用实验室（青海大学），西宁 810016

摘要：在图形处理器（GPU）上实现对角稀疏矩阵向量乘法（SpMV）可以充分利用GPU的并行计算能力，并加速矩阵向量乘法；然而，相关主流算法存在零元填充数据多、计算效率低的问题。针对上述问题，提出一种对角SpMV算法DIA-Dynamic（DIAgonal-Dynamic）。首先，设计一种全新的动态划分策略，根据矩阵的不同特征进行分块，在保证GPU高计算效率的同时大幅减少零元填充，去除冗余计算量；其次，提出一种对角稀疏矩阵存储格式BDIA（Block DIAgonal）存储分块数据，并调整数据布局，提高GPU上的访存性能；最后，基于GPU的底层进行条件分支优化，以减少分支判断，并使用动态共享内存解决向量的不规则访问问题。DIA-Dynamic与前沿Tile SpMV算法相比，平均加速比达到了1.88；与前沿BRCSD （Diagonal Compressed Storage based on Row-Blocks）-Ⅱ算法相比，平均零元填充减少了43%，平均加速比达到了1.70。实验结果表明，DIA-Dynamic能够有效提高GPU上对角SpMV的计算效率，缩短计算时间，提升程序性能。

关键词：图形处理器,对角稀疏矩阵,稀疏矩阵向量乘法,动态划分,共享内存

基金资助：国家自然科学基金资助项目(62062059);青海省科技计划项目(2022?ZJ?701)