分布式并行处理系统中节点间软流水的优化技术

《分布式并行处理系统中节点间软流水的优化技术》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、分布式并行处理系统中节点问软流水的优化技术+陈莉张兆庆乔如良冯晓兵高琳(中国科学院计算技术研究所体系结构研究室100080)摘要在分布式系统中如何发掘并行性和极小化同步、通讯的开销是一个重要的课题。全局优化的数据分布和计算分割模型的推导，都无法避免在程序的某些循环中引入数据重分布、通讯和同步。本文提出一种通过循环合并．发掘流水并行的算法．从而获得并行性．实现通讯和计算的重叠，较好地解决了重分布和大量通讯对程序性能的影响。关键诃并行编译技术；重分布，软流永；并行循环；循环台并；规范可分割循环】引言目前分布式处理系统的并行

2、编译技术还处于研究阶段，对于实际应用程序还很难获得高性能。在程序中充分发掘并行性和极小化同步、通讯的开销是需要协同考虑的两个方面。考虑全局数据分布和循环分割时，在应用程序中仍然可能存在这样一些情况：在程序中按全局优化数据分布策略，某数组采用一种数据分布方式会取得好的效果，但对某些循环而言，该数组必须采用另一种分布模式。才能并行．这种情况下处理办法一般有两种：其一是在循环体中引入同步和／或通讯：其二是采用数据重分布(remap)。数据重分布在存储、通讯上的开销非常大．每次数据重分布，通讯总量相当于被重分布的各数组的总规模

3、，通讯的次数至少是n·(n—1)，其中n是处理机的个数．且需要解决网络竞争[12]。如果重分布点出现在一个循环中，每次重分布均需要做两次，通讯开销呈数量级增长．重分布还会引入额外的存储开销，尤其当问题规模比较太的时候。[13]和[8]等各自提出了通过权衡代价，确定重分布的算法。第二种策略，在循环体中引入同步和通讯。当外层循环的迭代次数较小时，通讯的代价是可以接受的；但当同步或通讯在循环的内层，且无法实现通讯外提，而且外面每层循环的选代次数又较大时，通讯的开梢有时远远大于数据的重分布．数据分布与可选的循环分割不一致时，。

4、流水是一种解决此矛盾的优化手段．流水的可分块性，易于实现通讯的向量化．较好地实现通讯的隐藏；流水比之重分布，通讯总量会大大降低。[1]、C33和[2】讨论了通过循环交换、分块(stripmining)技术实现粗粒度流水，对降低通讯开销、提高性能的作用。粗粒度流水在[23、E4]及[5]等一些编译器中得到实现．‘在现实应用程序中，有的循环体由若干个并列循环组成，并列循环问有复杂的数据依赖，可并行的外层循环与数组分布维不一致．如果按照数组分布维对循环进行分割．会引起大量的通讯．这时采用软流水是一种优化的方法．本文，提出一种

5、对可分割的循环进行合并，用以获取流水并行的算法．在本文中，’4车工作稃刘国家863项目(863‘306一Ol一02—5)·周家自然科学基金项目(69933020)的资助·一81—我们对数据分布与可选的循环分割不一致的循环套，通过对内层并列可分割循环进行合并．得到可分割的流水循环。紧嵌的流水循环．有机会通过循环交换，大规模地降低通讯的次数，更好地隐藏通讯的开销。文中以下各节是这样组织的：第2节提出规范的可分割循环的概念，并给出其循环相容的条件、合并的条件：第3节给出了相窑的规范可分割循环合并算法的核心，即对准向量的求法；

6、第4节提出了发掘流水并行的算法。第5节通过对NAS标准测试程序包中一个程序的几种并行方案的分析比较，说明了发掘流水并行的算法对提高并行性和降低通讯开销的作用．2规范的可分割循环及其合并本文只考虑数组的规则引用。即循环中任一数组}f用的下标表达式都是循环索引变量的线性形式。循环P的分割映射中．把循环P的迭代集映射到各个处理机．先简单起见．本文只讨论对一维处理器序列的映射，和数组的一维块分布。文中．未分布数组是指被复制分布的数组。首先给出可流水循环的定义．定义1．循环L称为可流水的，如果存在分割映射o(把迭代集映射到多维处

7、理器网格)，对L的任意一个数据依赖关系S(j)6S’(j’)，有中。·(f’)一m。(f)>=0j且存在一个数据依赖关系St(i)6S：(j’)，有乱-(，’)一中“(f)>0性质1．循环L的紧嵌深度(perfectlynested)为d，其d层循环不是并行循环．一且对L的任意数据依赖关系s(i)6。s‘(f‘)．0是对应的依赖距离向量．Od>=O，则L必是可流水的。．一。该性质是显然的。我们只需对d层循环简单地进行块分割映射o，容易征明。满足定义l。定义2：循环L的紧嵌深度是d，如果存在c，O

8、c层循环是并行循环．或可流水的循环；任一个分布数组的引用点，其分布维下标必是c层循环索引变量的线性式

9、_若L中存在未分布数组B的定值语句S，则B在该定值点至少存在一个下标是c层循环索引量的线性式：，此时，我们称c为循环L的可分割层次．循环L是规范的可分割循环。规范的可分割循环的定义中，2)保证了数组的分布与循环分割一致；3)保证了