HVMS:基于混合向量化的SpMV优化机制  

HVMS:A Hybrid Vectorization-Optimized Mechanism of SpMV

作　　者：颜志远 解壁伟[1,2] 包云岗 Yan Zhiyuan;Xie Biwei;Bao Yungang(State Key Lab of Processors(Institute of Computing Technology,Chinese Academy of Sciences),Beijing 100190;University of Chinese Academy of Sciences,Beijing 100049)

机构地区：[1]处理器芯片全国重点实验室(中国科学院计算技术研究所),北京100190 [2]中国科学院大学,北京100049

出　　处：《计算机研究与发展》2024年第12期2969-2984,共16页Journal of Computer Research and Development

基　　金：国家重点研发计划项目(2022YFB4500403);国家自然科学基金项目(62090022);中国科学院战略性先导科技专项(XDA0320300)。

摘　　要：在科学计算和系统工程等领域,稀疏矩阵向量乘(sparse matrix-vector multiplication,SpMV)占据着极其重要的位置.受限于矩阵稀疏性所导致的访存不规则性,向量优化一直是SpMV的难点.针对此问题,进行深入分析并且总结影响SpMV向量化效率的主要因素.除却稀疏矩阵内非零元分布的不规则,不同稀疏矩阵之间的非零元分布特征亦有明显不同,导致单一的向量优化策略难以适用于多种不同特征的稀疏矩阵.另一方面,多样化向量硬件在向量特性和指令上的差异,影响了SpMV向量优化方法的通用性.把不规则的稀疏矩阵映射到规则的向量硬件上进行计算,是SpMV向量化面临的最主要挑战.基于此,提出一种基于混合向量化方法的SpMV优化机制(hybrid vectorization-optimized mechanism of SpMV,HVMS).HVMS首先对向量硬件的特性进行抽象建模,并基于抽象出的基本操作,设计相应的规则指导稀疏矩阵进行规则化转换.按照不同的矩阵特征,HVMS将稀疏矩阵划分为不同的部分,弱化稀疏矩阵的不规则程度,并引入不同的优化策略最大化SpMV的向量化效率,从而提升性能.基于Intel Xeon平台,在30个常用稀疏矩阵上对HVMS进行实验分析.结果表明,相比现有代表性工作如CVR,SELL-C-σ,Intel MKL,HVMS分别获得1.60倍、1.72倍和1.93倍的平均加速比.ed basic operations to guide the regularization conversion of sparse matrices.HVMS divides the matrix into different parts according to the different characteristics.For each part,the non-zero distribution can be less irregular and then HVMS introduces corresponding optimization mechanisms to boost the vectorization efficiency of SpMV.We implement and evaluate HVMS on an Intel Xeon processor and compare it with three state-of-the-art approaches using 30 sparse matrices.Experimental results show that HVMS can achieve an average speedup of 1.60x,1.72x,and 1.93x over CVR,SELL-C-σ,and Intel MKL,respectively.

关 键 词：稀疏矩阵向量乘 向量优化 稀疏矩阵 SIMD 多核系统 

分 类 号：TP391[自动化与计算机技术—计算机应用技术]