（计算机系统结构专业论文）openmp到mpi转换中的数据流分析技术.pdf

o p e n 抽到m p i 转换中的数据流分析技术 摘要 m p p 和机群计算是当今并行计算的主流，它们都基于面向消息传递 的标准m p i 或p v m 。而当m p p 和机群计算显示出强大的扩展能力的同 时，我们不得不面对面向消息编程是一个艰难而复杂的任务这一事实。另 一方面，s m p 曾一度叱咤风云，现存大量基于内存共享o p e n m p 规范的 并行程序。可见对于o p e n m p 到m p i 转换的研究相当有意义。 通过并行变换来得到m p i 程序，完全以程序的数据流信息为依据； 尽可能准确的数据流分析结果，意味着尽可能多的并行性被挖掘，这样全 局一致的数据划分才有可能取得。 本篇论文描述的是一种为取得全局一致数据划分的数据流分析方法的 研究成果，较之a f t 系统中的s m p 并行分析方法，它在两方面得到增 强：一、利用数组生命期分析的方法给并行变换模块提供比较精确的和更 多的相关性信息：二、利用过程间相干的测试方法给公用块复制提供依 据。在复旦大学a f t 0 4 系统中，该算法得以实现，通过对s p e c 9 5 、 s p e c 2 0 0 0 等b e n c hm a r k 中部分程序的测试得出比较满意的结果。 关键字 m p i ，并行变换，数据流分析，数组生命期，数据划分 o p e n 岫到m p l 转换中的数据流分析技术 a bs t r a c t m p pa n dc l u s t e r sp r e v a i li nc u r r e n tp a r a l l e lc o m p u t i n g t h e i r s t a n d a r di sm p io rp v m ，w h i c ha r eb a s e do nm e s s a g e o r i e n t e d m p p a n dc i us t e r ss h o wp o w e r f u la b i l i t yo fe x t e n s i o nw h i l ei tisaf a c t t h a tt op r o g r a mw i t hm e s s a g e o r i e n t e ds t a n d a r di sac o m p l e xa n d t o u g hw o r k o nt h eo t h e rs i d e ，s m pp r e v a i l e df o rat i m e ，t h e r e r ea l o to fp a r a l l e lp r o g r a m sw i t ho p e n m ps t a n d a r db a s e dons h a r e d m e m o r y s oi t i sm e a n i n g f u lt or e s e a r c hont r a ns 1 a t i o nf r o m o p e n m pt om p i t h em p ip r o g r a mw ew a n tt oa c h i e v ef r o mp a r a l t e l t r a n s f o r m a t i o nd e p e n d sont h ei n f o r m a t i o n0 fd a t af l o wo ft h e pr o g r a mt o t a l l y t og e tt h ee x a c tr e s u l to fd a t af l o wa n a l y s i sm e a n s t h ep a r a l l e l is ms h o u l db ed i ga sm o r ea sp o s s i b l e a sar e s u l t ， t h e r e sap o s s i b i l i t yt h a tw ec o u l da c h i e v eg l o b a lc o n s i s t e n c yo f d a t ap a r t i t i o n t h es t u d yd e s c r i b e sa na p p r o a c ho fd a t af l o wa n a l y s i st oa c h i e v e t h eg l o b a lc o n s i s t e n c yo fd a t ap a r t i t i o n c o m p a r e dw i t ht h ep ar a l l e l a n a l y s i so ns m pi na f ts y s t e m ，t h ea p p r o a c hh a sb e e ne n h a n c e di n t w oa s p e c t s f i r s ti st ot a k ea d v a n t a g eo ft h ea n a l y s isonar r a y1 i f e c y c l et op r o v i d em o r er e l a t i v e l yp r e c i s ei n f o r m a t i o no fd e p e n d e n c y t ot h em o d u l eo fp a r a l t e lt r a n s f o r m a t i o n s e c o n di st ouset h et es to f i n t e r v e n t i o nb e t w e e np r o c e d u r e st og e tt h ef e a s i b i i i t yo fc o m m o n b l o c kc o p y w ei m p l e m e n tt h ea l g o r i t h mi nf u d a nu n i v e r s i t ya f t 0 4 s y s t e m ，w h i c hp er f o r m sw e l lo ns e l e c t e db e n c h m a r k si ns p e c 9 5 ， s p e c 2 0 0 0 ，n a s ae t c 8 o p e n 如到m p i 转换中的数据流分析技术 k e y w o r d s m p i ，p a r a l l e lt r a n s f o r m a t i o n ，d a t af l o wa n a l y s is ，a r r a yl i f e c y c l e ，d a t ap a r t i t i o n o m m l 怕到咿i 转换中的数据流分析技术 第一章引言 1 1 并行编译研究的历史和现状 当初发明计算机的那一代科学家绝对不会料想到，现在的计算机单机 性能可以达到如此惊人的地步并依然以摩尔定律保持快速的发展。然而我 们可以发现计算机单机性能的飞速增长依然无法满足人们在科学和工程计 算中的需求：另一方面随着物理上极限的日益逼近，摩尔定律不可能一直 保持下去；此外嵌入式芯片由于对低功耗的要求，芯片的频率不能设计得 过高。于是计算并行化将逐渐成为提高计算机性能的主流。 1 1 1 并行计算机一一m p p 是超级计算机主流 我们可以发现当今世界上最强大的超级计算机都是使用了并行体系结 构，以大家熟知的i b m 的与世界棋王卡斯帕罗夫战成平手的“深蓝”为 例。该超级计算机的最新型号是一种3 2 节点的i b m ( s p ) 计算机。每个 节点的s p 使用的装有8 个专用的v l s i 国际象棋处理器的单一微通道 卡，总共有2 5 6 个处理器并行运行。这种网络是可扩充的并行系统，它 能在标准国际象棋比赛中为选手每步所分配的3 分钟内计算出5 0 0 亿至 1 0 0 0 亿步。 2 0 0 2 年4 月1 8 日，日本n e c 宣布，他们研制成功“地球模拟者” 超级计算机。采用了5 1 0 4 个处理器的“地球模拟者”达到了每秒35 6l 万亿次的浮点运算速度，成为当时世界上最快的超级计算机。 直到2 0 0 4 年月8 曰，i b m 宣布其16 个机架的i b me s e t v e r b 1 t i eg e n es 0 1 u t i o n 超级计算机以每秒7 0 7 2 万亿次浮点运算速度创 造了新的世界纪录，成为全球最强大的超级计算机。在位居“超级计算机 5 0 0 强”排行榜榜首2 年半后，n e e 公司研制的“地球模拟者”终于被 赶了下来。i b b l 公司的b 1 u eg e n e l( 蓝色基因) 正式成为了超级计 算机市场上的新王者。 0 p 和到舯i 转换中的数据流分析技术 b lu eg e n e l 这个超级庞然大物拥有3 2 0 0 0 颗处理器，i b m 的原型 机用l in p a c k 基准进行了基准测试，测试结果达到每秒7 0 7 2 万亿次运 算( 7 0 7 2 t f l 0 p ) ，几乎是“地球模拟者”3 5 9 t f l 0 p 的2 倍。 在美国劳伦斯一利弗莫尔国家实验室，科学家们利用“蓝色基因” 从事宇宙领域的研究工作。研究恒星双星组、激光等离子体交互作用的行 为以及高爆现象的行为及演变。 日本国家先进工业科技学院购买了“蓝色基因”通过模拟的方法，研 究d n a 中的基因信息是如何成为构成蛋白质的“积木链”的。 此外，“蓝色基因”的客户还包括美国能源部国家核安全局、 h s t r o n 射电望远镜计划、阿尔贡国家实验室等机构。 1 1 2 并行编译技术 我们在使用并行技术中遇到的最大问题是，如何正确而有效地使用并 行计算机，充分利用并行计算机的资源、发挥并行计算机的能力。容易理 解，一个拥有16 个处理器结点的并行系统，通常情况下不可能产生1 6 倍的加速比，这是由程序对象的并行性、处理器协同机制等因素所限制。 在并行机上运行，我们必颓编写并行的程序编写并行程序与编写串行程 序相比，其程序的移植、维护、调试等方面均非常困难，最困难的是要求 程序员有充分的并行处理概念，程序员只有掌握了诸如：多处理、私有变 量、同步、多级存储等概念后才能编写出高质量的并行软件。而现在一般 的并行计算用户都是进行科学研究的，并非专业计算机研究人员，让他们 掌握如此复杂的概念意义不大。现在国外有些机构，在进行并行程序设计 时，往往分为两步，第一步由科学工作者编写串行程序，然后由计算机和 计算数学工作者将串行程序改写为并行程序。 进行上述第二步的代价是昂贵的，替代这步骤的一条可能途径是使用 并行化编译系统。并行化编译系统是一个可以将串行程序自动地转换为等 价的并行程序的编译器。虽然并行化编译技术有一定的局限性，但它始终 是并行计算机系统中最重要的程序开发工具之一。这是因为：首先，由于 并行化编译系统的使用，用户可以继续保持原有的串行程序设计习惯，继 o p e n 到咿l 转换中的数据流分析技术 续使用他们熟悉的编程语言( 如f o r t r a n 和c ) 进行程序设计，从而使开 发出的程序更易于移植、调试和维护。其次，由于并行化编译系统提供的 有效分析功能可以为用户提供有用的信息，从而有利于用户改善程序的性 能，因此高效能的并行化编译系统是并行计算机系统上开发高效软件的基 础，一切并行程序开发工具和环境都必须依靠并行化编译技术。最后，并 行化编译技术的研究可以为并行语言的设计提供依据并有效的界定语言、 编译和用户的责任。 并行化编译系统是伴随超级计算机的出现应运而生的。迄今为止超级 计算机经历了向量机、s m p ( 对称多处理机) 和m p p ( 大规模并行处理 机) 三个阶段，超级计算机的主要应用领域是科学与工程计算，这些计算 需要耗费大量的c p u 和m e m o r y 资源。并行化编译系统从商业角度来看 只在向量机上取得了成功，而对s m p 则只在某学术系统上取得了初步成 功，对m p p 而言它还相当不成熟，有很多人甚至认为它永远不能成功。 1 1 3 并行编译技术随着并行计算机技术的发展 v e c t o rm a c h i n e ( 向量机) 一一向量化编译的研究可追述到七十年 代中期超级计算机的出现。在向量化编译的研究中，d a v i dk u c k 教授的 研究小组研究了实用的相关性测试方法，完善了相关性概念，并于七十年 代末完成了第一个真正意义上的向量化编译器，但效果并不令人满意。到 八十年代初，由于实验工作进展良好，向量化编译技术逐渐成熟。值得一 提的是，由于可向量化的对象是程序中的最内层循环，向量化编译系统只 开发小粒度并行性，其分析范围可以非常局限，所以实验工作的研究对象 也相对简单，实验工作很容易展开。 s m p ( s y m m e t r ym u l t i p r o c e s s o r ，对称多处理机) 一一较之向量 化，基于s m p 的并行处理要复杂许多。九十年代初，l l l i n o is 大学的 c s r d 开展了实验性研究工作，这次的研究目标是针对s m p 的并行化编 译技术。他们在分析了一些程序后指出：数组私有化、归约识别、非线性 递归标量识别、符号数据相关性分析和过程间分析是非常重要的并行化技 术。这些新的方法对一些实用程序非常有效，并且具有相当大的代表性， 0 0 e n m p 到t l p l 转换中的数据流分析技术 是新的并行化编译系统设计时必须考虑的问题。九十年代中，出现了 i l l i n o is 的p o l a r is 、s t a n f o r d 的s u i f 和复旦大学的a f t 等s m p 的并 行化编译系统。这些系统的并行化效果有了明显提高，并行化编译的研究 又达到了一个新的高潮。 m p p ( m a s s i v ep a r a l l e lp r o c e s s o r ，大规模并行处理机) 一一较之 s m p ，m p p 要更加复杂，前者基于共享的存储系统，后者的存储系统则 是分布是的，因此进程的同步、资源的共享机制要复杂得多。但是正因为 m p p 系统基于分布式存储，因此其拥有惊人的扩展能力，可以联结成千 上万的结点，显示出比s m p 强大得多的处理能力，是并行化的大势所 趋。通过分析可以看出：针对s m p 的并行化编译技术对m p p 而言是必 不可少的，但这些技术对m p p 而言还十分有限。实验结果表明：在针对 m p p 的并行化编译系统中，分析和变换都非常重要，还有一些非常重要 的新技术需要实现，但实现这些技术的难度非常大。和深蓝一样，当今的 超级计算机基本上都是基于m p p 技术。 c l u s t e rs ( 机群) 一一机群可以是异构的分布式的平台。它和m p p 一 样都是基于消息传递的资源共享，其主要区别在于一是可以异构，二是节 点的连接方式没有严格的规范。因此机群拥有更强的扩展能力和廉价的硬 件设施，当然对控制系统的要求也就更高。网络上存在许多机群计算的成 功案例，譬如s a r s 病毒的d n a 计算等，机群就单个节点的运算能力和 使用效率而言远不及m p p ，但是它的最大优势在于它可以将许多廉价的 硬件设施组织起来并拥有几乎无穷尽的扩展能力。基于机群，产生了网格 计算( g r i dc o m p u t i n g ) 的新概念，其主要关注的是互联网上计算资源 的组织、调度、分配、维护等方面的技术。 1 2o p e n m p 到m p i 转换的关键技术 可以发现，m p p 和机群计算是当今并行计算的主流。 向消息传递的标准m p i 或p v m 。 而当m p p 和机群计算显示出强大的扩展能力的同时， 面向消息的编程是一个艰难而复杂的任务这一事实。 而它们都基于面 我们不得不面对 o p e n m p 到m p i 转换中的数据流分析技术 我们从事并行编译的研究工作，研究的对象是如何让编译器自动识别 并完成从串行程序或者是基于内存共享的并行程序到为面向消息的并行程 序的转换。其目的不光是为了将广大从事科学和工程计算的工程师们解放 出来，还能够将大量现存的科学和工程的程序转换为面向消息的并行程 序，其意义相当深远。当然这是一项艰巨的任务。 在很长一段时间里，s m p 曾叱咤风云，因此现存大量基于内存共享 o p e n m p 规范的并行程序。可见对于o p c n m p 到m p i 转换的研究相当有 意义。 1 2 1 o p e n m p 与m p i 的主要区别 虽然o p e n m p 与m p i 都是并行编程规范，但它们面向的对象不同，编 程模式也不同，是完全不同的两种编程标准。这主要体现在以下几点： o p e n m p 面向s m p 结构的机器，采用多线程执行模式，线程间共享 地址空间，通过共享变量通讯，共享变量为所有线程公有。m p i 面向分布 式存储结构的机器，采用多进程执行模式。每个进程都有各自独立的地址 空问，根本没有共享变量的概念，所有的变量都是私有的。进程间交换数 据需要显式的通讯，且涉及到的进程都需要参与同步。 同步的实现方式不同。在o p e n m p 中有c r i t i c a l 和a t o m i c 编译 指导命令，b a r r i e r 和l o c k 库函数，通过这些命令和库函数实现多线程 间的同步。在m p i 中没有临界区和l o c k 函数，只能通过阻塞的点对点通 讯实现类似功能。 o p e n m p 程序在执行期间遇到并行区时由主线程创建其它线程，退 出并行区时主线程等待其它线程结束并将它们销毁。】i l p i 程序则很难动态 的创建进程，一般情况下，所有进程存在于整个程序运行周期。 编程模式不同。o p e n m p 通过在程序中加入编译指导命令 ( d i r e c t iv e ) 说明数据属性和代码执行方式，具体实现完全交给编译 器做。m p i 程序所有的执行细节都需要程序本身体现，进程间通讯需要显 式调用m p i 提供的库函数。 4 o p e n 帖到舯i 转换中的数据流分析技术 由此可见o p e n m p 与m p i 之间没有一一对应关系，要想把o p e n m p 程序转 化为m p i 程序必须首先处理这些不同点。 1 2 2 o p e n m p 转化为m p i 的基本方法 实现共享变量 识别变量属性 一 p r i v a t e f ir s t p r i v a t e l a s t p r iv a t e r e d u c t l 0 n d e f a u l t 0 p e n m p 主要结构的转换： p a r a l l e lr e g l 0 n 在串行区遇到该结构时0 进程启动数据服务，其它进程并行执行该结 构内的代码，所有共享变量都从o 进程取得。我们不支持并行区嵌套， 内层并行区由进入这个结构的进程串行执行。 w o r k s h a r i n g 包括o m pd o 和o m ps e c t i o n s 。若该结构处于串行区内则该结构里 的代码由0 进程做。若该结构处于第层并行区内，此时0 进程作为数 据服务器，其它进程分做该结构的代码。若处于内层并行区，则该结构的 代码由进入这个结构的进程串行执行。 c o m b i n e dp a r a l l e lw o r k s h a r i n g 该结构为以上两个结构的联合。在串行区遇到该结构时0 进程启动数 据服务，其它进程分做该结构内的代码，所有共享变量都从0 进程取 得。在并行区遇到该结构时由进入这个结构的进程串行执行。 十锁机制和临界区的实现 用m p i 的带阻塞的消息函数mp i s e n d m p i r e c v 代替o p e n m p 中 的l o c k 函数 如e n 帅到k l p i 转换中的数据流分析技术 1 2 3 全局一致数据划分 如何取得全局一致数据划分是o p e n m p 到m p i 转化中的核心技术。 由于在适合m p i 规范的并行处理环境中，各处理器独享各自的内存，也 就是各自的数据空间，为了避免开销巨大的处理器间通信，我们应尽量避 免处理器a 去访问处理器b 的数据空间中的数据这种情况。所以我们要 取得全局一致的数据划分。 我们有必要理解并行变换中的两个基本概念一计算划分与数据划分 计算期分：将计算任务分配给各i 作线程的方法 数据娥分：将数据分配翻各处理器私舂内存空间的力法 容易发现，在原始的o p e n m p 程序中，我们拥有的仅仅是第一层的 计算划分信息，而要取得全局一致数据划分，我们必须拥有充分的计算划 分和数据划分信息，也就是所谓的挖掘并行性。 1 2 4 数据重组方法的研究进展 为了取得充分的数据划分信息，我们必须进行数据重组。其目的是取 得全局一致的数据划分，或者尽量减少处理器间的数据通信开销。 该领域的研究进展包括我们现今可以利用的数组重组方法： 换名 私有化 数组扩张 循环交换 幺模变换 0 循环拆分 o p e n m p 到m p i 转换中的数据流分析技术 在无法取得一致数据分布的情况下，我们可以尽量减少处理器间的数 据通信开销，使得转换后得到的m p i 程序依然有着计算性能上的大幅提 升。这里减少通信开销，不是单纯的减少通信的数据量，而是减少额外通 信时间。我们可以通过程序变换来达到计算覆盖通信的目的。 而数据重组方法的依据则是数据流分析，要取得尽可能有效的数据重 组结果，我们必须取得精确的数据流分析结果。标量的数据流分析技术已 经相当成熟，定值引用链分析以及s s a 方法都堪称经典之作。而数组不 同于标量，它由下标来确定具体成员，而下标又依赖于上下文环境。因此 数组的生命期分析必然要复杂许多，这也是本篇论文的论述重点所在。我 在这方面研究的成果在本篇论文中加以描述，并在a f t 0 4 系统中得以应 用并取得良好的效果。 0 p e n i i p 到舻l 转换中的数据流分析技术 第二章数组的数据流分析的经典技术 2 1 相关性测试的经典方法 2 1 1 相关性定义 在定义相关性前，我们使用i n ( s ) 和o u t ( s ) 分别记录语句s 的读变 量集记与写变量集：语句实例s ( ，) 的读、写变量集分别记为 n ( s ( ，f 2 ，) ) 和o u r ( s ( ，之，t ) ) 。下面给出了相关性的形式化定 义： 设s ( f l ，i 2 ，f ) 和t ( j l ， ，b ) 为两语句实例，如果存在迭代( i ，f ：，i 。，) 和( ，。，：， ，) 使得s ( i 。，i ：，i “) t ( j ，j ：，j k , ) 并且 1 如果o u t ( s ( f 。，i 2 ，i e ) ) c 、i n ( t ( j ，2 ， ，) ) o 则称语句s 到t 有 流相关( f l o wd e p e n d e n t ，苗稀磁t r u ed e p e n d e n t ) 记为s 艿7r ： 2 如果i n ( s ( i i ，f 2 ，i “) ) n 0 u t ( t ( l ，2 ，矗) ) o 则称语句s 到t 有 反相关( a n t id e p e n d e n t ) s 扩r ； 3 如果o u t ( s ( i l ，屯，f ) ) n 0 u t ( t ( ，l ，j 2 ，h ) ) 0 则称语句s 到t 有输出相关( o u t p u td e p e n d e n t ) 记为s 矿r 。 2 1 2 相关性测试的本质 根据相关性定义，我们可以得出，语句问存在相关的共同点在于，它 们必然拥有至少一个的相同数据。根据语句对于该数据的操作是读或写， 以及操作的先后顺序，可以的出语句s 到t 是否存在相关以及存在何种 相关。 可见对数组进行相关性测试的本质在于：一、是否对某个相同数组元 素进行操作的判断，二、对该元素进行操作的语句执行先后顺序的判断。 0 p e n g p 到m p l 转换中的数据流分析技术 2 1 3 对是否存在相同元素的判断 对数组下标建立方程求解判断是否存在相同数组元素是行不通的，因 为我们需要的是一种快速、简单、有效的方法。在快速、简单、有效的前 提下尽可能提高算法的精确性。为了保证正确性，我们的算法可以把不存 在相关性的语句当成存在相关性，但万万不能忽略事实上存在的相关性。 因此这里所谓的精确性也就是说尽量使得所有由算法识别出来的相关性 是真正存在的。在数组下标是基于循环标量的线性表达式的假设下，经典 的算法是g c d 测试+ b a n e r j e e 测试。而事实上，几乎所有的科学和工程 计算程序都是遵循这个假设的。 g o d 测试 g c d 测试是最大公约数测试的缩写，其原理基于一个古老的数学定 理：只有当常数项差整除所有系数的最大公约数的情况下，一对线性表达 式的联立方程才有可能有整数解。 数组元素a 2 i + l 】和a 4 j + 2 】无论循环变量i ，j 如何取值永远也不会 表示同一个元素，就是应用g c d 测试得出的结果。当然，我们可以发现 前者的下标是奇数后者下标是偶数，所以永远不可能相等。但g c d 还能 得出一些更复杂不能轻易看出的结果，更重要的是它是一种快速简单的自 动算法。 b a n e r j e e 测试 b a n er j c e 测试基于如下中值定理：在实数区间r 上，函数，( x ) 连续， 如果m j n ( ，( x ) ) 0 m 努( ，( 上) ) ，则必有区间r 内的点工满足方程，( j ) = 0 。 通过中值定理，可以将线性方程厂( x ) = o 看成线性函数f ( x ) ，从而将判定 线性方程厂( 石) ：0 在线性不等式约束条件尺下是否有解，转变成计算在线 性不等式约束异下，厂扛) 的最大值和最小值。 为了计算线性函数的极值，b a n e r j e e 引入了一对记号：对一整数 d ，a + = m a x ( a ，0 ) ，口一= m a x ( 一a ，0 ) 。有了这对记号，他可以将线性函数a x 在线性约束条件p 工q 下的极值表为 m i n ( a x ) = a + p a - q ，m a x ( a x ) = a + q - a p 。对一般的线性函数 厂o ) = a o + 口1 而+ 口2 屯+ a 相。，如果办s x q i ，1 9 k _ 0 时需 要) 。注意，这里l _ o 表示和循环无关的相关，当然就不存在距离向 量。后面，我们用u d d u f m ，r 3 ：t ) = “m ，n ：i d ) 来表示 u d d u 链。 如果数组t 在程序段中出现了n 次，通过n + 1 次遍历p a r s et r e e 对 定值点和引用点的数组下标进行相关性测试 ( 一般利用g c d 测试+ b o n er j e e 测试可 以快速得到比较精确的结果) ，我们可以为 该数组建立粗糙u d d u 链。如图1 中的程 序p1 ，对于数组t ，通过遍历p a r s e t r e e ，我们可以得到数组t 的粗糙u d d u 链： d u ( 2 ，1 ：t 】= “4 ，1 ：o 】，( 4 ，2 ：o 】) d u ( 3 ，1 ：t ) = “4 ，1 ：2 - 0 ) ，f 4 2 ：2 1 ) ) u d ( 4 ，1 ：t 】= “2 ，1 ：o 】，( 3 ，1 ：2 - 0 ) ) u d ( 4 2 ；t ) = “2 1 ：oj ，( 3 ，1 ，2 1 ) ) 3 1 2 重定值链 类似于u d d u 链对应的是流相关，我 们建立重定值链d d 来表示输出相关。建立 p r o g r a mp 1 e m p l i c i ti n t e g e r ( i - t ) c o m m o n m r r 0 0 0 5 ) s ( 1 0 0 5 ) o ( 10 d o i = 11 0 0 d oj = 15 s 0 j ) = e n o d 0 e n d d o d o i = 15 d oj = 2 1 0 0 d ok = i5 t ( j k ) ；s ( j 一1 k ) + o ( 1 ) e 扣 e n o d o d o k = 2 5 s ( j ，k ) ：t ( j k 1 ) + t ( j - 1 k ) 4 s 0 i ) = o ( i ) 5 ) s ( j k 一1 ) = s ( j k - 1 ) + 0 ( i + 1 ) 6 e n o d o q ( i ) = s ( j 5 ) + i 7 e n d d o e n d o o e n d 图l 3 0 o p e n 即到咿i 转换中的数据流分析技术 d d 链的方法和前者完全一样，数据结构也完全一样。这里，d d 链表示 的是指定定值点之后可能经过的定值点。 如图l 中程序p 1 ，对于数组s 我们可以得到： d d ( 1 ，1 ：s ) = ( 4 ，1 ：0 】，( 5 1 ：0 】，( 6 ，1 ：o ) ) d d ( 4 ，1 ；s ；= ( 4 ，1 ：1 - + ) ，f 5 ，1 ：+ 一+ ) ， 6 ，1 ：1 - + 3 - 1 ) d d f 5 ，1 ：sj = ( ( 4 ，1 ：+ 一+ 】，( 5 ，1 ：2 - + 3 - + j ，( 6 ，1 ，+ 一+ ) ) d d ( 6 ，1 ；s ) = “4 ，1 ：1 一+ ) ，( 5 ，1 ：+ - + ) ，f 6 ，1 ：1 一+ ) 注意，这里我们用来分隔各种可能产生相关的层次，此外用+ 表示 距离向量或循环层次上包括l 到循环次数一1 的任意值，丽