GPU上稀疏矩阵向量乘积优化及最优存储格式预测方法

发布时间：2021-01-24 15:38

　　求解大型（稀疏）线性代数方程组（Ax=b）是科学计算的基础共性问题,其主要计算量是（稀疏）矩阵向量乘积（SpMV）,因此,高效计算矩阵向量乘积是提升科学计算的核心重要环节。近年来随着图形处理器（GPU）的快速发展,其多处理器和独特的物理架构适合计算密集型和高度并行的计算。GPU上SpMV的性能主要受稀疏矩阵存储格式的影响。本文利用GPU对稀疏矩阵向量乘积进行加速,并研究最优存储格式的预测。首先,基于JAD格式的排序思想,我们对ELLR格式进行了优化和改进,提出了PELLR格式。通过排序减少了SpMV的迭代次数和冗余计算,且与ELLR格式相比,PELLR格式的性能提升了 1.5倍。与其它格式对比,如CSR、BiELL等,70%测试矩阵中PELLR格式是性能占优的。此外,我们推导了公式用于计算迭代次数和矩阵行非零元素个数的扰乱程度。其次,我们提出了一种方法来预估GPU上SpMV的计算时间,通过预测的时间来判断哪种存储格式对SpMV在计算上是最优的。该方法采取了分而治之的思想,把总时间分为三部分:数据传输Tc、SpMV计算Ts和结果重排Tp,每个部分的估计分别使用了GPU的构架参数和稀疏矩阵... 

【文章来源】：东北师范大学吉林省 211工程院校 教育部直属院校

【文章页数】：65 页

【学位级别】：硕士

【文章目录】：
中文摘要
英文摘要
第一章 绪论
    1.1 研究背景
    1.2 相关研究工作
    1.3 论文安排
第二章 预备知识
    2.1 GPU硬件架构
    2.2 CUDA编程模型
第三章 GPU上稀疏矩阵向量乘积及其优化
    3.1 一般稀疏矩阵存储格式
        3.1.1 坐标格式（Coordinate,COO）
        3.1.2 压缩稀疏行格式（Compressed Sparse Row,CSR）
        3.1.3 对角线格式（Diagonal,DIA）
        3.1.4 ELL格式（Ellpack,ELL）
    3.2 优化的稀疏矩阵存储格式
        3.2.1 ELLR和ELLR-T格式
        3.2.2 齿对角线格式（Jagged Diagonals,JAD）
        3.2.3 SELL-C-σ格式
        3.2.4 BiELL和BiJAD格式（Bisection ELL/JAD, BiELL/BiJAD）
        3.2.5 混合存储格式（Hybrid Format,HYB）
    3.3 新的PELLR格式:基于行置换的ELLR格式
    3.4 数值实验
    3.5 本章小节
第四章 最优存储格式的预测方法
    4.1 测试矩阵
    4.2 稀疏矩阵向量乘的次数比较
    4.3 SpMV运算时间的预测
        4.3.1 Tc的预测
        4.3.2 Tp的预测
        4.3.3 ELL格式Ts的预测
    4.4 本章小节
参考文献
在学期间公开发表论文及著作情况
展望
致谢


【参考文献】：
期刊论文
[1]基于HYB格式稀疏矩阵与向量乘在CPU+GPU异构系统中的实现与优化[J]. 阳王东,李肯立.  计算机工程与科学. 2016(02)

博士论文
[1]基于GPU的矩阵乘法优化研究[D]. 殷建.山东大学 2015

硕士论文
[1]异构并行机上快速求解线性方程组[D]. 郑骢.中国工程物理研究院 2014
[2]基于CUDA的大规模线性稀疏方程组求解器的设计[D]. 吴长江.电子科技大学 2013



本文编号：2997501