论文部分内容阅读
一直以来,处理器芯片厂商通过不断提高主频和指令级并行执行能力来提升处理器的性能。现如今这种方法受到内存带宽、指令级并行度、单线程性能、功耗等诸多因素的限制,已无法延续下去。从应用需求来看,日益复杂的科学计算、多媒体、虚拟化等多个应用领域都在呼唤更为强大的计算能力。在技术困境和应对计算能力需求的双重驱动下,多核处理器芯片作为处理器芯片厂商的应对策略,成为提升处理器性能的事实上的解决方案,这使得提升处理器性能的思路转变成为不断提高单个处理器芯片中处理核心的数目。多核处理器提供大规模线程并行执行能力,使应用本身有巨大的性能提升潜力,但这给高效率地开发高性能并行应用提出巨大挑战。另一方面,并行程序性能优化的过程一直都是以具体程序和具体计算平台架构为研究对象,收集性能数据、分析数据、寻找解决办法、修改代码实施改进及评测性能,这使得优化后的程序很难保证性能的可扩展性。而从应用角度出发,分析、归纳各个种应用中的核心计算过程,利用符合多核处理器芯片架构的并行计算模型对这些核心计算过程进行优化,得出可以被重复利用的高性能可扩展的软件库,即可以支持新应用的高效开发,也可以保证程序性能的可扩展性。在此背景下,本文以分层并行计算模型思想为指导,从应用驱动的并行程序性能优化的角度出发,首先提出了面向多核处理器芯片体系结构的并行算法设计模型,在此基础上对并行扫描算法进行分析优化,得出新的具有良好扩展性、高性能g-scan算法,之后对13种核心计算实体之一的稀疏线性代数计算实体深入研究,应用g-scan算法设计实现了新的稀疏矩阵-向量运算算法,并应用到结构工程领域中广泛使用的有限元分析软件OpenSees,大大提升了其执行效率。本文主要的工作和研究成果包括:(1)面向同构多核处理器芯片体系结构的UPMM并行计算模型本文以当前主流处理器芯片厂商推出的多核处理器芯片体系结构为研究对象,通过分析各种多核处理器芯片缓存结构及片上处理核心之间互连特征,设计出适用于多种同构多核处理器体系结构的并行算法设计模型UPMM,并详细描述其模型参数及特征。根据数值计算及科学计算应用中的基本算法逻辑单元,分析其数据访问模式;以此为依据分析UPMM模型数据访问开销。最后基于UPMM模型及数据访问开销分析结论对矩阵乘运算的并行算法进行详细的性能及缓存开销的研究。实验证明,利用UPMM模型能较为准确地分析并行算法的性能及缓存访问开销。(2)可扩展多核处理器模拟器针对目前难以通过较少核心数目的多核处理器芯片来推断较多处理核心数目芯片的应用程序性能瓶颈和性能需求的问题,本文基于SimpleScalar用户态模拟器工具,利用SystemC设计并实现了配置灵活、可扩展的多核处理器芯片模拟器。通过功能性实验证明该模拟器能够实现多个模拟核并发执行指令的设计目标;通过与实际采用多核处理器芯片架构的计算机对比,证实本文设计实现的多核模拟器能够较为准确地模拟多核处理器多线程并发执行的特点;通过模拟器性能实验证明该模拟器比sim-outorder在指令执行上更加高效;通过测试cachemisses实验,证明了UPMM模型在对并行算法性能分析时的准确性。(3)研究基于UPMM模型基础并行算法本文对广泛应用于排序、最小生成树、稀疏矩阵-向量运算等问题的并行扫描算法开展深入研究,对其在PRAM模型和UPMM模型上的计算复杂度进行分析比较,改进原有算法的数据访问顺序,充分发掘数据的时间和空间局域性,并设计出基于UPMM模型新的扫描算法,即g-scan算法;通过对13种计算实体之一的稀疏矩阵-向量运算算法的研究,应用g-scan算法,设计实现了适用于多种体系结构的稀疏矩阵-向量运算算法。多核模拟器的仿真实验和实际多核处理器计算机的真实实验,证明了新算法具有较高的性能和较好的可扩展性。该研究成果为实际应用如有限元分析、分子动力学分析等提供高性能的基础运算例程。(4)并行有限元分析软件OpenSeesSP的性能优化本文以广泛应用于结构工程领域中的开源有限元软件OpenSees的并行版本OpenSeesSP为研究对象,通过详细分析其性能,发现该程序三个性能瓶颈分别是求解线性/非线性方程组时的分解矩阵算法、进程间通信及求解线性/非线性方程组时的矩阵-向量运算算法。设计基于行优先的并行矩阵UTDU算法,在单节点使用多线程进行矩阵分解,大大提高计算节点的计算效率;通过利用MPI2中对于多线程通信的支持,使用OpenMP多线程多进程同时通信,提高进程间通信效率,有效缓解通信性能瓶颈。通过利用新设计的稀疏矩阵-向量计算算法,大大加快线性/非线性方程组求解过程。在实际高性能多核集群计算平台中测试了上述性能优化方案,实验结果表明对OpenSeesSP的性能优化非常显著。