论文部分内容阅读
当今世界上主流的高性能计算机系统大多提供了丰富的并行机制,其中分布存储结构、共享存储结构及SIMD短向量功能部件等可支持不同级别的并行程序运行,如何在并行化编译系统中自动发掘应用程序中蕴含的不同层次、不同粒度的并行性已成为提高高性能计算机系统应用性能的一项关键技术。在分布存储结构下,每个计算节点都拥有着独立的存储空间,节点之间需要明确的消息传递完成数据的交换。这意味着,面向分布存储的并行化编译需要准确给出程序中的计算划分与数据分布,使得并行计算中各计算节点尽量引用本地数据,以获得最大的数据局部性和并行性。而由于计算节点访问本地存储器的速度远远快于通过网络访问异地存储器的速度,所以通信代码的效率直接影响到程序的并行性能。为此面向分布存储的并行化编译还需要生成正确、高效通信代码来维护数据的一致性。本文以并行化编译器SW-VEC的研发为背景,系统深入地探讨了面向分布存储并行化编译中数据分布和代码生成的若干问题,研究的主要内容和贡献包括:1、面向数据分布的数组数据流分析。传统数组数据流分析方法主要针对精确依赖测试、数组私有化等问题进行研究,无法为数据分布算法提供数组在循环间详细的定义-引用信息,从而影响了数据分布方案的优化选择。针对该问题提出了面向数据分布的数组数据流分析算法,通过引入定义-引用图描述数组元素在循环间的数据流向,为实施数据分布算法中优化方案的选择提供了详细的数据流信息。测试结果表明所提出的算法,能够有效提高数据分布算法的并行收益评估精度,减少生成代码中的通信冗余;2、面向分布存储的仿射分解。现有的仿射分解为了兼顾共享存储和分布存储两种结构的并行,存在划分约束过紧的问题,限制了自动并行化过程中对存在反依赖和输出依赖代码的并行性挖掘。针对该问题,本文通过分布存储结构下内存私有的特点建立划分约束条件,以此对仿射分解进行了改进,消除了其在分布存储结构下反依赖和输出依赖的冗余约束限制,提升了并行化编译对并行性的挖掘能力;3、数据分解中的数组生命期。现有的数据分布研究未考虑数组生命期对数据分解结果的影响问题,导致数据分解在数组的不同生命期中不一致时会产生冗余通信,还会影响代价评估模型对并行收益的判断,减少数据分解的选择。为解决上述问题,提出了一种基于数组生命期的数据分解算法,使用分解映射表为数组不同的生命期建立各自的数据分解版本,消除了数据分解在不同生命期之间的无效关联,有效减少了分解中数据重分布的次数以及由重分布产生的通信开销;4、基于主导值的数据分解优化。数据迁移代价最昂贵数组的分布好坏直接决定了数据分解结果的优劣。提出了基于主导值的数据分解优化算法,将数组可能引起的通信代价量化为主导值以指导分解的先后次序,优先为主导值大的数组寻找数据分布方案,并通过推后其它数组的划分以减少其对主导数组分布的约束,有效降低了主导数组重分布所产生的大量冗余通信;5、精确通信代码的生成与优化。传统的代码生成研究主要通过将每个需要重映射的数据都同步到所有处理器来完成通信,会带来大量随着处理器数目的增长而递增的通信冗余。针对该问题,提出了一种精确的通信代码生成算法,按照数组重分布前后的数据分解对局部数据空间的划分来求解每个数据重映射的源处理器和目的处理器,以产生精确的通信代码。实验结果表明,该算法能够有效消除数组重分布的通信冗余,提升自动生成并行程序的执行性能。6、不规则问题的数据分布和代码生成。许多大规模计算程序包含了不规则循环,但在面向分布存储的自动并行化中,以往的研究较难在编译时划分不规则问题的数据,无法生成有效的通信代码。针对一类包含仿射可并行循环层的不规则问题提出了一种数据分布和代码生成方法,通过仿射计算分解和数组引用的访问表达式来分配不规则数组访问的数据到各处理器,并通过冗余复制技术来满足不规则数组的生产者-消费者关系,生成有效的计算和通信代码。实验结果验证了该方法的有效性,并对测试用例取得了预期的加速比。本文提出的优化技术已在课题组研制的SW-VEC系统中得到了实现和应用,验证了以上算法的正确性和有效性。