基于分块存储格式的稀疏线性系统求解优化

针对基于GPU求解大规模稀疏线性方程组进行了研究,提出一种稀疏矩阵的分块存储格式HMEC（hybrid multiple ELL and CSR）。通过重排序优化系数矩阵的存储结构,将系数矩阵以一定的比例分块存储,采用ELL与CSR存储格式相结合的方式以适应不同的分块特征,分别使用适用于不对称矩阵的不完全LU分解预处理BICGStab法和对称正定矩阵的不完全Cholesky分解预处理共轭梯度法求解大规模稀疏线性系统。实验表明,应用HMEC格式存储稀疏矩阵并以调用GPU kernel的方式实现前述两种方法,与其他存储格式的实现方式作比较,最优可分别获得31.89%和17.50%的加速效果。     

GPU加速不完全Cholesky分解预条件共轭梯度法

不完全 Cholesky 分解预条件共轭梯度（incomplete Cholesky factorization preconditioned conjugate gradient ,ICCG）法是求解大规模稀疏对称正定线性方程组的有效方法。然而ICCG法要求在每次迭代中求解2个稀疏三角方程组,稀疏三角方程组求解固有的串行性成为了ICCG法在GPU上并行求解的瓶颈。针对稀疏三角方程组求解,给出了一种利用GPU 加速的有效方法。为了增加稀疏三角方程组求解在GPU上的多线程并行性,提出了对不完全Cholesky分解产生的稀疏三角矩阵进行分层调度（level scheduling ）的方法。为了进一步提高稀疏三角方程组求解的并行性能,提出了在分层调度前通过近似最小度（approximate minimum degree ,AMD）算法对系数矩阵进行重排序、在分层调度后对稀疏三角矩阵进行层排序的方法,降低了分层调度过程中产生的层数,优化了稀疏三角方程组求解的GPU内存访问模式。数值实验表明,与利用NVIDIA CUSPARSE实现的ICCG法相比,采用上述方法性能可以获得平均1倍以上的提升。     

微分域网格变形的GPU加速算法

微分域网格变形方法能够较好的保持网格模型的局部细节特征,但其计算需要耗费较长的时间.结合GPU的高速并行运算性能,设计并实现了一种基于GPU的微分域网格变形算法.通过GPU进行网格的微分坐标求解、线性系统系数矩阵的Cholesky分解、线性系统求解等运算,从而将网格局部细节特征编码和解码过程以及变形结果的绘制完全通过GPU完成.实验结果表明该算法能够有效加速微分域网格变形方法的计算和绘制.     

基于GPU的稀疏矩阵Cholesky分解

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

在线光束平差法的高速计算方法研究

光束平差法（bundle adjustment,BA）是同步定位和地图构建（simultaneous localization and mapping,SLAM）后端优化的关键技术。在线使用光束平差时能否满足实时性要求,是将其应用于自动驾驶车端等实时系统的关键因素。首先分析特定场景中SLAM数据特点,提出滑动窗口机制降低计算规模;分析局部BA计算中稀疏矩阵性质提升算法的可并行性;最后基于嵌入式GPU对算法进行并行加速。将其应用于车载SLAM系统并在真实场景下测试,实验结果表明,在AGX Xavier嵌入式GPU上,针对720P道路场景,该方法比同平台CPU上处理性能平均提升4.8倍,可以处理15 fps的相机位姿地图数据,满足了30 fps的视频处理需求,达到了车载系统的实时性要求。     

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

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

面向异构架构的传递闭包并行算法

传统求图传递闭包的方法存在计算量大与计算时间长的问题。为加快处理大数据量的传递闭包算法的计算速度,结合算法密集计算和开放式计算语言（OpenCL）框架的特征,采用本地存储器优化的并行子矩阵乘和分块的矩阵乘并行计算,提出一种基于OpenCL的传递闭包并行算法。利用本地存储器优化的并行子矩阵乘算法来优化计算步骤,提高图形处理器（GPU）的存储器利用率,降低数据获取延迟。通过分块矩阵乘并行计算算法实现大数据量的矩阵乘,提高GPU计算核心的利用率。数据结果表明,与CPU串行算法、基于开放多处理的并行算法和基于统一设备计算架构的并行算法相比,传递闭包并行算法在OpenCL架构下NVIDIA GeForce GTX 1070计算平台上分别获得了593.14倍、208.62倍和1.05倍的加速比。     

正定矩阵在MIMD计算机上的并行因子分解

本文研究利用多处理机的MIMD型计算机计算方型实对称正定矩阵的三角因子问题。文章从算法的加速比和效率的角度,导出并分析了当所用的处理机台数为(ⅰ)无限和(ⅱ)O(n)时,基于Cholesky分解法和Gaussian消元法的并行算法,其中n是矩阵的阶。对于第(ⅱ)种情况,它表明并行消元法能够达到与并行Cholesky方法相同的加速比,而仅需Cholesky方法所用处理机台数的一半。     

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

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

基于浮点数的Cholesky分解FPGA实现

在阵列信号抗干扰算法中,常常需要求解协方差矩阵的逆矩阵。Cholesky分解利用了协方差矩阵的厄米特（Hermitian）正定的特性,大大简化了矩阵求逆运算的计算量。论文介绍了Cholesky分解数学原理,并提出了一种适合FPGA实现的结构。基于浮点数的算法实现相比传统的定点数,大大提高了结果的精度。由于Cholesky分解需要涉及浮点数的开方运算,论文引入了平方根倒数法来提高开方运算的速度。通过仿真与实测,选取了最优的资源与速度的实现方案。