（计算机应用技术专业论文）网格环境下面向地震资料处理程序的自动并行化技术研究.pdf

网格环境下面向地震资料处理程序的自动 并行化技术研究 田世峰( 计算机应用技术) 指导教师：全兆岐( 教授) 梁鸿( 副教授) 摘要 自动并行化技术的研究是随着并行计算机的出现而开始的，如何用 好并行处理系统以解决大规模科学计算问题是当前计算机科学面临的一 个重要课题，开发高效的并行软件是解决问题的核心。网格这种基于分 布式存储的网络技术的出现，将分散在网络上的计算能力结合起来，形 成有机的整体，能提供比任何单台高性能计算机都强大的处理能力。因 此，网格环境下自动并行化技术的研究意义重大 程序自动并行化技术一直是并行处理领域的研究热点与难点，目前 虽然已经取得了长足进步，但实际应用效果并不理想。经研究，主要原 因在于面向通用程序。我们以地震资料处理为应用领域，重点分析其中 的三维叠前深度偏移，旨在将自动并行化技术应用于网格这种超强计算 能力中，使得工程实践中已经积累的大量串行应用程序高效并行执行。 本文的主要工作体现在： 1 通过阅读大量的三维叠前深度偏移串行程序，分析并归纳出其并 行化特征，指出：l ( i i c h h o 伍积分法叠前深度偏移中，旅行时的计算适合 采用按炮点并行计算，成像输出适合基于炮检距的自动并行化：分步傅 立叶法叠前深度偏移适合按单炮记录进行并行。 2 在分析三维叠前深度偏移串行程序自动并行化特征的基础上，提 出一个自动并行化模型，并介绍模型中各模块所采用的关键技术。 3 针对模型中的数据及循环分布这一难题，论文将其分为无通信及 有通信两种情况分别进行分析。无通信情况下，分别针对数组与循环、 同名数组间、异名数组间三种情况，提出三个算法，解决对应情况下的 数据及循环分布问题；有通信情况下，将该问题抽象成一个数学模型 ( a p d g 图的划分) 。 4 给出一个基于改进蚂蚁算法的任务调度策略，用以将a p d g 图 划分后的各子集调度到网格系统中的处理机上。 关键词：网格，并行编译，自动并行化，数据及循环分布，三维叠前深 度偏移 a u t o m a t i cp a r a l l e l i z a t i o nf o rs e i s m i cd a t a p r o c e s s i n g p r o g r a m so ng r i de n v i r o n m e n t t i a ns l l i f e n g ( c o m p u t e ra p p l i c a t i o nt e c h n o l o g y ) d i 曲e db yp r o f e s s o rt o n g z h a o q ia s s o c i a t ep r o f e s s o rl i a n gh o n g a b s t r a c t p a r a l l e lc o m p i l i n gh a sb e e nc a r r i e do u tw i t ht h ed e v e l o p m e n to ft h e p a r a l l e lc o m p u t e r = c h i t e c t u r e a n dh o w t ou s ep a r a l l e ls y s t e me f f i c i e n t l yt o s o l v et h ec o m p u t a t i o n - o r i e n t e dp r o b l e m si sad i f f i c u l t yi nc o m p 咖s c i e n c e i ti sf l l la l l - i m p o r t a n tk e yt od e v e l o ph i g hp e r f o r m a n c e p a r a l l e ls o f t w a r e g r i di sa ni n n o v a t i v em o d e lo fd i s t r i b u t e dm e m o r y , f o c u s i n g0 1 1 c o m p u t i n g r e s o u l f c c s s h a r i n g f o rd a t a p r o c e s s i n g a n dc o l l a b o r a t i v e a p p l i c a t i o n so fv m u a lo r g a n i z a t i o n s g r i di sa 叩e c t e dt oi n t e g r a t et h e s c a t t e r e dr e s o u r c e sa n dp r o c e s s i n ga b i u t yi n t o 孤o r g a n i cw h o l e w h i c hc a n p r o v i d eh i g h e rc o m p u t i n gp e r f o r m a n c et h a na n ys i n g l eh i g hp e r f o r m a n c e m u l t i - p r o c e s s o r s t h u s ，i t i ss i g n i f i c a n tt o 坞簧黜ht h et e c h n o l o g yo f a u t o m a t i cp a r a l l e l i z a t i o no ng r i d 。a sah o tr e s e a r c h t o p i c i n p a r a l l e lc o m p u t i n ga r e a , a u t o m a t i c p a r a l l e l i z a t i o ni sa t t r t i n gm o 砖a n dm o r er e s e a r c h e r s m u c hp f o 掣e 鲻i n e x p l o i t i n gc o a r s e - g r a i np a r a l l e l i s mh a sb e e nm a d ei nr e c e n ty e a r s ，b u t a p p l i c a t i o nr e s u l t sa g os t i l ld i s a p p o i n t i n g , s i n c em a n yp r o g r a m sa c h i e v e d l i t t l eo rn os p e e d u pw h i l ee x e c u t e di np a r a l l e l i nt h i sp a p e r , w es t u d yt h e s e i s m i cd a t ap m c e s s i n gp r o g r a m sa n dm a i n l ya n a l y z et h e3 dir e s t a c k d e p t hm i g r a t i o n , f o rt h es a k eo fa p p l y i n ga u t o m a t i cp a r a l l e l i z a t i o nt og r i d c o m p u t i n gs oa st oa c h i e v ed a t ap a r a l l e l i s mw i t hl a r g es c a l ea n dh i g h e f f i c i e n c y 1 1 1 em a i nc o n t r i b u _ c i o n so f t h i sp a p e rc a nb el i s t e da sf o l l o w s ： 1 b yr e a d i n g a m a s s o f s o u r c e c o d e sa b o u t 3 d ir e s t a c k d e p t h m i g r a t i o n ，w ep o i n to u tt h a t , i np r e - s t a c kd e p t hm i g r a t i o nb a s e do nk i r c b l l o f f , t h ec o m p u t a t i o no f t r a v e lt i m ei sf i tf o rp a r a l l e l i z a t i o na c c o r d i n gt os h o t ，t h e i c o m p u t a t i o no f i m a g i n gr e s u l ti sf i tf o rp a r a l l e l i z a t i o na c c o r d i n g t oo f f s e t ； a n di nt h es p l i t s t e p1 0 r e s t a c kd e p t hm i g r a t i o n ，i ti sf i tf o rp a r a u e l i z a t i o n a c c o r d i n g t os i n g l e - s h o tr e c o r d 2 w ep r e s e n ta p p s d m m ( a u t o m a t i cp a r a l l e l i z a t i o no f3 dp r e - s t a c k d e p t hm i g r a t i o nm o d e l ) b a s e do nt h ea n a l y s i s o f3 dp r e - s t a c kd e p t h m i g r a t i o ns e q u e n t i a lp r o g r a m sa n d i t si n 缸o d u c f i o no f k e yt e c h n i q u e s 3 i no r d e rt or e s o l v et h ep r o b l e m so fd a t aa n dl o o p sd i s t r i b u t i o n , w e p a r t i t i o ni ti n t ot w op a r t sa c c o r d i n ga sw h e t h e rt h ep r o c e s s o r sc o m m u n i c a t e w i t ho t h e r sa f t e rd i s t r i b u t i o n w h e ni td o e sn o tr e l a t et 0c o m m u n i c a t i o n s ，w e p u tf o r w a r dt h r e ea l g o r i t h m s ，w h i c hr e s p e c t i v e l yr e s o l v et h ep r o b l e m so f a l i g n m e n tb e t w e e na r r a y sa n dl o o p s ，a r r a y sw i t ht h es a m en 锄e ，a n da r r a y s w h i c hw i t hd i f f e r e n tn f l l n e s a sf o rt h eo t h e rs i t u a t i o n , w ei m p l e m e n tt h e p r o b l e m st h r o u g hc 】( 臼_ a l 嘶n ga p d g ( a u t o m a t i cp a r a l l e ld i s t r i b u t i o no m p h ) 丘o mt h em u l t i l a y e rn e s t i n gl o o p s w h i c hi ss u b j e c t1 0t h er e s t r i c t i o nt h a tt h e e d g e sc o n n e c t e db e t w 啪d i f f e r e n ts u b s e t sa f t e rd i s t r i b u t i o na r el e a s t 4 a na l g o r i t h mb a s e do ni m p r o v e da n ta l g o r i t h mw a sp r e s e n t e dt 0s o l v e t h ep r o b l e mo f t a s ks c h e a l l l i n ga f t 盱t h ep a r t i t i o no f a p d g k e y w o r d s ：0 r i d , p a r a l l e lc o m p i l i n g ，a u t o m a t i cp a r a l l e t i z a t i o n ，d a t aa n d l o o p sd i s t r i b u t i o n , 3 dp r e - s t a c kd e p t h m i g r a t i o n 独创性声明 本人声明所呈交的论文是我个人在导师指导下进行的研究工作及取 得的研究成果。尽我所知，除了文中特别加以标注和致谢的地方外，论 文中不包含其他人已经发表或撰写过的研究成果，也不包含为获得中国 石油大学或其它教育机构的学位或证书而使用过的材料。与我一同工作 的同志对本研究所做的任何贡献均己在论文中作了明确的说明并表示了 谢意。 签名： 纠年争月j 日 关于论文使用授权的说明 本人完全了解中国石油大学有关保髯、使用学位论文的规定，即： 学校有权保留送交论文的复印件及电子版，允许论文被查阅和借阅；学 校可以公布论文的全部或部分内容，可以采用影印、缩印或其他复制手 段保存论文。 ( 保密论文在解密后应遵守此规定) 学生签名： 导师签名： 枷7 年牛月日 己少年乒月，耍 中国石油大学( 华东) 硕士论文第1 章绪论 第1 章绪论 1 1 选题背景及依据 地震资料数据处理与天体演变研究、核爆炸模拟、中长期天气预报 和大规模事物处理等为数不多的几个领域，一直属于高性能计算机的应 用范畴。 随着油气田勘探和开发难度的不断增加，对地震勘探的精度要求越 来越高。目前，三维地震技术已得到了普及，野外采集的地震数据已从 二维测线过渡到了三维数据体，数据量成倍增长随着高分辨率地震勘 探和四维地震勘探等新技术的推广，地震数据野外的采集量将变得更加 庞大。这就使完成地震资料处理、得到高质量的成果剖面所需的计算量 大大增加。地震资料科学的、大规模的并行处理已变得越来越迫切【l 】。 具有超强计算能力的网格技术的出现，恰好满足了地震资料数据处理对 更强、更大、更灵活的计算力的需求。 在地震资料处理领域长期的工程实践中已经积累了大量的串行应用 程序，这是一笔巨大的财富，要想将其移植到网格环境下并行高效执行， 重新开发相应的并行程序显然事倍功半。因为，要想开发高效的并行程 序，程序员必须掌握诸如：多处理、私有变量、同步、多级存储等概念， 而现在一般的并行计算用户都是进行科学研究的，并非专业计算机研究 人员，让他们掌握如此复杂的概念意义不大而且，并行程序与体系结 构密切相关，随着体系结构的不断变换，又需要重新开发软件，导致并 行软件开发耗资巨大一种可行的解决办法是借助于自动并行化工具， 使程序员在编制程序时集中精力于算法的研究，而无须考虑如何将串行 程序转化为并行程序，从而极大地减轻了用户的负担只需用户提供串 行程序，由自动并行化工具考虑以上的复杂问题，自动地实现从串行程 序到并行程序的转换。 本课题组研究的“基于网格技术的地震资料处理解释系统”，简称 g s p s ( g r i d s e i s m i c p r o 嘲s i n g s y s t e m ) ，是在胜利油田和中国石油大学重 大科技攻关项目“微机机群并行交互地震处理解释系统”的基础上提出 的，目的在于将基于机群的地震处理解释系统移植到计算网格环境下 中国石油大学( 华东) 硕士论文第1 章绪论 为了使地震资料处理高效地利用网格的超强计算力，课题组将根据网格 技术的特点，研究设计适合地震资料数据处理的网格基础设施，为地震 资料处理需要的赢性能计算能力提供平台，并在此平台上开发地震资料 处理解释系统。本论文是g s p s 课题的子课题，旨在研究一个基于网格 系统的自动并行化编译系统，重点解决其中的数据及循环分布问题，为 网格技术在地震勘探资料处理领域中的应用做好基础性工作。 1 2 自动并行化技术研究现状 自动并行化的前身是自动向量化。自动向量化的研究可追溯到7 0 年代中期超级计算机的出现。在自动向量化的研究中，d a v i dk u c k 教授 提出了相关性理论，通过相关性分析可以确定程序的向量化部分。对于 阻碍向量化的相关性可通过各种程序变换尽可能消去，以便向量化成功。 相关性分析和程序变换构成了自动向量化的基础。 8 0 年代的并行计算机一般为共享存储多机系统，程序自动并行化的 研究主要集中在数据依赖关系分析和程序变换这两个方面，通过数据依 赖关系分析和程序变换，尽量开发串行程序中的多机性。这一阶段的程 序自动并行化取得了很大的成就，相继出现了一批成功的面向共享存储 多机系统的并行化工具，如i l l i n o i s 大学的p a r a 五x a s e - 2 ，r i c e 大学的p f c l 2 ， m m 公司的阴l a n 例等。 。 9 0 年代以来，大规模并行处理m p p ( m a s s i v e l y p a r a l l e lp r o c e s s o r s ) 得 到迅速发展，这种基于分布存储系统为程序自动并行化增加了新的内容， 也带来了新的技术难题。例如，如何确定一个好的数据分布和并行划分 模式以获得最大的数据局部性和程序并行性1 4 1 7 如何进行同步控制以保 证并行程序的正确性? 这些问题具有相当的理论研究深度和工程实现难 度，面向m p p 系统的程序自动并行化研究仍处于探索阶段。 目前，国际上已经出现了一些比较有名的自动并行化系统。 美国s t a n f o r d 大学的s u i f 编译器组多年来一直在进行程序自动并 行化的研究工作，他们的研究涵盖了相关性分析、指针分析、分块、预 取、程序变换、过程间分析等方面。在理论研究的基础上他们开发了基 于共享存储结构的自动并行化编译系统s u i f 5 1 ，现在已经发展到了 2 中国石油大学( 华东) 硕士论文第1 章绪论 s u i f 2 t 6 ，它以串行的c 或f o r t r a n 程序作为输入，自动生成优化过 的并行源程序代码。它已经能解决一些实际的应用问题。他们新近的工 作集中在过程间优化和提高并行度与局部性的仿射变换上【7 l 。 美国i l l i n o i s 大学的高性能计算研究与开发中心( c s r d ) 对自动并行 化技术进行了多年的研究，他们开发了基于共享存储结构的自动并行化 编译系统p o l a r i s 8 1 ，其中使用了过程间符号分析技术和r u n - t i m e 分析、 数组私有化、循环聚变等技术。目前他们正与位于u r b a n a - c h a m p a i g n 的 i l l i n o i s 大学的高可靠与高性能计算( c g 王w c ) 中心合作开展 p a r a d i o m ( p a r a l l e l i z i n gc o m p i l e rf o rd i s l r i b u t e d - m e m o r yg e n e r a l - p u r p o s e m u l f i c o m p u t e r s ) 项目，试图研究出更好的算法，可以针对更广范围的源 程序及更通用的并行机进行源到源的消息传递程序的自动并行。 英国g - r e e w i c h 大学的并行处理组也在进行程序自动并行化的研究 工作，他们在多年研究的基础上开发了交互式的程序自动并行化工具 c a p t o o l s ，主要用于将现存在计算力学软件中的串行f o r t r a n 7 7 并行 化。c a p t o o l s 输入串行程序，对程序进行分析，通过用户参与，产生插 入了通信调用的并行程序。 在国内，复旦大学并行处理研究所的朱传琪教授等一直在对自动并 行化技术进行跟踪研究，并开发出了自动并行化系统a f t 9 ( a u t o m a t i c f o r t r a n t r a n s f o r m e r ) 。它采用了数组私有化【l o 】、过程间分柝、过程繁衍【1 1 1 、 过程嵌入等多种技术。通过对p e r f e c tb e n c h m a r k 及国际标准基本函数库 b l a s 的测试结果表明，a f t 对某些问题自动并行的效果令人满意。 中科院计算技术研究所的先进编译技术研究组自9 0 年代以来一直 从事程序自动并行化方面的研究工作，先后开发了共享内存多处理机系 统上的自动并行识别器v c c ，分布存储多处理机系统上的自动并行识别 器a m o p a r 1 2 1 。目前仍在进行先进计算机体系结构优化编译器【1 3 ，1 4 ”】， s m p m p p 并行机上的自动并行识别烈州的研究和开发。 另外，中科院计算所高性能计算中心的张兆庆教授、唐志敏教授、 清华大学的郑纬民教授以及其它一些高校及研究单位1 1 7 , 1 8 , 19 】也在进行程 序自动并行化技术的研究工作。 中国石油大学( 华东) 硕士论文第1 章绪论 1 3 本课题主要研究内容 自动并行技术的难点就在于既要保证并行化后程序的正确性，又要 获得高效率。目前的自动并行化系统离真正的实用还有较大的距离。我 们认为最根本的原因是现有的技术瞄准通用的方向。虽然面向通用程序 的全自动并行化系统是我们追求的最终目标，但是目前看来条件还不成 熟。最突出的矛盾是不同领域的问题之间彼此的特点相差甚远，撇开问 题的特点而研究通用的技术，在具体应用中难免使效率受到很大的制约。 鉴于完全通用且高效的自动并行化系统在理论与实现技术上的困 难，针对典型应用开发高效的自动并行化软件，是一个切实可行的方向。 再结合实验室具体情况，我们把研究对象定位在地震资料处理领域中的 一些计算密集型算法，本论文重点分析三维叠前深度偏移串行程序的特 点，寻找其并行化特征。 本论文研究内容如下： 1 深入分析一些传统的并行化技术基础理论，了解相关性分析、程 序变换等的相关方法，系统掌握并行编译系统中所需要的核心技术。 2 解析网格计算环境，归纳网格体系结构的特征。由于网格的分布 性，网格环境下的自动并行化问题要求我们必须掌握分布式体系结构方 面的知识。 3 学习地震勘探原理、地震资料数据处理方法，深入分析地震资料 处理方法中的三维叠前深度偏移方法及所涉及的算法，找出它们的自动 并行化特征。 4 针对三维叠前深度偏移串行程序中所总结的并行化特征，提出一 种自动并行化模型，介绍模型中各模块的功能，详细介绍其中的关键技 术，比如数据及循环分布技术、交互模块等。 5 理解目前国际国内流行的数据及循环分布方法，重点掌握图划分 方法。针对数据及循环分布问题，按照分布后处理机是否需要进行远地 访问，我们分为无通信及有通信两种情况进行分析。无通信情况下，分 别针对数组与循环、同名数组间、异名数组间三种情况，提出三个算法， 解决对应情况下的数据及循环分布问题：有通信情况下，将多层嵌套循 4 中国石油大学( 华东) 硕士论文第1 章绪论 环抽象成a p d g - ( a u t o m m i c p a r a l l e l d i s t r i b u t i o n g r a p h ) 图，将该图划分后， 要求所得子集间所连接的边数最少。 1 4 论文的组织结构 本论文共分为七个章节，其中： 第1 章为绪论，主要介绍了论文的选题背景及依据、自动并行化技 术的研究现状、论文的主要研究内容等。 一 第2 章首先介绍网格的概念，接着给出了自动并行化的关键技术， 作为本论文研究的理论基础，它主要包括相关性分析，程序变换技术、 并行编程模型、通信及优化等问题。 第3 章首先分析了三维叠前深度偏移( 射线法及波动方程法) 串行程 序的特点及并行化特征，然后，在此基础上，提出一个自动并行化模型， 并介绍该模型各模块中所用到的关键技术。 ， 第4 章重点探讨了数据及循环分布问题。首先，对这一阔题进行了 形式化描述、介绍了其发展现状及主要技术；接着，将该问题分为无通 信和有通信两种情况分别进行详细分析。 第5 章首先对蚂蚁算法进行了改进，接着给出改进后蚂蚁算法的思 想及流程。最后介绍如何添加负载平衡因子。改进后的蚂蚁算法可用于 将第4 章中a p d g 图划分后生成的子集调度到各处理机上 第6 章是实验测试与结果分析。我们先介绍了实验室的具体硬件及 软件环境，接着在实验平台上，随机挑选若干任务对改进后的蚂蚁算法 进行实验。实验结果表明，该算法可以有效地均衡负载，提高任务集的 整体运行效率。 第7 章是全文工作总结以及进一步的工作展望。 5 中国石油大学( 华东) 硕士论文第2 章理论基础介绍 第2 章理论基础介绍 2 1 网格的概念 什么是网格昵? “网格之父”k mf o s t e r 博士对网格有一个经典的定 义，他认为网格是一个集成的计算资源环境，或者说是一个计算资源池 ( c o m p u t i n gp 0 0 1 ) 。网格能充分吸收各种计算资源，并将它们转化成一种 随处可得的、可靠的、标准的、便宜的计算能力。2 0 0 0 年，i a nf o s t e r 在网格的剖析这篇论文中把网格进一步描述为“在动态变化的多个 虚拟机构间共享资源和协同解决问题。”2 0 0 2 年7 月，i a nf o s t e r 在什 么是网格? 判断是否网格的三个标准一文中，限定网格必须同时满足 三个条件：( 1 ) 在非集中控制的环境中协同使用资源；( 2 ) 使用标准的、 开放的和通用的协议和接口( i a af o s t e r 认为目前只有g l o b u s 才算得上标 准协议) ；( 3 ) 提供非平凡的服务。刚这三个条件非常严格，像p 2 p 、s u n g r i de n g i n e 、c o n d o r 、e n l t o p i a 、m u l f i c l u s t e r 等都被排除在网格之外。 鳓 至此，k m f o s t e r 已经把他头脑中的网格概念描绘清楚了但并不是 所有人都同意他的观点，例如，有许多人赞同广义的网格概念，它称作 巨大全球网格( g r e a tg l o b a lg r i d ) ，它不仅包括计算网格、数据网 格、信息网格、知识网格、商业网格，还包括些已有的网络计算模式， 例如对等计算p 2 p ( p e e r t o p e e r ) 、寄生计算等。可以这样认为，i a n f o s t e r 赞成狭义的“网格观”，而c , g g 是一种广义的“网格观”。 清华大学李三立院士将网格与信息高速公路作了比较，他说：“将先 进计算基础设施( 网格) 与信息高速公路相比较，可以说，信息高速公 路是信息传输和获取的信息基础设施，而先进计算基础设施则是信息处 理的信息基础设施。虽然，国内外都有不断把信息高速公路扩充频带宽 度、改进路由器性能的计划，但是，国外科学家认为：真正的下一代信 息基础设施是先进计算基础设施。它将使以计算机为主体的信息处理发 生根本性的变化。”口l 】 中科院计算所李国杰院士认为：“网格不同于国外正在搞的i n t e m e t 2 或下一代i n t e m e t ( n g i ) ，网格可以称作是第三代i n t e m e t ，其主要特点是 7 中国石油大学( 华东) 硕士论文 第2 章理论基础介绍 不仅仅包括计算机和网页，而且包括各种信息资源，例如数据库、软件 以及各种信息获取设备等，它们都连接成一个整体，整个网络如同一台 巨大无比的计算机，向每个用户提供一体化的服务。”圈 2 2 相关性理论 相关性分析的理论和技术是自动并行化技术和并行编译技术的基础 和关键，并行识别及多种并行变换都需要用到相关性信息。只有做出正 确的相关性分析，才能保证并行程序的正确性，只有找到尽可能多的不 相关部分，才能提高并行程序的并行度。 2 2 1 相关性概念 定义2 l ：在一个程序中，如果在事件或动作b 发生前，事件或动 作a 必须发生，则称b 依赖于a ，称这种关系为依赖( 相关) 关系。依 赖关系又分为控制依赖关系和数据依赖关系两种。 定义2 - 2 ：控制相关对于程序中两条语句( 语句块) s ，是，若最的 执行取决于s 的执行结果，称最与墨控制相关。 例如下面的语句r 控制相关于s ： s ：i f o e q 0 ) t h e n t ：a = b c e n d i f 控制相关导致程序流程的变化。在并行编译技术中常采用控制流图 ( c o n t r o lf l o wg r a p h ) 来分析、测试控制相关关系 由于影响程序并行化的主要是数据相关，因此，自动并行化技术中 讨论的相关一般都是指数据相关。本文后面提到的相关，如无特别声明， 均指数据相关。 数据相关是由读写同一数据引起的因为并行化的对象主要是针对 循环的( 循环一般占程序中的大部分运行时间) ，因此下面我们定义循环 中两个语句之间的数据相关。 定义2 3 ：数据相关嵌套循环工中的两个语句丁和s ，如果存在s 的 一个实例s ( i ) ，t 的一个实例丁( 力，以及s 的一个变量x ，t 的一个变 量y ，且满足以下条件，则称语句s 与f 数据相关： 中国石油大学( 华东) 硕士论文第2 章理论基础介绍 1 x 和y 至少有一个是它所在语句的输出变量； 2 r 在实例s ( 0 中和y 在实例r ( 力中都表示同一个存储单元m ； 3 在程序串行执行时，s ( 0 先于r u ) 执行； 其中，i = “，i ：，) ，= “，办，l ) 表示循环的一次迭代实例， 嵌套循环的层数为m ，由变量x 和y 引起的语句r 与s 的数据相关包含 三种类型： 1 如果工o c r r ( s ) ，y n 口) ，则r 与s 流相关： 2 如果x n ) ，j ，o u r ( r ) ，则r 与s 反相关； 3 如果x e o u t ( s ) ，y o u r ( r ) ，则r 与s 输出相关。 o u t ( r ) 和n ( t ) 分别表示语句f 的输出变量、输入交量的集合由 于反相关和输出相关是由重用( r e u s e ) 和重新赋值( r e a s s i g n m e n t ) 造成的， 通过一定的变换可以消除这种相关例，因此以后我们考虑的相关都是流 相关 在定义2 - 2 中，若向量i = _ ，则称f 与s 的相关是与循环无关的相 关，否则，称r 与s 的相关为跨循环相关 2 2 2 循环体中的依赖关系分析 循环占用了串行程序的绝大部分执行时间，因此，对循环体的依赖 关系分析一直是最受关注的t 2 * , z 5 l 。早期的工作主要集中于数组是线性下 标的精确方法和运行速度足够快的近似方法，分析也都是静态的。因此， 在大多数情况下只能得到保守的结果。 相关性分析的主要难点为数组相关性测试，数组相关性测试的基本 问题为判断在一个嵌套循环中同一数组的两次出现( 其中一次为写) 之 间是否存在相关，即是否会对同一地址( 数组下标) 进行操作。由于数 组下标可以看成是循环变量的函数，所以上述问题可以看作一个判断满 足一定的约束条件的丢蕃图方程是否存在整数解的问题。下面我们对国 际上著名的几种相关性测试技术分别进行介绍。 g c d 测试 g c d 测试是最简单的一种测试方法 9 中国石油大学( 华东) 硕士论文第2 章理论基础介绍 若一整数方程q 而+ z 1 2 x z + + q 矗= c 存在整数解，则 g c d ( a l ，口2 ，以) 必能整除c ，否则肯定没有整数解。 基于上述定理，g c d 测试对每个丢蕃图方程考察其系数的最小公约 数是否整除c ，若有一个丢蓍图方程不满足该条件，则必然没有整数解， 也即相关性不存在，否则就假设相关性存在。 b a n e r j e e 测试。 b a n e r j e e 测试1 2 6 是被许多并行编译系统广泛采用的种测试方法。 它的实现很方便，但它的测试范围并不是很广泛，同时也不是很精确。 其实现方法如下： 一 对一整数口，记a + = m a x ( a ，o ) ，a = m a x ( - a ，o ) 。那么，我们有 p 工 q ， 贝ua + p - o g a x a + q - a p 若对f = 1 , 2 ，”，有 p ， 一 q ，则口j p - a q ， 口，葺 c 或 m ( 口? 吼一a t p ，) c ，则说明该方程没有整数解。 百 b a n e r j e e 铡试的一个弱点在于，它要求系数a 。不能为符号。只能为 常量。 o m e g a 测试 o m e g a 测试是由w i l l i a mp u g h 于1 9 9 1 年提出的一种新的铡试方法 2 7 1 。o m e g a 测试较前两种测试方法，在精度上有很大提高。但它实现比 较困难，在实际系统中比较少得到应用。 。 o m e g a 钡g 试实质上是基于f o u r i e r - m o t z k i n 消除法的种整数规划问 题算法。它的基本操作是投影。o m e g a 测试将约束分为等式约柬与不等 式约束。它首先将等式约束代到不等式约束中。消去等式约束。接着。 o m e g a 测试开始对不等式约束进行投影，每次投影将消去一个变量。直 至整个问题仅剩下一个变量，我们就能很容易她判断它有没有整数解。 由于o m e g a 测试监测的为整数解，而非实数解，所以在做投影时， l o 中国石油大学( 华东) 硕士论文 第2 章理论基础介绍 若投影中含有整数解，并不能说明原来的约束中含有整数解，因为被消 去的变量可能仅存在实数解。于是，o m e g a 测试将投影分为黑影a r k s h a d o w ) 与实影嘬c a ls h a d o w ) ，实影即为上面所说的投影，而黑影为实影 的一个子集，它表示若它具有整数解，则原约束必有整数解。若某次投 影仅有实影而不存在黑影，o m e g a 测试便将原来的问题转换为多个子问 题，来求原约束是否存在整数解。 2 2 3 过程问的依赖关系分析 为了开发大粒度并行性以及全程优化，需要利用过程间依赖关系分 析技术。过程繁衍技术【2 9 】提高了过程间依赖关系分析的精度和效率。流 敏感的过程间数据流分析框架的引入，使得分析的精度和效率及可分析 的程序的大小都得到了提高。精确而又易于操作的数组表示，为精确的 过程间数组引用分析奠定了基础。 过程繁衍 传统上有两种方式用于处理程序中的过程调用。 最简单的是过程嵌入( i n t i n e ) 的方法。过程嵌入是在过程被调用处直 接加入过程体的一个副本。这种方法的优点是，对过程的优化可以根据 调用点的上下文来进行。它的缺点是可能导致程序代码的过度膨胀及编 译时间过分延长，而且一些过程不能被嵌入。 第二种方法是上下文不敏感的过程间数据流分析技术。在分析一个 过程时，它将所有调用点信息的综合作为入口信息，因此，每个调用点 所获得的被调用过程的信息将是一致的。采用这种技术的优点是只需为 每一个过程生成一个实现( h n p l c 豇n e n t a t i o n ) 。它的缺点主要是对具体调用 点而言，信息是不精确的，影响过程和整个程序的优化。 流敏感的过程间数据流分析框架 传统的过程间数据流分析，或者是由于全部采用过程嵌入技术而难 以分析大程序，或者是由于缺少特定路径的过程间信息而精度不够，或 者是分析效率太低。h a l l 等人提出的流敏感的过程间数据流分析框架例 具有分析效率高、分析结果精确以及可以容易地分析大程序等特点，还 集成了支持过程边界数组变形( a r r a yr e s h a p e ) 的公式。这主要是通过组合 下面两项技术而得到的。 中国石油大学( 华东) 硕士论文第2 章理论基础介绍 基于区域( r e g i o n - b a s e d ) 的流敏感分析。为了获得精确的过程间信息， 需要使用流敏感的分析方法，即根据程序中每条可能的控制流路径导 出分析结果。通过使用基于以表示嵌套关系为基础的区域图的分析，h a l l 等人的框架解决了其他方法可能会出现的不可能存在的路径 ( u n r e a l i z a b l ep a t h s ) 的影响以及慢收敛问题。 选择性过程繁衍。对于程序中由多条路径激活的过程，h a l l 等人的 框架采用了选择性过程繁衍技术，即只有在能提供优化机会时才使用路 径特定的信息。这样既可以得到与完全嵌入相同的精度，也避免了不必 要的复制。 数组区域的表示 精确的数组的数据流概要分析首先要用合适的形式表达和描述数组 区域。在选择表达方式时，要考虑表达的精确性、区域合并的能力以及 检测区域相交的能力。 传统的描述方法都只描述单区域。由于合并操作的不封闭性，为了 用单区域描述合并操作的结果，只能采用近似的方法，这会丢失概要信 息。g a r s ( g u a r d e da r r a y 托g i o 璐) 表示方法【3 0 】使用规则数组区域的链表来 表示访问区域，还为规则的数组区域增加了卫哨( g u a r d s ) ，以更好地处理 l f 条件。g a r t s 的使用为数组概要信息提供了更精确的表示，有利于数 组私有化等优化的进行。 2 3 程序变换技术 程序变换技术是一种优化技术，它的目的是将一些妨碍并行性的相 关消除，从而使程序能够被更有效的并行化( 而不是从串行程序到并行 程序的变换) 它在改善程序性能的同时，不能破坏程序的正确性，因此， 变换前后要保证程序在语义上是等价的 程序变换是自动并行化的关键技术之一，目前已取得了很大的进展， 提出了许多的变换技术，如标量扩展( s c a l a re x p a n s i o n ) 、循环裂变( 1 0 0 p f i s s i o n ) 、循环聚变( 1 0 0 pf u s i o n ) 、循环交换( 1 0 0 pi n t e r c h a n g i n g ) 、循环单 重化( 1 0 0 pc o l l a p s i n g ) 等。这些技术都是为了提高并行度或者便于实现并 行化而提出的。e i g e n m a n n 等人通过手工并行化标准测试程序包所进行 1 2 中国石油大学( 华东) 硕士论文第2 章理论基础介绍 的大量研究【3 1 l 表明，数组私有化、归约操作并行化和广义归纳变量 ( g e n e r a l i z e di n d u c t i o nv a r i a b l e s ) 替换是开发并行性最重要的程序转换技 术。 数组私有化 标量或数组的私有化是指将标量或数组的拷贝分配于每一个处理节 点。私有化可以消除循环反依赖和输出依赖，开发并行性。标量的私有 化技术已被普遍采用，两由于确认可私有化数组的复杂性，数组私有化 技术还未被普遍采用。 数组私有化判定的条件是简单的：如果数据项在循环迭代中定值先 于引用，则可以私有化。为了发现这些信息，需要对数组或数组块的定 值和引用进行复杂的分析 2 9 , 3 0 1 。由于可私有化的数据结构常常是数组的 一部分，它的范围一般由标量变量的值确定，确定这些标量变量的值常 常需要进行过程间分析，包括对变量的值、变量间关系、关系保持的条 件的分析及过程间常量传播、符号值传播1 3 2 1 分析的精确程度也与编译 器对数组区域的表示能力有关。因此，数组私有化能力的开发是紧密依 赖于过程间分析的能力的 归约操作并行化 归约变量工是指循环体中这样的一个变量，它出现在形如f x o e x p 的结合操作( a s s o c i a t i v eo p e r a t i o n ) 中，其中。是结合操作符，并且x 不出 现在表达式e x p 或循环的其他位置归约变量引起的数据依赖妨碍了循 环的并行性开发归约变换可删除由归约操作所引起的数据依赖。 开发归约并行性需要做两步工作：识别归约变量和并行化归约操作。 归约变量的识别过程是，首先将循环体中语句与归约模板进行语法 匹配，然后对候选变量进行数据依赖分析并行化归约操作可用以下几 种不同的方式来实现： ( 1 ) 原位同步。每一归约操作用l o c k u n l o c k 对加以保护。这种变换 需要改变的代码最少。 ( 2 ) 私有化并行归约。这种方法将部分和加入循环私有的变量，这些 变量以后用于在临界段中更新初始变量。使用私有部分和变量提高了局 部性，但仍然需要同步段。 中国石油大学( 华东) 硕士论文第2 章理论基础介绍 ( 3 ) 扩展并行归约。这种方法将部分和变量扩展为具有与处理机相同 数量的元素的一维数组，并赋予全程域。每一处理机使用处理机号为索 引使用数组的一个元素。并行循环结束后，部分和被加入初始变量。这 种变换产生了可完全并行的循环。 如何挑选合适的并行化方法以及如何将这些方法组合使用，需要综 合考虑循环迭代的数量和处理机环境。 广义归纳变量替换 循环中的数组下标经常使用形如v = vo pk ( 其中k 的值是循环不变 式) 归纳变量的