一种具有重排通信的数据分布策略摘要：主要讨论了一种适用于分布和共享内存的循环级的数据分布策略。该方法支持由数据重排而引起的通信。关键词：高性能并行计算机；自动并行编译；数据分布；计算划分：TP314文献标志码：A：1001－3695(2007)07－0019－03并行处理的思想几乎是随着计算机的诞生而诞生的。并行处理技术一直是人们提高计算能力的一个重要手段。在应用并行计算机时，人们总是希望有一个具有自动并行化功能的并行编译系统[1]来自动发掘程序中的并行性，从而使串行程序能自动转换为并行程序。并行程序编译器是一个可以将串行程序自动转换为等价并行程序的编译器，然后再由并行语言的系统编译器将转换出来的并行程序编译为机器码在并行机器上予以执行。虽然并行化编译技术有一定的局限性，但它仍然是并行计算机系统中最重要的程序开发工具之一。提高并行化编译方法对充分利用并行机资源和提高并行机效率起着十分重要的作用。基于共享内存的自动并行编译技术已经比较成熟；基于分布内存的并行编译技术由于数据划分问题还存在着很多困难。本文重点针对分布内存体系结构中的数据分布及优化技术进行了讨论。??在分布存储模式下，对单一循环的最大限度并行化和本地化[2]的技术已经比较成熟，而如何对多循环进行最优的并行化和本地化则是一个需要解决的问题。Kennedy和Kremer表明寻找最佳的数据分布模式的问题是NP完全问题[3]，但研究者针对特定的程序模式提出了许多数据分布方案。对于高性能并行计算机而言，如何找到一种好的计算和数据划分，对数据和计算进行合理划分，增强数据本地化，减少处理器间的通信是提高其并行性能的关键。但在数据划分过程中，重排通信有时不可避免，如何进行合理的数据和计算划分以减少通信并最大限度地利用程序的并行性，是并行编译中的一个重要问题。??1具有完全一致数据分布的数据和计算的划分方法??在分布存储的机器上，循环级并行的并行性是通过循环嵌套迭代空间的分解来实现的。过程内一致性数据分布是指在整个过程中数组的分布方式唯一，即无数据重排。??在过程内求解具有一致性数据分布的数据和计算划分[4]过程中，首先要定义三个向量空间，即循环迭代空间L、数组下标空间A、处理器空间P；然后基于以上三个向量空间建立一组满足分解条件的仿射关系方程式；最后通过解方程来找到满足条件的数据划分和计算分解。有解则存在具有过程内完全一致的数据分布，使得程序能够并行执行；无解则程序只能串行执行。??在上述三个定义中，将计算和数据划分的线性部分用线性矩阵C、D表示，划分的偏移部分用常向量δ、γ表示。??若数组元素和循环迭代满足上述方程[5]关系，则这种划分是一种无重组无流水通信的划分，这种分解称为线性分解。数据分布方式是一种过程内具有完全一致数据分布的数据划分。这种分解方法是本文进一步分析具有数据重排的数据和计算划分方法的基础。??2具有数据重排的数据和计算划分方法??数据和计算分解算法[6]是以中粒度循环级并行为基础进行的。在对程序进行分析时，首先要分析过程内的数组是否存在一致性划分，即数组在过程内有唯一分布且不存在数组重排通信。数据一致性分解虽然可以最大限度地减少由重排引起的通信，但由于很多程序中数组找不到一致性分布方式，不能并行执行，并行效率低，使用的程序范围很小，实际应用中价值小。能不能设计一种算法综合考虑通信开销和并行效率两方面因素，在进行数据和计算分解时允许存在一定的数据重排通信，即数组在过程内可以有多种分布方式。程序执行时，当分布方式发生变化，数组则进行一次重排通信，即在算法实现中综合考虑通信开销与并行度之间的关系，使得算法所处理的程序能在有一定通信开销的情况下并行执行，从而使能处理的程序范围增加。??允许数据重排的划分方法是指数据的分布方式在各个循环嵌套之间是可变的，重排划分实现的基础是数据一致性分解算法。在允许重排的划分中，首先将根据数组和循环嵌套之间的关系建立通信图。通信图中的顶点向量表示循环嵌套；边表示两个循环嵌套之间是否有数组可达。有数据可达则存在一条边；否则不存在边。边的权值为数组可达的通信开销。??2...