点击数: 更新日期: 2022-09-20
中文题目：TileSpGEMM：一种GPU上的并行稀疏矩阵-矩阵乘分块算法
论文题目：TileSpGEMM: A Tiled Algorithm for Parallel Sparse General Matrix-Matrix Multiplication on GPUs
录用期刊/会议：Proceedings of the 27th ACM SIGPLAN Annual Symposium on Principles and Practice of Parallel Programming (PPoPP '22，CCF A类会议)
作者列表：
1）牛宇瑶 中国石油大学（北京）信息科学与工程学院 计算机科学与技术专业 研19-2
2）芦正阳 中国石油大学（北京）信息科学与工程学院 计算机科学与技术专业 研21-2
3）戢昊男 中国石油大学（北京）信息科学与工程学院 计算机科学与技术专业 研20-3
4）宋姝慧 中国石油大学（北京）信息科学与工程学院 计算机科学与技术专业 研19-2
5）金洲 中国石油大学（北京）信息科学与工程学院 计算机科学与技术系
6）刘伟峰 中国石油大学（北京）信息科学与工程学院 计算机科学与技术系
背景与动机:
稀疏矩阵-矩阵乘（SpGEMM）操作将两个稀疏矩阵A和B相乘，得到一个结果稀疏矩阵C。作为第三层稀疏BLAS中的关键操作，SpGEMM在稀疏线性解法器（例如AMG方法），图处理框架（例如GraphBLAS中的宽度优先搜索和三角计数）以及机器学习算法（例如Markov聚类和深度神经网络）中具有广泛的应用。 然而，现有的SpGEMM工作仍面临主要三个问题：（1）行-行方法不断将非零元插入到稀疏结构无法预测的的行中的随机位置，现有工作已经为不同稀疏结构的矩阵提出了众多稀疏累加器方法，如稠密行，堆方法，hash方法，sort方法以及merge方法等，但很难选择一种有效的稀疏累加器的方法。（2）C中行的计算量可能非常不均衡，因此很难构建负载均衡器来使特定GPU中的现代大规模并行处理器满载运行。（3）C的大小是未知的，并且通常需要一个很大的临时空间来存储中间结果，因此很难为中间结果分配适当的大小来平衡内存空间和执行时间。
设计与实现:
我们提出了一种有效的分块SpGEMM算法TileSpGEMM，首先将稀疏矩阵存储为多个大小相同的稀疏块，将块作为基本的计算单元以获得更好的数据局部性，之后将整个计算过程分为三步：（1）确定C的稀疏性结构，运行一次完整的SpGEMM操作，将两个以块结构存储的输入矩阵A和B的高层次结构相乘，找出C中可能的非空块；（2）为C中每个稀疏块生成行指针数组以及位掩码数组，并求得每个稀疏块中的非零元数，为C分配内存，以及（3）计算C中所有非零元的值和行/列索引，即完成数值SpGEMM的计算。在此过程中，为优化计算性能，我们使用了几种优化方法，如在第二步中使用二分查找求得相交集合，求解符号SpGEMM时的位掩码操作以及第三步中设计自适应的稀疏累加器算法等。图1展示了计算C中两个稀疏块相乘的示例。
图1 一个16×16的稀疏矩阵TileSpGEMM算法示例
实验结果及分析:
图2 TileSpGEMM和其它四种最新的SpGEMM方法在Geforce RTX 3090和3060 GPU上计算C=A2和C=AAT的性能比较
图3 在18个代表性矩阵上运行C=A2的运行时间峰值空间成本
图2展示了在RTX 3060 和3090 GPU上 142个矩阵使用TileSpGEMM与其它四种最新的SpGEMM方法cuSPARSE v11.4、bhSPARSE、NSPARSE以及spECK计算双精度C=A2和C=AAT的性能对比。由图中可以看出，cuSPARSE v11.4、bhSPARSE和NSPARSE只能完成数据集中的部分矩阵，而spECK和TileSpGEMM可以完成全部142个矩阵，且TileSpGEMM在RTX 3090上分别在139、138、127和94个矩阵的计算速度快于其它四种方法，在RTX 3060上在142、128、114和92个矩阵的计算速度快于其它四种方法（此次数据集中没有矩阵可以在RTX 3060 GPU上用cuSPARSE完成计算）。此外，TileSpGEMM的整体性能相比于其他四种方法也有很大的提高。具体来说，五种SpGEMM方法在RTX 3090 GPU上的平均性能分别为30.82、11.54、37.73、46.92和54.56 Gflops，即TileSpGEMM相比于其它四种方法获得的几何平均加速比为：1.77倍、4.73倍、1.45倍和1.16倍。在RTX 3060上，TileSpGEMM相较于cuSPARSE、bhSPARSE、NSPARSE和spECK分别实现了高达2.78倍、145.35倍、97.86倍和3.70倍的加速。图3绘制了TileSpGEMM和其它算法在18个代表性矩阵上运行C=A2的内存占用过程。TileSpGEMM在多数矩阵上都比这三种方法使用的空间更少，且完成得更快。
通讯作者简介:
刘伟峰，博士，中国石油大学（北京）信息科学与工程学院教授，院长，博士生导师，欧盟玛丽居里学者。2002年和2006年于中国石油大学（北京）计算机系获学士与硕士学位。2006年至2012年在中国石化石油勘探开发研究院历任助理工程师、工程师和高级研究师，其间主要研究领域为石油地球物理勘探的高性能算法。2016年于丹麦哥本哈根大学获计算科学博士学位，主要研究方向为数值线性代数和并行计算，其中尤其关注稀疏矩阵的数据结构、并行算法和软件。研究工作发表于SC、ICS、PPoPP、ASPLOS、IPDPS、ICPP、TPDS、JPDC、FGCS和Parco等重要国际会议和期刊。担任TPDS、SISC和TKDE等多个重要国际期刊审稿人，以及SC、ICS、IPDPS和ICPP等多个重要国际会议的程序委员会委员。他还是IEEE和CCF高级会员以及ACM和SIAM会员。
联系方式：weifeng.liu@cup.edu.cn