（计算机软件与理论专业论文）循环变换增加并行粒度与改善数据访问局部性.pdf

摘要 ， f 在程序自动并行化的过程中，并行粒度和数据访问局部性是两个常常被关注的 问题。实用的并行化算法必须考虑并行化后的循环有适当的并行粒度和良好的数据 访问局部性，以降低处理机花费在进程同步和内存访问不命中上的开销。 一些经典的循环并行化方法往往把注意力集中在挖掘循环的并行性上，这是出 于简化问题的原因。然而在实用并行化编译器的研制中，应当充分考虑到一些次要 问题对并行化结果的影响，对经典算法进行适当的补充和扩展，以满足实用性的需 、一 要。 本文在迭代空间变换的基础上，提出了一种利用循环变换增加循环并行粒度， 改善循环数据访问局部性的方法。首先针对循环并行粒度的问题，本文利用了给定 二重循环的相关向量集的某些性质，对迭代空间进行折叠，将外层循环变量不同， 而内层循环变量相等的若干次迭代合并，成为折叠后迭代空间的一个结点，并且保 持内层循环的并行性不变，从而达到增加循环并行粒度的目的。对于更普遍的情况， 本文讨论了如何根据给定循环的循环向量集，确定一个循环变换对迭代空间进行变 换，达到内层循环可并行和扩大循环粒度两个目的。 其次针对循环变换中数据访问局部性可能变差的问题，本文从原程序的循环是 局部性良好的循环这一前提假设出发，提出了对内层循环的不同迭代先合并，根据 合并后的相关向量集变换迭代空间，以及折叠迭代空间的方法。这种方法能够在保 持扩大循环粒度效果的基础上，达到保持原程序数据访问局部性的效果。 本文从实际应用的角度出发，能够达到很好的循环并行化效果，而且是现有循 环变换方法的一个推广。 关键字循环变换，并行化霜诲，u 模变换，迭代空伺折叠，数据访问局部性， w a v e f r o n t 方法 0 a b s t r a c t i na u t o m a t i cp r o g r a mp a r a l l e l i z i n g ，g r a n u l a r i t ya n dd a t al o c a l i t ya r ei s s u e so f t e n c o n c e r n e d p r a c t i c a l p a r a l l e l i z i n ga l g o r i t h m m u s t k e e pg o o dg r a n u l a r i t y a n dd a t a l o c a l i t yo ft h ep a r a l l e ll o o p si no r d e rt or e d u c et h eo v e r h e a do fp r o c e s ss y n c h r o n i z i n g a n da c c e s sm i s si nm e m o r y s y s t e m m o s tp a r a l l e l i z i n ga l g o r i t h mp u tg r e a te f f o r t si nh o wt o g e tm a x i m a lp a r a l l e l i z e d l o o p s f r o mt h e p r o g r a m t h i s c o n s i d e r a t i o nw i l l s i m p l i f y t h e p r o b l e m i n t oa d i s c u s s a b l ed e g r e e b u ti nt h ed e v e l o p m e n t o f p r a c t i c a lp a r a l l e l i z i n gc o m p i l e r , w em u s t c o n s i d e rt h e s em i n o rf a c t o r s r e g a r d i n g t h ee f f e c t so fp a r a l l e l i z e d p r o g r a m s o m e a l g o r i t h m s h o u l db ee x t e n d e dt om e e tt h e s e c o n s i d e r a t i o n ，s o m es h o u l db es l i g h t l y m o d i f i e d i nt h i st h e s i sw ed i s c u s s e dal o o pt r a n s f o r m a t i o nm e t h o dw h i c hc o u l di n c r e a s et h e g r a n u l a r i t yo f t h el o o pb o d ya n di m p r o v et h ed a t al o c a l i t yo ft h et r a n s f o r m a t e dl o o p ：b y a n a l y z i n gt h ed e p e n d e n c ev e c t o rs e to f t h eg i v e nn e s t e dd o u b l e l o o p ，w ec o u l dm e r g e s e v e r a ln o d e si nt h ei t e r a t i o n s p a c e ，w h i c hh a v es a m eo u t e rl o o pv a r i a b l ev a l u ea n d d i f f e r e n ti n n e rl o o pv a r i a b l ev a l u e ，i n t oo n en o d ei nt h ef o l d e di t e r a t i o n s p a c e ，w h i l e p r e s e r v i n gt h ep a r a l l e l i s mo ft h ei n n e rl o o pa t t h es a m et i m e t h u s ，w ei n c r e a s e dt h e g r a n u l a r i t y o ft h e p a r a l l e ll o o pb o d y f u r t h e r m o r e ，w ed i s c u s s e dh o wt o f i n da u n i m o d u l a rm e t r i c st ot r a n s f o r mt h eg i v e ni t e r a t i o ns p a c ew i t ht h eg i v e nd e p e n d e n c ei n t o a ni t e r a t i o ns p a c ei nw h i c hi t e r a t i o nn o d e sc o u l db em e r g e du s i n go a rm e t h o d sg i v e n a b o v e w ea l s op r e s e n tam e t h o dt op r e s e r v et h el o c a l i t yo ft h eo r i g i n a l l o o p w h i l e d o i n g o u r l o o pt r a n s f o r m a t i o na n d i t e r a t i o ns p a c ef o l d i n g o u rm e t h o dd i s c u s s e di nt h i s a r t i c l ei st h e g e n e r a l i z a t i o no f t h ew a v e f r o n tm e t h o d k e y w o r d s l o o pt r a n s f o r m a t i o n ，p a r a l l e l i z i n gc o m p i l e r s ，u n i m o d u l a rm e t r i c s ，i t e r a t i o n s p a c e f o l d i n g ，d a t al o c a l i t y ，w a v e f r o n tm e t h o d 循环变换增加圳行粒度和改善数据访问局部性 1 背景介绍 1 1 并行编译的有关背景 高性能计算一直是计算机科学中的一个重要的分支。科技的发展，在各个牛产 领域中产生了在短时间内完成大量计算任务的要求，这些要求推动了高性能超级计 算机体系结构的发展。在各种高性能计算机中，并行处理技术是一个重要的组成部 分。通过对计算任务的并行处理，人们能够获得数倍于原来的处理速度。而并行计 算对对软件技术，特别是并行编译技术的发展提出了很高的要求。在并行计算中， 各个处理机之间需要进行数据交换，这些数据交换的时间相对于串行计算而言，构 成了一项额外的时间开销，部分的抵消了并行计算所获得的好处。我们记原来串行 程序的运行时间为t ，记其中能够并行化的部分运行时间为a t ，程序并行化对串行 部分和并行部分所增加的额外开销分别为b 倍和c 倍，处理机数目为p 。那么我们 得到并行程序总的执行时间为a c t p + ( 卜a ) b t ，加速比为i a c p + ( 1 一a ) b 。我们在公 式中可以看出即使c 较大，随着p 的增加，这一部分的时间也会逐渐变小，但是如 果f 1 a ) b l ，那么无论我们怎样增加处理机的数目，都不会得到有效的加速比。我 们在并行编译，也就是程序自动并行化的过程中，需要尽量减小串行和并行部分时 间开销的相对比例，以获得有效的时间加速比。一般而言，减小串行部分时间开销 的相对比例对于提高并行程序的时问加速比能够带来更大的好处。需要注意的是， 程序并行化时间开销所占的比例并不是一个常数，而是和程序运算的规模以及处理 机的个数有关的一个量。如果并行部分的时间开销是和处理器的个数有关的，那么 这部分对并行程序的时间加速比影响也会很大，就需要对这一部分的执行效率进行 优化。程序并行化所带来的额外开销是不可避免的，我们要在定量或半定量分析的 基础上，减小那些关键性的时间开销，以获得满意的并行程序时问加速比。对于 b e n c h m a r k 中的许多程序而言，四机并行能够得到的加速比在二到三之间，而那些 加速比不：n - - 的程序是值得我们关注的目标。 第l 页 衙环变换增加并行粒度和改善数据访问局部性 1 2 主要内容 在程序自动并行化中，并行粒度和数据访问局部性是影响并行程序额外时间开 销的两个丰要的原因。程序的并行粒度越大，并行程序需要进行的同步次数就越少， 并行化后的程序花在进程同步与通信上面的开销就越小，程序的并行加速比就越高。 而数据访问局部性也经常影响并行程序的加速比，如果并行化后的数据访问局部性 不佳，那么内存访问就成为程序执行的主要瓶颈，增加处理器或者提高处理器的速 度不再能够减小程序的执行时间，程序的加速比就不能达到预料的效果。进程的同 步开销属于程序串行部分的额外开销，所以应当特别的关注。而数据访问局部性产 牛的开销由于涉及到处理机之间的通讯问题，会随着处理机数目的增加而增加，所 以也需要考虑。由于这两部分的时间开销和处理器的个数无关，因此在程序并行化 中对并行加速比往往起到决定性的作用。 程序自动并行化主要针对循环的自动并行，首先我们对程序中的多重嵌套循环 进行读写相关性分析，根据褥到的相关向量组，我们能够确定是否能对某层循环进 行并行化。对较外层循环并行化能得到较好的并行粒度，因为较外层循环的每一次 迭代都包含内层循环的许多次迭代，数据访问局部性也比较好。当外层循环均无法 并行化时，我们对最内层循环进行并行化，这时我们将最内层循环的各次迭代平均 分配给各个处理器，并使邻近的迭代在同一个处理器上执行，这样并行粒度和数据 访问局部性都控制在不影响程序并行效果的范围内。( 此时有一个前提假设，即原串 行程序是局部性良好的，邻近的迭代访问的数据也相邻。如果原串行程序的数据访 问局部性并不是很好，并行化后的程序的数据访问局部性不会比原串行程序的数据 访问局部性差很多) 如果最内层循环的迭代次数很少，和处理器个数在一个数量级 上，那么对最内层循环进行并行化往往得不到好的并行化结果，因为同步产牛的时 间开销比一次迭代的时间都多，反而降低了程序的执行效琦夏。如果内外层循环是可 交换的，那么将内外层循环交换，并对原来的内层循环进行并行化，可以兼顾并行 度和并行粒度的要求，达到较好的效果 2 1 2 2 2 3 。 有时各层循环都无法并行，这时我们可以通过循环变换，将迭代空间变换成可 以并行的形式。w a v e f r o n t 1 方法就是常用的循环变换方法，然而w a v e f r o n t 方法也 有并行粒度小，数据访问局部性不佳等缺点。这是因为w a v e f r o n t 方法产生的是内 第2 页 循环变换增加州行粒度和改善数据访问局部性 层可并行化的循环，因此外层循环每迭代一次，都要进行一次同步操作。当嵌套循 环的循环体计算量较小，并且内层循环的循环次数较少的时候，程序的并行加速比 就会受到很大影响。而同时，循环变换会将原来相邻迭代之间的距离拉远，如果原 循环的数据访问局部性很好，那么变形后循环的数据访问局部性就会变得很差。 本文在w a v e f r o n t 方法的基础上进行了推广，利用循环变换的思想，提出了利， 利用循环变换增加内层循环并行粒度的方法，它利用循环变换中常见的u 模变换， 通过对迭代空间进行一定的变形，使内层循环变量的值保持不变，而外层循环变量 的值不相等的若干个相邻迭代可以合并成为内层循环的一次迭代，从而增加了变形 后的迭代空间一次迭代的粒度，并且依然保持内层循环的并行性。本文进行了五方 面的工作，首先是给出了能够做这种结点合并，迭代空间中相关向量集应该满足的 条件( 2 2 ) ；其次是对于给定的初始循环和u 模变换，给出了变换后的循环形式， 和确定循环界限的算法( 2 3 ) ；第三是对于一个给定的循环和相关向量集，找出一 个u 模变换，使得相关向量集变换成为满足条件的形式( 2 4 ) ；最后，对于u 模变 换引起的数据访问局部性不佳的问题，本文提出了一个解决的方法( 31 ) 。 1 3 相关的研究 u b a n e r j e e 在循环并行化和迭代空间的线性变换中做了不少研究( 2 ；f t l 4 ) ， 本文在他的研究基础上对他的迭代空间变换算法做了一些改进，使其能够适应本文 方法中的非线性变换。m i c h a e lw o l f e 在其著作 1 中对数据相关性以及循环变换有十 分详尽的叙述，本文中的记号除- - + 部分来自b a n e r j e e 的著作外，主要参考了该著 作。1 2 l l jj 羽语句调度消除循环中的同步和数据交换，也能够增加循环的并行粒度， 但是对循环中的语句相关性有一些特殊要求，而我们的方法是没有这种要求的。 3 和 5 】中从不同角度对增加循环粒度进行了一些讨论，但主要是从挖掘外层循环可并 行性角度出发的。 第3 页 循环变换增加井行粒度和改善数据访问局部性 1 4 前提假设、名词解释和记号 夺对二重循环而言，为了化简问题所涉及的情况，我们假设二重循环在并行化 变形前循环界限是常数，表现为如下形式： f o r i = 0 t or i l f o rj = ot ou 2 2 h 心吣，m 是以l 。为参数的一个操作。包含钉或多行的程守代码， e n d f o r e n d f o r 夺循环界限可以用两个对角矩阵表示： l = ( ：习；u = 夺我们假设循环是递增的，步长为1 ，如果循环本身不符合这个条件，可以通 过改写循环来满足这个条件，于是我们得到关于循环界限的不等式： “l l 0 “2 2 0 夺而在并行化之前循环的相关性表现为相关向量集：d = d 。，d ：，。d 。 夺为了将循环并行化，对程序进行的变形可以用一个u 模变换来描述：它的 形式为： t = ( ；：乏 ；t 一= ( _ ! 瓮。i ：2 其中a = h = 1 ，且f 口l ；i ， 1 ，2 夺经过t 的变换，循环的相关向量集变换成为t d = t d ；，t d ：，t d 。 ，变换 后的循环变量旺 和原循环变量匕 的关系为 = 1 ( j 。 第4 页 循珂、变换增加井行粒度和改善数据访问墒i j j 性 夺对于相关向量集d = d 。，d ：，。d 。 ，我们定义s p l i t x 和s p l i t y 函数为 s p l i t x ( d ，a ) s p l i t y ( d b ) = ( 弘酬叫= ed ) ( 咖吲旧= n ( 弘 s p l i t x 和s p l i t y 函数都将一个相关向量集和一个整数映射成为一个相关向 量集，它们分别表示对二维迭代空间在内层循环方向和外层循环方向分块 后，所获得的相关向量集。s p l i t x ( s p l i t y ( d ，b ) ，a ) = s p l i t y ( s p l i t x ( d ，a ) ，b ) ， 表示对迭代空间在内层循环方向以步长为a 分块，外层循环方向以步长为b 分块，所得到的相关向量集。 夺数据访问局部性：如果程序执行时有良好的c a c h e 和虚拟页面命中率，我们 称程序的数据访问局部性比较高；如果c a c h e 不命中或者缺页的情况比较严 重，那么程序执行的数据访问局部性就比较低。 第5 页 循环变换增加拼行粒度不f 段善数据访问局部性 2 通过循环变换增加并行粒度 2 1 通过对迭代空间的变形增加并行粒度 首先考虑一种特殊情况，t = f ：? ，t 。= 。= ( 1 ，。) ( 1 1 ) ，如下罔所小j 中 i ，代表外层循叫、，i z 代表外层循环。这个二重循环的内层循环是可以并行化的，由 于内层循环的迭代次数很少，循环并行化后的效率并不高。在这种情况下我们u j 以 对迭代空间进行变形以增加并行粒度，如图所不，如果我l f 对经过t 变形后的迭代 空间再进行一次u 模变换( j ： ，得到t = ( j 然后将变换后的绌点两两合并c 见 下图b 中彭】白仃大结占) ，会发珊同一行中的白伽结点可以并行： u u 2 2 + 1 u 7 7 + l a b c 循环变换增加爿 j 粒度用f 改善数据访问局部抖 每个白色的绝点中的各个黑色小结点之间顺序执行( 按照相关向量的箭头方 向) ，而同行的若干白色结点之间可以并行执行，此时并行循环的循环粒度与原先 的循环相比增加了一倍。 1 1 、 我们可以继续增加并行粒度，如图中c 所示，令t 1 5 【jjj ，我们町以将二个 循环结点合并成一个循环结点。在罔中b 和c 里面循环边界外有一些虚线的结点， 这些虚线的结点实际上并不包含实际的运算，它们的存7 【：只是为了力便结点合并。 可以把迭代空问想像成个平面，而结点合并的过程就足迭代卒问甲面折叠的 过程，几个不同的结点通过折叠映射成为一个结点，从而增加了迭代空间结点的粒 度( 循环并行粒度) ，如下图所示。 ，_ i 卜_ _ 、 多 ，vq _o囊 。、 j- f-、4 ， jj i j _ 7 1 l ，v 般情况下增加并行粒度的的矩阵t 5 = f j i ，通过t 5 对循环进行变形后，可 般情况下增加并行粒度的的矩阵t 5 2 l j ；j 通过t 5 对循环进行变形后，可 以将s + 1 个结点合并成一个绌点进行并行执行，经过变换后的循环如下所永 f o r i l = q t ou 、七u s ，s t e ps + l 钋睦循珥的迭代范禹与受形后的达代空闻自i 列出 t mi 2 = m a x ( 0 二_ 竺生、t qm i n ( u n 坐、? 报掘外甚褫珥的迭代数选拜边蹿条件 s s i f ( t s ) 。1c ij5 ( 0 , 1 , - - , u 1 1 ) ( o ，“z z ) 捡舀“k 定搿存送，c 空蒯力 帮7 负 循环变换增加并行粒度年改善数据访问局部性 峨气弋忒、j 。嚼皤棼眵再纷卺电蓉司| i | 殉 1 静营强醇磊毪拎t l j t j ，? 以豫始l j 1 2 为参数执行操作h c n d i f i f c t s ，( ：1 c 。，一，“，c 。，“：， 咿) - l ， e n d i f i f c t s ，t ( ：占) c 。，“。，c 。， 州一( a e n d i f e n d f o r e n d f o r 经过变形后的程序与原程序等价，并且内层循环可以并行化。循环粒度扩大为 原来的s + l 倍。 2 2 结点可以合并的条件 在上面的例子中，我们注意到相关向量集聊门，经过变换矩阵( ：； 变换 后成为 ( 1 ，0 ) ，( 1 + s ，1 ) ) ，并且在最内层循环获得了大小为l + s 的并行粒度，这个条件可 以一般化，如果我们在某个变换t 后得到循环形式： # l o o p a f o r j l = m lt om l 第8 页 衙环变换增加= j f _ 行粒度和改善数据访问局 | f 性 f o r j 2 = m 2 0 1 ) t om 2 0 1 ) 叫( 羔 ， e n d f o r 和相关向量集： ( rz ，o ) ( r 2 ，o ) ，( r l ，o ) ，( p l ，q o ，( p 2 ，q z ) ，( p m ，q m ) ，( s l ，一t 1 ) ，( s 2 ，一t 2 ) ，( s n ，- t n ) ) p l ，p 2 ，p m ，q l ，q 2 ，q m ，r l ，r 2 ，r e ，s i ，s 2 ，s n ，t l ，t 2 ，t n 为正整数 那么我们可以对迭代空间进行折叠，把循环写成如下的形式： # l o o p b f o r i l = i n lt o m ts t e p w f o ri 2 = m f f i l ) t om k i l ) i f t - ( ： c 。，“。，c 。，“：， 叫( m t f t t ( ：1 ) c 。，- ，“。，c 。，- ，“：， 叫( 扎 i r t - - ( + ：一1 e c 。，“，c 。，“：， 叫( + ， e n d f o r e n d f o r 其中o w _ m i n p l ，p 2 ，p m , s l ，s 2 。，s n ，并且内层循环可以并行化。 第9 页 循环变换增加并行粒度和改善数据访问局部 证明：任取l o o p b 中的两个迭代i l = x i 2 = y 1 ) 和 t 1 2 x i 2 = y 2 ) y t 车y 2 在这两个迭代中各自任取一个语句 漱l j 岬一戈娜：岬i ：) 弋t 由l o o pb 的形式我们司以知i 差b a l w = m i n p | p 2 p g , s i s 2 ，s 然吼b a w - m i n p ! ? p 2 一p m , s i ? s 2 s n j 和上面的关系式矛盾 ? js t r u tl 和s t m t22 闻不司能存在相关性 r l o o p b 中迭代t 尸x i 2 = y 1 ) 霹l ( i l = x , i 2 = y 2 ) y j y 2 之闯不存在稆关性 ? 。l o o pb 的内甚循环司以并行化证毕 如果g c d ( r l ，r 2 ，r l ，p 1 p 2 ，r m , s 1 ，s 2 ，s n ) 为不等于l 的正整数，那么我们可以把 外层循环按照并行度为g c d ( r , p ，s ) 进行并行( 参考文献 3 ) 。 2 3 一般的u 模变换情况 在第六节中，我们将讨论如何在已知原始相关向量集的情况下，通过u 模变换 在得到一个循环粒度较大的内层可并行循环。在这之前，我们先讨论当我们通过某 个u 模变换t 得到了相关向量集 ( r l ，o ) ，( 1 2 ，o ) ，( r l ，o ) ，( p l ，q 1 ) ，( p 2 ，q 2 ) ，( p m ，q m ) ， ( s 1 ，t 1 ) ，( s 2 ，一t 2 ) ，( s n - t n ) ) 后，如何给出变形后的循环形式。一般而言，经过一个u 模变换后，我们的迭代空间变换为为一个平行四边形，例如下图所示 第1 0 页 衙环变换增加鲋行粒度年改善数据访叫0 5 部r l ： 一j t _ _ 而此时 t d = ( _ ，o ) ，( _ ，o ) ，( 丘，o ) ，( ，。，q ) ，( p 2 ，q 2 ) ，( p ，g 州) ，扫。，一，。) ，( s 二，一f 二) ，( s x , - f 。) ，在t 图的例予中t = f ；, t d = t c 功邝，z ，根据第四节的结论，我们可以将循 环改写成粒度为3 的二重循环形式。我们通过修改后的b a n e r j e ei 一维循环变形算法 ( 参考文献 2 算法4 1 ) 得到变形后的循环。循环变形要解决的丰要是循环界限问题。 在b a n e r j e e 算法中给出了u 模变换后的循王1 、界限，我们的算法使用了这个结果。对 于需要合并的若干行，我们取内层循环界限为各行循环界限的并，得到迭代卒问折 替后的循环界限。而在内层循环的一次迭代中再去判断参力合并的各个结点( 上图 中白色大结点中的各个黑色小结点与虚线结点) 是否是原始迭代空问中的结点( 虚 线结点不是原始迭代空间中的结点而黑色结点是) 。我们将修改后的算、法给出如f ： 给定仞始_ 重紧嵌套循环 f o r l - 0 t ou l i f j rj - 0 t o “， 第| _ ；三 。 ， 州一 循环变换增加井行粒度和改善数据访问局部性 州， e n d f o r e n d f o r 和一个二阶u模变换 t = 匕：乏 ， 且 t 。= m 加l ( r 2 ，0 ) ，( r c ，0 ) ，( p i ，q 0 ，( p 2 ，q 2 ) ，( p m ，q m ) ，( s t ，一t 1 ) ，( s 2 ，- t 2 ) ，( s h ，一t n ) ，p h p 2 ，p m ，s i ，s 2 ，s n 为大于1 的正整数 算法1 给出一个二重循环和原循环等价，新的循环具有如下形式，且内层循环 可以并行化循环粒度扩大为p ( 相对原循环而言) ： w 2 r a i n p l ，p 2 ，p m ，s l ，s 2 ，s n f o r i l = m lt om is t e pw f o ri 2 - - m 2 ( i l ) t om 2 ( i l ) i f t - ( i c ，2 ，“。，c ，2 ，“：， 叫， e n d i f i f t t ( ：1 o ，2 ，“，。，x c ，2 ，“：， 叫， 第1 2 页 “2“ ：| ) 2、， 0 一 w k ，=_j+ 一 ，h 、”如小o + t r i l h t 循玮变换增加并行粒度和改善数据访问局部性 e n d f o r e n d f o r 算法1 ：计算r n i ，m l ，1 t 1 2 ( i l ) 和m 2 ( i l ) 的值 1 令卜d e t ( t 、。 若h i ，算法结束( t 不是u 模变换矩阵) 2 令 m 。一一( c “。+ f 五“：) m l - f j “l l + t i z u 2 2 舯。a 一+ ：= m a x - a , o ， m a xa 。 d= 一，u 3 找出i 2 循环的循环界限 h 。垂刘卅岫m h 羹鍪肛砌吣小。 i 。n 哗9 坐竽m 。 m 唑掣，业掣业川 h 鹰驯卅舢- ”fi 眦 业掣坐，唑掣川 m f 燕黧 卜“m 。j 业芒型业薯 业 ，”舢l 。她m l 吣 业二等哑业1 等乜圳 当t 1 2 = 0 或者t l 尸0 时，在相应的公式中舍去t 1 2 或t l l 为分母的一项即可。 算法1 完 当t = 口书且。= t c 聊门m ，时，我们得到了第三节中的结果。 第1 3 页 剥鬻| | 鞘 fil；广ffj1lp m 平 铺环变换增加；f 行粒度和改善数据访问局部性 第3 步中的两个循斟：界限公式是由b a n e r j e e 的u 模变换方法( 参考文献【2 】算法 4 1 ) 直接推导得到，包含了很多m i n ，m a x 操作。然而实际的程序变形中并不需要 做这么多m i n ，m a x 操作。首先根据t l2 和t l l 的值，上面的两个公式分别只有四种情 况中的一种被选到；其次，注意到每种分支情况中内层m a x 或m i n 中的参数是单调 线性递增，递减，或者不变的。仅以m 2 ( i l ) 为例，m 2 ( i o 具有如下的一般形式： m 2 ( ) = ir a i n m a x b l ( i ) ，6 2 “) ) ， m a x a 。+ 岛( f 1 ) ，以：+ b 2 ( i ) m a x a 。( w 一1 ) + 6 l ( f 。) ，口：( w 1 ) 十6 j ( ) ) 则由上囱式j 二的单调性可得 若q 2 0 n a ：0 ，则，”：( f 。) = m a x b , ( 。x6 2 ( 1 。) ) 1 若。0 a a ：0 ，则m ：( f 。) = 厂m a x a 。( w 一1 ) + 6 1 ( f l l a ：( w 1 ) + 6 2 ( 1 1 ) ) 若n 。o a a ： o n6 l ( f 1 ) 6 2 ( f i ) ，则m 2 ( ) = b ( f 1 ) 若l o a n ：o a b l ( i , ) 6 2 ( f ，) ，则m ：( f ，) = f b 2 ( f 1 ) 若口。o a a ： o a a ( w 一1 ) + 岛( f 1 ) a 2 ( w 1 ) + 6 2 ( f 1 ) ，则m 2 ( f 。) = l ：( w 一1 ) + 6 ：“门 若q 0 的情况) i f ( - a t ：) o ，) 0 攻卺 冰( 小 吲= h 警删 第1 4 页 岫十“业等型蛐坠型 j e i s e i f ( t n 丁l 。n ( 等) s 。 圳= h 雀半，丛半业 1 循环变换增加并行粒度年改善数据访问局部性 m 卟u n 型一生 j e n e 矿( 昔) ；。n ( 等) s 。 扩g 0 ) 啷，= 旧 f 血p 矿o + w is0 ) 删- 毪p e l s e a s s e 一0 i l + w 一1 ) m 2 ( i l ) = 0 一 矿o ( m 。+ m ) ) 学j e b e 矿“+ w 一1 ) a ( 州i + m i ) ) 毗，0 业半型j 一盼。n 盼。 , y o ，0 ) 吲沪酬 e t s e g o 十w - ls 0 ) 可唑掣1 e l s e a s s e r ( i t 0 s + 1 , 9 1 ) 2 ( i t ) = 0 ， f ( i i a ( m i + m ，) ) 州掣j p h e 抓h + w 一1 ) a ( m i + m i ) ) 1 盟等型j e l s e d s s e r t ( i l 州+ m 1sl + w 一1 ) a s s p r t ( i i5 + m 1 - s 令t ：f 1 _ 1 1 ，于是我们得到t d ： ( r ，o ) ，( p - q , q ) ，( s + t ，t ) ，因为m i n ( p q ) ， 01j 一 。、 ( s + t ) m i n ( p s ，所以经过t 变换后得到的并行粒度大于原来的并行粒度。 我们可以重复执行这一步直到并行粒度无法再增加，或者并行粒度已经满足 要求为止。 4 d = ( r ，o ) ，( p ，q ) ，( s ，一0 1 ；p , q ，r ，s ，t 为正整数，且s - t p 令t = f ： ，于是我们得到t 。= ( r 。) ，( p 十q q ) ，( s - t t ) ，因为m i n ( p + q ) ， ( s - t ) m i n p ，s ，所以经过t 变换后得到的并行粒度大于原来的并行粒度。 我们可以重复执行这一步直到并行粒度无法再增加，或者并行粒度已经满足 要求为止。 情况1 ，2 , 3 ，4 都可以一般化。 第1 6 页 衙环变换增加并行粒度和改善数据访问局部性 根据上面的讨论，对于给定的相关向量集t d ，我们设法将其归入情况0 4 中的一种，以获得较大的循环粒度，并将循环写成可并行化的形式。如果相关向量 集t d 无法归入这五种情况之一，那么或者外层循环可以并行化，或者循环无法并 行化，或者无法再继续扩大循环的粒度。 2 5 非u 模变换 由上面的讨论可以看到，本文介绍的方法是w a v e f r o n t 方法的扩展，但是我们的 方法并没有完全覆盖w a v e f r o n t 方法的所有情况。这是由于w a v e f r o n t 方法还允许使 用一类n o n s i n g u l a rm a t r i c s ( 非u 模整数变换) 对迭代空间进行变换，获得新的并行 性。我们的方法同样适用于非u 模变换的情况，然而这种推广并非是简单的。丰要 的困难体现在非u 模变换更复杂的循环边界，这样合并后的循环边界将比i j 模变换 产生的循环边界更为复杂。如果要实现适用于非u 模变换的算法，需要参考文献【1 中9 ，7 1 中的有关内容，和本文的主要思想。 第1 7 页 椭环变换增加，f 行粒度年改善数据访问局爵怔r i 3 通过迭代空间分块增加数据局部性 3 1 u 模变换前通过结点合并增加数据局部性 通过u 模变换获得并行性虽然能带来扩大并行粒度的好处，但是也会对数据访 问的局部性带来不利的影响。一般而言，原程序的内层循环对数据的访问是遵循数 据相邻的原则的，这样在程序执行时一个c a c h e 块或者一个虚拟页面中的数据可以 被多次快速的访问，从而提高了程序的效率。然而在做过u 模变换和外层循环的结 点合并之后，原来相邻执行的迭代不再保持相邻关系，影响了数据访问的局部性， 对程序执行的效率产生了负面的影响。为了消除这种不利的影响，我们可以在u 模 变换之前，对内层循环的结点进行适当的合并，这样数据访问的局部性便可以在以 后的u 模变换和结点合并中一直保持。 内层循环的结点合并是非线性变换，然而在循环界限是固定界限的情况下，程 序的变换比较容易，给定初始的二重紧嵌套循环，和内层循环的合并度d ： f o r i = 0 t o “ f o rj = o t o u 2 2 州， e n d f o r e n d f o r 我们给出合并后的循环形式： f o r i = 0 t o “1 1 f o rj = o t ou 2 2s t e pd f o rk = ot om i n ( d 一1 ，u 2 2 一j ) h c ( ，i + k ) e n d f o t 第1 8 页 循环变换增加并行粒度年l l 改善数据访局部性 e n d f o r 合并后的相关向量集为d = s p l i t x ( d ) ( 见第一节中的定义) ，如果d 中含有非 法相关向量，那么合并失败，应当适当减小合并度。 我们把合并后的最内层循环看做外面两重循环的循环单元，把合并后的相关向 量集作为新的相关向量集，在这个循环和相关向量集的基础上做u 模变换和结点合 并，便可以在保持数据访问局部性的基础上达到并行化和增加循环并行粒度的目的。 也可以对迭代空间进行两个方向上的分块合并，使用s p l i t x ( s p l i t y ( d ) ) 计算合并 后的相关向量集。这样可以同时兼顾循环粒度和数据访问局部性，在得到合并后的 相关向量集后可以视情况进行w a v e f r o n t 变换。需要注意的是，这种合并方法产生 的结果和前面所讨论的利用u 模变换进行结点合并的结果是不同的。这种合并方法 产生的代码可以减少很多边界判断，但是局限性较大。主要体现为合并后的迭代空 间必须能够做w a v e f r o n t 变换，而单纯本节的分块合并方法往往不能产生适合 w a v e f r o n t 变换的相关向量集。 第1 9 页 循环变换增加卅彳粒度和改善数据访问局部性 4 整体实现与结论 4 1 一般的处理流程 我们给出一般情况下的循环并行化处理流程： 1 根据需要按照3 1 中的方法合并内层结点，并得到合并后的相关向量d 2 根据初始的相关向量集d ，利用2 4 中的方法确定相应的u 模变换t ， 获得满意的并行粒度 3 利用第2 3 节中的算法得到变形后的循环形式 4 将变形后的内层循环改写成并行循环 完毕 4 2 实验数据 我们通过i a p c mb e n c h m a r k 中的一个程序来说明本文方法的效果。y g x 是 i a p c m b e n c h m a r k 中的一个程序，它的计算模式是迭代一收敛计算模式。在y g x 中 存在一些两层紧嵌套循环，可以通过w a v e f r o n t 方法对内层循环进行并行化，例如 下面的例子 d 0 1 - - 1 md oi i = 2 m + n d o j = o p ld o a l l j 2 m a x ( 1 ，i i - m ) ，m i n ( n , i i - 1 ) a 0 1 ) = a ( j 1 ) + a ( j 1 o + a f j i - i ) i = i i j 七a q 1 七1 1 斗a q 七1 1 ) a ( j p = a ( j i ) + a ( j 1 i ) + a ( j f 一1 e n d d o 七a i j ，l + 1 ) 七a q 1 1 1 e n d d oe n d d o e n d d o a 。五点模式i ，- g z b 传统w 驯t o o n t 方法 第2 0 页 衙环变换增加并行粒度和改善数据访问局 ：f | i 什 在这种方法中，内层循环的迭代次数最多不超过m i n ( m ，n ) 。在y g x 中，外层 循环的迭代次数，只有三四次，因此使用这种方法将得不偿失，因为并行循环本 身的粒度太小。为此我们用我们的方法对循环进行结点合并和并行化。 我们将原循环转换为我们的标准形式： d o i i = 0 m 一1 d 0j j = 0 p 一1 i = i i + l j = j j a ( j ，1 ) = a ( j ，i ) + a ( j 1 ，i ) + a ( j ，1 1 ) + a ( j ，l + 1 ) + a ( j + l ，i ) e n d d o e n d d o 此时的相关向量集为： ( 1 ，o ) ，( o ，1 ) 在第六节的分析中我们知道此时为了达到并行粒度s ，应该采用u 模矩阵( 三i 对程序进行变形。根据第五节中的分析，此时程序变形为： d o i i = 0 ，m + s + p - ( s + 1 ) ，s d o a l l j j = m a x ( 一( m - 1 一i i ) s ，o ) ，m i n ( ( i i + s 一1 ) s ，p 一1 ) i = i i s * j j + i j = j j d o k = 0 s - 1 a ( j ，i ) ：a ( j ，i ) + a ( j 一1 ，i ) 十a ( j ，i 一1 ) + a ( j ，i + 1 ) + a ( j + 1 ，i ) i = l + 1 e n d d o e n d d 0 e n d d 0 简单的分析可以知道在这个例子中，第五节中变形后程序中的所有语句的判断 是恒成立的，所以可以忽略。 我们设定合并度为1 0 0 ，并在o r i g i n 2 0 0 四机系统上比较进行结点合并前后，程 序y g x 并行加速比的变化： 第2 1 页 循环变换增加升行粒度和改善数据访问j | _ = 6 部性 运行时间( 秒) 使用方法串行执行 串行执行 单机并行双机并行三机并行四机并行 原程序并行程序执行执行执行执行 结点合并 2 9 7