点击数: 更新日期: 2022-10-04
中文题目：TileSpMSpV：一种GPU上稀疏矩阵-稀疏向量乘法的分块算法
英文题目：TileSpMSpV: A Tiled Algorithm for Sparse Matrix-Sparse Vector Multiplication on GPUs发表会议：51st International Conference on Parallel Processing (CCF B类会议)
作者列表
1) 戢昊男 中国石油大学（北京） 信息科学与工程学院 计算机科学与技术专业 研20级
2) 宋慧敏 中国石油大学（北京） 信息科学与工程学院 计算机科学与技术专业 研20级
3) 卢世博 美国东北大学
4) 金 洲 中国石油大学（北京） 信息科学与工程学院 计算机科学与技术系
5) 谭光明 中国科学院计算技术研究所计算机体系结构国家重点实验室
6) 刘伟峰 中国石油大学（北京） 信息科学与工程学院 计算机科学与技术系
背景与动机:
稀疏矩阵-稀疏向量乘（SpMSpV）操作是将一个稀疏矩阵A与一个稀疏向量x进行乘法，得到一个结果稀疏向量y的操作，被广泛的应用于图框架处理、图算法加速和机器学习等领域。但现有工作仍然存在两个主要的问题：（1） 输入和输出向量的稀疏性使其浮点效率普遍低于稀疏矩阵-向量乘（SpMV）和稀疏矩阵-矩阵乘（SpGEMM）；（2）现有的并行方法专注于各种按行和按列的存储和合并操作，却很大程度上忽略了输入矩阵和向量的数据局部性与稀疏模式；这使得我们提出一种新的SpMSpV并行算法。
设计与实现:
本文首先将输入稀疏矩阵划分为若干个大小为nt×nt的稀疏矩阵块，并以稀疏矩阵块为基本工作单元，其中nt在实现中可以是 16、32 或 64，输入和输出向量也将被分成长度为nt的稀疏向量块。该设计不仅利用了矩阵和向量的稀疏性，还利用了GPU的SIMD/SIMT执行模型（例如CUDA warp中的32个线程）。本文进一步扩展TileSpMSpV实现了BFS。由于我们只关注无权重的BFS算法，即我们只需要访问图的稀疏结构，因此，本文让每个矩阵块还存储一个大小为nt×nt的密集位掩码，用于BFS中的快速符号操作。
TileSpMSpV算法中，矩阵块是最小的工作单元，向量的稀疏性决定着需要的计算量，所以本文提出了一种针对稀疏向量的分块存储方式，可以实现对稀疏向量O（1）时间复杂度的访问，并且消除浪费在空块上的相乘时间，从而大幅度提高计算性能。
在TileSpMSpV上，本文实现了一种称为TileBFS的BFS算法，该算法会选择适合自己的矩阵块大小，将矩阵和向量都分块压缩存储，并且根据输入向量稠密度和节点访问量的变化趋势，从 Push-CSC、Push-CSR、Pull-CSC 三种不同的处理方式中选择最优的来进行BFS中每一层节点的遍历，避免了单一遍历方式带来的庞大运算量。
图1：一个从源顶点0开始使用三种方法（Push-CSC、Push-CSR、Pull-CSC）进行三层迭代的BFS算法的实例。
实验结果及分析:
图2：四种SpMSpV方法TileSpMSpV（我们的方法）、TileSpMV、cuSPARSE和CombBLAS在四种不同稀疏度下的性能比较。
图3：三种BFS方法TileBFS（我们的方法）、Gunrock和GSwitch方法在两个NVIDIA GPU上的性能比较。
本文在两个NVIDIA GPU（NVIDIA RTX 3060和NVIDIA RTX 3090）上对TileSpMSpV和TileBFS进行了测试，并将它们分别与其他SpMSpV方法（TileSpMV、cuSPARSE和CombBLAS）和其他BFS方法（Gunrock和GSwitch）进行了比较。数据集选自SuiteSparse Matrix Collection中的2757个矩阵，其中的2081个方阵用来测试BFS。
图2显示了四种SpMSpV算法在不同向量稀疏度下的性能。实验表明，在RTX 3090上使用 2757 个稀疏矩阵的测试中，TileSpMSpV算法相比于TileSpMV、cuSPARSE和CombBLAS算法的平均加速比分别是1.83倍、17.18倍和17.20倍，最高加速比可达7.68倍、1050.02倍和235.90倍。
图3显示了三种BFS方法在两个NVIDIA GPU上的性能。实验表明，我们的算法性能在大多数矩阵上优于其他方法。我们的TileBFS算法比Gunrock和GSwitch的平均性能分别高出 2.88倍（最高 21.35倍）和 4.52倍（最高 1000.85倍）。
通讯作者简介:
刘伟峰，博士，中国石油大学（北京）信息科学与工程学院教授，院长，欧盟玛丽居里学者。2002年和2006年于中国石油大学（北京）计算机系获学士与硕士学位，2006年至2012年在中国石化石油勘探开发研究院历任助理工程师、工程师和高级研究师，其间主要研究领域为石油地球物理勘探的高性能算法。2016年于丹麦哥本哈根大学获计算科学博士学位，主要研究方向为高性能稀疏线性代数子程序。他的主要研究兴趣为数值线性代数和并行计算，其中尤其关注稀疏矩阵的数据结构、并行算法和软件。 他的研究工作发表于SC、ICS、PPoPP、ASPLOS、IPDPS、JPDC、FGCS和Parco等重要国际会议和期刊。他还是TPDS、SISC和TKDE等多个重要国际期刊审稿人，也是SC、ICS和ICPP等多个重要国际会议的程序委员会委员。他是IEEE高级会员以及CCF、ACM和SIAM会员。
联系方式：weifeng.liu@cup.edu.cn