HASpMV：现代非对称多核处理器上的异构感知稀疏矩阵-向量乘法

中文题目：HASpMV：现代非对称多核处理器上的异构感知稀疏矩阵-向量乘法

论文题目：HASpMV: Heterogeneity-Aware Sparse Matrix-Vector Multiplication on Modern Asymmetric Multicore Processors

录用期刊/会议：25th IEEE International Conference on Cluster Computing（CCF- B）

录用/见刊时间：2023.7.4

封面图片：

论文摘要：

稀疏矩阵-向量乘（SpMV）是科学与工程中的基本运算，近年来，非对称多核处理器（AMP）正成为更多台式机和工作站计算机的主流之一，然而目前还缺乏在AMP上加速SpMV的异构感知研究。在本文中，我们提出了一种异构感知的SpMV并行算法（HASpMV）。

作者列表：

1） 李文瑄 中国石油大学（北京） 信息科学与工程学院 计算机科学与技术专业 本20

2） 程贺琳 中国石油大学（北京） 信息科学与工程学院 计算机科学与技术专业 本20

3） 芦正阳 中国石油大学（北京） 信息科学与工程学院 计算机科学与技术专业 硕21

4） 卢玥辰 中国石油大学（北京）信息科学与工程学院 信息科学与工程学院 计算机科学与技术专业 博22

5） 刘伟峰 中国石油大学（北京）信息科学与工程学院 计算机科学与技术系 教授

文章简介:

在本文中，我们提出了一种在现代非对称多核处理器上的异构感知的SpMV并行算法(HASpMV)，通过基准测试了解SpMV分别在Intel和AMD AMP上两种不同内核的关键性能表现，并且提出了一种两级划分方案来提高SPMV的cache局部性和负载均衡性，设计了一种新的稀疏格式HACSR。与现有的SpMV方法相比，具有较好的cache局部性和负载均衡性，实现了良好的性能。

摘要:

稀疏矩阵-向量乘SDMV)是科学与工程中的基本运算，在各种同构并行处理器(如CPU、GPU)上的优方法受到广泛关注。近年来，非对称多核处理器（AMP）正成为更多台式机和工作站计算机的主流之一，具有异构的性能和能效核（如lntel和Apple的P-核和E-核、ARM的big.LITTLE架构），或者具有不同缓存结构的内核（如AMD的3DV-Cache内核）。然而，目前还缺乏在AMP上加速SpMV的异构感知研究。

在本文中，我们提出了一种异构感知的SpMV并行算法（HASpMV）。首先，我们对微基准带宽和多核/单核SpMV进行性能测试，收集性能特征并对算法设计进行激励；其次，提出了一种两级划分方案来提高SPMV的cache局部性和负载均衡性，将稀疏矩阵按照缓存行数量分别划分为lntel的P-核和E-核以及AMD的CCD0和CCD1两部分，并根据核数的不同进一步划分；第三，为了存储SpMV运行时所需的辅助信息，设计了一种新的稀疏格式HACSR。在实验中，我们将HASpMV在Intel和AMD处理器上与现有SpMV方法进行了比较，即nte oneMKl库、AMD优化CPU库(AOCL)、CSR5和merge-SpMV。实验结果表明，三个处理器上得到了平均1.3-3.73倍的加速比(最高达4.49-10.8倍)。

背景与动机:

图片1：SpMV的一个例子，其中A是稀疏的，x和y是稠密的

图片2：三种AMP的核心组成和缓存配置

图片3：在两台Intel AMP和一台AMD AMP上进行带宽测试

动机1：由于两种内核的性能不同，因此，我们的算法需要分配最佳工作量来利用这两种类型的核心。

图片4：2888 SuiteSparse矩阵在三个AMP上的并行SpMV性能

动机2：我们算法中的任务分配不仅要平衡工作量，还要考虑实现更高的工作负载缓存利用率

图片5：2888个矩阵的平均行长度的相关性

动机3：最好根据行长度重新排序，并将“最佳”长度的行分配给最合适的核心。

设计与实现:

我们的方法在处理稀疏矩阵-向量乘法中长行和短行时考虑了AMP两个核心之间的性能差异。为了优化性能，我们首先对矩阵重新排序以获得HACSR格式，这是标准CSR格式的一个小变体。此外，为了解决矩阵结构不平衡的挑战，我们利用缓存线成本作为矩阵分区的基础，而不是简单地基于非零的数量进行分区。这使我们能够在AMP内核之间实现更好的负载平衡。我们设计了一种两级矩阵划分方法（图6所示），根据AMP中两种核的带宽测试，将矩阵划分为两部分。随后，我们将等量的任务分配给同一组内的每个核心，有效地解决了处理器不平衡带来的挑战。此外，包括处理冲突行和合并其他性能改进技术。

图6：一个按照缓存行数量划分稀疏矩阵的例子

实验结果及分析:

图7展示了HASpMV和其他SpMV方法的性能结果。实验结果表明，与最新版本的Intel oneMKL库和CSR5和merge-SpMV相比，HASpMV在i9-12900KF处理器上的平均加速分别为2.61倍、2.31倍和3.73倍(最高可达5.23倍、4.46倍和8.23倍)。在i9-13900KF处理器上，HASpMV实现了3.17倍、1.52倍和2.23倍的平均加速比(最高可达9.46倍、5.31倍和4.49倍)。此外，当比较AMD Ryzen 9 7950X3D和7950X AMPs时，HASpMV比AMD优化CPU库(AOCL)， CSR5和merge-SpMV分别带来1.43倍，1.3倍和1.29倍(高达6.28倍，7.8倍和10.8倍)的平均加速。

图7：2888 SuiteSparse矩阵在三个AMP上，分别使用HASpMV与oneMKL、AOCL、CSR5和Merge-SpMV算法的性能比较

结论:

本文提出了在现代非对称多核处理器上的异构感知的SpMV并行算法（HASpMV）。我们的方法通过微基准测试了解了英特尔P-核和E-核(AMD的CCD0和CCD1)的关键性能特征，并提出了更好的缓存局域性和负载平衡技术。在三款最新的英特尔和AMD AMP上进行的实验显示，与现有SpMV方法相比，速度有了显著提高。

通讯作者简介:

刘伟峰，博士、中国石油大学（北京）教授、博士生导师，欧盟玛丽居里学者。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会员。

联系方式：weifeng.liu@cup.edu.cn