摘要：分析稀疏矩阵向量乘(SpMV)程序优化的难点,介绍两个自动调优的代表性工作:基于预实现模板的SMAT和从头设计程序的AlphaSparse。详细介绍了它们的设计思路、实现细节、测试结果以及各自的优缺点。最后,对SpMV自动调优的发展趋势进行了分析和预测。

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

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

摘要：作为典型的不规则算法,稀疏矩阵向量乘的计算过程具有非常低的访存局部性和计算访存比,因此在基于cache的通用处理器上计算效率很低。提出了一种面向可重构计算平台的基于IEEE-754浮点数据格式标准的稀疏矩阵向量乘算法加速器的设计。在一维划分的行压缩稀疏矩阵数据存储技术以及计算部件的流水化设计的基础上,提出了一种基于单个浮点加法器的无阻塞累加器设计。通过实验验证表明,简化了算法的设计提高了算法执行的并行度和外部存储器的带宽利用率,获得了相对于传统处理器1.37-2.60倍的性能加速比。

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

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

摘要：矩阵主特征向量(principal eigenvectors computing,PEC)的求解是科学与工程计算中的一个重要问题。随着图形处理单元通用计算(general-purpose computing on graphics pro cessing unit,GPGPU)的兴起,利用GPU来优化大规模稀疏矩阵的图形处理单元求解得到了广泛关注。分别从应用特征和GPU体系结构特征两方面分析了PEC运算的性能瓶颈,提出了一种面向GPU的稀疏矩阵存储格式——GPU-ELL和一个针对GPU的线程优化映射策略,并设计了相应的PEC优化执行算法。在ATI HD Radeon5850上的实验结果表明,相对于传统CPU,该方案获得了最多200倍左右的加速,相对于已有GPU上的实现,也获得了2倍的加速。

摘要：世界首台峰值性能超过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%.

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

摘要：稀疏矩阵向量乘(Sparse Matrix-Vector Multiply,SMVM),形如Ab=x,在科学计算、信息检索、数据挖掘等领域中都是重要的计算核心之一。稀疏矩阵中非零元素的稀疏性,使得在微处理器上实现该类运算时,存在Cache缺失率高等问题,导致性能并不理想。针对该问题提出了基于FPGA实现SMVM运算系统的新思路,对系统功能进行了软硬件划分,并完成了系统中硬件浮点乘累加处理单元(ProcessingElement,PE)的设计与实现。目标器件为Virtex4LX60,工作频率达到123.6MHz。