基于BWDSP1042的复数矩阵向量乘的优化与实现

采用两种方法对复数矩阵向量乘进行优化,提高其在BWDSP1042上的运行效率。一是按列分块与减少二级循环内循环次数相结合的方法(矩阵列非4的倍数);二是模八寻址与减少二级循环内循环次数相结合的方法(矩阵列为4的倍数)。实验结果表明,采用第一种方法可缩短复数矩阵向量乘的运行周期2.8倍以上,第二种方法可缩短其运行周期3.1倍以上。

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

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

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

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

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

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

基于FPGA的稀疏矩阵向量乘的设计研究

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

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

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

EBE技术在结构分析中的应用（Ⅰ）─EBE矩阵向量乘积方法及其实现

矩阵向量乘积运算是数值分析领域中的一种基本运算。本文基于单元分组技术，提出了在有限元结构分析中，当不形成总刚度矩阵而进行矩阵向量乘积的ＥＢＥ计算方法。该方法不仅预处理过程简单，实现容易，而且其并行化、向量化处理都极为直接。同时，数值试验结果还表明了它的有效性。

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

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

矩阵向量乘在流处理器上的实现

Imagine是一款致力于媒体处理的流体系结构芯片,而它是否适合科学计算应用是当前国际上的热点讨论问题。本文研究了典型科学计算核心——矩阵向量乘在Imagine处理器上的有效映射,主要开发了四种不同的流程序版本,并且提出了优化方法。实验结果表明,经过优化的矩阵向量乘程序能够开发Imagine处理器的潜能。

稀疏矩阵向量乘法在申威众核架构上的性能优化

计算机数值模拟是现代科学和技术发展的重要触发力量.在数值模拟中,求解大规模稀疏线性方程组是非常重要的一个环节.迭代求解过程中稀疏矩阵向量乘法是耗时最长的计算核心之一,存在严重的数据局部性差、写冲突、负载不均衡等问题.因此,稀疏矩阵向量乘法已经成为了当前性能优化的难点和研究热点.本文面向国产众核处理器架构,以申威26010国产众核处理器为平台,针对稀疏矩阵向量乘法,在线程级和指令级并行层面上进行细粒度的并行算法设计和优化实现.其核心思想是,将众核架构设计精巧的矩阵分层分块技术用于矩阵存储、访问和任务调度,在保证右端向量数据复用的同时有效实现了负载均衡,避免了申威26010上因频繁缓存判断和细粒度访问导致的潜在性能问题.通过对SuiteSparse矩阵集合中的2710个算例的测试,该算法可以获得与主核上的串行算法相比11.7倍的平均加速和55倍的最高加速.

基于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模型的区别.

基于Intel Xeon Phi的稀疏矩阵向量乘性能优化

稀疏矩阵向量乘(Sp MV)是线性求解系统等科学计算中重要的计算核心.鉴于传统的稀疏矩阵向量乘算法在Intel Xeon Phi众核集成架构上存在SIM D利用率低,不规则访存开销高及负载不均衡的问题,难以发挥其运算能力.本文针对Intel Xeon Phi的体系结构特点,提出了一种通用的分块压缩存储表示的稀疏矩阵向量乘并行算法:(1)在ELLPACK存储格式基础上按列分块及压缩矩阵,增加非零元的密度,提高SIMD利用率;(2)通过精心的数据重排,保留矩阵非零元本身的局部性,从而提高数据重用率,降低访存开销;(3)将矩阵压缩后划分成近似等大的矩阵块并静态等量分配到不同核上计算,使各核负载均衡.实验结果表明,与Intel Xeon Phi上已有的MKL数学库中的CSR算法相比,本算法获得了更高的计算访存比,性能比M KL的CSR算法平均快2.05倍.

浮点矩阵向量乘法的FPGA设计与优化

提出了一种基于IEEE-754的32 bit、64 bit浮点数格式,二叉树数据流(binary tree data flow)的矩阵向量乘法器.其在FPGA上流水线和高度并行化的高效执行.以Altera公司的EP2C70为实现设备,研究了设计的硬件规模,时钟速度,和峰值GFLOPS能力.

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

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

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

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

选择粗化函数优化并行稀疏矩阵向量乘法

讨论了如何分划稀疏矩阵的非零元素以减少并行矩阵向量乘法的通信代价。通过以粗化函数为工具,统一现有的数据分划方法;提出一种基于行列分划为初解的粗化函数选取方法,在理论上的证明其运行效率与分划质量不逊于一维数据分划方法;实验数据表明,该方法产生分划质量超过一维数据分划方法的结果,接近甚至超过二维细粒度方上法的结果。

基于申威1621的通用矩阵向量乘法的性能分析与优化

通用矩阵向量乘法(GEMV)函数是整个二级基础线性代数子程序(BLAS)函数库的构建基础,BLAS作为关键基础计算软件之一,目前在申威处理器上却没有一个高性能实现的版本。针对上述问题,为充分发挥申威1621平台的高性能BLAS库计算优势,提出一种基于申威1621的通用矩阵向量乘法的性能分析与优化方法。首先对GEMV函数进行计算重排序、循环分块的改进;然后采取单指令多数据流(SIMD)以及指令重排的优化方式;最后对内存分配方式进行择优选择。测试结果表明,GEMV函数平均性能达到GotoBLAS版的2.17倍。在使用堆栈分配内存空间或增加对y向量步长的判断分支两种方案后,相较于GotoBLAS,小规模矩阵的平均性能由2.265倍提升至2.875倍。为提高大规模矩阵的性能,以及发挥申威1621多核处理器并行机制,在开启4线程后,平均性能达到单核的3.57倍。因此,优化后的GEMV函数在申威平台上较好的体现了并行效果。

Hermitian Toeplitz矩阵向量乘积的快速算法

众所周知,大规模Hermitian Toeplitz矩阵向量乘积Ax可由快速Fourier变换(FFT)进行计算.事实上,Hermitian Toeplitz矩阵在酉相似变换下可约化为一个实的Toeplitz矩阵与Hankel矩阵之和.基于此,本文利用DCT和DST,构造了一个更有效的方法,只需O(n)的复运算.

面向稀疏矩阵向量乘的DMA设计与验证

稀疏矩阵向量乘法(SpMV)是迭代法求解大型线性方程组的核心算法,被广泛应用在科研和工程中。高性能共轭梯度算法(HPCG)是评价高性能计算系统性能的测试程序之一,需要多次调用SpMV进行迭代计算。但是,SpMV计算过程中包含大量不规则访存操作,降低了系统计算性能。基于X-DSP项目,在DMA中设计一条面向SpMV的专用数据通道实现不规则访存的功能,提高HPCG算法运算速度。设计代码的验证与综合结果表明预期的功能实现正确,且满足项目对时序、面积和功耗的要求。