基于LDLT分解求实对称矩阵特征值的递归算法

基于线性代数与矩阵理论,给出利用LDLT分解计算实对称矩阵特征值的递归算法。该算法可求出实对称矩阵在给定区间内的特征值的个数,并可计算满足精度要求的特征值。理论分析和实际测试证明该算法是有效的。     

对称正定矩阵的并行LDLT分解算法实现

基于网络机群这一新的并行环境和消息传递界面MPI给出了两种不带平方根的Cholesky并行分解算法，算法采用行卷帘存储方案和提前发送策略，从而减少了负载的不平衡，增加了计算通信的重叠，减少了通信时间。理论分析和数值试验均表明，算法具有较高的并行加速比和效率。     

基于GPU的稀疏矩阵Cholesky分解

稀疏矩阵Cholesky分解是求解大规模稀疏线性方程组的核心算法,也是求解过程中最耗时的部分.近年来,一系列并行算法通过图形处理器(GPU)获得了显著的加速比,然而,由于访存的不规则性以及任务间的大量数据依赖关系,稀疏矩阵Cholesky分解算法在GPU上的计算效率很低.文中实现了一种新的基于GPU的稀疏矩阵Cholesky分解算法.在数据组织方面,改进了稀疏矩阵超节点数据结构,通过超节点合并和分块控制计算粒度;在计算调度方面,将稀疏矩阵Cholesky分解过程映射为一系列的数据块任务,并设计了相应的任务生成与调度算法,在满足数据依赖性的前提下提高任务的并行性.实验结果表明,该算法能够显著提高稀疏矩阵Cholesky分解算法在GPU上的实现效率,在单个GPU上获得了相对4核CPU平台2.69~3.88倍的加速比.     

LDLT分解协处理器的并行结构研究

为提高LDLT分解协处理器的性能,基于FPGA平台,研究其并行结构。分析循环片间的数据依赖关系,提出LDLT分解细粒度并行算法,并在可扩展一维阵列处理器中加以实现,利用主机、算法加速器组成单精度浮点LDLT分解协处理器的并行结构。实验结果表明,与运行在2.50 GHz Pentium微处理器上的C代码相比,该协处理器可获得32.03倍~43.25倍的性能提升。     

广义稠密对称特征问题标准化算法在GPU集群上的有效实现

广义稠密对称特征问题的求解是许多应用科学和工程的主要任务,并且是计算电磁学、电子结构、有限元模型和量子化学等计算中的重要部分。将广义对称特征问题转化为标准对称特征问题是求解广义稠密对称特征问题的关键计算步骤。针对GPU集群,文中给出了广义稠密对称特征问题标准化块算法在GPU集群上基于MPI+CUDA的实现。为了适应GPU集群的架构,广义对称特征问题标准化算法将正定矩阵的Cholesky分解与传统的广义特征问题标准化块算法相结合,降低了标准化算法中不必要的通信开销,并且增强了算法的并行性。在基于MPI+CUDA的标准化算法中,GPU与CPU之间的数据传输操作被用来掩盖GPU内的数据拷贝操作,这消除了拷贝所花费的时间,进而提高了程序的性能。同时,文中还给出了矩阵在二维通信网格中行通信域和列通信域之间完全并行的点对点的转置算法和基于MPI+CUDA的具有多个右端项的三角矩阵方程BX=A求解的并行块算法。在中科院计算机网络信息中心的超级计算机系统“元”上,每个计算节点配置2块Nvidia Tesla K20 GPGPU卡及2颗Intel E5-2680 V2处理器,使用多达32个GPU对不同规模矩阵的基于MPI+CUDA的广义对称特征问题标准化算法进行测试,取得了较好的加速效果与性能,并且具有良好的可扩展性。当使用32个GPU对50000×50000阶的矩阵进行测试时,峰值性能达到了约9.21 Tflops。     

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

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

基于批量LU分解的矩阵求逆在GPU上的有效实现

给出批量矩阵的LU分解和批量求逆算法在GPU上实现及优化方法.针对批量LU分解问题,分析Left-looking和Right-looking等常用LU分解块算法在GPU上实现时对全局内存的数据读写次数,针对GPU架构特点,选择具有较少访存数据量的Left-looking块算法.在LU分解的选主元过程,采用适合GPU架构的并行二叉树搜索算法.此外,为了降低选主元引起的行交换过程对算法性能的影响,提出Warp分组行交换和行交换延迟2个优化技术.针对LU分解后的批量求逆问题,分析矩阵求逆过程中修正方法,为了减少修正过程对全局内存的访问,在批量求逆的GPU实现中采用延迟修正的矩阵求逆块算法.同时,为了加快数据读写速度,采用更多利用寄存器和共享内存的优化方法和减少访存数据量的列交换优化方法.另外,为了避免线程的闲置和共享内存等GPU资源浪费,提出运行时动态GPU资源分配方法,相较于一次性分配的静资源分配方法性能得到明显提升.最终,在TITAN V GPU上,对10000个规模在33–190之间的随机矩阵进行测试,测试的数据类型为单精度复数、双精度复数、单精度实数和双精度实数.所实现的批量LU分解算法的浮点计算性能分别可达到约2 TFLOPS、1.2 TFLOPS、1 TFLOPS、0.67 TFLOPS,与CUBLAS中的实现相比加速比最高分别达到了约9×、8×、12×、13×,与MAGMA中的实现相比加速比分别达到了约1.2×–2.5×、1.2×–3.2×、1.1×–3×、1.1×–2.7×.批量求逆算法的浮点计算性能分别可达到约4 TFLOPS、2 TFLOPS、2.2 TFLOPS、1.2 TFLOPS,与CUBLAS中的实现相比加速比最高分别达到了约5×、4×、7×、7×,与MAGMA中的实现相比加速比分别达到了约2×–3×、2×–3×、2.8×–3.4×、1.6×–2×.     

LU分解和Laplace算法在GPU上的实现

随着图形处理器(GPU)性能的大幅度提升以及可编程性的发展,已经有许多算法成功地移植到GPU上.LU分解和Laplace算法是科学计算的核心,但计算量往往很大,由此提出了一种在GPU上加速计算的方法.使用Nvidia公司的统一计算设备架构(CUDA)编程模型实现这两个算法,通过对CPU与GPU进行任务划分,同时利用GP...     

结合GPU技术的并行CP张量分解算法

随着高维数据的涌现,张量和张量分解方法在数据分析领域中受到了广泛关注。然而,张量数据的高维度和稀疏特性,导致算法的复杂度较高, 阻碍了张量分解算法在实际中的应用。许多学者通过引入并行计算来提升张量分解算法的计算效率。在现有研究的基础上,给出一种简化计算Khatri-Rao乘积的GPU并行CP张量分解算法,称为ParSCP-ALS。在模拟数据集和真实数据集上的实验结果显示, 相比现有并行算法,文中设计的ParSCP-ALS算法能有效提高CP张量分解的计算效率,其中在Movielens数据集上 的计算时间减少了约58%。     

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

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

使用GPU加速计算矩阵的Cholesky分解

针对大型实对称正定矩阵的Cholesky分解问题,给出其在图形处理器(GPU)上的具体实现。详细分析了Volkov计算Cholesky分解的混合并行算法,并在此基础上依据自身计算机的CPU以及GPU的计算性能,给出一种更为合理的三阶段混合调度方案,进一步减少CPU的空闲时间以及避免GPU空闲情况的出现。数值实验表明,当矩阵阶数超过7000时,新的混合调度算法相比标准的MKL算法获得了超过5倍的加速比,同时对比原Volkov混合算法获得了显著的性能提升。     

带状稀疏矩阵乘法及高效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算子的加速。在实际应...     

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

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

基于GPU的高效图像协方差矩阵算法与实现

为提高图像处理领域协方差矩阵的计算效率,满足其在实时要求下的应用,借助GPU通用计算技术,结合CUDA编程模型,对协方差矩阵的计算进行有针对性的并行化优化,设计并实现一种高效的并行图像协方差矩阵算法。为在通用PC平台上使用协方差矩阵并满足实时性需求的各种图像处理应用提供了一个可行的解决方法,对其它领域涉及到协方差矩阵的实时计算也有良好的借鉴作用。与原有的CPU实现方法相比,GPU的效率有了平均数千倍的提升。     

GPU上的kD-tree雷达模拟加速

为了加速对雷达系统的计算机仿真模拟,提出一种基于kD-tree的GPU并行加速算法.采用CUDA实现了多种kD-tree的并行遍历算法,并对这些遍历算法性能进行比较分析,从中筛选出了最适合在GPU上进行雷达模拟加速的Shortstack-kD算法.实验结果表明,Shortstack-kD算法不仅对不同种类的场景都能带来明显的效率提升,还可以根据场景的不同情况控制Shortstack-kD的栈长度,以达到算法的最高性能和最大灵活性;在CPU上进行建树的过程中还针对雷达模拟的应用需求进行了优化.     

神经网络前向传播在GPU上的实现

基于CUDA架构在GPU上实现了神经网络前向传播算法,该算法利用神经网络各层内神经元计算的并行性,每层使用一个Kernel函数来并行计算该层神经元的值,每个Kernel函数都根据神经网络的特性和CUDA架构的特点进行优化。实验表明,该算法比普通的CPU上的算法快了约7倍。研究结果对于提高神经网络的运算速度以及CUDA的适用场合都有参考价值。     

模板操作在GPU上的实现与优化

随着GPU的快速发展,使用GPU来加速科学计算应用已成为必然趋势。本文抽取了SPEC2000中富含模板操作的Mgrid的两个典型子程序Rprj3和Interp,使用Brook+语言把它们移植到AMD GPU上运行。采用Brook+语言提供的线程调节机制,我们实现了不同线程粒度下的程序版本,并分析了加速比不同的原因,总结了线程粒度调节对模板程序移植的指导意义。我们使用AMD RadeonHD4870 GPU作为实验平台,对比Intel Xeon E5405 CPU上的运行结果发现,在最大规模下,Rprj3获得的相对于CPU版本的加速比为5.37×,Interp获得的相对于CPU版本的加速比为12.8×。     

多体问题在GPU上实现的讨论

多体问题(N-body)是力学的基本问题之一,研究N个质点互相作用的运动规律。结合分子动力学计算模拟软件LAMMPS和天体多体物理模拟软件Gadget-2这两个有广泛应用的多体并行计算软件,分析其基本算法和实现,讨论这两个有代表性的并行计算软件在GPU等加速部件上移植的基本思路。     

语音信号稀疏分解的FOA实现

信号的稀疏表示在信号处理的许多方面有着重要的应用,但稀疏分解计算量十分巨大,难以产业化应用。利用果蝇优化算法实现快速寻找匹配追踪（MP）过程每一步的最优原子,大大提高了语音信号稀疏分解的速度,算法的有效性为实验结果所证实。     

一种在GPU上高精度大型矩阵快速运算的实现

设计了一种在图形处理器(GPU)上完成大型矩阵快速运算的方法,主要通过使用Kahan求和公式来确保计算精度,根据GPU特点设计矩阵分块方式和内存分配机制来减少对数据访问频次,以发挥GPU的并行体系结构特性来提高计算速度。实验结果表明此方法能够取得较好的效果,可大大提升大型矩阵乘法的运算速度和精度。