稀疏矩阵向量乘及自动调优

论文摘要

在数值分析领域中,稀疏矩阵是阵内元素大部分为零的矩阵。大规模稀疏矩阵广泛出现在科学计算以及工程领域中,用于大规模线性求解系统和求解矩阵特征值等问题。稀疏矩阵在很多科学问题的物理过程离散求解中都有着重要的作用,如在有限元分析中利用稀疏矩阵来表示元素之间的相互作用,在图论中利用稀疏矩阵来描述图并通过稀疏矩阵的运算来实现图的变换,流体力学偏微分方程的求解等等。目前,针对稀疏矩阵的研究已经渗入到很多领域,在结构分析、网络理论、电力分配系统、化学工程、摄影测绘学以及管理科学等方面研究中,都出现了上千阶直至几百万阶的稀疏矩阵。因此对于稀疏矩阵向量乘(SpMV)及其调优技术的研究有助于提升解决相关领域问题的运算效率,有着巨大的研究价值与意义。本文在大量阅读国内外相关研究文献的基础上,研究并实现了稀疏矩阵向量乘运算的相关优化技术与方法,给出了一种基于主成分分析法的优化技术自动调优算法,进而提出并开发了一种整合现有优化技术的数学库COSC。在以上工作的基础上,本文创新性地提出一种基于四叉树的稀疏矩阵存储方式,利用递归进行分解重排,保证在该存储格式下的稀疏矩阵向量乘运算拥有较高的Cache命中率,从而提升运算的整体性能。进一步的,本文给出了基于四叉树的稀疏矩阵向量乘优化技术的性能分析与优化原则。本文的主要工作总结如下：(1)查阅并研究国内外现有优化技术,从面向计算体系结构的优化方面入手,论述、总结并归纳了在该方向上的四类基本策略及现有优化技术的优势与不足,从而为本文的研究提供了基本的研究方向。(2)阐述和介绍了基于CSR格式的稀疏矩阵向量乘优化与自动调优。该部分通过编码实现与优化,给出了一种基于训练集与主成分分析法的自动调优策略SCS,并基于此提出一种可整合优化策略的数学库COSC。实验表明SCS的有效性,结合COSC,可以为以稀疏矩阵向量乘运算为计算热点的相关问题在解决效率上带来显著的改进。(3)提出一种基于四叉树的稀疏矩阵存储方式。该存储方式通过递归进行分解重排,保证了进行稀疏矩阵向量乘运算时的高Cache命中率,从而带来性能上的提升。基于该存储方式,本文亦提出了其上相关的优化技术,进而分析了各优化技术的性能影响。实验证明基于四叉树存储结构的稀疏矩阵在矩阵乘法中具有较高的性能,其结构利于计算并行化并具较高的数据局部性。在深腾7000高性能计算集群上的实验表明基于四叉树存储结构的矩阵向量乘较MKL的实现能获得平均63%的性能提升。(4)对本文的上述方面研究作了总结性的概括,给出了本课题今后的研究方向,展望并提出下一步工作。

论文目录

• 摘要
• ABSTRACT
• 第一章 绪论
• 1.1 课题相关背景与研究意义
• 1.2 课题相关领域国内外的发展现状
• 1.3 论文的主要工作
• 第二章 稀疏矩阵向量乘及其优化技术
• 2.1 面向算法时间复杂度的改进
• 2.2 面向计算机体系结构的改进
• 2.2.1 数据结构改进
• 2.2.2 底层优化
• 2.2.3 并行优化
• 2.2.4 自动调优
• 2.3 本章小结
• 第三章 基于CSR格式的稀疏矩阵向量乘优化及自动调优
• 3.1 优化技术
• 3.1.1 底层优化
• 3.1.2 工作集优化
• 3.1.3 并行优化
• 3.2 自动调优技术
• 3.2.1 动机
• 3.2.2 预处理
• 3.2.3 算法核心
• 3.3 实验结果与分析
• 3.4 本章小结
• 第四章 基于四叉树的稀疏矩阵存储方式及矩阵乘优化
• 4.1 基于四叉树的稀疏矩阵存储格式
• 4.1.1 稀疏矩阵的递归分解和逻辑描述
• 4.1.2 四叉树存储格式的实现
• 4.2 基于四叉树存储格式的乘算法
• 4.2.1 矩阵向量乘
• 4.2.2 矩阵间乘法
• 4.3 存储格式效率分析
• 4.3.1 目标区域长度d对效率的影响
• 4.3.2 矩阵性质对效率的影响
• 4.4 性能优化与并行
• 4.4.1 SIMDization
• 4.4.2 线程级优化
• 4.4.3 分布式并行
• 4.5 实验
• 4.5.1 实验平台及数据
• 4.5.2 实验结果与分析
• 4.6 本章小结
• 第五章 总结与展望
• 5.1 工作总结
• 5.2 下一步展望
• 致谢
• 参考文献
• 附录
• 详细摘要