《一种具有重排通信的数据分布策略.doc》由会员分享,可在线阅读,更多相关《一种具有重排通信的数据分布策略.doc(6页珍藏版)》请在三一文库上搜索。
1、一种具有重排通信的数据分布策略并行处理的思想几乎是随着计算机的诞生而诞生的。并行处理技术一直是人们提高计算能力的一个重要手段。在应用并行计算机时,人们总是希望有一个具有自动并行化功能的并行编译系统1来自动发掘程序中的并行性,从而使串行程序能自动转换为并行程序。并行程序编译器是一个可以将串行程序自动转换为等价并行程序的编译器,然后再由并行语言的系统编译器将转换出来的并行程序编译为机器码在并行机器上予以执行。虽然并行化编译技术有一定的局限性,但它仍然是并行计算机系统中最重要的程序开发工具之一。提高并行化编译方法对充分利用并行机资源和提高并行机效率起着十分重要的作用。基于共享内存的自动并行编译技术已
2、经比较成熟;基于分布内存的并行编译技术由于数据划分问题还存在着很多困难。本文重点针对分布内存体系结构中的数据分布及优化技术进行了讨论。 在分布存储模式下,对单一循环的最大限度并行化和本地化2的技术已经比较成熟,而如何对多循环进行最优的并行化和本地化则是一个需要解决的问题。Kennedy和Kremer表明寻找最佳的数据分布模式的问题是NP完全问题3,但研究者针对特定的程序模式提出了许多数据分布方案。对于高性能并行计算机而言,如何找到一种好的计算和数据划分,对数据和计算进行合理划分,增强数据本地化,减少处理器间的通信是提高其并行性能的关键。但在数据划分过程中,重排通信有时不可避免,如何进行合理的数
3、据和计算划分以减少通信并最大限度地利用程序的并行性,是并行编译中的一个重要问题。 1具有完全一致数据分布的数据和计算的划分方法 在分布存储的机器上,循环级并行的并行性是通过循环嵌套迭代空间的分解来实现的。过程内一致性数据分布是指在整个过程中数组的分布方式唯一,即无数据重排。 在过程内求解具有一致性数据分布的数据和计算划分4过程中,首先要定义三个向量空间,即循环迭代空间L、数组下标空间A、处理器空间P;然后基于以上三个向量空间建立一组满足分解条件的仿射关系方程式;最后通过解方程来找到满足条件的数据划分和计算分解。有解则存在具有过程内完全一致的数据分布,使得程序能够并行执行;无解则程序只能串行执行
4、。 在上述三个定义中,将计算和数据划分的线性部分用线性矩阵C、D表示,划分的偏移部分用常向量 、表示。 若数组元素和循环迭代满足上述方程5关系,则这种划分是一种无重组无流水通信的划分,这种分解称为线性分解。数据分布方式是一种过程内具有完全一致数据分布的数据划分。这种分解方法是本文进一步分析具有数据重排的数据和计算划分方法的基础。 2具有数据重排的数据和计算划分方法 数据和计算分解算法6是以中粒度循环级并行为基础进行的。在对程序进行分析时,首先要分析过程内的数组是否存在一致性划分,即数组在过程内有唯一分布且不存在数组重排通信。数据一致性分解虽然可以最大限度地减少由重排引起的通信,但由于很多程序中
5、数组找不到一致性分布方式,不能并行执行,并行效率低,使用的程序范围很小,实际应用中价值小。能不能设计一种算法综合考虑通信开销和并行效率两方面因素,在进行数据和计算分解时允许存在一定的数据重排通信,即数组在过程内可以有多种分布方式。程序执行时,当分布方式发生变化,数组则进行一次重排通信,即在算法实现中综合考虑通信开销与并行度之间的关系,使得算法所处理的程序能在有一定通信开销的情况下并行执行,从而使能处理的程序范围增加。 允许数据重排的划分方法是指数据的分布方式在各个循环嵌套之间是可变的,重排划分实现的基础是数据一致性分解算法。在允许重排的划分中,首先将根据数组和循环嵌套之间的关系建立通信图。通信
6、图中的顶点向量表示循环嵌套;边表示两个循环嵌套之间是否有数组可达。有数据可达则存在一条边;否则不存在边。边的权值为数组可达的通信开销。 21通信图G(V,E)的建立 图G的顶点集V:V中的任一顶点表示过程内程序具有一级或多级并行性的可并行的循环嵌套。 边集E(无向):若在循环嵌套u与循环嵌套v之间有数组可达,则在循环嵌套u与循环嵌套v之间存在一条边(u,v)(即使u、v之间存在多个数组可达,也仅用一条边表示)。边的权值w(u,v)表示数组从循环嵌套u到循环嵌套v所需的最大通信开销。计算公式为 根据例1建立的通信图如图1所示。进行允许数据重排的划分时,通信图中的顶点向量根据数据分布的变化划分为不
7、同的分解区域。在每个分解区域中数据的分布方式不变化,即具有一致性划分;在分解区域之间数据的分布方式是变化的,即存在允许数据重排的划分。 在动态划分算法中,为了便于解决问题,首先将图1所示的通信图扩充为如图2所示的完整的层次结构树型图。图中将增加顶点向量来表示最外层的串行循环,并在层次之间增加一些边将图扩充为树型结构。 22动态分解算法思想 在动态算法中,将通信图中每一个顶点作为一个分解区域,从一个顶点出发使用贪心法将此顶点所连的边中具有最大权值的边所对应的顶点向量试图合并到一个分解区域中。经计算,若数组存在一致性分解,则两个顶点属于一个分解区域,可以合并;否则,两个顶点分别属于两个不同的分解区
8、域,不能合并。由此减少这两个顶点向量所表示的循环嵌套之间发生数据重排的可能性。算法通过自底向上的顺序,使得通信尽可能发生在循环嵌套的最外层。在循环嵌套的每一层,边值按降序排列,对于每一条边(u,v),算法试图将两个顶点u、v合并到一个分解区域。每合并一个点,将重新计算数据划分的通信开销。若小于合并前,则进行合并,将u、v并入一个分解区域;否则,不进行合并,u、v分别在不同的分解区域,沿此边进行数据重排。此算法中,贪心的开始节点是由最下层的通信量最大边的叶子节点开始合并。若通信量相同,则从最下层的第一个叶子节点开始合并,先同层贪心,再由下向上。这符合本文进行并行时使并行尽可能发生在最外层的粗粒度
9、并行的思想。 对例1根据上面所讲的算法思想进行动态分解。首先根据程序建立如图1所示的通信图,根据式(2)可计算出各条边的通信量;再将图补充为完整的树型层次图(图2)。根据动态分解算法思想,从最内层的通信量最大的边的叶子节点开始使用贪心法合并。如果合并完数据分布不变,则合并成功;否则,不能合并,两个节点分别处于不同的分解区域。合并后的通信图如图3所示。节点1、21属于同一划分区,节点22与23属于另一分解区域;在两个分解区域之间进行数据重排通信。 3结束语 在自动并行编译算法中,如何最大限度地发现程序的并行性,提高串行程序并行化的效率,一直是自动并行化工作中所需解决的难点问题。本文主要阐述了在分布式存储环境的并行化编译中数据和计算的划分算法。基于该算法实现的并行化编译器能够自动对串行代码进行数据一致性和允许数据重排通信的分解,并在后端代码生成部分根据已得到的数据和计算划分来将数据和计算分到不同的处理器中执行。代码实现中的并行编译平台基础是基于斯坦福大学的SUIF7。通过对ppopp95和NAS测试程序测试,程序并行执行结果与串行执行结果一致,但并行执行效率还有待于进一步提高。
链接地址:https://www.31doc.com/p-1591954.html