点击数: 更新日期: 2023-09-18
中文题目：DASP：一个专用稠密矩阵乘加单元加速的通用SpMV算法
论文题目：DASP: Specific Dense Matrix Multiply-Accumulate Units Accelerated General Sparse Matrix-Vector Multiplication
录用期刊/会议：【期刊名称】The International Conference for High Performance Computing, Networking, Storage, and Analysis（CCF-A）
封面图片：
封面摘要：
DASP是一种使用通用稠密矩阵乘加(MMA)单元加速的通用稀疏矩阵-向量乘法(SpMV)算法。我们发现计算部分可能是SpMV的另一个关键性能瓶颈，而MMA作为一个新的硬件单元可以给处理器带来更高的计算能力，从而提升SpMV的性能；因此我们提出了可有效利用MMA单元的数据结构，并设计了不同的CUDA Kernel。实验证明，在最新的两款NVIDIA 架构的GPU上，DASP比当前SpMV方法有显著的性能提升。
作者列表：
1） 卢玥辰 中国石油大学（北京）信息科学与工程学院 先进科学与工程计算专业 博22
2） 刘伟峰 中国石油大学（北京）信息科学与工程学院 计算机系 教师
背景与动机:
一直以来，稀疏矩阵向量乘法（SpMV）都被认为是一个访存受限的操作，因此现有的SpMV研究主要集中于解决内存局部性差和负载不均衡的问题上。然而我们通过将SpMV操作开销分为随机访问、内积计算和读写其他数组三部分并测试其相对整体开销的占比（如图1）发现：计算部分在SpMV开销中也占据较大比例，我们认为其可能是SpMV的另一个关键性能瓶颈。而专用的矩阵乘法累加（MMA）单元做为一个新的硬件单元可以给处理器带来更高的计算能力，从而提升SpMV的性能。
图1. A100 GPU上运行标准CSR格式的SpMV算法的三部分开销占比。
设计与实现:
在SpMV中利用MMA单元的计算能力并非易事。主要原因是：一方面，SpMV中矩阵的非零元分布可能非常不规则；另一方面，MMA单元需要严格的规则数据布局才能充分利用硬件。为了解决这个问题，我们在本工作中提出了一种使用专用稠密MMA单元加速通用SpMV的新算法DASP。
DASP由两个主要部分组成：可以有效利用MMA单元计算的新数据结构，以及相应的SpMV算法。我们根据稀疏矩阵的行长度（每行非零元个数）将所有行分为长行、中间行和短行三类，然后针对各类行特点使用不同的方式将其整理为可有效利用MMA单元计算的块结构（如图2所示）。对于长行，每行非零元被分为若干个group，每个group的非零元为2×MMA_M×MMA_K；对于中间行，每MMA_M行被视为一个行块，每个行块根据参数threshold被分为若干个大小为MMA_M×MMA_K的小块；对于短行，我们采用拼接策略，分别将长度为1和3的行拼接、两个长度为2的行拼接得到长度为4的行。
图2. 一个2020的稀疏矩阵 A 被存储为若干个大小为24的块（设MMA_M=2， MMA_K=4）。
对于不同类别的行，我们使用了不同的分配方法调用MMA指令进行计算，然后通过调用 CUDA shfl指令，从MMA指令所得的累加器中提取所需结果写入连续线程的寄存器中，经过整理再写回给结果向量。如图3所示，在短行部分，我们采用了拼接策略将长度为1和长度为3的行拼接得到一个长度为4的行，使得每个WARP load一次矩阵A的数据后可调用两次MMA指令进行计算，今儿分别得到长度为1的行和长度为3的行对应的结果y值。
图3. 短行1&3拼接部分的DASP算法示例。
实验结果及分析:
我们在两款最新的NVIDIA GPU A100（Ampere）和H800（Hopper）上使用SuiteSparse Matrix Collection的所有2893个矩阵对双精度和半精度DASP进行了测试。在A100上，我们测试了双精度DASP、CSR5、TileSpMV和cuSPARSE四种方法的性能，DASP分别在2403、2579和2344个矩阵上比这三种方法更快。同时，DASP相对这三种方法分别达到了（几何）平均1.46x、2.09x和1.52x的加速比，最高加速比分别可达12.64x、17.48x和6.94x。
图4. A100 GPU上的双精度DASP性能和加速比
我们分别在A100和H800上测试了半精度DASP和cuSPARSE两种方法的性能。与cuSPARSE相比，DASP在A100和H800上分别有2578和2576个矩阵是更快的。同时，DASP在这两个机器上相对cuSPARSE分别达到了（几何）平均1.70x和1.75x的加速比，最高加速比分别可达26.47x和65.95x。
图5. A100（左）和H800（右）GPU上的半精度DASP性能和加速比
作者简介:
卢玥辰，中国石油大学（北京）2022级博士生。2020年于中国石油大学（北京）获计算机系学士学位，2020年于中国石油大学（北京）攻读硕士研究生，2022年转硕博连读，主要研究领域为高性能计算。在此期间开发了使用稠密矩阵乘加单元加速的稀疏矩阵-向量乘算法DASP，目前该项目代码已经开源在github上，该研究工作已经被SC‘23所录用。
通讯作者简介:
刘伟峰，博士、中国石油大学（北京）教授、博士生导师，欧盟玛丽居里学者。2002年和2006年于中国石油大学（北京）计算机系获学士与硕士学位。2006年至2012年在中国石化石油勘探开发研究院历任助理工程师、工程师和高级研究师，其间主要研究领域为石油地球物理勘探的高性能算法。2016年于丹麦哥本哈根大学获计算科学博士学位，主要研究方向为数值线性代数和并行计算，其中尤其关注稀疏矩阵的数据结构、并行算法和软件。研究工作发表于SC、PPoPP、DAC、ASPLOS、ICS、IPDPS、ICPP、TPDS、JPDC、FGCS和Parco等重要国际会议和期刊。担任TPDS、SISC和TKDE等多个重要国际期刊审稿人，以及SC、ICS、IPDPS和ICPP等多个重要国际会议的程序委员会委员。他是IEEE高级会员、CCF高级会员、ACM和SIAM会员。