基于GPU的稀疏矩阵存储格式优化研究

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

基于CUDA编程模型的稀疏对角矩阵向量乘优化

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

面向定制结构的稀疏矩阵分块方法

稀疏矩阵向量乘是科学计算的核心问题,采用定制结构来加速稀疏矩阵向量乘的执行对提升科学计算性能具有重要意义。针对目前面向定制结构的稀疏矩阵分块方法和表示方法的缺点,提出了稀疏矩阵二维均匀分块方法和相应的表示方法嵌套分块CSR。实验结果表明,提出的稀疏矩阵分块方法和表示方法能够有效减少填零个数。     

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

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

稀疏三角矩阵线性系统的基于树结构并行求解

本文分析了大型稀疏矩阵线性方程组直接法求解的回代过程．基于改进的树结构（Ｍ—ｔｒｅｅ），提出了一种新的面向分布存储多机系统的稀疏三角矩阵线性系统并行Ｆｏｒｗａｒｄ求解算法ＭＰＦＳ．文中讨论了Ｍ—ｔｒｅｅ的结构特征，并将所提出的并行求解算法与基于Ｅｌｉｍｉｎａｔｉｏｎ—ｔｒｅｅ求解算法进行了分析和比较．结果表明，ＭＰＦＳ算法不仅适用于更多的稀疏矩阵系统，而且在求解过程中可以开发Ｅｌｉｍｉｎａｔｉｏｎ—ｔｒｅｅ算法不能开发的计算并行性，从而使求解性能得到显著改进．     

基于带行指针向量的链式存储结构的稀疏矩阵基本运算实现

应用稀疏矩阵压缩存储技术之带行指针向量的链式存储结构,设计基于此链式存储结构的稀疏矩阵的转置算法及相乘算法,以及这些矩阵运算基于C++类模板的具体实现,并对算法的性能进行了分析.     

基于监督学习的稀疏矩阵自动任务分配

针对稀疏矩阵与稠密向量乘运算探讨了不同的任务分配策略对性能的影响，观察到任务分配策略的选择会显著地影响稀疏矩阵的运算性能，且不存在一种固定的任务分配策略针对所有的稀疏矩阵都能获得最佳性能。为此，提出了一种基于机器学习的最优任务分配策略选择模型，其训练过程仅使用稀疏矩阵的特征来刻画输入数据集，且能够针对给定的数据集和目标平台自动地训练模型。实验结果表明，相对于默认的块分配方法，使用该模型选择的任务分配方式能够获得平均约35%的性能提升。     

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

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

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

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

     

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

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

基于GPU的稀疏线性系统的预条件共轭梯度法

研究了基于GPU的稀疏线性方程组的预条件共轭梯度法加速求解问题,并基于统一计算设备架构(CUDA)平台编制了程序,在NVIDIAGT430 GPU平台上进行了程序性能测试和分析。稀疏矩阵采用压缩稀疏行(CSR)格式压缩存储,针对预条件共轭梯度法的算法特性,研究了基于GPU的稀疏矩阵与向量相乘的性能优化、数据从CPU端传到GPU端的加速传输措施。将编制的稀疏矩阵与向量相乘的kernel函数和CUSPARSE函数库中的cusparseDcsrmv函数性能进行了对比,最优得到了2.1倍的加速效果。对于整个预条件共轭梯度法,通过自编kernel函数来实现的算法较之采用CUBLAS库和CUSPARSE库实现的算法稍具优势,与CPU端的预条件共轭梯度法相比,最优可以得到7.4倍的加速效果。     

Auto-tuned Krylov methods on cluster of graphics processing unit

Exascale computers are expected to have highly hierarchical architectures with nodes composed by multiple core processors (CPU; central processing unit) and accelerators (GPU; graphics processing unit). The different programming levels generate new difficult algorithm issues. In particular when solving extremely large linear systems, new programming paradigms of Krylov methods should be defined and evaluated with respect to modern state of the art of scientific methods. Iterative Krylov methods involve linear algebra operations such as dot product, norm, addition of vectors and sparse matrix–vector multiplication. These operations are computationally expensive for large size matrices. In this paper, we aim to focus on the best way to perform effectively these operations, in double precision, on GPU in order to make iterative Krylov methods more robust and therefore reduce the computing time. The performance of our algorithms is evaluated on several matrices arising from engineering problems. Numerical experiments illustrate the robustness and accuracy of our implementation compared to the existing libraries. We deal with different preconditioned Krylov methods: Conjugate Gradient for symmetric positive-definite matrices, and Generalized Conjugate Residual, Bi-Conjugate Gradient Conjugate Residual, transpose-free Quasi Minimal Residual, Stabilized BiConjugate Gradient and Stabilized BiConjugate Gradient (L) for the solution of sparse linear systems with non symmetric matrices. We consider and compare several sparse compressed formats, and propose a way to implement effectively Krylov methods on GPU and on multicore CPU. Finally, we give strategies to faster algorithms by auto-tuning the threading design, upon the problem characteristics and the hardware changes. As a conclusion, we propose and analyse hybrid sub-structuring methods that should pave the way to exascale hybrid methods.     

基于文件过滤驱动的移动存储控制方法

针对移动存储在内网中的安全使用问题,提出了基于文件过滤驱动的移动存储访问控制方法。该方法通过识别移动存储设备生成的多个卷和每个卷的唯一标识,并结合每个卷的访问权限,实时进行控制;通过监控进程的执行,防范和查杀卷中存储的病毒木马。该方法有效地控制了移动存储设备的使用,增强了移动存储设备使用过程中的安全性。