论文部分内容阅读
近年来计算机体系结构的复杂化和计算平台的多样化,对程序优化产生了不容忽视的影响。通用编译器优化所得性能已经不能满足高性能计算的需求,开发人员越来越多地转向对程序和算法的手工优化。手工优化固然可以取得高性能,但对程序开发者的要求较高,优化工作量大,并且其程序平台通用性较差。这种情况下出现了自动调优技术,它既可以在特定的体系结构上提升程序性能,不同平台之间也表现出很好的移植性。实际应用中非规则计算作为科学计算和社会计算的核心操作之一,其性能和效率对应用起着关键作用。鉴于它的访存密集型特征,浮点性能受限于访存带宽和访存延迟,相对缓慢的内存发展使得非规则计算问题的优化和研究显得尤为重要。 本论文针对典型的非规则计算——稀疏矩阵向量乘法,使用自动调优技术进行优化,主要工作包括以下几个方面: 本文对稀疏矩阵算法的实际应用层和核心优化层进行分析,发现了两者之间的性能鸿沟,并设计了应用感知和体系结构感知兼顾的自动调优架构。该架构提取实际应用和体系结构的特征,使用学习集对特征参数进行离线提取并构建预测模型,建立统一输入接口的基于模型的自动调优架构,从而找出最优的算法及实现。 基于实际应用中稀疏矩阵的非零元素分布模式不尽相同的特点,本文从佛罗里达稀疏矩阵集中提取2000多个矩阵组成学习矩阵集,进行稀疏矩阵向量乘法的性能测试、总结非零元分布规律,从中提取有代表性的稀疏矩阵特征参数。通过对学习集进行规律总结,确定特征参数的阈值,从而构建矩阵的分类模型,建立基于该模型的稀疏矩阵向量乘法自动调优器。相对Intel的MKL数学库,在单核CPU上获得了约50%的性能提升。 为提高兼容性和增强准确度,本文引入数据挖掘技术对稀疏矩阵学习集离线建立预测模型,使用该模型进行在线预测并结合运行反馈技术,建立了平台感知和应用感知兼顾的基于数据挖掘的稀疏矩阵向量乘法自动调优器。该自动调优器增加了对体系结构特征的感知,针对特定体系结构离线选择最好的优化方法,输出最优存储格式和最优算法实现。相对MKL多线程数学库,在多核CPU上获得了平均3倍多的加速比。由于数据挖掘技术的使用,该自动调优器具有良好的平台和应用适用性及扩展性。 本文在重要的数值求解器之一——代数多重网格算法上验证自动调优器的应用适用性,算法通过调用自动调优器获得了高于20%的性能提升。在Intel的新型Xeon Phi众核处理器和GPU上,验证了其平台适用性和对第三方数学库的良好兼容性。此外,将SpMV自动调优器进行存储格式扩展,说明了调优器良好的算法扩展性。