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

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

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

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

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

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

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

稀疏矩阵向量乘和卷积作为高性能计算的两大计算核心, 是非规则和规则访存的典型代表.目前已经做了许多针对性的优化工作, 但是对于大量运行着不同指令集和拥有不同计算和访存性能的机器, 仍然无法判定在特定的体系结构下导致性能效率无法被完全释放的主要原因及性能瓶颈, 同时也很难准确预测出程序在特定机器上可达到的最佳性能.通过使用性能模型方法, 建模程序在真实机器上的运行细节, 可以得出更加精确的性能预测, 并且根据模型输出的反馈信息提出针对性的优化指导.提出了PPR(probability-process-ram)模型, 并在一个通用处理器上建模程序内指令执行和数据传输开销, 其中包括使用模型预测各种指令数量及内存层次之间的数据传输大小去分析程序各个阶段的性能瓶颈, 并且根据模型反馈的信息提出优化方案以及优化后的性能期望.最终使用PPR建模和优化2个计算核心, 同时也比较了与常用的Roofline和ECM模型的区别.     

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

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

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

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

基于GPU的稀疏矩阵存储格式优化研究

稀疏矩阵存储格式中的稀疏矩阵向量乘(SpMV)计算效率低下,且分块行列(BRC)存储格式的计算结果缺少再现性和确定性。为此,提出一种改进的BRCP存储格式。采用不同的二维分块策略,根据矩阵各行非零元素分布的统计特性自适应调节分块参数,提高SpMV在GPU平台上的并行性,并设计基于快速分段求和算法的GPU内核函数,保证计算结果的确定性及其在不同GPU平台上的再现性。实验结果表明,BRCP存储格式具有较高的计算效率,相比BRC存储格式可减少并行环境中的SpMV计算误差,并提高PageRank排序的准确率。     

带状稀疏矩阵乘法及高效GPU实现

稀疏-稠密矩阵乘法（SpMM）广泛应用于科学计算和深度学习等领域,提高它的效率具有重要意义。针对具有带状特征的一类稀疏矩阵,提出一种新的存储格式BRCV(Banded Row Column Value)以及基于此格式的SpMM算法和高效图形处理单元（GPU）实现。由于每个稀疏带可以包含多个稀疏块,所提格式可看成块稀疏矩阵格式的推广。相较于常用的CSR(Compressed Sparse Row)格式,BRCV格式通过避免稀疏带中列下标的冗余存储显著降低存储复杂度;同时,基于BRCV格式的SpMM的GPU实现通过同时复用稀疏和稠密矩阵的行更高效地利用GPU的共享内存,提升SpMM算法的计算效率。在两种不同GPU平台上针对随机生成的带状稀疏矩阵的实验结果显示,BRCV的性能不仅优于cuBLAS(CUDA Basic Linear Algebra Subroutines),也优于基于CSR和块稀疏两种不同格式的cuSPARSE。其中,相较于基于CSR格式的cuSPARSE,BRCV的最高加速比分别为6.20和4.77。此外,将新的实现应用于图神经网络（GNN）中的SpMM算子的加速。在实际应...     

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

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

二元域大型稀疏矩阵向量乘的FPGA设计与实现

作为Wiedemannn算法的核心部分,稀疏矩阵向量乘是求解二元域上大型稀疏线性方程组的主要步骤。提出了一种基于FPGA的二元域大型稀疏矩阵向量乘的环网硬件系统架构,为解决Wiedemannn算法重复计算稀疏矩阵向量乘,提出了新的并行计算结构。实验分析表明,提出的架构提高了Wiedemannn算法中稀疏矩阵向量乘的并行性,同时充分利用了FPGA的片内存储器和吉比特收发器,与目前性能最好的部分可重构计算PR模型相比,实现了2.65倍的加速性能。     

面向GPU平台的并行结构化稀疏三角方程组求解器

稀疏三角线性方程组求解(SpTRSV)是预条件子部分的重要操作,其中结构化SpTRSV问题,在以迭代方法求解偏微分方程组的科学计算程序中,是一种较为常见的问题类型,而且通常是科学计算程序的需要解决的一个性能瓶颈.针对GPU平台,目前以CUSPARSE为代表的商用GPU数学库,采用分层调度(level-scheduling)方法并行化SpTRSV操作.该方法不仅预处理耗时较长,而且在处理结构化SpTRSV问题时会出现较为严重GPU线程闲置问题.针对结构化SpTRSV问题,提出一种面向结构化SpTRSV问题的并行算法.该算法利用结构化SpTRSV问题的特殊非零元分布规律进行任务划分,避免对输入问题的非零元结构进行预处理分析.并对现有分层调度方法的逐元素处理策略进行改进,在有效缓解GPU线程闲置问题的基础上,还隐藏了部分矩阵非零元素的访存延迟.还根据算法的任务划分特点,采用状态变量压缩技术,显著提高算法状态变量操作的缓存命中率.在此基础上,还结合谓词执行等GPU硬件特性,对算法实现进行全面的优化.所提算法在NVIDIA V100 GPU上的实测性能,相比CUSPARSE平均有2.71倍的加速效果,有效访存带宽最高可达225.2 GB/s.改进后的逐元素处理策略,配合针对GPU硬件的一系列调优手段,优化效果显著,将算法的有效访存带宽提高了约1.15倍.     

GPU上稀疏矩阵与矢量乘积运算的一种改进

稀疏矩阵和矢量的乘积运算在工程实践及科学计算中经常用到,随着矩阵规模的增长,大量的计算限制了整个系统的性能,因此可以利用GPU的高运算能力加速SpMV。分析了现有GPU上实现的SpMV存在的问题,并设计了行分割优化和float4数据类型优化两种方案。实验表明,该方案可以使性能提升2—8倍。     

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

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

GPU 上的矩阵乘法的设计与实现

矩阵乘法是科学计算中最基本的操作,高效实现矩阵乘法可以加速许多应用。本文使用NVIDIA的CUDA在GPU上实现了一个高效的矩阵乘法。测试结果表明,在Geforce GTX260上,本文提出的矩阵乘法的速度是理论峰值的97％,跟CUBLAS库中的矩阵乘法相当。     

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

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

面向稀疏卷积神经网络的GPU性能优化方法

近些年来,深度卷积神经网络在多项任务中展现了惊人的能力,并已经被用在物体检测、自动驾驶和机器翻译等众多应用中.但这些模型往往参数规模庞大,并带来了沉重的计算负担.神经网络的模型剪枝技术能够识别并删除模型中对精度影响较小的参数,从而降低模型的参数数目和理论计算量,给模型的高效执行提供了机会.然而,剪枝后的稀疏模型却难以在GPU上实现高效执行,其性能甚至差于剪枝前的稠密模型,导致模型剪枝难以带来真正的执行性能收益.提出一种稀疏感知的代码生成方法,能够生成高效的稀疏卷积GPU程序.首先为卷积算子设计了算子模板,并结合GPU的特点对模板代码进行了多种优化.算子模板中的源代码经过编译和分析被转换为算子中间表示模板,设计了一种稀疏代码生成方法,能够结合剪枝后的稀疏参数,基于中间表示模板生成对应的稀疏卷积代码.同时,利用神经网络执行过程中的数据访问特点对数据的访问和放置进行了优化,有效提升了访存吞吐量.最后,稀疏参数的位置信息被隐式编码在生成的代码中,不需要额外的索引结构,降低了访存需求.在实验中证明了:相对于GPU上已有的稀疏神经网络执行方法,提出的稀疏感知的代码生成方法能够有效提升稀疏卷积神经网...