论文部分内容阅读
高性能计算机是现代科学研究、工程技术开发和大规模数据处理的关键支撑技术。随着高性能计算机的发展,并行计算机的体系结构越来越复杂,并行程序设计的难度也越来越大。使用先进的并行化编译技术,自动将串行程序转换为等价的能在并行计算机上高效运行的并行程序,是克服并行计算机编程困难、软件难于移植的主要手段,是充分发挥高性能并行计算机潜能的有效途径。近年来,虽然并行化编译技术取得了可喜的进步,但仍有许多问题需要深入研究。在分布存储并行计算机上开发并行化编译器,碰到的第一个问题就是如何分布一个程序中的数据。分布存储并行计算机与共享存储并行计算机相比,最大的区别就是数据分散存储在不同的处理器上。使用分布存储并行计算机时,除了要考虑计算的并行性外,还必须考虑数据的划分问题。本文以并行化编译器S-KAP的研究开发为背景,针对目前在分布存储并行计算机系统上,开发并行化编译器时的数据和计算划分问题进行了研究,探讨了串行程序并行化过程中的数据和计算的自动划分及优化技术,实现了进行数据和计算划分的两级映射模型;1、数据和计算映射到一个规模不受限的虚拟处理器;2、虚拟处理器以BLOCK、CYCLIC、BLOCK CYCLIC(b)方式映射到物理处理器。本文针对分布存储并行计算机系统,首先研究了串行程序并行化时,过程内具有一致性数据分布的数据和计算划分问题;然后讨论了虚拟处理器到物理处理器的映射方式;最后探讨了分布存储并行计算机的数据和计算划分的优化。研究的主要内容和贡献包括;1.在分析Anderson和Lam算法的基础上,提出了一种改进的数据和计算划分算法,实现了无流水和无数据重分布通信的计算和数据划分,并验证了算法的有效性。2.针对邻近通信和负载平衡问题,给出了BLOCK、CYCLIC、BLOCK CYCLIC三种映射方式的选取策略,设计并实现了虚拟处理器到物理处理器的CYCLIC映射算法。测试表明,该算法能够实现负载平衡。3.基于改进的过程内具有一致性数据分布的数据和计算划分算法,以及精确的数组数据流分析,实现了具有DOALL和DOACROSS类型并行的嵌套循环的数据和计算划分算法。4.基于改进的过程内具有一致性数据分布的数据和计算划分算法,以及用符号系数不等式表示数据划分时的BLOCK映射方式,实现了只读数组的复制和边界冗余。引入此方法是在保证原有读写数组的并行度,并且不引入额外的数据重分布通信开销的基础上,实现只读数组的优化。测试表明,边界冗余有效地减少了通信的数据量,提高了程序的并行性能。