基于PPR 模型的稀疏矩阵向量乘及卷积性能优化研究

在科学计算和系统工程等领域,稀疏矩阵向量乘（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倍的平均加速比.

     

GPU稀疏矩阵向量乘的性能模型构造

稀疏矩阵向量乘(Sparse matrix-vector multiplication,SPMV)是广泛应用于大规模线性求解系统和求解矩阵特征值等问题的基本运算,但在迭代处理过程中它也常常成为处理的瓶颈,影响算法的整体性能。对于不同形态的矩阵,选择不同的存储格式 ,对应的算法往往会产生较大的性能影响。通过实验分析,找到各种矩阵形态在不同存储结构下体现的性能变化特征,构建一个有效的性能度量模型,为评估稀疏矩阵运算开销、合理选择存储格式做出有效的指导。在14组CSR,COO,HYB格式和8组ELL格式的测试用例下,性能预测模型和测量之间的差异低于9%。     

基于CUDA编程模型的稀疏对角矩阵向量乘优化

稀疏矩阵向量乘是很多科学计算问题中的核心问题。本文针对稀疏对角矩阵,在DIA存储格式的基础上,设计了一种新型压缩存储格式CDIA,结合CUDA编程模型的特点,在计算线程上进行了细粒度的任务分配,同时为满足CUDA对存储器的合并访问要求,将压缩矩阵做了相应的转置处理,设计了细粒度算法与程序,并根据稀疏矩阵向量乘特点,做了相应的程序优化。实验数据显示,这种存储格式能够很好地发挥CUDA在数据处理方面的优势,在测试数据中,最高获得了单精度39.6Gflop/s和双精度19.6Gflop/s的浮点计算性能,性能在Nathan Bell和Michael Garland的基础上分别提高了7.6%和17.4%。     

基于缓存数据重用的稀疏矩阵向量乘序列优化

稀疏线性方程组求解等高性能计算应用常常涉及稀疏矩阵向量乘（SpMV）序列Ax,A²x, …, A^sx的计算. 上述SpMV序列操作又称为稀疏矩阵幂函数（matrix power kernel,MPK）. 由于MPK执行多次SpMV且稀疏矩阵保持不变,在缓存（cache）中重用稀疏矩阵,可避免每次执行SpMV均从主存加载A,从而缓解SpMV访存受限问题,提升MPK性能. 但缓存数据重用会导致相邻SpMV操作之间的数据依赖,现有MPK优化多针对单次SpMV调用,或在实现数据重用时引入过多额外开销. 提出了缓存感知的MPK（cache-aware MPK,Ca-MPK）,基于稀疏矩阵的依赖图,设计了体系结构感知的递归划分方法,将依赖图划分为适合缓存大小的子图/子矩阵,通过构建分割子图解耦数据依赖,根据特定顺序在子矩阵上调度执行SpMV,实现缓存数据重用. 测试结果表明,Ca-MPK相对于Intel OneMKL库和最新MPK实现,平均性能提升分别多达约1.57倍和1.40倍.     

基于深度学习的稀疏矩阵向量乘运算性能预测模型

稀疏矩阵向量乘（SpMV）是求解稀疏线性方程组的计算核心,被广泛应用在经济学模型、信号处理等科学计算和工程应用中,对于SpMV及其调优技术的研究有助于提升解决相关领域问题的运算效率。传统SpMV自动调优方法基于硬件平台的体系结构参数设置来提升SpMV性能,但巨大的参数设置量导致搜索空间变大且自动调优耗时大幅增加。采用深度学习技术,基于卷积神经网络,构建由双通道稀疏矩阵特征融合以及稀疏矩阵特征与体系结构特征融合组成的SpMV运算性能预测模型,实现快速自动调优。为提高SpMV运算时间的预测精度,选取特征数据并利用箱形图统计SpMV时间信息,同时在佛罗里达稀疏矩阵数据集上进行实验设计与验证,结果表明,该模型的SpMV运算时间预测准确率达到80%以上,并且具有较强的泛化能力。     

基于GPU的高性能稀疏矩阵向量乘及CG求解器优化

以有限元/有限差分等为代表的一类数值方法,其总体矩阵常常具有“带状”、稀疏的特点。针对“带状”稀疏矩阵,提出和实现了一种高效的矩阵向量乘存储格式和算法“bDIA\"。基于nVidia的GTX280系列GPU对其进行了测试,结果显示:与CUSP支持的5种常见稀疏矩阵存储格式和算法相比较,所提出的bDIA格式以及相应的spMV算法的单双精度浮点效率均可以提高1倍以上,并突破了该系列GPU在spMV计算时4%的单精度浮点效率上限和22.2%的双精度浮点效率上限;应用于共扼梯度(CG)与稳定双共扼梯度(BiCGStab)求解器,相对于DIA格式均有1.5倍左右的加速。     

基于异构平台的稀疏矩阵向量乘自适应计算优化

稀疏矩阵向量乘（SpMV）是一种重要的数值线性代数运算,现有的优化存在预处理及通信时间考虑不全面、存储结构不具有普适性等问题。为了解决这些问题,提出异构平台下SpMV的自适应优化方案。所提方案利用皮尔逊相关系数确定相关度高的特征参数,并使用基于梯度提升决策树（GBDT）的极端梯度提升（XGBoost）和轻量级梯度提升（LightGBM）算法训练预测模型,以确定某一稀疏矩阵更优的存储格式。利用网格搜索确定模型训练时更优的模型超参数,使这2种算法选择更适合的存储结构的准确率都超过85%。此外,对于预测存储结构为混合（HYB）格式的稀疏矩阵,在GPU和CPU上分别计算其中的等长列（ELL）与坐标（COO）存储格式部分,建立基于CPU+GPU的并行混合计算模式;同时为小数据量的稀疏矩阵选择硬件平台,提高运算速度。实验结果表明,自适应计算优化相较于cuSPARSE库中的压缩稀疏行（CSR）存储格式计算的平均加速比可以达到1.4,相较于按照HYB和ELL存储格式计算的平均加速比则可以分别达到2.1和2.6。     

稀疏矩阵向量乘的FPGA设计与实现

针对传统的通用处理器(GPP)平台上执行稀疏矩阵向量乘计算效率低的问题,提出一种基于可重构计算平台的SpMXV协处理器设计。方案采用二叉树结构高度流水的数据流、IEEE-754的32 bit浮点数数据格式和对角存储格式。数据通路以流水线方式进行组织,能够优化计算性能。仿真结果表明,与GPP平台上的软件实现相比,通过硬件实现的设计能达到最高2.69倍的性能加速。     

基于GPU的稀疏矩阵向量乘优化

针对稀疏矩阵运算难以发挥图形处理器的强大运算能力的现状,基于图形处理器的统一计算架构,在线程映射、数据复用等方面研究了一系列并行计算优化方法,从而完成了一种行压缩存储表示下的稀疏矩阵向量乘并行算法.这些优化方法包括:(1)利用Warp内线程天然同步特性,Half-warp完成结果向量一个元素的计算;(2)取整读取数据,实现合并访问;(3)输入向量放入纹理存储器,数据复用;(4)申请分页锁定内存,加速数据传输;(5)使用共享存储器,加速数据存取.实验分析表明,提出的各种手段起到了优化的作用.与已有的CUDPP和SpMV library中的CSR-vector算法相比,本算法获得了更高的存储器带宽和浮点运算吞吐量;整体性能比CPU串行执行版本快了3倍以上.     

基于约简核矩阵的稀疏最小二乘支持向量机

为了解决最小二乘支持向量机模型稀疏性不足的问题,提出了一种约简核矩阵的LS-SVM稀疏化方法.按照空间两点的欧式距离寻找核矩阵中相近的行(列),并通过特定的规则进行合并,以减小核矩阵的规模,进而求得稀疏LS-SVM模型.以高斯径向基核函数为例,详细阐述了改进方法的实现步骤,并通过仿真表明了采用该方法求得的稀疏LS-SVM模型泛化能力良好.     

面向国产申威26010众核处理器的SpMV实现与优化

世界首台峰值性能超过100P的超级计算机——神威太湖之光已经研制完成,该超级计算机采用了国产申威异构众核处理器,该处理器不同于现有的纯CPU,CPU-MIC,CPU-GPU架构,采用了主-从核架构,单处理器峰值计算能力为3TFlops/s,访存带宽为130GB/s.稀疏矩阵向量乘SpMV（sparse matrix-vector multiplication）是科学与工程计算中的一个非常重要的核心函数,众所周知,其是带宽受限型的,且存在间接访存操作.国产申威处理器给稀疏矩阵向量乘的高效实现带来了很大的挑战.针对申威处理器提出了一种CSR格式SpMV操作的通用异构众核并行算法,该算法从任务划分、LDM空间划分方面进行精细设计,提出了一套动静态buffer的缓存机制以提升向量x的访存命中率,提出了一套动静态的任务调度方法以实现负载均衡.另外还分析了该算法中影响SpMV性能的几个关键因素,并开展了自适应优化,进一步提升了性能.采用Matrix Market矩阵集中具有代表性的16个稀疏矩阵进行了测试,相比主核版最高有10倍左右的加速,平均加速比为6.51.通过采用主核版CSR格式SpMV的访存量进行分析,测试矩阵最高可达该处理器实测带宽的86%,平均可达到47%.     

并行计算稀疏矩阵乘以向量的负载平衡算法

稀疏矩阵乘以一个向量（SpM×V）的问题是许多大型应用问题的核心计算问题,文中提出了一种在并行计算机上并行计算SpMXV的负载平衡算法,计算复杂性为O（N）（N为稀疏矩阵的阶）,而目前计算此类问题的最优负载平衡算法的计算复杂性为O（N·P）（P为处理机台数）。文章最后给出了并行数值实验。     

一种用于图形渲染的高性能SpMV专用加速器结构

图形渲染中涉及的几何变换、投影变换、视口变换等需要大量稀疏矩阵向量乘法(Sparse Matrix-Vector Multiplication,SpMV)运算,如何实现SpMV高性能计算成为了图形处理器设计中的关键性问题之一,然而,当前的SpMV运算存在并行度较差,资源占用较多等问题.为提升硬件运算的性能,本文基于矩阵...     

基于高预测性的稀疏矩阵向量乘法并行计算优化

稀疏矩阵向量乘法(sparse matrix-vector multiplication, SpMV)是广泛应用于科学计算、工业仿真和智能计算等领域的重要算法,是核心的计算行为之一. 在一些应用场景中,需要进行多次的SpMV迭代,以完成精确的数值模拟、线性代数求解和图分析收敛等计算要求. 受限于SpMV本身的高度随机性和稀疏性所导致的数据局部性极差、缓存效率极低、计算模式非常不规则等问题,导致其计算负载成为当前高性能处理器的优化难点和研究热点. 基于现代高性能超标量乱序处理器的架构特征,深入研究SpMV的各类性能瓶颈,并且提出从提升可预测性和降低程序复杂度的角度进行全面的性能优化. 其核心思想是：通过构建串行访问的数据结构,提升数据访问的规律性和局部性,大幅度优化数据预取效率和缓存利用效率;通过构建规则的分支跳转条件,提升程序的分支预测准确率,有效提升程序执行效率;通过灵活运用SIMD指令集,有效提升计算资源利用率. 通过对以上特性的优化,该方法可以显著缓解性能瓶颈,大幅度提升处理器资源、缓存资源和访存带宽的利用率,并且获得与主流商用计算库MKL相比平均2.6倍的加速比,相比于现有最先进算法获得平均1.3倍的加速比.     

SpMV的自动性能优化实现技术及其应用研究

在科学计算中,稀疏矩阵向量乘(SpMV)是一个十分重要且经常被大量调用的计算内核.由于SpMV一般实现算法的浮点计算和存储访问次数比率非常低,且其存储访问模式极为不规则,其实际运行性能往往很低.通过采用寄存器分块算法和启发式分块大小选择算法,将稀疏矩阵分成小的稠密分块,重用保存在寄存器中向量x元素,可以提高该计算内核的性能.剖析和总结了OSKI软件包所采用的若干关键优化技术,并进行了实际应用性能测试.测试表明,在实际应用这些优化技术的过程中,应用程序对SpMV的调用次数要达到上百次的量级,才能抵消由于应用这些性能优化技术所带来的额外时间开销,取得性能加速效果.在Pentium 4和AMD Athlon平台上,测试了10个矩阵,其平均加速比分别达到了1.69和1.48.     

Vectorizing matrix operations arising from PDE discretization on 9-point stencils

When solving a system of PDEs, discretized on 9-point stencils over a nonrectangular domain, the linear systems that arise will have matrices with an irregular block structure. In this paper we discuss the vectorization of the matrix-vector multiply and of the Incomplete LU factorization and backsolve for these types of matrices. The performance of the matrix-vector multiply is already optimal for a small number of grid points (one result per clock cycle). For the ILU factorization and backsolve the vector performance is not as satisfying, partly because the resulting vector length is generally small and partly because of the heavy use of indirect addressing. A comparison with the general-purpose routines from the SLAP library shows a significant gain in computational time.This work was supported by Cray Research, Inc., under grant CRG 92.05, via the Stichting Nationale Computerfeciliteiten (National Computing Facilities Foundation, NCF).