面向P量级系统计算节点层次存储架构和并行粒度优化的多级循环分块方法研究

In the domestic high-performance computing system, how to take full advantage of hierarchical cache memory of computing node to relieve the “memory wall” problem and efficiently develop program parallelism has become one of the key issues for current PetaFlops computing. The nested loop structure, as the hotspot of programs and basic algorithms in scientific computing and engineering applications, is the most available part which can exploit program locality and parallelism. Loop tiling is a useful optimization scheme to improve memory access efficiency and parallel granularity for programs with nested loops. The loop tiling technologies are going to be studied in this project from four aspects for exposing/exploiting parallelism and data locality as follows: ①parameterized multi-level loop tiling method for arbitrary nested loops; ②adaptive parallel granularity optimizing strategy for tiling task; ③optimal tile size selection model based on neural network; ④automatic source-to-source tiled code generation system and its formalization. The research achievement can be directly applied to domestic PetaFlops high-performance computing systems for improving hierarchical cache memory access efficiency and exploiting the maximal parallelism performance of computing nodes. It will promote parallel program development efficiency for scientific computations and engineering applications as well. The research of this project can also provide theory and practice foundation of program optimization for coming ExaFlops computing.

在高性能计算机系统中，如何充分利用计算节点层次Cache存储架构性能改善“访存墙”问题以及高效开发应用程序并行性成为目前P量级计算系统面临的关键科学问题。在科学计算与工程应用中，嵌套循环结构作为应用程序和基础算法的热点，是最能利用程序局部性、开发并行性的部分。为提高访存效率，优化程序可并行粒度，研究基于带嵌套循环应用程序的优化方案，从四个层面开展提高数据局部性和并行性的循环分块方法的研究：①面向任意嵌套循环的参数化多级分块方法；②自适应的分块任务并行粒度优化策略；③基于神经网络的最优分块因子预测模型；④源到源转换的自动分块并行代码生成系统及其形式化描述。研究成果可直接应用于国产P量级高性能计算机系统，挖掘层次Cache存储系统的访存效率，发挥计算节点的极限并行性能，提高科学计算和工程应用中的并行程序开发效率，并为应对未来E量级计算系统的程序优化奠定良好的理论和应用基础。

充分利用计算节点层次Cache存储架构特点改善高性能计算的“访存墙”问题以及开发应用程序并行性是目前P量级计算系统面临的关键科学问题。在科学计算与工程应用中，嵌套循环结构作为应用程序和基础算法的热点，是最能利用程序局部性、开发并行性的部分。课题组为了提高片上访存效率、优化程序可并行粒度，深入研究了循环分块方法及相关优化技术。研究了基于多面体模型的循环分块方法，从理论上给出循环变换的形式化描述，对基本测试集采用循环分块优化后，并行代码性能可以实现1.5-20倍的加速比。研究了访存相关的局部性理论和优化方法，基于对访存地址的统计，提出了一个判断循环分块收益的模型；同时，通过建立多核架构下多作业并行执行时的共享cache失效模型，提出了一种基于共享cache局部性的作业调度策略，能有效降低多作业运行时的cache失效率，使并行效率提升近30%。研究了循环分块中的最优分块因子选择(TSS)算法，提出了一种基于cache均匀映射的TSS算法，相对目前最先进的算法能提高平均4%的性能；同时提出了一种基于神经网络的TSS预测模型，预测的分块因子相对目前最先进的一种静态分析模型和一种ANN模型可以分别提高平均7%和9%的性能。研究了DOACROSS循环的并行线程同步通信优化问题，提出了一种分块多线程的动态分配和同步机制，避免了资源浪费和线程等待，比最通用的PLuTo策略性能平均提高了32%，比POST-WAIT策略平均提高了56%。设计并实现了一个半自动化源到源并行代码转换及优化框架，首次实现了C/C++代码到Intel TBB并行代码的转换，提出了一种动态程序依赖分析方法，能有效降低分析的时空开销，同时可以提取粗粒度的代码段并行任务和DOALL循环并行任务，能在抽象语法树层上进行深度的并行代码重构；该框架还集成了课题组的部分研究成果，如循环分块方法、分块收益模型、TSS算法等，可以有效地为DOALL循环提供相应的优化策略，在任务级和循环级并行代码上分别实现了平均3.12和9.92倍加速比。课题组的研究成果能提高高性能计算机硬件性能的应用效率，为应对未来E量级计算的程序优化奠定良好的理论和应用基础。