MAD-HiSpMV：一种基于矩阵自适应设计和混合行分布的加速方法，用于在FPGA上实现对不平衡SpMV（Spare Matrix Multiplication Vector）运算的高效加速

《ACM Transactions on Reconfigurable Technology and Systems》：MAD-HiSpMV: Matrix Adaptive Design with Hybrid Row Distribution for Imbalanced SpMV Acceleration on FPGAs

稀疏矩阵向量乘法（SpMV）加速技术及其在混合工作负载中的优化

　　

摘要

稀疏矩阵-向量乘法（SpMV）在科学计算、机器学习（ML）和图分析等众多应用中至关重要。尽管最近的研究在加速配备HBM的FPGA上的SpMV方面取得了巨大进展，但在处理非平衡稀疏矩阵的SpMV时仍存在多个挑战，这些矩阵中非零元素的分布在不同行之间是不对称的。这些挑战包括：（1）并行处理单元（PEs）之间的工作负载分布不均衡；（2）输出向量上的浮点数累加存在长距离依赖性；（3）在SpMV加速之后，经常被忽视的密集向量对外部存储器的访问成为新的瓶颈；（4）通用加速器对各种类型的稀疏矩阵的性能不够理想；（5）此外，机器学习工作负载通常同时包含SpMV和一般矩阵-向量乘法（GeMV），这两种操作存在内核切换效率低的问题。

为了解决这些问题，我们提出了MAD-HiSpMV，以加速配备HBM的FPGA上的非平衡SpMV，采用以下创新解决方案：（1）一种混合行分布网络，实现行间和行内数据的均衡分配；（2）使用加法器链和基于寄存器的循环缓冲区实现完全流水线的浮点数累加；（3）通过设计空间探索（DSE）由我们的自动化框架生成的矩阵自适应设计配置，以最大化给定矩阵的性能；（4）在同一内核中集成GeMV层，以高效处理混合工作负载。实验结果表明，与最先进的通用设计相比，MAD-HiSpMV通过DSE选择的配置在SpMV基准测试矩阵上实现了1.3倍（最高2.12倍）的平均加速比，并且每瓦特性能提高了1.15倍（最高1.54倍）。对于SpMV基准测试矩阵，与在24核Xeon Silver 4214 CPU上运行的Intel MKL相比，MAD-HiSpMV实现了8.80倍的平均加速比；与在Nvidia GTX 1080ti GPU上运行的cuSparse相比，MAD-HiSpMV的每瓦特性能提高了2.57倍。此外，集成在MAD-HiSpMV中的GeMV层实现了156.7 GFLOPS的峰值吞吐量，这比在U280上运行的Vitis L2 GeMV基准测试高出2.64倍，并且在处理混合工作负载时，其性能比在24核Xeon Silver 4214 CPU上运行的Intel MKL提高了2.7倍。MAD-HiSpMV的代码可在https://github.com/SFU-HiAccel/HiSpMV获取。