当前位置: 主页 > 学术动态 >

TileSpGEMM:一种GPU上的并行稀疏矩阵-矩阵乘分块算法

点击数:   更新日期: 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)操作将两个稀疏矩阵AB相乘,得到一个结果稀疏矩阵C作为第三层稀疏BLAS中的关键操作,SpGEMM在稀疏线性解法器(例如AMG方法),图处理框架(例如GraphBLAS中的宽度优先搜索和三角计数)以及机器学习算法(例如Markov聚类和深度神经网络)中具有广泛的应用。 然而,现有的SpGEMM工作仍面临主要三个问题:(1)行-行方法不断将非零元插入到稀疏结构无法预测的的行中的随机位置,现有工作已经为不同稀疏结构的矩阵提出了众多稀疏累加器方法,如稠密行,堆方法,hash方法,sort方法以及merge方法等,但很难选择一种有效的稀疏累加器的方法。(2)C中行的计算量可能非常不均衡,因此很难构建负载均衡器来使特定GPU中的现代大规模并行处理器满载运行。(3)C的大小是未知的,并且通常需要一个很大的临时空间来存储中间结果,因此很难为中间结果分配适当的大小来平衡内存空间和执行时间。

设计与实现:

我们提出了一种有效的分块SpGEMM算法TileSpGEMM,首先将稀疏矩阵存储为多个大小相同的稀疏块,将块作为基本的计算单元以获得更好的数据局部性,之后将整个计算过程分为三步:(1)确定C的稀疏性结构,运行一次完整的SpGEMM操作,将两个以块结构存储的输入矩阵AB的高层次结构相乘,找出C中可能的非空块;(2)为C中每个稀疏块生成行指针数组以及位掩码数组,并求得每个稀疏块中的非零元数,为C分配内存,以及(3)计算C中所有非零元的值和行/列索引,即完成数值SpGEMM的计算。在此过程中,为优化计算性能,我们使用了几种优化方法,如在第二步中使用二分查找求得相交集合,求解符号SpGEMM时的位掩码操作以及第三步中设计自适应的稀疏累加器算法等。图1展示了计算C中两个稀疏块相乘的示例。


1 一个16×16的稀疏矩阵TileSpGEMM算法示例

实验结果及分析:



2 TileSpGEMM和其它四种最新的SpGEMM方法在Geforce RTX 3090和3060 GPU上计算C=A2C=AAT的性能比较



3 在18个代表性矩阵上运行C=A2的运行时间峰值空间成本

2展示了在RTX 3060 和3090 GPU142个矩阵使用TileSpGEMM与其它四种最新的SpGEMM方法cuSPARSE v11.4bhSPARSENSPARSE以及spECK计算双精度C=A2C=AAT的性能对比。由图中可以看出,cuSPARSE v11.4bhSPARSENSPARSE只能完成数据集中的部分矩阵,而spECKTileSpGEMM可以完成全部142个矩阵,且TileSpGEMMRTX 3090上分别在13913812794个矩阵的计算速度快于其它四种方法,在RTX 3060上在14212811492个矩阵的计算速度快于其它四种方法(此次数据集中没有矩阵可以在RTX 3060 GPU上用cuSPARSE完成计算)。此外,TileSpGEMM的整体性能相比于其他四种方法也有很大的提高。具体来说,五种SpGEMM方法在RTX 3090 GPU上的平均性能分别为30.82、11.5437.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