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

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

基于HYB格式稀疏矩阵与向量乘在CPU+GPU异构系统中的实现与优化

稀疏矩阵与向量相乘SpMV是求解稀疏线性系统中的一个重要问题,但是由于非零元素的稀疏性,计算密度较低,造成计算效率不高。针对稀疏矩阵存在的一些不规则性,利用混合存储格式来进行SpMV计算,能够提高对稀疏矩阵的压缩效率,并扩大其适应范围。HYB是一种广泛使用的混合压缩格式,其性能较为稳定。而随着GPU并行计算得到普遍应用以及CPU日趋多核化,因此利用GPU和多核CPU构建异构并行计算系统得到了普遍的认可。针对稀疏矩阵的HYB存储格式中的ELL和COO存储特征,把两部分数据分别分割到CPU和GPU进行协同并行计算,既能充分利用CPU和GPU的计算资源,又能够发挥CPU和GPU的计算特性,从而提高了计算资源的利用效能。在分析CPU+GPU异构计算模式的特征的基础上,对混合格式的数据分割和共享方面进行优化,能够较好地发挥在异构计算环境的优势,提高计算性能。     

基于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的高性能稀疏矩阵向量乘及CG求解器优化

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

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

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

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

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

稀疏矩阵向量乘法的并行计算

本文研究大型稀疏矩阵向量乘法的并行化措施。主要包括高效的存储方法,核心代码用汇编语言编写,循环展开,宏任务和微任务方式,重排序和分块技术。根据实际问题的需要,分别给出了一般稀疏矩阵和对称正定带状矩阵向量乘法内核子程序,ELLPACK,ITPAKC及LINPACK等库和许多应用程序可直接调用它们。     

一种准对角矩阵的混合压缩算法及其与向量相乘在GPU上的实现

稀疏矩阵与向量乘(SpMV)属于科学计算和工程应用中的一种基本运算,其高性能实现与优化是计算科学的研究热点之一。在微分方程的求解过程中会产生大规模的稀疏矩阵,而且很大一部分是一种准对角矩阵。针对准对角矩阵存在的一些不规则性,提出一种混合对角存储(DIA)和行压缩存储(CSR)格式来进行SpMV计算,对于分割出来的对角线区域之外的离散非零元素采用CSR存储,这样能够克服DIA在不规则情况下存储矩阵的列迅速增加的缺陷,同时对角线采用DIA存储又能充分利用矩阵的对角特征,以减少CSR的行非零元素数目的不均衡现象,并可以通过调整存储对角线的带宽来适应准对角矩阵的不同的离散形式,以获得比DIA和CSR更高的压缩比,减小计算的数据规模。利用CUDA平台在GPU上进行了实验测试,结果表明该方法比DIA和CSR具有更高的加速比。     

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

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

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

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

基于CUDA的稀疏矩阵与矢量乘法的优化

随着VLSI技术的发展,在单芯片上集成若干个处理器核的思想成为现实,现代GPU就是一个典型的多核处理器设备;由于面向计算密集型的应用发展非常迅速,当前的GPU又具有了较强的通用计算能力;全文首先介绍了CUDA和稀疏矩阵的相关知识;基于矩阵的CSR表示格式,文章提出了三种CUDA模型下的程序优化方法;论文分析并实现了这三种程序优化方法,在Geforce 9600GT上的实验结果表明,最大可以实现4倍左右的加速比.     

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

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

基于CUDA平台的FIR滤波算法的设计与优化

针对目前基于普通DSP的FIR算法速度低、扩展性差的缺点,提出并实现基于CUDA平台实现的FIR滤波算法。由于在CUDA中程序可以直接操作数据而无需借助于图形系统的API,使开发者能够在GPU 强大计算能力的基础上建立起一种效率更高的密集数据计算解决方案。该算法将CUDA用于FIR滤波器输入输出关系计算,采用矩阵乘法的并行运算技术,在GPU上建立并行滤波模型,并对算法进行了优化。实验结果表明,在Tesla C1060平台上,和传统的基于DSP的FIR滤波算法计算速度相比,基于CUDA平台计算FIR滤波算法时,其加速比可接近30,解决了传统基于DSP计算FIR滤波算法速度较慢、扩展性差的问题。     

按行及按列划分的并行矩阵向量乘法的分析

文中首先总结按行划分和按列划分的并行矩阵向量乘法在原理上的异同。然后实现基于MPI模型的按行划分以及按列划分的矩阵向量乘法的程序,并分析了程序在基本框架方面的异同。最后给出测试这两种程序的实验条件和任务,并对这两种程序在不同情况下的执行时间进行分析。     

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

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