适合向量化的稀疏矩阵存储格式研究

作     者：谢佩珍 

作者单位：国防科学技术大学 

学位级别：硕士

导师姓名：徐涵

授予年度：2016年

学科分类：07[理学] 08[工学] 070104[理学-应用数学] 081201[工学-计算机系统结构] 0701[理学-数学] 0812[工学-计算机科学与技术（可授工学、理学学位）] 

主      题：稀疏矩阵向量乘 行压缩稀疏矩阵存储格式 向量化 性能优化 

摘      要：稀疏矩阵向量乘(SpMV)(y=A*x)广泛用于科学计算和工程计算中,如大规模线性代数系统的求解,粒子输运模拟,流体动力学偏微分方程的求解,天体物理学和偏微分问题等。它被归类为“七个小矮人的成员,即被认为在下一个十年最重要的数值方法之一。因此对于稀疏矩阵向量乘(SpMV)及其优化技术的研究有助于提升解决相关领域问题的运算效率,有着巨大的研究价值与意义。由于稀疏矩阵含有大量零元素,这直接导致SpMV访存的不规则性和差的浮点性能。SpMV访存的不规则性不仅使得计算平台在进行稀疏矩阵向量乘运算时很难充分使用向量单元进行加速,并且还会增加Cache未命中次数。由于稀疏矩阵自身的特点,使得稀疏矩阵向量乘运算的实现对稀疏矩阵的存储格式依赖十分严重。针对目前主流的稀疏矩阵存储格式CSR,本文提出了新的适合向量化的稀疏矩阵存储格式CSR(r),CSR(r,l1,l2),BCSR(r,l1,l2)。本文的主要工作总结如下:(1)查阅并研究国内外现有优化技术,从面向计算体系结构的优化方面入手,论述、总结并归纳了在该方向上现有优化技术的优势与不足,从而为本文的研究提供了基本的研究方向。(2)对目前主流存储格式CSR进行改进,提出了新的适合向量化的稀疏矩阵存储格式CSR(r),CSR(r,l1,l2)。与传统格式CSR相比,CSR(r)、CSR(r,l1,l2)的性能分别提高了45%,49%。(3)将CSR(r,l1,l2)向量化存储格式与块存储格式相结合,提出二维的稀疏矩阵存储格式BCSR(r,l1,l2)。与传统格式CSR相比,BCSR(r,l1,l2)的性能提高了66%。(4)对本文的上述方面研究作了总结性的概括,给出了本课题今后的研究方向,展望并提出下一步工作。