（计算机软件与理论专业论文）程序潜在最大并行性分析的动态实现.pdf

程序潜在最大并行性分析的动态实现 摘要j f i 6 94 s 并行程序设计环境提供了将自动化编译技术和用户干预相结合的一种手段 在并行程序设计环境中，为了使用户方便而有效地识别串行程序的潜在并行性， 我们设计了基于并行编译系统的一个辅助工具、该工具能够使用户了解需进行并 行化计算或分析的目标程序循环一级的最大并行程度。 我们采用的是动态实现程序潜在最大并行性分析的方法对于给定程序，该 方法可识别出所有可完全并行执行的循环，在此基础上，对于可并行化循环给出 该循环的私有变量信息，并能对判定的结果按过程调用环境不同进行分组汇报 这些信息能有效地指导用户改写原来的串行程序，产生更为高效的并行程序与 以往的方法相比，该方法对于多层嵌套循环以及跨过程的相关性分析都作了较完 善的处理我们已实现了这一方法，对一些应用程序作了测试，并给出了测试结 果来证明这一方法的有效性 关键诃并行程序设计环境， 并行编译系统，最大并行性，可完全装行循环，私 有变量 程序潜在屉太并行性分析的动态实现 a b s t r a c t p a r a l l e l p r o g r a m m i n g e n v i r o n m e n t p r o v i d e s a w a y t oc o m b i n ea u t o m a t i c p a r a l l e l i z a t i o nw i t hu s e ri n t e r v e n t i o n u n d e rp a r a l l e lp r o g r a m m i n ge n v i r o n m e n t ，w e d e s i g nat o o l ，w h i c h c a l la n a l y z el o o p l e v e lp o t e n t i a lp a r a l l e l i s mf o rf o r t r a np r o g r a m s o u r a n a l y s i sm e t h o di si m p l e m e n t e di nr u n t i m e a f t e rt h ep r o g r a m se x e c u t i o n w ec a ni d e n t i f ya l ld o a l ll o o p s ，f u r t h e r m o r ew ec a nr e c o g n i z et h ep r i v a t i z e d v a r i a b l e sf o rad o a l ll o o p a l s ow ep r e s e n tam o r es o p h i s t i c a t e dw a yt oh a n d l e i n t e r p r o c e d u r ea n a l y s i s a n dg r o u p e dt h ef i n a lr e s u l t sb yt h e i rc a l l i n gc o n t e x t s t h i s i n f o r m a t i o ni sv e r yv a l u a b l ef o ru s e r st ot r a n s f o r mt h es e q u e n t i a lp r o g r a m st om o r e e f f i c i e n tp a r a l l e lp r o g r a m s w eh a v ei m p l e m e n t e do u rm e t h o da n dg i v e t h et e s tr e s u l t t os h o wi t se f f e c t i v e n e s s k e y w o r d s p a r a l l e l p r o g r a m m i n ge n v i r o n m e n t ，p a r a l l e lc o m p i l e r , m a x i m u m p a r a l l e l i s m ，d o a l ll o o p ，p r i v a t i z e d v a r i a b l e 2 程序潜在最大并行性分析的动态实现 第一章绪论 第一节引言 现代科学技术、国民经济、工业生产与军事诸方面的高速发展，迫切需要 更高性能的计算机近年来并行计算体系结构得到了长足的发展，多种多样的 并行计算机不断涌现，运行速度的极限不断被新的并行计算机打破，并行计算体 系结构成为世界各国发展高性能计算机，解决“巨大挑战”问题( 即3 t 问题一 每秒一万亿次的浮点运算速度，一万亿字节的存储器，每秒一万亿次的通讯速度) 的主要途径未来单处理器芯片设计研究也大量采用并行结构来提高速度近年 来，由于c l i e n t $ e l - v e t 结构，i n t r a n e t 和电子商务的发展，并行计算机和松耦台的 计算机群集开始在商用市场获得越来越多的应用并行计算机的广泛应用，给我 们提出了这样一个问题：那就是如何正确，有效地使用并行计算机，充分利用并 行计算机的资源、发挥并行计算机的能力 传统的方法是：为每个应用开发并行程序并行程序，尤其是高效的并行 程序的开发、维护和移植，是极为困难的并行计算机的用户只有充分地掌握了 并行处理的概念，了解并行计算机的存储体系结构对于并行算法的影响，才能编 写出高教的并行软件但是大多数并行计算机用户并不是专业计算机研究人员， 掌握如此复杂的概念对他们来说极为困难，也没有必要即使对有经验的专业程 序员来说，编写高效可靠的并行计算机也是相当困难的，因为并行程序设计方法 与人类的顺序思维方式相背，使得设计并行算法比设计传统的串行算法复杂得多 也更易出错另外，并行程序的调试和排错也非常困难，因为并行程序的执行有 很大的不确定性和不可再现性 解决这个问题的有效途径是采用自动并行化编译系统 并行化编译系统是将串行源程序自动地变换为等价的并行源程序的编译器， 即以串行程序为输入，通过并行分析与优化，自动地把串行代码转化成显式的并 行代码它的主要优点有： 1 将大多数用户从复杂的并行程序编程中解脱出来，保持7 他们的串行程序编程 习惯，提高了软件生产率 2 保护了人类丰富的串行软件遗产一些程序库是过去几代人的努力结果，如果 程序潜在最大并行性分析的动态实现 将其付之一炬，重新进行并行编程，将是一项巨大的浪费 3 并行编译系统的研究将更清楚的界定并行语言，并行编译器及用户之间的关系 第二节本文的工作 在并行编译系统研究的基础上，我们可以进一步地提供并行程序设计环境 1 2 】， 它提供了自动并行化技术与适当的用户干预相结合的一种手段。并行化编译的核 心部分是相关性分析。然而，编译时进行的相关性分析一般都是比较保守的。并 行编译器只要发现对程序作并行变换会有可能违反数据相关或改变程序的语义， 它就不会对程序进行变换。在一些情况下，编译器报告出的相关性在实际运行时 是不可能发生的。在完全自动化的并行编译系统中，用户没有机会根据自己的 经验和常识对并行编译器报告出的相关性作出进一步分析，干预。并行化程序 设计环境则提供了将两者有机结合起来的一种途径对于那些一般常见的程序模 式，可由自动并行化编译系统来完成分析及变换，免去了用户大量不必要的重复 劳动。而用户通过并行化程序设计环境提供的辅助工具来对那些复杂的，由编译 静态分析只能进行保守估计的程序作进一步分析，并采取适当干预，这些干预往 往是通过用户对原程序插入循环断言或变量说明来实现。通过并行程序设计环 境，可以充分将用户的经验常识与自动并行编译进行结合，产生更为高效的并行 化程序。因此，结合对并行化技术的分析和研究而设计的高质量的并行程序设计 环境软件将能极大地推动并行计算机的应用，具有广泛的前景 在并行程序设计环境中，为了使用户方便而有效地识别串行程序的潜在并行 性 1 l 】，我们设计了基于并行编译系统的一个辅助工具，该工具能够使用户了解需 进行并行化计算或分析的目标程序循环一级的最大并行程度。该工具可以在程序 运行一次后，得到所有可完全并行化循环o a l l ) 的信息。同时还可以判断出任 意一个指定的d o a l l 循环需要私有化的变量。有了这些信息，用户可以直接 对原来的串行程序进行改写( 在原程序中增加d o a l l 循环断言和私有化变量说 明) 。 程序潜在最大并行性分析的动态实现 第一章， 第二章， 第三章， 第四章 第五章 第三节本文的组织 即本章，为绪论部分介绍了总体背景以及本文的工作。 介绍了并行编译系统a f t 以及a f t 系统中采用的并行化技术， a f t 的中间表示m ，作为我们以后算法实现的基础。 介绍了程序潜在最大并行性识别的基本思想，主要包括可完全并 行化循环的识别，私有变量的识别，以及过程间分析。 介绍了以上想法在系统中的具体实现，及组成系统的各子系统之 间相互作用关系，并给出了实验结果来证实本算法的有效性， 对系统今后性能的改进和功能的扩展提出了一些展望。 程序潜在最大井行性分析的动态实现 第二章并行编译系统概貌及a f t 系统 a f t 系统已有了十多年的历史，它庞大又复杂，但它是新代并行系统，它 充满了活力，因为p p i 成员一直致力于新技术的运用与开发 第一节并行化技术的研究 并行机的出现，使得如何提高并行机使用效率成为了热门课题并行编译系统 凭借种种优势，得到了研究者们的青睐并行编译系统的主要功能是将己存在的 串行程序进彳亍处理，识别并标记出其中的并行成分，将其转变为可充分利用并行 资源的并行程序 七十年代中期，dk u c k 与kk e n n e d y 开始了并行化的研究在相关性分析 与程序变换的理论基础上，在八十年代初产生了许多自动向量化系统在早期的 系统中，有p a r a f r a s e , k a p 【1 6 ，v a s t 【1 7 ，p c f , p t r a n 等，其中k 他v a s t 为 这一代系统的代表，并于八十年代中期进行了扩充，具有了一定的并行化功能九 十年代初，人们开始注意到这些早期系统中及早期技术中的一些缺陷，c s r d 的 w i l l i a mb l u m e 与r u d o l f e i g e n m a r m 在文献【l8 】中，对k a p , v a s t 两系统进行了 分析，并指出了它们的不足更为重要的是，他们还对一系列并行化技术用实际 的p e r f e c t 程序测试包进行了评估，这些技术包括：递归变量替代( i n d u c t i o n v a r i a b l e s u b s t i t u t i o n ) ，标量扩张( s c a l a re x p a n s i o n ) ，向前替代( f o r w a r d s u b s t i t u t i o n ) ，循环交换( l o o pi n t e r c h a n g e ) ，同步并行循环( s y n c h r o n i z e d d o a c f o s s l o o p s ) 。递归识别( r e c u r r e n c er e c o g n i t i o n ) , 归约语句( r e d u c t i o n s t a t e m e n t ) ，循环分块( l o o ps t r i p - m i n i n g ) 等实验结果表明，上述大部分并行化技 术并没有提高实际程序的加速比，仅标量扩张及归约语句两项技术对大部分程序 有很好的效果，而循环分块在多数程序中起了反作用 为了克服早期系统的缺点，在实际应用程序中开发更大的并行性，于九十年 代初，人们开始了新一轮的研究w i l l i a mp u g h 的欧米格测试( o m e g at e s t ) 1 9 ， u b a n e j e e 的单模变换( u n i m o d u l a rt r a n s f o r m a t i o n ) 【2 0 】，以及数组私有化 7 ，过 程繁衍【2 2 】等技术纷纷问世，此外，c s r d 中心继续进行他们的研充并在实验 结果的基础上，指出了一些在实际应用程序中需要的技术，其中包括动态测试， 4 程序潜在最大并行性丹析的动态实现 数组归约，数组私有化，广义递归变量等在采纳了上述技术之后，并行编译系统 的眭能有了明显的进步，在这个时期开发的系统有了p o l a r i s 1 5 ，s u i f 1 3 【1 4 及a f t 9 目前的v l s l 技术已经可以将相当1 0 至2 0 个微处理器集中到一个芯片上 硬件的高速发展推动了并行机的系统结构及软件的发展在系统结构方面，人们 提出了m u l t i s c a l a r 和s u p e r t h r e a d 两种并行机体系结构，它们最有望被下一代并行 机广泛采用在软件方面，人们对并行加速比的要求越来越高，使得研究者再次 进行新技术的探索 。 为了适应当今并行编译技术的发展，p p i 在一九九六年中期开始对s p e c 9 5 f p 程序测试包进行研究，试图从实际程序中得到启发，发展新技术于一九九七年 初，p p i 提出了对s p e c 9 5 f p 程序包中若干程序有效的技术，其中主要有：数组信息 传递，动态数据流分析，非循环级并行等 第二节并行编译系统中采用的主要技术 由于科学计算领域普遍采用的语言为f o r t r a n 7 7 ，所以并行编译系统的输 入一般为f o r t r a n7 7 源程序，经并行转换之后，其输出为针对c r a y , s g i ，银 河或其他并行机的并行f o r t r a n 语言 图1 并行编译系统的结构 ，一：2 7 竺t ! 。 f f lj 程序潜在最大并行性分析的动态实现 并行编译系统的主要工作是找出串行源程序的并行成分，并将串行程序转换为并 行程序图1 表示了并行编译系统的结构由于程序文本是无法直接处理的，我 们必须首先将源程序进行语法分析( p a r s e r ) ，生成系统中对源程序的中间表示 fi r ) 。以后系统中的各项分析将直接对该中间表示进行由于程序中主要的执行 时间都耗费在循环中，所以我们的分析是针对循环而言的在分析个循环的并 行性之前，我们还需要关于该循环的若干信息，譬如说，某数组是否私有，某变量 是否为常数，变量的各种数据流信息等等于是我们在测试循环中各变量依赖关 系( d e p e n d e n c et e s t ) 之前，我们还需要进行各种分析，如数据流分析( d a t a f l o w a n a l y s i s ) ，向前替代( f o r w a r ds u b s t i t u t i o n ) ，数组私有化分析( a r r a yp r i v a t i z a t i o n ) 等 等此外，在分析之前，为了简化及加速以后的分析，我们还需进行程序规范化 ( n o r m a l i z a t i o n ) ，以消除程序中一些特例，如：s a v e ，e n t r y , a r i t h f , 还将g o t o 语句 消除实现程序的结构化在得到了足够的信息之后，我们对该循环进行相关性 测试，判断该循环是否可并行为了获取更好的并行效果，我们还需要一些变形 技术，如循环交换，波前变换等等下面将对并行编译系统中些重要的技术逐一 简单的介绍 1 1 程庄趣堇丝 在早期f o r t r a n 7 7 程序中，存在许多g o t o 语句，它们提高了代码的利用 率及灵活性，但降低了程序的可读性，增加了并行编译中各技术的实现难度，我 们在程序规范化t 9 1 2 3 ，利用源程序的流图，将其结构化，消除了g o t o 语句还 有其他一些非规范语句，如e n t r y 、s a v e 、算术、计算g o t o 、赋值g o t o 等，由于它们在程序中出现的频率很低，所以我们在不改变其语义的情况之下， 用其它语句来代替这些非规范语句 垒) 过捏闻拉苤 早期的并行编译系统的一个重要缺陷就是忽略了对过程的处理，使得它们对 实际应用程序收效甚微高级语言强调程序的模块性，过程的广泛采用，使得过 程间技术迅速发展了起来 过程间技术的基本框架为信息在过程中的收集与过程间的传播由于 f o r t r a n 程序中不允许存在递归调用，故此它的过程调用为无圈图在过程调 用图上，我们进行自底向上与自顶向下的分析在自底向上的分析中，我们收集 6 程乎潜在最大并行性分析的动态实现 每一过程的信息，因为此时被该过程调用的过程的信息都已总结出来，也即已经 知道个调用点的行为，故此我们可以顺利的分析出该过程的信息而自顶向下的 分析主要着眼于信息的传播，因为我们需要将调用点的信息传到被调用的过程 过程间技术主要有过程间数据流分析，过程间向前替代，过程繁衍等 过程闻数据流分析 过程间数据流分析求出过程的暴露集合，确定写集合，可能写集合，读集合及 活跃变量集合过程间数据流分析是与过程内数据流分析相配合实现的过程内 分析得到该过程的部分数据流信息，由过程间分析将其总结并送至调用点，再进 行上层过程的过程内分析：或者，过程内分析得到该过程中调用点处的数据流信 息，由过程间分析将其送至被调用过程，再进行下层过程的过程内数据流分析 过程间数据流分析为相关性分析，过程间向前替代，数组私有化，死码删除等奠 定了基础 过程间向前替代 文献【2 1 】提出了过程间向前替代的算法框架，实现了过程间的向前替代过 程间向前替代包括两部分的信息传递，头信息( t o pi n f o r m a t i o n ) 与返回函数( r e t u r n i n f o r m a t i o n ) 头信息为由调用点传至过程的约束条件，它由过程内向前替代及总 结实参间关系两种渠道而得对一程序单元来说，头信息为一由虚参组成的线形 表达式的集合，它是过程内向前替代的起点返回函数描述了被调用过程的行为， 当然，过程本身是对过程行为的最佳描述，而返回函数尽可能描述被调用过程的 部分行为返回函数由被调用过程传至调用点，以帮助调用过程的过程内向前替 代在向前替代过程中，由于信息的传递，我们可以同时做一些变形，如语句 消除，递归变量识别等等由于信息的传递与这些变形是交互影响的，所以它们 需要数次迭代才能稳定 过程繁衍 当过程调用的环境( c o n t e x t ) 不同时，为不同的环境产生不同的过程版本，成为 过程繁衍该技术开销比过程嵌入( i n l i n e ) 小，而比简单的过程间信息传递更精确 文献 2 2 1 对过程繁衍有前面的介绍传统技术仅处理实参为常数值的情况，a f t 提 出了更为一般的方法，它可分析实参之间的线性关系，将这些等式约束传递到多 版本中。从而增强系统跨过程的符号分析能力，有助于相关性分析，变量私有化 7 程序潜在最大并行性分析的动态实现 等 墨1 担差世型达 相关性铡试为自动并行化的基础，并行识别及多种并行变换都需要用到相 关性信息相关性测试的主要难点为数组相关性测试，数组相关性测试的基本问 题为判断在一个嵌套循环中同一数组的两次出现( 其中一次为写) 之间是否存在 相关，即是否会对同一地址( 数组下标) 进行操作由于数组下标可以看成是循 环下标的函数，所以上述问题可以看作一个判断满足一定的约束条件的丢番图方 程是否存在整数解的问题下面我们对不同的相关性测试技术进行分别介绍 g c d 测试 g c d 测试是最简单的一种测试方法 若一整数方程 a l x l + a 2 x 2 + + a r 矗= c 存在整数解，则g c d ( a ，a 2 , 一，a n ) 必能整除c ，否则肯定没有整数解 基于上述定理，g c d 测试对每个丢番图方程考察其系数的最小公约数是否整 除c 若有一个丢番图方程不满足该条件，则必然没有整数解，也即相关性不存在， 否则就假设相关性存在 b a n e r j e e 测试 b a n e r j e e 测试【2 0 】是被许多并行系统广泛采用的一种测试方法它的实现很 方便但它的测试范围并不是很广泛，同时也不是很精确其实现方法如下 对一整数a 记a _ = m a x ( a , 0 ) ，a _ = m a x ( - a o ) 那么，我们有 若p x q ，贝0a + p a - q a x a q a - p 若对i = l ，2 ，n ，有p i x i q 。，则 m1 1 1m e ( 4 + p 。一巩一q ，) x ) t h e n a = b + c e n d i f d = a + e s 1 s 2 ，s 3 s 4 s 5 圈1 1 由于现有计算机系统在编制操作一级或语句一级的并行程序方面存在许多困 难。但对大多数应用程序而言，主要的计算量都集中在d o 循环中。所以人们对 程序的并行性分析的注意力已集中到对d o 循环的并行性分析和识别上。在对d o 循环的并行性分析上，存在着两种方向：一是识别d o a c r o s s ；一是识别 d o a l l 。d o a c r o s s 的执行方法是d o 循环中所有循环实例都并行地执行，而 每个循环实例的所有语句是串行执行的。但是，由于不同的循环实例中的变量有 可能存在数据相关性，所以要求机器在执行d o a c r o s s 时对有数据相关的变量加 一些同步控制f 通讯) 以保证结果的正确性。d o a l l 的执行方法是完全的并行执 行，不需要加同步控制。d o 循环的所有循环实例并行执行，而每个循环实例中 的语句串行执行。目前并行处理机系统在执行d o a c r o s s 时效率不高，编程难度 大，但对执行d o a l l 贝t j 都提供了充分的支持，相对而言处理也较容易。因此，我 们的工作重点就放在对d o a l l 循环的分析和识别上。 p a u d a 毛e 4 1 提出了一种分析d o a l l 循环的方法。 该方法是在运行时实现 的，对指定循环的变量赋值语句用一些标识语句来替换，实际运行后判断这一循 环是否可以执行d o a l l 但这一方法只能处理指定的一层循环，不能一次识别出 所有的d o a l l 循环，而且对于过程调用等情况没有作很好的解决，其实用性受到 很大的限制。 本文中我们实现的是一个在并行编程环境下进行程序潜在最大并行性分析的 辅助工具。它能在程序运行时对程序中的d o a l l 循环及私有变量进行识别。 该方法主要基于数据流计算机的思想、在程序动态执行的过程中，判断d 0 循 环的迭代间是否存在数据相关性来确定是否可以执行d o a l l 操作。程序执行结 束后，我们就可以识别出所有可执行d o a l l 的循环。在此基础上，我们还对任一 指定的d o a l l 循环判断出需私有化的变量，并能对判定的结果按过程调用环境不 】4 程序潜在最大并行性分析的动态实现 同进行分组汇报。与以往的方法相比，该方法对于多层嵌套循环以及跨过程的 相关性分析都作了较完善的处理。 第二节循环并行性 循环可以不需同步而完全并行执行的充要条件是循环执行的预期结果不以任 何方式依赖于不同的循环实例的执行顺序为了判断循环实例的执行顺序是否会 影响原有循环的语义，必须分析循环体语句间的数据相关性在两个语句之间可 能存在3 种类型的相关性：流相关( 先写后读) ，反相关( 先读后写) ，输出相关( 先写 后写) 流相关是数据的生成和引用的相关性，它反映了程序中数据流最基本的关 系反相关和输出相关是与存储器有关的相关，由存储单元的重用产生 如果循环的不同迭代间存在流相关，那么该循环以完全并行的方式执行 ( d o a l l 方式) 就不能保证原有程序的语义未被改变这样的循环迭代间不是完全 独立的，因为有些值在其中的一些迭代中生成，而在以后的实例中又被引用到如 图2 1 循环( a u o 计算数组a 的总和由于第+ 1 个实例需要用到第i 个实例生成的值， 其中2 i n + l ，所以此循环必须按照原来的程序串行地执行 d oi = 2 1 0 0 s 2 ：a i l = a i 1 l d oi l in s 2 ：a i 】= 2 + a i 1 e n d d oe n d d o f b ) 图2 1 d o i = l ，n 2 s l ：t r a p = a 2 + i 1 s 2 ：a 【2 + i 】= a 2 + i l 】 s 3 ： a 2 + i - i - - t r a p e n d d 0 ( c ) 原则上，如果不存在跨循环的数据流相关，循环就可以完全并行地执行。最简单 的情况就是流相关，反相关和输出相关都不存在。在这种情况下，循环中的所有 实例都是独立的，循环也就可以完全并行执行例如，循环( b ) 就不存在任何跨循环 的相关性此循环的实例i 只对数组元素a 【i 】进行引用和赋值，l i n 如果循环中 不存在跨循环的流相关，但是存在跨循环的反相关或输出相关，我们在这些迭代并 程序潜在最大并行性分析的动态实现 行执行前必须对循环体进行修改膝去这些非本质的相关性为了除去这些反相关 和输出相关，我们通常采用对循环体内有关变量进行私有化的方法私有化方法使 执行循环的每个处理器都得到引起反相关和输出相关的变量的私有拷贝如所示 的循环( c ) 中，对每个偶数值i ，将数组元素a 【l 】和a i - 1 1 进行互换在循环实例i 的 语句s 3 和循环实例( i + 1 ) 的语句s l 之间存在反相关，1 i n 2 但我们可对临时变 量t m p 进行私有化而消除这一相关这一循环在进行私有化后就可以并行地执行 了 从上述讨论中可以看出，要开发程序循环一级的并行性，首先应识别出哪些循 环可以完全并行执行，即分析循环实例间是否存在跨循环的流相关在识别可完 全并行的循环f 即d o a l l 循环) 的基础上我们还需判断出指定的循环中哪些变量 是可私有化的，并把这些边量标志出来而这一步中，因为我们己知道指定的循环 没有跨循环的流相关，所以只需分析跨循环的反相关和输出相关以标志私有化变 量 第三节d o a l l 循环的识别 对d o a l l 循环的识别我们采取运行时分析的策略，主要基于以下想法：对 一给定的f o r t r a n 源程序p ，我们为其增加修改一些新的语句( 这些语句均为对 分析算法的调用) ，从而得到经过变形的f o r t r a n 程序p 1 对程序p 经过编译和 执行后就可以得到原程序的执行结果和我们需要的d o a l l 循环的信息对于 原程序增加和修改的目的是使在程序执行时调用判断循环迭代间是否存在流相关 的算法，这些修改并不改变原有程序的语义和执行结果。下面我们具体说明原程 序所需的变换以及分析算法的作用 3 1 映射变量 对程序p 中所使用的每个变量，在新程序p 中都要增加两个相应的映射变量： “写映射变量”和“读映射变量”，用于记录相应变量最近一次被修改的时间以及被 1 6 程序潜在最大并行性分析的动态实现 引用的时间多维数组的映射变量是两个具有相同维数和上下界的多维数组，用 于记录每个数组元素的两个相应时间值 对映射变量的命名规则是写的映射变量前面加“t 、矿，读的映射变量前面加 “t r ，例如a 的映射变量分别为t w a , t r & 数组元素b g 的映射变量分别为 a m r b i ，t r b i 32 映射变量的说明及其作用 对于映射变量，由于所记录的值主要用于判定在d o 循环中读，写同一变量 时间的先后，为了便于实现，可毗将映射变量的值只记录到循环迭代的数目而不 去记录绝对的系统时间值考虑到某些实用程序的计算量很大，执行时间会很长， 映射变量的值也会变得很大为了对映射变量进行修改时减少误差和防止上溢， 我们将映射变量说明成双精度型 所有映射变量的初始值都置为0 此外我们需要定义一个全局“时间”变量t ， 用于记录整个程序执行到现在已经经过的循环迭代的个数，变量t 在程序开始为 0 ，每经过一个循环迭代该值加1 这样每个变量写映射变量和读映射变量所记录 的值即为程序运行到该点时t 的值在以下的文章中，我们以t 值来代替系统时 间 我们判断数据流相关是通过写映射变量实现的如图31 所示循环，数组元 素a i 建立的相应的映射变量t w a i 进入d o 循环的相对初始t 值为1 ，对于 迭代1 的s 1 ，a 1 1 被赋值，t w a 1 等于1 对于第二次迭代的s 2 语句，a 1 】被 引用，我们可以比较a 1 】的映射变量t w a i 的值，如果t w a 1 大于等于进入 该循环的初始t 值l 且小于进入当前迭代的初始t 值2 ，说明该变量存在跨循环 迭代的先写后读的流相关，这一循环也就不能进行d o a l l 操作 d o i = 1 ，1 0 0 a i i = b 【i 】 s i c 田= a i - l 】 s 2 e n d d o 图31 而读映射变量主要用于识别私有变量，我们在第四节中再进行叙述。 1 7 程序潜在最大并行性丹折的动态实现 34 对嵌套d o 循环的处理 在以上讨论映射变量的作用时，我们已经知道如何判断循环间是否存在数据 相关，从而判断出是否可执行d o a l l 这一方法要求知道进入该d o 循环的初始 t 值以及当前循环实例的t 值由于我们要在程序只执行一次的情况下，识别出 所有能进干亍d o a l l 操作的循环，因此要对嵌套循环进行特别处理，具体识别出 哪层循环可以并行执行，哪能不能并行对图3 2 所示的嵌套循环，虽然内层循环 每次都可以执行d o a l l ，而外层循环由于存在跨循环的流相关不能执行 d o a l l 。要求我们在程序运行时能同时对这两个循环进行判断 d o i = l ，1 0 0 d o j = l ，1 0 0 a i ，j 】= b i , j 】 s l c 【i ，j 】= a 【i - 1 ，j 】 s 2 e n d d o e n d d 0 图3 2 首先，为了能在最后的输出结果( 以外部数据文件方法保存) 中区分不同的循 环我们对每个d o 循环进行标记，区分的标准是d o 循环所在的子程序名和d o 语句的标号其次，对每个d o 循环都设置两个域来记录进入该循环的初始t 值 以及当前循环实例的t 值，同时还应设置一个标志用于记录该层d o 循环是否可 执行d o a l l 的判定结果 为了处理多层嵌套的d o 循环，需建立一个用于进行分析的d o 栈，程序每 进入一层d o 循环，该d o 数据单元入栈，程序退出循环，相应的d o 数据单元出 栈。栈中保存的即为程序当前分析d o 循环所在的嵌套层次对于循环体内的所 有语句，对语句中读变量进行流相关判断，具体作法是：取出其对应的“写映射变 量”，分别与栈顶d o 所记录的两个时间标志进行比较，如果介于两者之间则说明 该读变量是在本d o 循环的以前迭代中被修改的，存在跨循环的流相关，置该层 循环的d o a l l 标志为假如果小于该d o 的初始时间，则说明该变量为此层d o 循环以外所写，可与栈中下一个d o 单元( 即此层循环的外层d o 循环) 的两个时 间标志进行同样比较，标志，直至栈底。 程序潜在最大并行性分析的动态实现 在以后的分析中若发现栈顶的d o 循环已被标记为不可并行，则可不再继 续对该循环体中的语句进行相关性分析，这样做可减少系统运行的开销。 3 5 特殊情况的考虑 3 5 1 归约变量的考虑 循环中存在归约变量时会影响找们对循环的d o a l l 分析我们的系统中 可利用编译器静态分析得出的归约变量信息，在归约变量所在的循环中对它的弓 起的数据相关性不作考虑，因此对该变量的读、写操作均不作分析和判断。 35 2g o t o 语句 f o r t r a n7 7 程序中，存在大量的g o t o 语句，g o t o 语句在早期的程序编 制中，担任了重要的角色然而，程序中存在g o t o 语句却会影响我们对嵌套d o 循环d o a l l 操作层次的判断，利用了a f t 程序结构化模块的作用，经过c l e a n u p 阶段后，生成的中间表示( u 中彻底消除了g o t o 语句 3 5 3 c o m m o n ，e q u i v a l a n c e 语句 f o r t r a n 7 7 程序中，用e q u i v a l e n c e 语句建立同一程序单位内的数据联 系c o m m o n 语句建立不同程序单位之间的数据联系程序中存在这两类语句为 我们处理每个变量对应的映射变量之间的关系带来了麻烦。为了简单起见，本系 统采用的方法是为对应的映射变量也产生相应c o m m o n , e q u i v a l e n c e 声明 语句，在映射变量之间也建立同样的数据联系。 1 9 程序潜在最大并行性分析的动态实现 第四节私有变量的识别 在识别出d o a l l 循环的同时，我们的系统可以对每个指定的d o a l l 循环 识别出所有需要私有化的变量私有化试图识别满足下列条件的变量：一旦它们 所对应的存储位置在某一次迭代被读取，所读取的值是已在同一迭代中被计算出 的这些变量所引起的跨循环相关可以通过将这些变量变换为私有变量来消除 从前面的讨论中可以知道，进行私有化变量识别时需要判断跨循环的数据 反相关( 先读后写) 和输出相关( 写写相关) 因而私有变量分析只需对循环体语句的 被写变量进行判断这两类的相关需要同时分析变量的两类映射变量，如图4ls 2 语句，需分析变量x 对应的映射变量t w x 和t r x d oi = 1 i i x = b 1 1 】 s 1 c i i = x s 2 e n d d o 图4 1 对该循环进行私有变量识别的具体作法是：将语句s l 中的写变量x 的映射 变量t r x , t w x 分别与进入循环的初始t 值和进入当前迭代的初始t 值进行比 较，如果t r x 介于两者之间，则变量x 存在跨循环的反相关，如果t w x 介于 两者之间则说明存在输出相关。如本例中，执行到本循环的第2 次迭代的语句s l 时，t r x 为l ，介于两个初始t 值之间，说明存在先读后写相关所以变量x 需要 私有化 事实上，还存在一类特殊的情况：如果一个变量在一次循环迭代中是先被读 的，然而所有前面的迭代都没有对它进行写操作，说明此变量是在循环以外赋的值 该变量可以通过“c o p y - i n ”循环外面值的机制来被私有化我们的算法对于这些变 量同样也可以进行识别只需根据该变量写映射变量记录的值，若该值小于进入 d o 循环时的初始t 值，则说明它是在循环外被赋的值，可以通过“c o p y - i n ”机制 将其进行私有化 2 0 程序潜在最大并行性分析的动态实现 第五节过程间分析 5l 过程间数据流分析 由于在d o 循环中会包含一些子程序的调用，要保证d o a l l 分析结果的正确 性，必须进行过程间数据流分析， 对于图4 1 ( a ) 的d o 循环，s 1 语句调用了子程序s u b l ，而s u b l 中的变量a 是我们跨循环数据流分析的对象，因此，必须在调用点将所有参数的映射变量也 作为参数传入子程序处理过后的例子如循环( b ) 所示在子程序中对变量a 读、 写的地方用映射变量t w a , t r a 进行分析 d oi = 1 r ld o 1 = 1 1 3 s 1 ：c a l l s t m l ( a ) s 1 ：c a l l s u b ( a t w a , t r a ) e n d d 0 ( a ) 图5 1 e n d d o ( b ) 52 过程繁衍 对于过程调用作更进一步分析，由于子程序中可能包含d o 循环，同一个子 程序可能存在不同的调用点，多个调用语句会向其传递不同的i n ，可能出现在某 些调用点上某一循环可以执行d o a l l ，而在另外的调用点上却不行的情况。 因 此即使对于同一个过程中的d o 循环，它是否可以执行d o a l l 操作，以及对应 的私有变量也会因调用环境不同而不同。所以需要将同一个循环的分析结果按 照该循环所在子程序的调用路径不同分组，分别进行处理。 将循环的判定结果按过程调用路径分组汇报，这样做对于今后用户以过程繁 衍的方式改写源程序是十分有帮助的。过程繁衍就是将调用环境按一定的原则 分类每一类的调用环境合并得到这一类调用点的公共调用环境。 根据调用环 境的分类，产生过程的多个副本，对这些副本进行过程嵌入。该技术开销比过程 2 l 程序潜在最大并行性分析的动态实现 嵌入小，而比简单的过程间信息传递更精确。实践证明，过程繁衍的方法对提高 程序的并行性是很有效的。 为了实现这一点，我们在程序运行时专门设立了一个用于进行过程分析的栈， 每遇到过程调用c a l l 或f u n c t i o n 语句，相应过程名入栈，调用结束后，过程 名出栈。这样，栈中自底向上的过程名的变化过程反映了程序执行时过程调用 路径的变化。记录分析结果时可以此作为区分调用环境的依据。 程序潜在最大并行性分析的动态实现 第四章算法的组成及实现 由以上的讨论可咀看出整个算法可以分为三部分： 一个动态分析子系统，是由各分析算法组成的在动态链接入程序的函数库， 用来在程序执行时识别d o a l l 循环以及私有变量 一个辅助性插入子系统，用来在源程序需要进行分析的地方插入对动态库 中算法调用的语句 一个输出子系统，将分析的结果以友好的形式向用户报告，来对用户改写 程序给出辅助性指示 三个子系统相互配合，彼此作用关系如下图所示 输 出 弋7 输出子系统 第一节插入子系统 1 1 插入子系统的主要模块 插入子系统的功能是对原有程序进行变形，插入对动态分析算法调用的语句 的过程插入子系统的主要流程为： 程序潜在最大并行性分析的动态实现 2 泽t ，映射变量的初始_化_ 上 对程序体自顶向下分析i 1 人 n y 上 插 p r o c 栈维护的算法i 。j 人 d o 循环7 h 、y 广 上 1 插入d 0 栈维护语句 2 分析循环体语句， 插 相关算法 下面对各模块的具体功能进行描述： t 变量，映射变量的声明。 t 变量的说明，为程序中的每个变量说明对应的映射变量 程序潜在最大并行性分析的动态实现 对于c o m m o n ，e q u i v a l e n c e 语句中的变量，为其对应的映射变量也产 生相应c o m m o n ，e q u i v a l e n c e 声明语句，在映射变量之间也建立同样的数 据联系。 t 变量，映射变量的初始化 将t 变量及映射变量赋初值0 p r o c 栈维护语句 在整个程序的过程调用语句前后增加处理语句( 过程单元迸栈，出栈) d o 栈维护语句 在整个程序中的d o 循环前后增加处理语句( d o 数据单元进栈，出栈) 对于循环体内语句的处理： t 变量的修改与记录 记录进入该d o 循环的初始t 值， 在每次迭代实例开始，t 值加l ，并记录该值至d o 数据单元 法 对于循环体语句中的读变量： 若该变量为标量，则在该变量前插入对该变量进行流相关分析的算法 若该变量为数组元素，则 a 在该数组元素前插入对该元素进行流相关分析的算法 b 对于数组中的所有下标变量，都作为读变量，插入进行流相关分析的算 分析完毕后，将当前t 值记录到各变量对应的读映射变量中 对于循环体语句中的写变量： 若该变量为标量，则在该变景前插入对该变量进行私有变量分析的算法 若该变量为数组元素，则 a 在该数组元素前插入对该元素私有变量分析的算法 b 对于数组中的所有下标变量，都作为读变量，在其前面插入进行流相关 分析的算法 分析完毕后，将当前t 值记录到各变量对应的写映射变量中 程序潜在最大井行性分析的动态实现 对于循环体中的过程调用语句：c a l l 语句，f u n c t i o n 语句 将所有参数的映射变量也作为参数传入子程序若参数为标量或数组元素 所以只需直接将其对应读写映射变量传入，若参数为整个数组，则应将其对应的 整个映射变量数组传入 1 2 插入子系统的实现： 具体实现时，插入子系统充分利用了我们开发的并行化编译系统a f t 经过语 法分析后产生的中间表示( i n t e r m e d i a t er e p r e s e m a t i o n ) ，在其中插入所需语句的结 点，则经过a f t 编译后的源程序即为变形后的程序 第二节分析子系统