（计算机系统结构专业论文）smp机群上的并行代码优化技术.pdf

幽：型f 堂型塑型坐生旦l 一 摘要 随着多处理器和高速通讯网技术的发展，s m p 机群由于其明显的价格比和良 好的可扩展性，成为备受欢迎的高性能计算平台。这类体系结构比之传统的并行 机的一个显著特征是它们混杂的内存模型：节点内的共享和节点间的分布内存模 式。层次式的体系结构，给程序设计提出了更复杂的问题。我们相信，s m p 机群 需要一个统一的、可移植的程序设计模型。0 p e n m p 是一个发展中的共享内存编 程标准，我们设计了一个适合分布内存环境的0 p e n m p 扩展，给出了它在s m p 机群上的一个支持层次并行的编译实现，并对层次模型中的若干优化问题进行了 较为深刻和独创性的研究，取得了良好的效果。 ( 本文的主要贡献如下： 1 基于“分布0 p e n m p ”的概念，实现0 p e n m p 在s m p 机群上的扩展；研究 了其三种可能的执行模式，给出了多级并行的总体框架，讨论了层次并行 性确定的基本策略和问题。 2 s m p 机群上同样存在数据分布和计算分割确定的问题，本文提出优化通信 的冗余计算分割技术，它的基本思想是针对并行循环序列，恰当地选择每 个并行循环套的冗余计算量，消除一般计算分割技术会引入的循环套之间 的通信。 3 提出通过循环合并发掘节点间流水并行的方法。该技术与传统流水技术的 不同在于，能从复杂的循环结构中发掘流水并行。 4 在全局通信优化的框架中，实现了全局的冗余消息消除和消息合并，并加 入对冗余计算分割的支持；全局阴影区优化技术的应用，大大减少了由过 程调用引起的数据重分布。过程间通信优化，实现了规则通信的过程间冗 余合并，其优化效果显著。 5 研究了节点内的并行域合并问题，提出过程间并行域合并技术，大大增加 了节点内并行性的粒度。 6 提出一种基于静态计算分割的同步消除技术。针对引用点之间的关系提出 3 类概念：对计算分割系数一致的引用点、强分离的引用点、分离的引用 点，并分别求出其对同步消除的影响对应的无同步偏移；最后在一个 整体框架中实现了基于计算分割调整的同步消除算法；此外，还研究了过 程问同步点消除的实现。 我们认为，支持混合内存体系结构和层次并行的编译技术是一个值得研究的方 向。本文的探索性研究仅仅是个开始。3 r 1 7 7 ) 关键词：o p e n m p 、计算分割、全局阴影区优化、流水优化、并行域合并、同步 点消除、过程间优化 ! 竺! 迎堕堂丛幽型堕一 o p t i m i z a t i o n o fp a r a u e lc o d e so ns m p c l u s t e r s c h e nl i ( c o m p u t e ra r c t l i t e c t u r e ) d i r e c t e db y z h a n gz h a o q i n g c l u s t e r so fs y h u n e t r i cm u l t i p r o c e s s o r s h a v e b e e n 埘d e s p r e a d i n h i g h p e r f o m a n c ec o m p m i n g ，也ea r c h i t e c t u r eh a v em e d r 锄a t i cf b a t u r eo fh y “dm e m a r y m o d e i s ：s h a r e d m e m o r y 、“t h i nn o d e sa i l dd i s 仃i b u t e d m e m o r y 锄o n gn o d e s t h e h v b r i da r c h i t e c t u r ep u t sf o ，a r dt l l ep m b l e m o f p m 旷鲫衄i n g m o d e la 1 1 dp e r f o 哪a n c e h y b r i dp r o g r a m m i n gm o d e lm i x i n gm p i a n dm r c a d s b r i n g so u tg r e a t c rc o m p l e x i t yt o p r o g r a m m e r s ，w eb e l i e v et h a tau n i 6 e dp r o g r a m m i n gm o d e l s h o u l db ea d o p t e do n s m pc l u s t e r s i nt h i sp a p e r ，a 1 1 e x t e n s i o nt o o p e n m pi s d e v i s e dt om a t c ht h e u n d e r l y i n ga r c h i t e c t u r e ， a i l da n i m p l e m e n t a t i o n w h i c h s u p p o r t sm u l t i p l e 1 e v e l p a r a l k l i s mi sg i v e n i n d e p mr e s e a r c hi sd o r 圮o ni s s u e sp a r t i c u l a rt om i sh i e r a r c h y a r c h i t e c t u r e t h em a i nc o n t r i b u t i o n so f t h i sp a p e ra r e ： l 、 b a s e do nt h en o t i o no f “d i s 仃i b u t e do p e n m p ”，d e v i s ea no p e n m pe x t e n s i o n s u i t c dt ot h ec l u s t e ra r c h i t e c t u r e ，s e v e r a le x e e u t i o nm o d e l sa r ed i s c u s s e d ，a 目r e n e m l 丘a m e w o r ki sg i v e n ，矗m d a m e m a ls t r a t e g i e sa b o u th o wt od e t e m l i n e m u l t i p l el e v e l p a r a l l e l i s m i sd i s c u s s e d 2 ) d a t aa n dc o m p u t a t i o np a r t i t i o ni sa l s oi m p o r t 锄tf o rs m pc l u s t e r s ，ar e d u n d a n t c o m p u t a t i o np a n i t i o n i n gt e c l h l i q u e i s g i v e n t o o p t i m i z i n g i n t e r - n o d e c o m m u n i c a t i o n t h et e c l l i l i q u ef o c u so np 砌l e ll o o ps e q u e n c e s ，t l l ei d e ai st o c h o o s er e d u n d a n t c o m p u 诅廿o np r o p e r l y f b re a c h p a m l l e ll o o p ， i no r d e rt o e l i m i n a t ei n t e r - l o o pc o m m u n i c a t i o n sw h i c ha r cu s u a l l yi n t r o d u c e du s i n go r d i n a r y p a n i t i o i l i n gs t r a t e g y 3 ) an e w a p p r o a c h b a s e do n l o o pm s i o n i sp r e s e n t e dt oe x p l o i t p i p e l i l l i n gp a r a l l e l i s m 。 t h e t e c h n i q u ee x p l o i t sp i p e l i n i n g 矗o m c o m p l e xl o o p s t m c t i l r e s ，w h i c h d i s t i n g u i s h e si t s e l f 舶m 缸a d i t i o i l a lp i p e l i n i n gt e c m q u e s 4 ) i na g l o b a l c o 咖m 岫c a t i o n o p t i m i z a t i o n 矗龇n e w o r k ， r e d u n d a n t m e s s a g e e l i m i n a t i o na 1 1 d m e s s a g ec o a l e s c i n g a r er e a l i z e d t h ei n 仰d u c t i o no fg l o b a l l y s h a d o w e da r e ag r e a t l yr e d u c e s 出【协r e d i s t r i b u t i o n si n c u r r e db yp r o c e d l l r 面c a l l s t h ei n t e r p r o c e d l 砌o p t i m i 盈i t i o no fr e g u l a rc o m m 蚰i c a t i o n sf h r t h e re l i m i n a t e s r c d u n d a n tm e s s a g e s 5 ) t h eg r a i no f “i n n a - n o d e ”p 删l e l i s ma r e o f i m p o r t a n c et op r o g r 锄p e r f o r n l a l l c e ，a c o n s t m c t i o na l g o r i m mo f p a r a l l e lr e g i o n si sg i v e ni n t e r p r o c e d u r a l l 弘 6 ) an e ws y n c l l l o n i z a t i o ne l i m i n a t i o n t e c h n i q u e i s p r e s e n t e d ，b a s e d o ns t a t i c c o m p u t a t i o np a r t i t i o i l i n g t 、v o k i n d so fn o t i o n sa r ei n t r o d u c e dt od e s c r i b et h e r e l a t i o n s h i pb e t w e e nr e f e r e n c e s ，w h e r ed a t ad e p e n d e n c eo c c u r s t h en o t i o n sa r e c a l i e ds 仃o n gc o n s i s t e n t ，a i l dc o n s i s t e n tw i t hr e s p e c tt oc o m p u t a t i o n p a r t i t i o n i n g ， a b o u te a c ho fw h i c ht h ei m p a c tt os y n c h r o n i z a t i o ni sd i s c u s s e di nt h et e mo f “s y n c h r o n i z a t i o n f k e o 丑奢e t ”a n a l g o r i t l l f n i s p r e s e n t e d t o e l i m i n a t e i ! 坚! ! ! 登：! 塑茎! 型! 堕垡些垫查二_ 塑堕一 s y n c h r o n i z a t i o n ，i t i sa l s od i s c u s s e di n t e r p r o c e d u r a l l y k e y w o r d s ：s m pc l u s t e r ，0 p e 心厦p ，c o m p u t a t i o np a m t i o l l i n g ，s h a d o w e da r e a ，s o f t w 甜e p i p e l i n i n g ，p a r a l l e lr e g i o n ，s y n c h r o n i z a t i o n e l i m i n a t i o n i 声明 本人声明所呈交的论文是我个人在导师指导卜进行的研究工作及取得 的研究成果。就我所知，除了文巾特别加以标注和致谢的地方外，论文中 不包含其他人已经发表或撰写过的研究成果。与我一同t 作的同志对本研 究所做的任何贡献均已在论文中作了明确的说明并表示了射意。 作者签名：邛啬、竭 口期：孕口。碑岁目2 ，目 关于论文使用授权的说明 中国科学院计算技术研究所有权处理、保留送交论文的复印件，允许 论文被查阅和借阅；并可以公布论文的全部或部分内容，可以采用影印、 缩印或其它复制手段保存该论文。 作者签名野舀、硝 导师签名：跟牡反日期：轨用l 辱争目巧日 星二童! l 童 一 第一章引言 当前科学技术迅猛发展，仅仅凭着理论推导和真实试验这两种科学认知手段 已不能满足需要，科学计算成为进行科学研究的第三种手段。高性能计算技术在 航空航天、石油勘探和开发、大范围气象预报、核爆炸模拟、材料设计、药物设 计、基因信息学、密码学、汽车制造等领域起着重要的作用。 从历史上看，计算科学的发展可以分为串行和并行两个阶段。串行计算技术 的产生和发展是与计算机技术的发展紧密相随的，本世纪8 0 年代以前，传统的计 算技术的研究主要体现在串行计算技术上，几十年的研究带来了丰硕的成果，但 也使得当前的程序设计思想打上了串行计算的烙印。虽然从8 0 年代开始，大量的 并行处理系统涌现出来，不少已经商品化。但是在实际应用中，所得到的计算速 度常常低于系统潜在理论峰值的3 0 。 缺少合适的并行软件是阻碍主流用户社会接纳并行计算的主要原因。计算机 界的一致共识是并行编程处于令人遗憾的状态，并行软件的开发远远落后于并行 硬件的进展。 1 1 现有的并行应用程序的主要开发方法 并行软件一直落后的主要原因是并行编程比串行编程要复杂。首先串行编程 只有一个基本模型( 冯诺依曼模型) ，而并行编程却有许多不同的模型( p r a m 、 b s p 、l o g p 等) ；第二，串行程序的软件环境工具有比并行程序先进得多；最后， 与串行编程相比，并行编程在时间、经验的积累上有很大差距。 并行应用程序开发的方法主要有两种：显式并行语言和编译辅助的自动、半 自动并行化编译。 1 显式并行的方法 由于历史的原因，高性能计算系统往往采用专用的程序设计语言、或者晦涩 的库函数以发掘机器的性能。这些语言从显式高级结构描述并行性，由于语言与 现有的已经被广泛采用的过程式语言不兼容，且缺乏可移植性。难以被市场接受。 今天被广泛采用的显式并行语言有三种：消息传递环境( m p i 或p v m ) ；高性能 f o r t r a i l ( h p f ) 、s m p 程序设计标准0 p e n m p 。 消息传递 消息传递环境中存在两种广泛使用的标准库m p i 和p v m ，二者已经在所有类 型的并行机上实现，极大地增强了消息传递程序的可移植性。m p i 指定了在串行 语言上的一组命名、调用序列、子程序。m p i 强有力的地方，也就是程序员能够 完全控制程序的行为。在m p i 程序中用户必须显式地把数据和工作负载分配到各 个进程，程序是多进程和异步的，需要显式的同步以保证正确的执行顺序。消息 传递程序通常用于开发大粒度的并行性。m p i 程序的编写对于应用程序员来说， 是一项繁重的工作，程序员必须考虑程序中通信、同步、计算分割等一系列问题。 一! 竺! ：! ! 壁! 竺堑堡! ! 塑些些垫查一 这也使得很多开发者不愿意把现有的程序移植到并行机上。 m p i 中的并行性从本质上讲，并不是显式的，而只是任务数和程序员意图的 结果。这也是m p i 程序难以编写的根本原因，实际上利用m p i 这样的编程模式， 是用一种不可靠的过程来代替并行程序设计语言及并行编译器的做法，其实是程 序设计结束的倒退。m p i 是随着分布内存的机器的出现而逐步发展起来的，在共 享内存的机器上，这种方式就失去了它的优越性。 数据并行 数据并行语言h p f ( 高性能f o r t r a n ) 也是在分布内存系统开始流行的时候发 展起来的。h p f 的一个主要任务是提供一个程序设计标准，使得现有的串行代码 能很容易地移植到分布内存地机器上，同时获得可移植性、简单性和标准化。语 言扩展把高层并行结构加到f o n r a i l 、c 中。h p f 对问题的数据空间进行分割，在 不同的数据子空间上施加类似或相同的操作。h p f 把数据移动和底层相应的消息 传递从编程者的层次降到了编译器的层次，由编译器处理实际的数据移动和局部 内存到全局内存的地址转换。 h p f 并没有象它的名字那样提供很高的性能。其关键原因是对非规则问题的 解决不理想，如何适应实际应用中各种不规则和或动态的：数据结构、数据存取 模式、数据依赖模式、数据分布、任务模式、任务分配是一个挑战性的课题。【z i m a 0 1 】 指出h p f 需要更普遍的分布模型：描述索引空间到处理器空间广义映射、同时允 许子集分布、提供广义的耦合关系( a m i l i t y ) 的声明、增加动态的分布和对准、并 增加对通信的高层控制。我们也许有一天会看到h p f 3 0 。 共享存储器模型0 p e n m p 多线程编程由于使属于同一个进程的各个线程共享可用的各种资源，是最适 合s m p 体系的编程方式。基于线程的程序设计主要有三种：显式线程库的方式、 并行化制导、线程化的库。显式线程库以p t l l r e a d 为标准，是共享内存模型上的一 个低端的标准。它主要针对提供任务并行，而很少有数据并行的支持；其实，它 并不是针对高性能计算的。1 9 9 7 年提出的o p e n m p 使共享存储器模型有了一个广 为接受的标准。0 p e n m p 制导给程序员提供了一组功能强大的高层并行结构和一 个扩展的并行程序设计模型，这两者都能满足很大范围的应用需求。o p e n m p 的 优点有：可移植性好、简单、扩展性好，支持多线程，具有负载平衡的潜力，支 持同一程序中同时实现细粒度循环级、粗粒度的两种并行，孤儿制导的引入增加 了对粗粒度并行的支持。孤儿制导是指哪些在并行区域的词法范围外，而在并行 区域的动态范围内的制导。o p e n m p 的缺点是：目前只适用于基享存储的机器， 支持动态可变的线程数比较困难。 2 自动并行编译 并行化编译系统是解决并行程序开发的重要途径之一。这种系统可以把串行 程序自动或半自动地转换成并行程序。它的优点是：并行化系统可以发现程序中 的潜在并行性，将其变换为等价的并行形式；降低了程序员编程、调试的难度一 一用户不必通晓并行编程和底层的并行体系结构：并行化系统可以针对不同体系 结构进行优化，可移植性得到保证：现有的串行程序的重用变得容易。但这也使 得编译器承担了更多的工作。p a r 晒e 2 、p f c 、s u i f 、p o l 撕s 等都是国际上著 蔓二皇! ! 童 名的自动并行化编译系统。 尽管并行化编译系统有着广泛的应用前景，可是迄今为止，全自动并行化系 统还远没有达到实用的程度，特别是对于分布内存的并行处理系统，自动并行的 性能不够理想。造成这种现象的原因在于应用问题的复杂性。1 ) 由于程序分析信 息难以十分精确，程序分析只能采用保守的处理方法，程序中蕴涵的并行性不能 完全发掘；2 ) 数据的局部性分析难以精确，而数据局部性分析与计算分割是相互 影响、相互制约的，是影响并行化后程序性能的关键因素；对非规则的、动态的 程序，需要更为复杂的编译时分析和运行时支持；3 ) 通信的优化，不规则的引用 往往伴随着复杂的通信模式，通信的优化与数据的局部性优化是密切相关的问题。 并行化编译中适当地引入程序员的干预，会使并行化的效果显著提高。一种 方式是通过用户制导的加入，用户向编译器提供更多的辅助信息；另一种方式则 是交互式编译，允许并行化编译器提问，用户提供关键的分析信息，以指导并行 化过程。 1 2 层次体系结构对并行程序设计的挑战 高性能计算的市场在过去的很长时间内被大型的由单c p u 节点组成的专用 m p p 所占据。近来，随着多处理器和高速通讯网技术的发展，s m p 机群由于其明 显的价格比和良好的可扩展性，成为备受欢迎的高性能计算平台。这类体系结构 比之传统的并行机的一个显著特征是其混杂的内存模型：节点内的共享内存和节 点间的分布内存模式。 图1 1 硬件的混合内存模型 层次式的体系结构，给程序设计提出了更复杂的问题。硬件发展表现出的垂 直可扩展性和水平可扩展性，给程序设计模型提出了支持两级扩展性的要求。如 何编写移植性好的并行代码，使得运行有效且扩展性好是并行计算面临的重要问 题。在层次体系结构上什么是最佳的程序设计方式，人们正对相应的性能问题和 程序设计模型进行探讨。 根据已有的分类法【l u s k 9 5 b u g g e 9 7 】，s m p 机群上程序设计可以使用单一 的内存模型、或者是混杂的内存模型。在单一的内存模型下，一个机制保证用户 看到的是统一的内存模型。 当然可以在整个系统上使用统一的m p i 。一些m p i 的实现已经升级为机群系 统提供单一内存模型。比如m p i c h p m c u j m p 直接支持机群体系，从而m p i ! 坚! 垫登：! 竺茎堡! ! ! ! 垡些垫查一 程序可以不加修改地在s m p 机群上运行。多个m p i 进程在同一个节点时，运行 库通过共享网络接口提供m p i 进程间透明的消息传递。 c a p 0 0 a ，c a _ p 0 0 b 】的研究 表明，在很多情况下，单纯m p i 的编程方式经常好于其他的程序设计方式。但是， m p i 显然不是s m p 机群上最佳的程序设计模型。这里的原因有二：其一，消息 传递模型的设计针对的是分布内存的系统，对共享内存的利用显然要差于共享内 存方式；另一个重要的原因是，m p i 在很大程度上是一个静态的模型，与层次式 的体系结构不匹配。 1 2 1 多级并行的需求 多级并行的需求来自两个方面：一是应用程序的 需求；应用程序固有的并行性可能就是有层次的， 比如程序中有多个同时的、独立的活动；而每个均 有个并行实现算法；外层的粗粒度并行所能划分的 任务数目有限( f c w ) ，但是每一个任务本身却包含 了大量的工作。每一个外层的任务可能本身又由更 细小的并行任务组成。当粗粒度并行任务的个数大 于处理器的个数时，这些任务可以被平均分到各个 处理器；丽当粗粒度任务的个数不足时，细粒度并 d oi _ 1 ，4 无跨迭代依赖 d o j = 1 ，w ( i ) n ，其中n 是逻辑处理 机的集合。向量l 、2 满足l s 6s 2 ，映射e ： ( i ) = ( p ( 歹) i 歹i t e r ( l ) ， _ 7 + l i _ 7 + 2 ，则称e 是循环套l 的亘金过簋坌割哒越，记作 = ( 中，( 1 ，2 ) 7 ) 。 并称( l ，2 ) 1 是e 的珏金囱量。 z 2 习m m 训如曲 。 训训 ! 坚! 坐壁! ：塑茎! 型型苎竺型生兰查一 循环套l 被驴( 中，( l ，2 ) 1 ) 分割，也即，如果某迭代被平分割在逻辑处理机p ， 则其近邻( r ，2 ) 范围内的各迭代也被 映射分在p 节点( 可能是冗余地) 执行。 当l = 2 = 6 ，冗余计算分割退化成一般的计算分割。基于通信的考虑，我们 为冗余向量设定一个阈值，因为太大的冗余向量会带来不规则的通信，甚至退化 成串行计算。 循环套l 被乒( 鼽) 分割，记s ( g ，p ) = 7 1 7 i t e r ( l ) ，p ( i ) ) ，表示在 分割下， 循环套l 在p 节点执行的迭代集。一个极端情况是，若s ( 中，p ) = ，则s ( ，p ) = 。 由于本节考虑一层循环的计算分割，向量j 只有一个非零分量，冗余向量可 简单记作厶= ( d l ，d 2 ) t ，其中d i 是常量。设循环n 的上、下界分别是l 、u ，若循环 n 被平计算分割后在p 节点的迭代集【b e g i n ，e n d ，则( 平，) 冗余计算分割后，循环 n 在p 节点的迭代集 m a 】( ( 1 ，b e g i n 州1 ) ，m i n ( u ，e n d + d 2 ) 。图3 1 给出了并行循环在 冗余计算分割后，在各逻辑节点上的迭代集。 为冗余向量定义。运算：( a l ，b 1 ) t 。( a 2 b 2 ) t _ ( m i n ( a l ，a 2 ) ，m a x ( b l ，b 2 ) ) 7 。记( a 2 ，b 0 7 ( a j ，b 】) 7 ，如果( a 1 ，b 1 ) t 。( a 2 ，妫t _ ( a l ，b 1 ) 。 定义3 2 程序段p = l l ，l 2 ，k ) ，是p 的冗余计算分割( 是l j 的冗余计 算分割) ，若对任意从l s 到w 1 s t 如) 的流依赖关系i ) 6r ，( ，) ，总有： 敬，) 5 ( 7 ) ，则称是p 的玉通信厦金让篡岔割。 所谓无通信，是指在p 的循环套之间没有通信。程序段p 之前、之后的通信 不在我们的优化范围。在节点间，通信是由流依赖关系引起的。 3 2 2 相对冗余向量、冗余关系图 计算分割的冗余分析采用数据流的方法，考虑循环间每个可能的通信。每个 循环间的流依赖均确定了计算分割的一个调整相对冗余向量。综合程序段中 所有的相对冗余向量，得到程序的冗余关系图。 兰三童羔生塑茎堑壁垡竺一 3 22 1 相对冗余向量 定义3 3 程序p = l l ，l 2 ，l 。 的计算分割映射是中，y = r ( i ) 6r ( f ) 是从l s 到h l s t u p ( 譬，p ) 或i 。 u p ( e ，p ) ，求证1 0 n 3 ，p ) i k u p ( ”8 ，p ) 。由乒o 知1 0 ( ，p + 1 ) = u p ( 。，p ) + 1 ， 则f i s ( 已p + 1 ) ，由是九确定的相对冗余向量知，i s ( 3 ，p + 1 ) 。i k l o ( e 5 ，p + 1 ) l o ( 5 ，p ) l o ( q 5 ，p ) 。下面只需证i k u p ( 5 ，p ) 。反证法。由i p u p ( 1 1 5 ，p ) ，知u p n5 ，p ) 不是l s 的被分割循环的串行上界，则u p ( t 1 8 ，p ) = u p ( 3 ，p ) + b + d 2 ，u p ( e 8 ，p ) = u p ( 中5 ， p ) + d 2 ；u p ( q 8 ，p ) 一u p ( ；8 ，p ) = b 。令c = i 。一u p ( e ，p ) ，显然0 c u p n 5 ，p ) - u p ( 5 ，p ) - b 。即c 娩c 。令，= f c + e k ，k f 一c + e 。则r ( ，) = r ( ，) 。 由j 。ki 。一c = u p ( e ，p ) ，知歹s ( ，p ) ；而由j k _ i k c i k c = u p ( 5 ，p ) ，即u p ( 1 5 ，p ) j k i k 知了i t e r ( l t ) 且了芒s ( 1 5 ，p ) 。这与是九确定的相对冗余向量矛盾。这说明i k u p ( t 1 5 p ) 。从而i s ( 1 1 5 ，p ) 。对i m 的第三种情形i m 6 。其中s 、 s 、s l 、s 2 是循环套中的语句。 对于一维处理器网格，显然有以下性质： 性质3 3 循环套l 的紧嵌深度为n ，且d ( d 如) 层循环不是并行循环，对l 的 任意数据依赖关系s ( 7 ) 6 0s ( n ，o 是对应的依赖距离向量，e d o ，则循环套l 是可流水的。 证明是显然的。只需对d 层循环进行块分割映射，容易证明。满足定义3 6 。 口 流水通信由跨迭代的流依赖引起，当流依赖的距离向量在可分割层的分量非 o 时，这就是该定值引起的流水宽度； 数据分布与可选的循环分割不一致时，流水是解决此矛盾的一种优化手段。 流水的可分块性，易于实现通信的向量化，较好地实现通信的隐藏；f o m a nd 优 化编译器 h i r 眦a n d a i l i 9 4 】通过循环交换、分块( s 仃i p m i i l i n g ) 调整流水的粒度， 降低通信开销。p a r a d i g m 利用粗粒度流水 b a i l 嘶e e9 5 解决d o a c r o s s 循环 的并行化问题。 可流水循环的定义并没有考虑循环分割与数据分布的一致性问题，而这对分 布内存的系统来说是至关重要的。在a u t l ) p a r 中流水循环的可行性判定，同时考 虑了数组分布维与可流水循环的对齐关系。仅当通信量可接受时，该循环才被分 割为流水循环。 篁三至堇壹塑苎堑堂堂兰l 一 33 2 分割循环的合并 循环合并是