（计算机系统结构专业论文）分布式存储系统上数据划分技术和编译实现.pdf

摘要 近年来以机群为代表的分布式存储超级计算机系统逐渐成为超级计算机的的主 流，与共享存储超级计算机相比，分布式存储机群系统最大的区别是数据分散存储 在不同的节点上的，在考虑其科学计算程序的并行化时，除了必须考虑到计算上的 并行性外，还必须考虑数据分布的问题。在当前网络传输技术条件下，过多数据通 讯是制约分布式存储系统性能的关键所在，因此，基于分布式存储系统的并行化编 译的研究重点就在于数据划分技术和一些辅助性的技术。 s t a n f o r d 大学的s u i f 等系统在分布式并行化编译上进行了一定的尝试，但在 该领域无论是在理论研究上还是实用系统研发上都还有很多地方需要进一步的研 究，本文在研究现有的并行化技术和数据划分技术的基础上，主要在以下三个方面 作了一些研究工作： 科学计算程序形式上的不规整性往往严重影响其并行性和数据可划分性，而复 杂非紧密嵌套循环更是常见的不规整计算模块，因此本文首先在分析常用循环变换 的特点的基础上，提出一个复杂非紧密嵌套循环的变换算法，具体b e n c h m a r k 的改 写证明，该算法能十分有效的改良一些科学计算程序的并行性和数据可划分性； 在这基础上，从实践性角度出发，针对现有分布式并行化系统缺乏一个能有效 解决边界问题整体框架的问题，结合我在参与开发我所o p e n m pt om p i 自动转换工 具的经验，提出自动数据划分的一些实用性算法，包换划分信息的表示，划分信息 的合并、传递，划分信息的决策、发布，数组的划块、对齐，数组边界代码的处理 和串行程序的处理等。 最后，给出一个能覆盖大量科学计算程序的数据划分算法基于幺模变换的 数据划分，该方法以每个循环的划分性为基础寻找一个能覆盖所有循环的幺模变 换，它能将单个嵌套循环数据划分的分析和循环间寻求统一全局数据划分的分析有 机结合起来，弥补了现有数据划分方法的不足，在具体b e n c h m a r k 测试中取得很好 的效果。 【关键字】：分布式存储系统，并行编译，非紧密嵌套循环，循环变换，数据划分 幺模变换 【中图分类号】：t p 3 1 4 a b s t r a c t a b s t r a c t d i s t r i b u t e dm e m o r ys y s t e mi sb e c o m i n gt h em a i n s t r e a mo fs u p e rs o m p u t e r s y s t e m b yc o n t r a s tw i t hs h a r em e m o r ys y s t e m ，i td i s t r i b u t e st h ed a t ao v e r d i f f e r e n tn o d e sa n db o t ht a s kd i s t r i b u t i o na n dd a t ad i s t r i b u t i o ns h o u l db e c o n s i d e r e dw h i l ep a r a l l e l i n gap r o g r a m c u r r e n t l yt o om u c hd a t a c o m m u n i c a t i o nw i l lr e d u c et h ep e r f o r m a n c eo fd i s t r i b u t e dm e m o r ys y s t e m s e v e r i t y s ot h ed a t ap a r t i t i o na n dr e l a t e da u x i l i a r yt e c h n o l o g yi st h ek e y o fp a r a l l e l i s mi nd i s t r i b o t e ds y s t e m s o m ep r o j e c t ss u c ha ss u i fs y s t e mo fs t a n f o r du n i v e r s i t yh a v ed o n es o m e r e s e a r c hi nt h i sa r e ab u tw h i c hn e e d sf u r t h e rr e s e a r c hb o t hi nt h e o r ya n d p r a c t i c e t h i sp a p e rb r i n g st h r e et o p i c sb a s eo nm yr e s e a r c hw o r ki n p a r a l l e l i s mi nd i s t r i b u t e ds y s t e m t h ei r r e g u l a r i t yo fs o m es c i e n c ep r o g r a m sr e d u c e st h ee f f e c t i v e n e s so f t h ed a t ap a r t i t i o na n di m p e r f e c tn e s t e dl o o pi sv e r yp o p l a ri nt h e s ep r o g r a m s s ot h i sp a p e rb r i n g sat r a n s l a t i o na l g o r i t h mt oh a n d l et h ei m p e r f e c tn e s t e d l o o p t e s to fs o m eb e n c h m a r ks h o w st h a ti tc a ni m p r o v et h ee f f e c t i v e n e s s o ft h ed a t ap a r t i t i o n i np r a c t i c eaf r a m e w o r kw h i c hc a nc o v e rt h eb o u n d a r yo fb o t ht a s ka n d d a t ad i s t r i b u t i o ni sv e r yi m p o r t a n ta n dt h i sp a p e ra l s ob r i n g ss o m ep a r t i c a l a l g o r i t h m si nau n i f i e df r a m e w o r ka c c o r d i n gt om yd e v e l o p m e n te x p e r i e n c e t h e s ea l g o r i t h m sc o v e r st h er e p r e s e n t i n g ，m e r g i n g ，c o l l e c t i n g ， d e c i s i o n m a k i n g ，d i s t r i b u t i n go fd a t ap a r t i t i o ni n f o r m a t i o n ，t h eb l o c k i n g ， a l i g m e n to fa r r a y ，t h eb o u n d a r yh a n d l i n gc o d eo fa r r a ya n ds e r i a lc o d e a tl a s tt h i sp a p e rb r i n g sad a t ap a r t i t i o na l g o r i t h mb a s eo nu n i m o d u l a r t r a n s f o r m a t i o nw h i c hc a nc o v e ral a r g ea m o u n to fs c i e n c ep r o g r a m t h i s a l g o r i t h ms e a r c h sf o rau n i m o d u l a rt r a n s f o r m a t i o nw h i c hc a n c o v e ra l ll o o p s i nt h ep r o g r a ma n di tc o m b i n et h ea n a l y s i so fs i n g l e1 0 c a li o o pw i t ht h e g l o b a la n a l y s i so fa 1 1l o o p s t e s to fs o m eb e n c h m a r k ss h o w st h a ti t i sa h i g he f f i c i e n td a t ap a r t i t i o na l g e r i t h m k e yw o r d s 】：d i s t r i b u t e dm e m o r y ，p a r a l l e lc o m p i l e r ，i m p e r f e c tn e s t e dl o o p ， d a t ap a r t i t i o n ，u n i m o d u l a rt r a n s f o r m a t i o n c h i n e s el i b r a r yc a t e g o r y 】：t p 3 1 4 绪论 1 1 课题背景 1 绪论 并行编译一直是高性能计算的热点所在，从向量编译到后来的共享存储并行编 译，自动并行化在高性能计算领域都是十分重要的，而这两者的研究成果也十分成 功的应用于具体的高性能计算领域上，大大减轻了科学计算程序员的负担。但是， 随着高性能技术的发展，以机群为代表的分布式存储超级计算机系统逐渐成为超级 计算机的主流，根据最新的数据显示，在世界超级计算机5 0 0 强中，机群式超级计 算机系统无论是数量还是运算性能都接近一半，但这些分布式存储超级计算机的平 均计算能力往往远远小于的系统的峰值运算能力，其中一个关键因素就是由于数据 分散在各个不同的计算节点上而引起的大量的数据通讯的存在。这就给并行编译的 研究工作者提出一个新的挑战，传统的并行编译技术能否有效的解决分布式存储系 统下科学计算程序的并行化问题。与共享存储超级计算机相比，分布式存储系统最 大的区别是数据分散存储在不同的节点上的，因此，分布式存储系统下并行化的难 点就在于数据划分技术，要注意的是，这里的数据划分是与一定的计算划分( 计算 并行性) 联系在一起的，计算划分通过以往的技术能得到有效的解决，但数据划分 就不是那么简单了。从另外一个角度考虑，数据毕竟是可以“移动”的，因此，在 程序运行过程中，可以动态的改变数据的分布，只是在现有的网络通讯技术条件下， 这种大最数据的“移动”开销十分昂贵，过多数据通讯往往是制约系统性能的关键 所在。因此，如何在已经开发出的计算并行性下进行有效的数据划分，既能充分利 用计算上的并行性，又能尽量减少不必要的数据通讯就成为分布式存储系统的并行 编译研究难点所在。 并行编译和商性能计算领域的学者们对数据划分技术进行了广泛的研究，其中 j m a n d e r s o na n dm s l a m 在 1 中给出数据划分的一般性定义，但从实用 性角度来讲，这些研究成果到目前为止还没有很好的实现，或者说到目前为止还没 有实现一个能较好的对科学计算程序自动分布式并行化的工具，经过研究，我们认 为问题出现在以下几个方面：一是目前的划分技术的确有一些很好的算法，单纯的 科学计算程序的主体能够得到有效的划分，但做为一个工具来说，当一个真正的科 学计算程序作为输入时，很多边界问题( 如数组边界元素的特殊计算，串行代码的 处理) 严重影响了这些工具的识别和处理能力；另外，由于高能性计算程序员的编 程习惯问题，很多本来能轻易划分的程序段以一种不规整的形式出现，造成了这些 程序段无法进行有效划分；最后，也是最关键的问题，就是当多个循环间的划分出 现冲突的时候，目前的数据划分方法只能采用一些保守的方法，这些方法包括简单 的数据重组和建立图的方式求最小重组代价，但这些方法的并行化效果在一个大型 程序中并不明显。针对上述问题，我们在复旦大学并行研究所的并行编译框架a f t 系统的基础上，对上述三个问题进行思考和研究，希望能够在在一定程度上解决或 缓解上面提到的三个问题。 1 2 论文内容安排 本文内容安排如下：第一章给出本文的研究背景和研究目标：第二章简单回顾 一下并行编译的理论和主要工具；第三章给出数据划分的一般化定义：第四章重点 描述一下循环变换在分布式存储并行编译中的应用；第五章则描述一下o p e n m pt o m p i 自动变换中的若干问题的研究结果：第六章重点描述我们提出的基于幺模变幻 的完全一致数据划分框架；最后一章则简单总结本文的研究成果和对进一步研究的 展望。 并行编译介绍 2 1 高性能系统体系结构 2 并行编译介绍 过去几十年，高性能计算机在巨大的需求下得到了高速的发展，处理机性能按 照m o o r e 定律飞速发展，与之相对应的计算机系统结构也在为适应新的需求而发 展，由开始的流水线，标量到超标量，向量机到共享存储并行机，计算机系统结构 也处在不断的演化当中。近年来以机群为代表的分布式存储超级计算机系统逐渐成 为超级计算机的主流。根据最新的数据显示，在世界超级计算机5 0 0 强中，分布式 存储机群式超级计算机系统无论是数量还是运算性能都接近一半。从系统结构的演 化过程中可以看到，并行化始终处于核心地位，无论是不同功能部件的并行执行， 还是向量机的多数据的并行执行，还是多处理机的多任务并行执行，并行化的最终 思想可以归结为计算的并行性和数据存储问题，其中前者是提高性能的根本方法， 后者是前者能顺利进行的保证。对于分布式存储系统来说，它与共享存储超级计算 机最大的区别是数据分散存储在不同的节点上的，在当前网络传输技术条件下，网 络通讯速度( 包括启动传输等开销) 要比数据计算速度至少慢一个数量级，因此数 据分布的问题就显得更加重鹱了。 图2 l 共享存储并行机和分布式存储并行机 与这些计算机并行化技术相对应，并行编译技术也随着应用的需要得到了很大 的发展，而随着计算程序规模的日益增大，程序员控制并行计算程序的难度也越来 越大，因此，自动并行编译( 转换) 工具在高性能计算领域的地位就越发重要了。 下面，我们首先简单介绍一下并行编译中的基本概念和经典方法，定义和定理的证明 详见并行编译的相关资料。 并行编译介绍 2 2 相关性分析 2 2 i 相关性定义： 定义一：在并行编译领域，相关性是最基本的概念，简单来说，程序中的两个语句 s l 到s 2 存在数据相关当且仅当：( 1 ) s 1 和s 2 访问了相同的存储单元，且至少有 一条语句写了该单元。( 2 ) 存在一条s 1 到s 2 的运行时的执行路径。 按照存一取的顺序，相关性可分为： 流相关：s 1 写s 2 读同一个单元。 反相关：s l 读s 2 写同一个单元。 输出相关：s l 和s 2 都写了同一个单元 交换两个相关语句的执行顺序，会改变程序原来的语义。 2 2 2 循环的相关 对一个循环从展开的角度去看，循环内的两条语句存在相关的定义如下： 定义二：迭代向量的关系 循环的两个迭代向量i = ( i 。，i ：，i 。i 。) 和j = ( j ，j 。j 。j 。) 的关系如下： i 在j 之前( i ( j ) ：当且仅当存在0 = k = n i 使得 j 。，j 。，j 。j 。 = i 。，i 。，i 。i 。 且i k + l j ) ：当且仅当存在o 0 s i g n ( a ) = = ”当a = 0 l ” 的方向向量为无效方向向量。 定理二：循环经过变换t ( 不重排循环体内语句) 后，如果所有原来的有效方向向 量没有变成无效的方向向量，则该循环变换t 是有效的。 定义六：循环携带的相关和循环无关的相关 循环体中语句s l 到s 2 有循环携带相关，当且仅当s l 在迭代i 中和s 2 在迭代 j 中访问了同一个存储单元，且d ( i ，j ) o ，即d ( i ，j ) 存在一个“ ”作为他的最左 非“= ”。如果s l 在s 2 之前( 程序中的行数顺序) ，则称这个相关为前向，反之为 后向。 循环体中语句s 1 到s 2 有循环携带相关，当且仅当s 1 在同一个迭代i 中访问了 同一个存储单元且存在一条从s 1 到s 2 的执行路径。 2 2 3 相关性测试 相关性测试就是要通过计算得出上面所提到的距离向量或方向向量，值得注意 的是严格来说要对每两条语句中的每个共同变量( 数组) 作测试。目前比较流行的 相关性测试有b a n e r j e e 测试，d e l t a 测试等，每种测试都有一定的覆盖范围和开 销，因此需要根据应用的要求选择不同的测试。本文就不详细介绍这些相关性测试。 2 2 4 向量化和并行化 向量化和并行化是并行编译的基本应用，其中向量化是小力度的语句级的并行， 而并行化是大力度的线程级的并行，因此对于同一个循环来说，向量化要将其拆分 成一个个最里层可并行且只有一条语句的循环，而并行化则力求最外层的大循环能 够并行化，如下例： d oi = 1 ，1 0 0 d oj = 1 ，1 0 0 a ( i ，j ) = b ( i ，j ) + c ( i ，j ) 串行程序 b ( i ，j ) = c ( i ，j 十1 ) e n d d o e n d d o 并行编译介绍 d oi = 1 ，1 0 0 d o v e c t o rj = 1 ，1 0 0 a ( i ，j ) = b ( i ，j ) + c ( i ，j ) 向量化程序( d o y e c t o r 表示e n d d o 取该循环向量化) d o v e c t o rj = 1 ，1 0 0 b ( i ，j ) ；c f i ，j + 1 ) e n d d o e n d d o d o a i ii = l ，i 0 0 d oj = 1 ，i 0 0 并行化程序( d o a i i 表示取该 a ( i ，j ) = b ( i ，) ) + c ( i ，j ) 循环并行化) b i ，j ) = c i ，j + 1 e n d d o e n d d o 2 3 过程问分析 程序的不同函数( 过程) 间的数据传递和调用关系是并行编译的难点之一，特 别是过程间变量复杂的关联关系对提取循环的并行性影响很大。另外，多点调用也 给循环并行化和数据划分带来了很大的困难。过程间分析的方法有很多，其中最基 本的方法就是建立调用图，利用一定过程问信息关联方式按照b o t t o m u p 和 t o p d o w n 的方法进行信息的传递。 2 4 开发并行性 并行编译的主要任务就是通过分析取得一定的信息，然后通过一定的变换方法 开发程序的并行性，下面就列出一些常用的开发并行性的变换方法： 方法 含义源程序变换结果 循环正规化使循环的下d oi = 1 0 0 ，2 ，一2d oi = 1 ，5 0 ，1 界为1 ，迭代a ( i ) _ a ( 1 0 2 2 i ) = 增量为+ le n d d oe n d d o 消除递归标量消除循环内d oi = 1 5 0d oi = 1 ，5 0 的递归标量l = l + 2 l = l 。+ 2 i ( 如l = l + 2 )e n d d oe n d d o 井行编译介绍 循环交换 交换两层嵌 d oi = 1 5 0 d oj = l ，1 0 0 套循环的顺d oj = l ，1 0 0d oi = 1 5 0 序o e n d d oe n d d o e n d d o e n d d o 循环合并 将两个并列 d oi = 1 5 0d oi = 1 5 0 循环和并在 s 1s l 一起 e n d d o s 2 d oi = 1 ，5 0e n d d o s 2 e n d d o 循环拆分将一个循环 d oi = 1 ，5 0 d oi ：1 ，5 0 拆分成多个 s 1 s l 并列循环 s 2e n d d o e n d d od oi = 1 ，5 0 s 2 e n d d o 归约识别识别循环中 d oi = 1 5 0 s u m 是归约变量 的归约变量s u m = s u m + a ( i ) e n d d o 标量扩展将循环中存 d oi = 1 ，5 0 d oi = 1 ，5 0 在相关的标t t p = a ( i )t m p ( i ) = a ( i ) 量扩展成数b ( i ) = t m pb ( i ) = t i a p ( i ) 组e n d d oe n d d o 数组扩展扩展循环中 d oi = 1 5 0d oi = 1 ，5 0 的数组d oj = 1 ，1 0 0d oj = 1 ，1 0 0 t m p ( i ) = a ( i ，j )t m p ( i ，j ) = a ( i ，j ) 1 3 ( i ，j ) = t m p ( i )b ( i ，j ) = t m p ( i ，j ) e n d d o e n d d o e n d d oe n d d o w a v e f r o n t 采用流水线 d oi = 1 ，3s 1 ( 1 ) 的形式执行 s ls 2 ( 1 ) s l ( 2 ) 循环的迭代 s 2 s 2 ( 2 ) s l ( 3 ) 语句 e n d d os 2 ( 3 ) 7 并行编译介绍 数组私有化将循环中的a ( 1 ) = 0 0a ( 1 ) = 0 0 临时数组私d oi = 1 5 0d o a l li = 1 ，5 0 有化 d oj = 2 ，1 0 0l o c a lp a ( 1 0 0 ) a ( i ) = a ( i ) + f ( i 。j )p a ( 1 ) = a ( 1 ) e n d d od oj = 2 ，1 0 0 e n d d o p a ( i ) = p a ( i ) 十f ( i ，j ) e n d d o i f ( i e q 5 0 ) t h e n d oj 2 2 ，1 0 0 a ( j ) = p a ( j ) e n d d o e n d i f e n d d o 表2 一l 常用的各种开发并行性的变换方法 上面列出的一些常用方法都有一定的变换条件，在不同的需求下有不同的应用。 数据划分的介绍 3 1 数据划分的概念： 3 1 1 数据划分的定义： 3 数据划分介绍 j m a n d e r s o na n dm s l a m 1 给出一般条件下数据划分的定义： 一个已规范划的，深度为l 的多重嵌套循环l ，确定了一个l 一维的多面体迭代 空间，嵌套礓环的每个迭代对应该多面体空间的一个整数点，可以用迭代向 量2 i 2 一， j 来表示。 一个m 维数组，确定了一个m 维的长方体空间a ，数组的每一个元素都可以用 向量口2 ，口2 ，口m ) 1 来表示。 类似的，一个n 维的处理机空间p 的一个节点可以用一个p2 ( p l ，p 2 一，p 一) 。来 表示。 如果迭代空间和数组空间a 之间存在线性关系，我们用一个线性转换函数， 来表示：f ：一a ，厂( f ) 2 f i + 后，其中f 是线性转换矩阵，厍是常数向量。 定义3 - 1 ；数据划分就是将m 一数组空间a 的每一个元素厅影射到n 一维处理机 空间p 的一个函数。 d ( 厅) ：a p d ( a ) = d a + 占 其中d 是一个h m 的线性转换矩阵，占是一个常数偏移向量。 定义3 - 2 ：计算划分就是将卜迭代空间的每一个元素i 影射到n 一维处理机 空间p 的一个函数于( i ) ： 一p 于( i ) = c f + 尹， 其中c 是个h x l 的线性转换矩阵，尹是一个常数偏移向量。 定义3 - 3 ：数据划分的问题可以归结为寻找嵌套循环的计算划分函数手( f ) 和 每个数组的数据划分函数d ( 扪，以最大化计算并行度和最小化通讯。 3 1 2 计算空间和数据空间是完全一致的： 计算空间和数据空间a 之间的关系可以十分复杂的，对于这种存在复杂关系 得计算程序来说，往往无法找出有效的数据划分。但幸运的是，对于大多数科学计 算程序来说，这两个空间是线性相关的而且符合以下条件： 数据划分的介绍 数组下标识一致产生引用( u n i f o r m l yg e n e r a t e dr e f e r e n c e s ) 2 2 ，即数组 下标的引用方式在整个程序中保持一致。 迭代空间和数组空间之间的转换函数符合初等变换，也就是说其线性转换函数 ，( f ) 2 f i + 中，f 是单位阵e 的初等变换矩阵。 在符合这些条件的情况下，称之为这两个空间是完全一致的，此时考虑任何一 个空间的同时也就考虑了相对应的另外一个空间，计算空间的维和数据空间的维是 一一对应的。此时，定义3 - 1 和3 - 2 中的厅和f 可以认为其等价，数据划分的问题 就转换成求解方程d uj = 。u ) 。 3 1 3 若干个并列嵌套循环无重组的数据划分 在数据空间和计算空间一致的条件下：若干个并列嵌套循环无重组的数据划分 的问题就是： 1 ) 一个统一的数据划分矩阵3 f f ) ： 2 ) 每个嵌套循环l j 的计算划分矩阵t ( i ) 能尽量满足其并行度的需要。 3 ) 方程组孑( i ) = i ，( n 最后，问题就转换成如何根据每个弓( ) 求取孑( ) 和以使得d ( ) 2 弓( ) 有解。实 际上，如果d ( f ) 固定下来，根据数据在哪，计算在哪的原则，则q uj 也是确定的， 最后问题就转换成怎么样的d ( f ) 才能使得其确定的每个q 【j 能保证其并行度。 3 2 现有数据划分技术简介及分析： 虽然寻求最优的数据划分已经被证明为n p 问题( m a c e 1 5 ，a n d e r s o na n dl a m ， l ia n dc h e n 1 7 ，k r e m e r 1 6 ) ，但大部分研究者都相信对于科学计算程序来说， 寻找一种有效的数据划分方法仍然是可行的。到目前为止，对于科学计算程序的数 据划分问题的研究，主要集中在两个方向上：一是单个嵌套多重循环内数组的划分； 二是多个循环间的全局数据划分。 3 2 1 单个嵌套多重循环内的划分 对于单个嵌套多重循环，如果数组下标是一致产生引用( u n i f o r m l yg e n e r a t e d r e f e r e n c e s ) ，c h e na n ds h e u 2 2 提出了一种有数组复制和无数组复制的启发式 算法，实现无处理机通讯；a n d e r s o n 2 ：h u a n ga n ds a d a y a p p a n 2 3 ：n i n ge t a 1 2 4 ：r a m a n u j a ma n ds a d a y a p p a n 2 5 ：s h i he ta 1 2 6 建立了将迭代空 间和数据空间影射到处理机空间方程式，然后以此来求解嵌套多重循环的无数据通 数据划分的介绍 讯的数据划分。如果数组下标是非一致产生引用，t e nh t z e n ，l i o n e lm n i 6 针对二维数组采用d c h ( d e p e n d e n c ec o n v e xh u l l ) 概念和d s f ( d e p e n d e n c es l o p e f u n c t i o n ) 方法将非一致产生引用数组下标转换成一致产生引用下标。对于单个嵌 套多重循环，为了实现程序的最大并行性和最少通讯，m i c h a e le w o l f ，m o n i c as l a m 1 提出一种方法，采用多重幺模变换对循环进行转换，寻找完全可置换循环 ( f u i l yp e r m u t a b l el o o p s ) ，从而完成数据分布。 上面这些研究的重点都在把数组的引用方式限定在一定的框架内，再在该框架 内寻求一种有效的数据划分方法。由于一般的科学计算程序的数组引用方式都比较 规整，符合定的框架，因此，这些研究取得了很大的进展，单个嵌套多种循环内 的数据划分问题可以说已经得到了较好的解决。 3 2 2 多个循环间的全局划分 然而，数据划分毕竟还是对整个程序而言的，因此，多个循环间如何寻求全局 的划分也就成为数据划分研究的另一个方向所在。目前循环间的数据划分研究的重 点在于当不同循环的划分存在冲突时如何处理，如何寻找一个全局的划分以尽量减 少划分冲突所引起的数据通讯代价。l i p e i z o n g 4 让每个嵌套循环有其独立的局 部数据划分，根据局部划分之间数据重组的代价和计算并行所带来的好处，从而决 定最后的数据划分。l ip e i z o n g 5 则进一步提出数组“重要性”的概念，按数组 的“重要性”来对准划分，从而保证重要数组不需要重组或尽量少的重组。k r e m e r 9 将程序分成断( p h a s e ) ，( 数组重组只允许在p h a s e 之间进行) ，建立c a o ( c o m p o n e n t a f f i n i t yg r a p h ) 和利用o - i 线性规划算法来寻找一种通讯代价最少的划分。7 0 r d i g a r c i a i 0 主要统一考虑了数据划分三个过程( 对准a l i g n m e n t ，划分 d i s t r i b u t i o n ，重组r e m a p p i n g ) ，在建立c p g ( c o m m u n i c a t i o n p a r a l l e l i s mg r a p h ) 和开销模型( c o s tm o d e l ) 的基础上利用0 - 1 线性规划算法来寻找一种代价最少的 划分。a m yw l i m g e r a l di c h e o n ga n d n i c es l a m 3 1 1 2 9 则进一步 建立了一个基于仿射变换( a f f i n e ) ( 统一了各种变换，如幺模变换( u n i m o d u l a r t r a n s f o r m a t i o n ) ，循环交换，循环拆分等) 的算法的框架模型，通过求解该模型 来寻求程序的最大并行度和最小通讯代价。 可以看到，建立划分图( g r a p h ) 和数学模型来寻找通讯代价最小的划分是这个 研究方向上一般方法，可惜的是，对于许多具体的科学计算程序，这些框架模型只 有理论上的意义而没有实用意义。 循环变换在并行编译中的应用 4 1 背景： 4 循环变换在并行编译中的应用 针对不同的并行系统模型的特点，有不同的并行化方法，其中对共享存储系统 ( s m p ) 的并行化主要考虑的是计算空间的并行性和数据的局部性，该领域已被广 泛研究并系统化，其中包括已经商品化的k a p ，s t a n f o r d 大学的s u i f ，i l l i n o i s 大学的p o l a r i s 和我所的a f t 。对于分布式存储系统( m p p ) 的研究则着重于数据 和计算的致划分上，虽然也进行了广泛的研究，其中a n d e r s o n ，l a m 和l i i 2 2 8 在抽象数据划分的核心问题上做出了巨大的贡献，但可惜的是这些模型 并没有很好的实例化，或者效果并不理想，到目前为止，还没有一个能够对广泛程 序取得理想加速比的系统。 根据科学计算程序的特点，无论s m p 还是m p p 模型，循环都是并行化最主要的 处理单元，在并行化一些b e n c h m a r k 中的程序时，我们发现很多并行系统无法对如 下 d oi p 2 s l e n d d o 9 0 t o ( ) ，t ( i )e i s e s 2d oj 3 d oj 1p 3 p 1e n d d o e n d d o s 4 s 3 i f ( c o n d )e n d d o d oj2 例4 1 存在复杂控制流的非紧密嵌套循环无法有效的并行化，从而影响了程序整体并 行性的开发。实际上，我们发现只要经过简单的循环变换 3 0 ，这些复杂循环就可 以有效地并行化，其中包括共享存储空间下的计算并行化 6 7 ，也包括分布式存 储空间下的计算和数据划分问题，本章结合分析b e n c h m a r k 和开发a f t 并行系统的 过程中取得的经验，给出复杂非紧密嵌套循环变换方法的一些探讨。 本章结构如下：第2 节给出一些常见的简单循环变换在复杂非紧密嵌套循环中 的应用。第3 节给出复杂非紧密嵌套循环变换的方法；第4 节给出具体的b e n c h m a r k 程序的变换及测试结果；第5 节是全章小结。 循环变换在并行编译中的应用 4 2 常见简单循环变换： 4 2 1 循环交换 循环交换就是交换嵌套循环中循环的顺序，无论对s m p 还是m p p 系统来说，都 需要粗粒度和大力度的并行性，合适的循环交换往往能提高嵌套循环的粒度的同时 减少同步和通讯 ，是大规模并行化一个十分有用的变换。 ( 4 一1 ) 对紧密嵌套循环的交换是合法的，当且仅当所有方向向量置换后不改变原方向 向量的类型，也就是说以“ ”为最左非 “= ”的方向向量不会互换。 考虑以下的嵌套循环模型( 例4 - 1 ) ： d oi d oj a i + 1 ，j = a i ，j + 1 e n d d o e n d d o 原方向向量为( ) ，交换i ，j 循环后变为( ， s i 的相关时就可以拆分的。若存在这种相关，而且只 涉及到临时变量或临时数组时，可以通过数组扩张来消除这种相关从而可以进行循 环拆分。 4 2 3 循环合并 循环合并是循环拆分的相反动作，它可以提高循环的粒度，减少同步和通讯， 但容易引入跨迭代的相关。实际上，在并行系统中，对源程序进行循环合并更多的 是为了将多个里层循环合并成一个循环以形成紧密嵌套循环，从而可以进一步循环 交换。 ( 4 3 ) d o1 可以被正确合并成 s 1 d oi e n d d o s 1 d o1 s 2 s 2 e n d d o e n d d o 的条件是合并前的前向相关s i - $ 2 合并后不会变成s 2 s l 的反向相关。 在简单循环中，利用相关性测试能够很容易的判断是否满足循环合并的要求， 但在存在复杂控制流的嵌套循环中，循环合并就变得复杂多了。先考虑考虑如下的 ( 4 - 4 ) p r e l 可以合并成如下形式 d oj = 1 ，m d oj = l ，m s 1 i f ( j = = 1 ) p r e l e n d d os 1 p o s t l i f ( j = = x ) p o s t l d oj = 1 ms 2 s 2 i f ( j = = m ) p o s t 2 e n d d oe n d d o p o s t 2 的条件是合并后所有原s i - p o s t l 与p o s t i - s 2 的相关保持原方向。其中的x 4 循环变换在并行编译中的应用 取值范围可以如下条件得出： 若原存在形如s i ( s ) - p o s t i 的相关，则s s 2 ( t ) 的 相关性，则t = x 。其中s i ( s ) 表示s l 第s 次j 迭代的执行，s 2 ( t ) 类似。若s t 则x 的取值范围为空，表示原循环不可合并。 ( 4 5 ) i f ( c o n d ) 可以通过添加一临时变量保存进入 d oi = l ，n if - t h e n 时c o n d 的值来达到循环合并的 s 1 效果： e n d d od o1 = 1 n e l s e i f ( i 2 = 1 ) c o n dt m p 2 c o n d d oi = l ，n i f ( c o n d t m p ) s 2s l e n d d oe l s e e n d i fs 2 e n d i f e n d 最后考虑存在类s w it c h 的g o t o 的循环： 往哪个j 循环) d oi = l ，n g o t o ( j 1 ，j 2 一j k ) ，t ( i ) d oj 1 = 1 ，m s 1 e n d d o d oj 2 = 1 ，m s 2 e n d d o d oj k = 1 ，m s k e n d d o ( 其中g o t o 语句根据t ( i ) 的值决定跳 ( 4 - 6 ) 可别合并成 d oi = l ，n d oj = 1 ，m i f ( j = = 1 ) c o n d = t ( i ) g o t o s 1 ，s 2 ， s k ) ，c o n d s 1 s 2 s k e i x d d o e n d d o 另外，可以利用循环合并来减少边界计算对共享存储系统中的数据划分的影响： 例4 4例4 - 5 d oi=1，n d oi=1n d oj = 1 ，m 一1d oj = 1 ，m 一1 a 【i ，j 】= a 【i - 1 t 1i f ( j b m ) e n d d o a i ，j 】= a f i 一1 ，j 】 e n d d o e l s e d oi2 1 ，n a i ，j 】。i 0 0 a i ，m 】= 1 0 0 e n d i f e n d d oe n d d o 例4 4 的两个循环如果直接考虑数据划分的话，则前面的两重循环要求对数组 循环变换在并行编译中的应用 a 按j 维划分，而第二个循环则要求按i 维划分，因此发生冲突，但如果我们把两 个循环如下和并在一起就可阻统一按j 维划分了( 例4 - 5 ) 。 4 3 复杂非紧密嵌套循环变换： 根据例4 1 所示的复杂非紧密嵌套循环的形式，我们定义复杂非紧密嵌套循环 为：一个n 层嵌套循环( 由外往内依次1 ，1 。，l 。) 其中至少有一层循环l - ( k n ) 由以下结构组成： i 若干个厶+ ，层循环； i i 若干不合- 。层循环的串行代码； i i i 类s w i t c h 的g o t o 语句且g o t o 语句不可跳转到。层循环内部或l 。层 循环外部； i v i f - t h e n 结构 对于满足上面定义的复杂非紧密嵌套循环，根据不同的需求( 如第4 节中提到 的s m p 系统下由于1 ，1 。，1 。不可并行而需要利用循环交换来提高并行粒度和 | l f p p 系统下的数据划分算法的要求) ，常见的一种变换就是将其转换成紧密嵌套循 环。实际上有三种方法可将上述的复杂非紧密嵌套循环转换层紧密嵌套循环：一是 合并所有l 。层循环并将i i ，i i i ，i v 类结构也并入循环体中：二是拆分1 ，12 i l k _ l ， l 。层循环，将原嵌套循环转换层多个紧密嵌套循环；三是混合采用拆分和合并方法。 下面就分别给出复杂非紧密嵌套循环的合并和拆分条件及算法： i 遍历。内的每个带有。层循环的i f t h e n 结点，根据条件( 4 5 ) 判断是 1 v v 否可将其合并成一个l + ，层循环；若可则用新的。层循环替代原i f t h e n 结点： 遍历。内的所有。层循环，对任两个。层循环p 。和p 。，n m ( n 和m 表示 其在。层循环的先后顺序) ，则合并后不能存在p - ) p 。的相关： 遍历以内的所有 + ，层循环，对任意串行语句s k ，根据条件( 4 4 ) 判断其 是否可加入合并循环中，并求出其x k 值的范围w 。且w 。不为空，注意这里应 该对s 。与所有- 。层循环重复应用条件( 4 4 ) ； 遍历厶内的所有。层循环，对任意两个串行语句s 。和s 。，k p 时多个循环间如果访问长度不一 致时，为了保证迭代长度最小的循环能够有足够的并行力度，应该按最小的n 进行 分块。但当最小的n 与p 差距并不大时，为了保证其他循环的并行力度，则应该舍 弃该n ，对该循环可以让部分计算节点空闲。算法如下： 在一个划分信息里，提取出每个数组出现的每个循环的迭代长度n ，所有的n o 芦n m p 加，i 自动变换中若千问题的研究 组成一个集合( n 。 ( 0 i m ) 且n 。 n 。，取最小的k ( 0 k m ) ，使得n t p d ，则按n 。d 为块大小进行