论文部分内容阅读
稀疏矩阵向量乘(Sparse Matrix-Vector Multiplication,SpMV)是高性能计算应用中常见的算法之一。因为稀疏矩阵中非零元排布不规则,SpMV算法的高效实现十分困难,通常需要针对不同高性能并行计算平台进行优化。新型众核体系结构拥有更强的处理能力和更高的访存带宽,是当前高性能处理器发展的重要趋势,针对新型众核体系结构研究SpMV的高效设计实现对于高性能计算应用具有重要意义。本文首先系统地评估了SpMV并行算法在Intel Knights Landing(KNL)和基于ARM v8的FT-2000Plus(FTP)两款新型众核平台上的性能,深入分析了体系结构特征、稀疏矩阵存储格式和矩阵数据集对算法性能的影响。由于矩阵存储格式选择依赖专家经验,且不具有体系结构、数据集的普适性。本文采用基于机器学习方法构建稀疏矩阵格式选择模型,实现了针对不同体系结构和数据集的自适应格式选择。在此基础上,进一步提出一种面向新型众核体系结构的混合存储格式,旨在博取原生存储格式之所长。主要工作如下:(1)首次系统全面深入评估了稀疏矩阵存储格式在KNL和FTP众核体系结构处理器上的性能表现。实验涉及956个稀疏矩阵数据集和5种主流稀疏存储格式,研究了两种体系结构上,NUMA绑定、向量化以及稀疏矩阵结构特征等因素对SpMV性能的影响,对比了SpMV算法在两个平台上的性能。结果表明高效的稀疏矩阵存储格式与处理器架构和输入矩阵结构特征密切相关。(2)采用决策树训练矩阵格式预测模型,帮助程序员选择最佳矩阵格式。该模型使用矩阵结构特征和最佳矩阵格式标签作为训练数据集进行离线训练,可用于预测任何输入矩阵的最佳存储格式。使用决策树分析了预测模型内部运行过程,对比了多种机器学习建模方法的预测效果。实验结果表明,本文的模型在KNL和FTP平台上分别能够取得最优性能的95%和91%,而且在运行SpMV程序时不引入预处理开销。(3)提出了一种混合稀疏矩阵存储格式HYB5,并设计了相应SpMV算法。该格式基于SELL-C-σ和CSR5对计算矩阵进行分割,将计算规则部分用SELL-C-σ格式表示而将不规则部分用CSR5格式表示。在KNL平台上的实验结果表明,HYB5的性能优于原生格式SELL-C-σ和CSR5,加速比分别达到58倍和1.62倍。