点击数: 更新日期: 2023-09-13
中文题目：HASpGEMM：现代非对称多核处理器上的异构感知稀疏矩阵-矩阵乘法
论文题目：HASpGEMM: Heterogeneity-Aware Sparse General Matrix-Matrix Multiplication on Modern Asymmetric Multicore Processors
原文DOI：https://doi.org/10.1145/3605573.3605611
原文链接：https://icpp23.sci.utah.edu/images/papers/icpp2023-38.pdf
录用/见刊时间：2023年06月16日
封面摘要：稀疏矩阵-矩阵乘（SpGEMM）是计算科学和工程中的重要操作，而在近年来逐渐成为主流的非对称多核处理器（AMP）上直接运行SpGEMM则会由于AMP核心的非对称性和稀疏矩阵的不规则性造成严重的不均衡，本文提出了一种能够解决该问题的构感知稀疏矩阵-矩阵乘法。
作者列表：
1） 程贺琳 中国石油大学（北京） 信息科学与工程学院 计算机科学与技术专业 本20
2） 李文瑄 中国石油大学（北京） 信息科学与工程学院 计算机科学与技术专业 本20
3） 卢玥辰 中国石油大学（北京）信息科学与工程学院 信息科学与工程学院 计算机科学与技术专业 博22
4） 刘伟峰 中国石油大学（北京）信息科学与工程学院 计算机科学与技术系 教授
文章简介:
在本文中，我们提出了一种现代非对称多核处理器（AMP）上的异构感知稀疏矩阵-矩阵乘法，该算法考虑了AMP的不同核心特性、SpGEMM的访存和计算特性开发了一种任务分配方案，并且根据基础SpGEMM内核的特性设计了一种逐行映射技术，能够平衡核心之间的负载，实现良好的性能。
摘要:
稀疏矩阵-矩阵乘（SpGEMM）是计算科学和工程中的重要操作，在同构处理器上有着广泛研究。近年来，由ARM的big和LITTLE核心，以及由苹果和英特尔的性能和能效核组成的非对称多核处理器（AMP），正成为现代计算机的主流处理器。然而，直接在AMP上运行现有的SpGEMM算法很容易由于稀疏矩阵和AMP两方面的不规则性而导致负载不均衡，并且目前还缺乏一种可以有效利用AMP上不同核心的并行SpGEMM算法。针对以上问题，我们首先通过微基准测试获得了Intel i9-12900KF和i9-13900KF两款AMP的不同核心上三种SpGEMM内核（即SPA、HASH和ESC）的性能特性。基于大量的测试数据，我们对三种常见内核设计设计了一种逐行映射技术，以更好地选择不同特性行的内核和核心，并且开发了一种任务分配方案，以更好地在计算和内存访问方面平衡两种类型的核心的工作负载。实验结果表明，与SPA、HASH、ESC、oneMKL相比，在i9-12900KF、i9-13900KF上分别达到了平均1.85-3.85倍和2.21-4.56倍的加速比。
背景与动机:
SpGEMM是将两个稀疏矩阵A和B相乘，得到一个稀疏矩阵C的操作，在本文我们用图1所示的矩阵乘矩阵的转置作为测试对象。稀疏矩阵存在大量零元的，且行间的非零元分布不均匀，这导致行间的计算与访存操作存在差异，所以基础的算法难以实现负载均衡。针对SpGEMM有三个常用的优化内核：SPA、HASH、ESC，如图3的下半部分所示，他们有着不同的空间开销和计算特性，且有着各自喜好的矩阵结构。非对称多核处理器（AMP）是当代计算机处理器的趋势，它由具有不同计算频率和缓存结构的核心构成，如图2展示了Intel的两款AMP的结构图，他们各自由性能核（P核）以及能效核（E核）组成。稀疏矩阵和AMP的两重不均衡性给并行化SpGEMM带来挑战，并且常用优化内核的不同喜好也加剧了算法设计的挑战。
图1：稀疏矩阵-矩阵乘样例
图2：(a) i9-12900KF具有八个P核心和八个E核心，以及(b) i9-13900KF具有八个P核心和16个E核心。
图3：任务分配策略以及三个SpGEMM内核的实现原理
为了得到算法设计的动机，我们首先通过使用SuiteSparse Matrix Collection中的全部2888个稀疏矩阵，选择了前面提到的Intel第12代和第13代AMP，进行了以下三组微基准测试：（1）如图4，P核心和E核心的性能比较。此基准测试旨在确定这两种类型核心所实现的加速比，从而使我们能够识别出最优的任务分配策略。可以看出（2）如图5，通过内存访问开销和计算开销对矩阵分区进行性能评估。此测试旨在分析内存访问操作和计算操作对性能的影响，以便了解任务分配如何带来更好的性能。（3）如图6、7，行数、中间乘积数量与三种基本累加器内核性能之间的相关性。在这里，我们可以理解在核心上运行这三种基本内核时，矩阵的性能行为，从而激发我们选择适用于不同矩阵和行数的合适内核。
图4：P核相对E核在处理SpGEMM时的加速比
图5：以访存开销作为矩阵划分依据时相对计算量作为矩阵划分依据的加速比
图6：在矩阵行数不同时的最优内核
图7：在矩阵中间积数量不同时的最优内核
设计与实现:
我们基于以上结果总结出HASp GEMM的两个阶段：分析阶段和执行阶段。在分析阶段，需要计算矩阵每行的负载权重，并且针对两种核心进行矩阵的两级划分。行负载权重的计算的伪代码如图8所示，将这一行计算中的中间积数量作为计算量，将访问矩阵B近似消耗的缓存行数量作为访存开销，两个因素之和作为行权重。下一步根据行权重执行图9伪代码所示的二级划分，将矩阵负载均衡得分给各个核心。在执行阶段，使用一个如图10所示的内核决策树实现不同内核的行映射，如果矩阵行数小于设置的阈值P_Bound，则直接选择SPA内核。否则，每一行将根据中间乘积数量选择最优内核。
图8：行权重计算的伪代码
图9：矩阵的二级划分伪代码
图10：SpGEMM内核的决策树。
实验结果及分析:
我们的测试平台包括两台分别配备了最新的Intel处理器 i9-12900KF 和 i9-13900KF 的计算机。这两台计算机均运行着支持Intel Thread Director 的Linux 版本操作系统 Ubuntu 22.10。详细信息如图11所示。
图11：实验平台信息
我们使用SuitSparse Matrix Collection中的全部2888个稀疏矩阵作为大规模测试的数据集，并且从中挑选了22个代表性矩阵进一步分析性能。我们将HASpGEMM与SPA、HASH、ESC三个内核以及最新版oneMKL进行性能对比，得到了图12所示的性能散点图和图13所示的柱状图，在i9-12900KF、i9-13900KF上分别达到了平均1.85-3.85倍和2.21-4.56倍的加速比。
图12：大规模测试性能对比散点图
图13：代表性矩阵测试性能对比柱状图
我们还分析了我们的任务划分策略的实际计算和访存负载情况，并绘制了图14所示的折线图，其中红线和蓝线分别代表了使用HASpGEMM算法和使用普通并行方法时每个核心的负载。
图14：HASpGEMM与普通并行方法的负载情况
我们也对HASpGEMM在22个代表性矩阵上执行两个时期的时间占比做出了分析，绘制了如图15所示的柱状图，蓝色和黄色分别是分析时期和执行时期的占比。在两个处理器上分析时间分别不超过30%和43%，考虑到带来的负载均衡收益是完全可以接收的时间。
图15：HASpGEMM的两个时期时间占比
结论:
在本文中，我们提出了HASpGEMM，一种新的SpGEMM算法，以更好地利用现代AMP。通过微基准测试，我们了解了基本累加器内核和两种类型核心的性能特性，并将其用于指导算法设计。与最新的现有工作相比，我们的HASpGEMM方法通过负载均衡的任务分配和逐行的内核选择在两个Intel AMP上为广泛使用的SuiteSparse矩阵集合中的大多数稀疏矩阵带来了显著的加速。
通讯作者简介:
刘伟峰，博士、中国石油大学（北京）教授、博士生导师，欧盟玛丽居里学者。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