论文部分内容阅读
人类对计算能力的需求永无止境，高性能计算水平逐渐成为世界强国竞相追逐的焦点。并行化编译作为高性能计算中不可或缺的一部分，能够识别程序中不同层次、不同粒度的并行性，并自动生成高效的并行代码。近年来，并行化技术在并行识别能力、并行编程模型、发掘方法和并行代码生成等方面均取得了丰硕的成果，但仍然存在许多亟待解决的问题。在大量基准测试集和科学计算程序并行化实践中的一个难点是：C、C++等程序的热点循环中包含指针变量时，实施并行化变换无法取得理想的加速效果。指针分析以程序分析为基础，是一项关键的数据流分析技术，其分析结果影响并行优化后程序的执行效率。本文以并行识别与自动并行化系统SW-VEC的研发为背景，系统深入的研究了支撑并行化变换的指针分析相关关键技术，以此来改进编译系统的并行化能力。 本研究主要内容包括：⑴在基于包含的指针分析技术中展开研究，对Narse优先权约束评估算法中存在的局限性进行分析，提出了一种基于指向更新的优先权指针分析技术。以指针的指向集更新信息确定约束评估的候选集，避免了冗余的约束评估。通过构建约束依赖图并以依赖关系确定约束评估的优先权，简化了优先权评估模型。在基准测试集SPEC2000/SPEC2006上的实验结果表明，该算法相比Narse优先权算法在时间开销和存储开销上具有明显的性能提升。⑵在需求驱动的指针分析技术研究的基础上，阐述了基于上下文无关语言可达的别名分析的主要思想，研究了一级流需求驱动的指针分析算法的不精确性。结合并行化的程序特征，提出了一种面向并行化的指针别名分析算法。利用基准测试集SPEC2006中的C语言测试程序用例进行实验评估，实验结果表明该算法具有较高的计算精度和良好的可伸缩性，其分析的别名信息能够显著提升OpenMP自动并行化程序的加速比。⑶基于需求驱动的数据流分析和引用点对界技术，分析了需求驱动的指针对界分析的有效性。为提高分析的精度和效率，首先进行一种指针对界预分析。在需求驱动的指针对界分析框架内，先后研究了过程内分析、处理控制流、过程间分析以及算法优化。在基准测试集和典型应用上进行了实验评估，验证了所提出的指针对界分析技术的有效性。⑷在指针范围分析相关研究的基础上，提出了一种面向数据传输优化的指针范围分析技术。首先给出了需求驱动的指针范围分析框架，定义了两种指针范围的表示形式：范围描述符域和程序范围描述符域。而后给出了计算指针范围的算法流程，分别研究了计算数据范围的转移函数以及计算控制范围的交函数和并函数，并通过扩大转换和缩小转换两种操作进行优化。最后在测试集上进行实验评估，验证了本文所提出的指针范围分析技术的有效性。⑸在反馈式编译和动态指针分析研究的基础上，设计了一种面向向量化的动态指针分析框架。首先采用快速静态指针分析提取候选别名分析集，以提升框架的可伸缩性。通过动态插桩和试运行提取指针别名信息，并反馈到向量化阶段指导向量化代码生成。从提取候选别名分析集、插桩及试运行和反馈优化对整体框架进行分析和研究。经通用测试集和典型应用程序进行实验评估，验证了该框架相比静态指针别名分析具有更精确的别名分析结果，且有效改进了向量化程序的加速比。