（计算机软件与理论专业论文）嵌套循环的自动并行化及在mpi平台上的实现.pdf

大连理工大学硕士学位论文 摘要 随着高性能计算机技术的迅猛发展，高性能计算机逐渐在很多行业的得到应用。网 格技术的迅猛发展更是促进了高性能计算机的使用。要充分发挥高性能计算的效能，要 有与之相适应的软件，并行操作系统、并行编程工具和应用程序是高性能计算机所需的 主要软件。特别是应用程序，适合在高性能计算机上运行的是并行应用程序，而编写并 行程序的难度远大于编写串行程序的难度，很多并行程序只能由专家来编写，这种状况 阻碍了高性能计算机的广泛使用。自动并行编程工具的出现无疑将会大大改变这种现 状，使很多串行程序员也能够在其帮助下编写出并行的应用程序。 自动并行化技术是随着编译器优化技术的发展而产生的，经过多年的发展已取得很 大的进展，特别是在基于共享主存的自动并行化方面，很多理论已趋于成熟。但是现有 的自动并行化工具都是在底层实现的，并行化后的程序可移植性差。基于分布式主存的 高性能集群系统是高性能计算机的发展方向，并且用户能够在前台直接使用的自动并行 化工具具有很大的实用性。消息传递接口m p i 已经作为一种事实上的消息传递标准被广 泛使用，具有很好的可移植性。 针对这种现状，本文在研究传统自动并行化理论的基础上，进行了如下工作： ( 1 ) 构建了一个实验性的程序分析平台； ( 2 ) 在平台上对基于嵌套循环类语句为基础的串行c 程序实现了数据流分析、依赖 分析、数据划分及自动生成m p i 并行程序： ( 3 ) 实现了一种基于s p m d 的自动并行转换模式； ( 4 ) 对并行化的程序在深腾1 8 0 0 大型机上进行了性能测试。 关键词：并行化；消息传递；分布式主存 大连理工大学硕士学位论文 a u t o m a t i cp a r a l m i z a t i o na n di m p l e m e n t a t i o no fl o o pn e s tb a s e do nm p i p l a t f o r m a b s t r a c t w i mt h er a p i dd e v e l o p m e n to fh i g hp e r f o r m a n c ec o m p u t i n gt e c h n o l o g y , h i g h p e r f o r m a n c ec o m p u t e r sh a v eb e e nw i d e l yu s e di nm a n yf i e l d s t h er a p i dd e v e l o p m e n to fg r i d c o m p u t i n gt e c h n o l o g yh a sg r e a t l yi m p r o v e dt h ea p p l i c a t i o n so fh i g hp e r f o r m a n c ec o m p u t e r s t h ek e ys o f t w a r e ，s u c ha sp a r a l l e lo p e r a t i n gs y s t e ma n dp a r a l l e la p p l i c a t i o np r o g r a m ，i s n e c e s s a r yt om a k eg o o d 眦o fh i g hp e r f o r m a n c ec o m p u t e r s b mv e r yf e wp r o g r a m m e r sc a n w r i t ep a r a l l e lp r o g r a m ，a n dm a n yp a r a l l e lp r o g r a m sa r es t i l lm a d ea te x p e r tl e v e l t h i s s i t u a t i o nh a sm a d ei tv e r yd i f f i c u kt ou s ew i d e l yh i g hp e r f o r m a n c ec o m p u t e r s a u t o m a t i c p a r a l l i z a t i o nt e c h n o l o g yw i l lg r e a t l yc h a n g et h i ss i t u a t i o n i tw i l lh e l pp r o g r a m m e rm a k e p a r a l l e lp r o g r a me a s i l y t h et e c h n o l o g yo fa u t o m a t i c p a r a l l e l i z a t i o n h a sm a d eg r e a tp r o g r e s sw i t ht h e d e v e l o p m e n to fo p t i m i z i n gc o m p i l e r st e c h n o l o g y t h er e l a t e dt h e o r yb a s e do ns h a r i n g m e m o r yi sb e c o m i n gp e r f e c t l y b u tt h ec u r r e n ta u t o m a t i cp a r a l l e l i z e ri ss t i l lr e a l i z e da tl o w e r l a y e r t h ep a r a l l e lp r o g r a mm a d eb ym e a n so ft r a d i t i o n a la u t o m a t i cp a r a l l i z e rc a nn o t t r a n s p l a n te a s i l y m p ih a sb e e nw i d e l yu s e da sar e a l l ys t a n d a r da n dam e s s a g et r a n s p o s e d i n t e r f a c e ，w h i c hh a sg o o dt r a n s p l a n t i n g t h em a i nc o n t r i b u t i o n so f t h i sp a p e ra r es u m m a r i z e da sf o l l o w s ( 1 ) c o n s t r u c tat e s t i n gp l a t f o r mf o ra u t o m a t i cp a r a u e l i z a t i o n ； ( 2 ) i m p l e m e n tp r o g r a ma r c h i t e c t u r ea n a l y s i s ，d e p e n d e n c ea n a l y s i s ，d a t ad i v i d i n ga n d t r a n s l a t i n gt h ea s tt om p ip a r a l l e lp r o g r a mo np a r to fs e r i a lcl a n g u a g es o u r c e p r o g r a m so nt h ep l a t f o r m ； ( 3 ) i m p l e m e n tt h es p m dm o d e lo fa u t o m a t i ct r a n s l a t ef r o ms e r i a ls o u r c ep r o g r a mt o p a r a l l e lp r o g r a m ； ( 4 ) t e s tt h ep e r f o r m a n c eo f p a r a l l e lp r o g r a mm a d eb yt h ea u t o m a t i cp a r a l l e lp l a t f o r m k e yw o r d s ：p a r a l l e l i z a t i o n ；m e s s a g ep a s s i n g ；d i s t r i b u t e dm e m o r y i i 独创性说明 作者郑重声明：本硕士学位论文是我个人在导师指导下进行的研究工 作及取得研究成果。尽我所知，除了文中特别加以标注和致谢的地方外， 论文中不包含其他人已经发表或撰写的研究成果，也不包含为获得大连理 工大学或者其他单位的学位或证书所使用过的材料。与我一同工作的同志 对本研究所做的贡献均已在论文中做了明确的说明并表示了谢意。 作者签名：到塾 日期：竺! ：兰! ! ! 大连理工大学硕士研究生学位论文 大连理工大学学位论文版权使用授权书 本学位论文作者及指导教师完全了解“大连理工大学硕士、博士学位论文版权使用 规定”，同意大连理工大学保留并向国家有关部门或机构送交学位论文的复印件和电子 版，允许论文被查阅和借阅。本人授权大连理工大学可以将本学位论文的全部或部分内 容编入有关数据库进行检索，也可采用影印、缩印或扫描等复制手段保存和汇编学位论 文。 作者签名：到壑 导师签名 垒本牝 圣翌年! 三月! 工日 大连理工大学硕士学位论文 1 绪论 1 1 课题提出的背景 随着高性能计算机技术的发展，高性能计算机已逐步应用到各个行业，特别是在大 规模科学与工程计算领域，比如，高速列车、海洋平台、高耸建筑物、核电站工程、航 空航天器等重大工程结构系统设计中的关键力学及多学科耦合问题，新材料的研究与制 备，材料的光电与结构性质及其演化分析，生命科学中的生物组织演化，基因重组，新 药研制，环境科学中的气象预报，灾害预测，污染扩散和防治，能源科学中的油气藏模 拟，地震波反演，采油工艺过程的模拟，军事上的核爆炸模拟等。而基因工程、全球气 候准确预报、海洋环流等被称为2 l 世纪人类所面临的“巨大挑战”问题，更是离不开 高性能计算机。在我国，高性能计算机技术也得到了很快的发展，目前代表我国高性能 计算机水平的主要有，银河机、神威机、深腾6 8 0 0 、曙光4 0 0 0 a 等，这些高性能计算机 正被广泛使用，很多大专院校及科研院所都已配备了高性能计算机。 高性能计算机要充分发挥作用，不仅要有高性能的硬件系统，也要有与之相应的软 件系统，包括支撑高性能计算机的并行操作系统、并行编译器、并行编程语言及其他适 合于高性能计算机的应用软件。并行计算机的体系结构、并行编译系统、并行操作系统 都是高性能计算机中不可或缺的一步分。而对于各行业的程序员来说，要充分使用高性 能计算机，必须编写出能够在高性能计算机上运行的并行程序。但是各个行业的程序员 大都是具有本行业背景的非计算机专业的程序员，即使是计算机专业的程序员，编写出 高质量的并行程序也不是一件容易的事，很多并行程序都是由专家编写的。而在各领域， 多年来积累了大量的串行程序，这些程序难于在并行计算机上发挥作用。要改变这种现 状，普遍认为新的并行环境或新的并行语言是解决并行程序开发的最终途径“1 。但就目 前而言，迫切需要一种工具能够将用户的串行程序自动转换为并行程序，即自动并行化 工具，使用户在编程时只需按串行的方法编写程序，而转变为并行程序是系统的事，这 不仅可以大大减轻程序员的负担，而且能够充分利用现有的程序资源。即使在将来，有 了新的并行环境或并行语言，自动并行化工具也会起到应有作用。 并行化工具可以作为一般的工具软件单独使用，即由用户来使用，也可以做为编译 器的优化器嵌入到并行编译器中。而前一种是在程序的源码一级实现的，用户能够看到 程序并行化后的并行源程序，也可以对其进行修改，因此，对于并行程序员也能提供参 考，可移植性好。而后一种是在并行编译中作为一遍扫描的并行化过程来实现，由编译 嵌套循环的自动并行化及在m p i 平台上的实现 器在中间代码一级来实现并行化1 2 】。自动并行化工具与并行编译系统的关系如图1 f 2 】所 示： 图1 1 并行编译体系结构 f i g u r e 1 。ls k e l t o no f p a r a l l e lc o m p i l a t i o n 1 2 国内外的研究现状 自从有了在大型计算机上运行的编译器，就开始了对编译器的性能的研究，也就有 了对编译器的优化器的性能的研究。而对自动并行化技术的研究，最早可以追溯到2 0 世 纪6 0 年代，虽然当时还没有自动并行化方面的专门研究，但是，当时的编译器的研究人 员就已提出了数据依赖【3 】，而数据依赖正是自动并行化的关键技术之一。自动并行化的 大连理工大学硕士学位论文 前身是自动向量化，将串行程序转换为在向量机上运行的程序。自动向量化的技术始于 7 0 年代，由l a m p o f t 【4 j 吲和k u c k ，m a r a o k a 和c h e n 6 1 1 7 1 最早陈述( 3 j 。到8 0 年代后，自动向量 化技术发展成熟，比较有代表性的自动并行化系统有r i c e 大学的f o r t r a n 转换器 ( p f c ) ，i l l i n o i s 大学的p a r a f i ：a s e ，a r d e n t 计算机公司的a r d e nt i t a n 。 自动并行化技术是在8 0 年代中期，随着并行计算机的发展而逐渐兴起的，自动并行 化技术以向量化为基础，但又和向量化有很大的不同，尤其在并行转化的算法上。而自 从9 0 年代以来，自动并行技术取得了很大的发展，出现了很多自动并行化系统，如 m a r y l a n d 得t i n y ，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 自动并行化系统，西北工业大学的 p a r a c t i v e ，清华大学的交互式并行化系统t i p s 。而我国比较有代表性的商业化的自 动并行软件是北京飞箭公司的有限元自动并行化软件，能够根据用户提交的符合其要求 的文件自动生成并行的有限元软件。 自动并行化软件根据其设计的目的可分为专业性的和通用型的，专业性的自动并行 化软件的适用范围通常是某一特定领域，如前面提到的飞箭公司的有限元自动并行化软 件，适用于有限元分析领域，而西北工业大学的p a r a c t i v e 也是适用于物理流场分析 的专业性软件。通用性软件不具体针对那一特定领域，试图发现程序中的各类并行性， 如复旦大学的a f t 。但就目前自动并行化软件的发展来看，不论是通用性软件还是专业 性软件，大都偏向于数值计算领域，试图从循环体中发现并行性，所依赖的关键技术是 依赖分析，包括数据依赖和控制依赖。在非数值计算领域，自动并行化软件的并行化能 力还显得非常弱。这一方面与自动并行化技术脱胎于程序的优化编译技术有关，也与大 型计算机最初主要用于科学计算有关，另一方面，在非数值计算领域，还没有成熟的并 行化分析理论产生，也许随着人工智能技术的发展自动并行化会在非数值计算领域取得 突破。根据自动并行化软件获取程序信息的方式，可分为人机交互式的和完全自动并行 化的方式。前者有的不需要读入程序，而只须用户输入一定的信息就可实现并行化，有 的需要读入源程序文件，并在分析过程中提示用户输a - - 定的信息来实现并行化，而完 全的自动并行化软件则只需用户输入能够正确运行的串行源程序，其它的步骤完全由自 动并行化软件来完成。交互式的软件在实现上要相对容易，在某些特定的领域比如有限 元分析、物理流场分析中都取得了很好的效果，可以很快投入使用。完全自动并行化的 实现有很多困难，对有些程序并行化的效果不好，离实际应用还有很大的距离。但是， 从长远的观点来看，完全自动并行化是有很大的潜力的，是自动并行化发展的方向。 根据自动并行化软件所输出的并行程序适合的体系结构，可分为面向共享主存的和 面向分布式主存的。前面提到的大部分软件都是基于共享主存的，面向共享主存的自动 嵌套循环的自动并行化及在m p i 平台上的实现 并行化软件已取得了很大的发展，而基于分布式体系结构的并行化软件的进展缓慢，由 于不能共享主存，造成了数据的远程访问，增加了通信消耗，并行化后的加速比和效率 要低于基于共享主存的并行程序。但是，基于分布式体系结构的并行机是大型机发展的 主要方向，随着大型机内部网络技术的提高，基于分布式主存的自动并行化工具具有很 大的应用前景。 1 3 本文的工作及研究方法 目前已有的自动并行化系统，在对f o r t r a n 语言的自动并行的研究进展非常大，但 对c 语言的自动并行的研究还不成熟，c 是作为一种”有类型的汇编语言”0 3 被设计的， 其语法灵活多变，“在很多情况下，c 的原则是：不仅不需要优化，而且不希望进行优 化”啪，处理起来不如f o r t r a n 和p a s c a l 等模块化语容易，特别是指针和别名伽及方言 啪的存在，增加了对c 语言进行并行化分析的难度，但由于c 语言程序的性能要在许多 方面都优于其他的高级语言程序的性能，c 语言已逐渐由开发大型系统软件的领域扩展 到其它各个领域，如科学计算等。c 语言正在逐渐成为一种普遍使用的程序设计语言， 因此，本文的自动并行化系统就建立在对c 语言源程序的分析基础上。m p i ( m e s s a g e p a s s i n gi n t e r f a c e ) 作为一种基于消息传递方式的并行编程技术和实事上的标准已得 到广泛的应用，它基于消息传递的方式使其能够广泛应用于多类并行机，特别适合在分 布式体系结构的并行计算机上应用，因此，基于m p i 的自动并行化系统将在实际应用中 具有很高的应用前景。 本文的主要工作如下： 研究现有的自动并行化技术与理论，并构建了一个实验性的程序分析系统。 在所构建的系统中通过数据流分析、数据依赖分析、数据划分及并行转换等过 程，依次发现各个多重循环中的并行性，并将其转换为m p i 并行程序。 为了检验本文的自动并行化系统的并行化能力，本文对多个有代表性的c 语言 串行源程序进行并行化实验，并对并行化的程序在深腾1 8 0 0 大型机上进行性能测试， 测试其加速比和运行效率。 1 4 本文的组织结构 全文共分六章。 第一章绪论。介绍课题提出的背景、国内外的研究现状及本文的研究工作及方法。 第二章自动并行化的关键技术。介绍现今国内外关于自动化并行化的关键技术和理 论。 一4 - 大连理工大学硕士学位论文 第三章消息传递并行编程环境m p i 。介绍消息传递并行接口m p i 的编程模式及本 系统中用到的命令。 第四章基于m p i 的自动并行化系统模型。详细阐述本文的自动并行化系统的设计 细节。 第五章有关算例及性能测试结果。对多个典型的串行的c 语言程序进行并行化， 并将并行化的程序在深腾1 8 0 0 大型机上运行，测试由并行化系统生成的并行程序的性 能。 第六章结论与展望。结合实验结果对全文进行总结，并对下一步工作提出计划。 嵌套循环的自动并行化及在m p i 平台上的实现 2 自动并行化的关键技术及理论 自动并行化技术脱胎于编译器的优化技术，因此，自动并行化的许多技术都与编译 技术有关。要对源程序进行并行化，首先是要理解源程序，然后是找出可并行化的部分 进行并行化。这一过程需要数据依赖分析技术、控制依赖分析技术。以下各节分别对现 有的各种技术及理论作以介绍。 2 1 并行化及向量化 程序并行化技术包括针对向量计算机的向量化和针对并行计算机的并行化技术。程 序并行化的对象可以是串行程序，也可以是并行程序，本文并行化系统的对象是串行程 序。将一个串行程序并行化就是要发现并将其可并行部分组织为并行进程或线程，并且 要优存储访问和减少同步、通信与组织循环并行执行的开销。基于分布式主存的体系结 构中，减少通信与同步的开销对提高并行程序效率至关重要，必须注意减少通信复杂性， 尽量避免不必要的远程访问。 2 1 i 向量化介绍 一个向量是由一组元素组成的有序集，元素的个数称为向量的长度。串行程序中常 常用循环来实现对数组的操作。当满足一定的条件时，就可以把一个循环中对数组元素 的操作用向量操作来实现。 向量化主要是针对向量计算机，串行程序向量化是指在依赖分析的基础上，通过一 系列的程序转换技术，消除防碍向量化的依赖关系，使程序中尽可能多的循环向量化。 一个可向量化的循环在原语言一级可用向量语言或串行语言加向量化编译指导命令来 表示。 可向量化循环的定义和判定条件如下： 定义2 1 “1 如果循环中仅含赋值语句，且每个语句都可以在循环中它之后的语句 执行之前，执行完对应于循环区间的每一个实例，而结果与串行执行时相同，则称该循 环是可向量化的。 设s 和r 是两个语句，s t 表示在程序中语句s 出现在语句r 之后 2 1 。 定理2 1 嘲一个循环是可向量化的，当且仅当对于循环体中的任意两个语句s 和n 当s 0 d ( i ，) 。= ”_ t 。，如果d ( f ，- ，) = 0 ( 扫1 ，2 ，打) ( 2 1 ) l ” ”，如果d ( f ，- ) i o ( 即d ( i j f ) 包含一个“ ”作为它的最左非“= ”分量) 。 定义2 7 咖从语句蜀到语句& 的循环携带依赖被称为后向的，如果在循环体中岛 出现在s l 前，或者蜀和& 是相同的语句；携带依赖被称为前向的，如果在循环体中 出现在蜀之后。 定义2 8 。1 携带循环依赖的层是此依赖的d ( i d 的最左非“= ”的索引。 嵌套循环的自动并行化及在m p i 平台上的实现 与循环携带依赖相反，循环无关依赖是由相对语句位置引起的。因此，循环无关依 赖决定循环嵌套中代码的执行顺序，而循环携带依赖决定循环必须迭代的顺序。 定义2 9 0 1 语句有一个对语句两的循环无关依赖，当且仅当存在两个迭代向量f 和_ ，使得s l 在迭代f 中引用存储单元 以岛在迭代j 中引用必且坷；并且迭代中 有一条从s l 到的控制流路径。 2 2 2 数据依赖测试的基本定理 对于嵌套循环厶设s 和r 为其循环体中的两个语句，x 和y 分别为s 和丁中对数组 4 的引用，定理2 6 给出了导致s 和r 之间存在依赖关系的必要条件。 定理2 6 习对于嵌套循环l 中的任意两个语句s 和t ，设x ；4 ( z ( ，) ， ( d ，正( ，) ) 是s 的一个变量，y ；a ( g ( n g ：( n ，g 。( 聊是丁的一个变量，且x 和y 中至少有一个 是其所在语句的输出变量，a 为n 维数组，石和昏( 1 七而均是索引向量 卢( 几五，五) 的线性整值函数。如果这两个变量导致5 和，之间的依赖关系，则方程组 五& = o 1 k 珂 ( 2 2 ) 又满足约束条件( 以下简称“约束”) p ，f ，g ，p ，q ，0 ，m ( 2 3 ) 的整数( f ，力，其中i = ( i t ，如，f 。) ，产u ，办，厶) 。并且，这个解满足下述特定情形下的 附加条件： 若s t 且鼢l 则f g ； 若争r 且鼢l 则f 止 若s _ f ； 定理2 7 。1假设方程组( 2 2 ) 有整数解( 力满足约束( 2 3 ) 那么 若i 工则r 占s ； 若巧，且s t 则s 8 n 2 2 3 数据依赖测试常用方法 在并行化系统中进行数据依赖测试，就是判断循环嵌套中在相同数组的下标引用之 间是否存在依赖。依赖一般采用保守的方法，即如果不能明确地证明依赖不存在就必须 认为依赖存在。依赖测试方法有精确的方法和近似的方法。常用的方法有一维g c d 测 大连理工大学硕士学位论文 试、广义g c d 测试、b a n e r j e e 测试、d e l t a 测试、傅氏消去测试、o m e g a 测试等。这些 方法大都是针对线性数组下标进行的，对于非线性的下标还不能进行测试。文献 2 5 】中 对g c d 测试和b a n e r j e e 测试作了介绍。下面就常用的方法分别加以介绍。 ( 1 ) 一维g c d 测试 一维g c d 测试是一种精确的测试方法，可以对一对一维线性下标进行测试，以确 定是否存在数据依赖，对于存在依赖的能够得出数据依赖的精确距离。 对于同一数组的两个下标表达式口l “+ 6 1 和a 2 i 2 + b 2 ，如果方程a l l l + 6 l = a 2 i 2 + b 2 有满足 约束f p p 毛i l - ；p 、g 为整数) 的解，那么两个下标表达式之间就存在依赖，相关的定理 如下： 定理2 9 。1 设a 、b 、c 表示整数，且a 和b 不同时为0 ，令g = g c d ( a , b ) ( 求a 和b 的最大公约数) 。线性丢番图方程 a x + b y = c ( 2 4 ) 有解，当且仅当g 除尽c 。当有解时，通解为 力= ( c x o g + b t g , c y o g + a t g )( 2 5 ) 其中，t 是任意整参变量，( x o , y o ) 是使得g = a x o + b y o 成立的一对整数。 定理2 1 0 。1 如果在循环l 中语句s 的变量a ( a t + a o ) 和语句t 的变量a ( b l + b o ) 导致 语句s 和r 之间存在依赖关系，则整数( 6 0 - 印) 是整数g c d ( a , b ) 的整数倍。 ( 2 ) 广义g c d 测试 依赖关系测试的基本思想就是找到一组线性方程组和线性不等式的整数解。一维 g c d 测试只能对数组的一维线性下标表达式进行测试，而对于多维下标，则必须用广 义的g c d 测试与其它的测试方法配合，比如b a n e r j e e 和傅氏消去测试。广义g c d 测试 能够检查现行方程组是否有整数解。广义测试的相关定理与算法如下： 定理2 1 1 “1 令4 为给定的m x n 的整数矩阵，c 为给定的n 个元素的整向量，x 为 肼个元素的变元向量，u 为一个m x m 的幺模矩阵，e 为一个m l t 的阶梯阵，且有u a = e 。 方程组 x a = c ( 2 6 ) 有解当且仅当存在一个m 个元素的整向量t 使得 t e = c ( 2 7 ) 当存在一个解时，方程组( 2 7 ) 的通解为 x = t u 嵌套循环的自动并行化及在m p i 平台上的实现 其中，t 是满足t e = c 的任意整向量。 算法2 1 脚对于嵌套循环l 中语句s 的变量x ( i s a + a o ) ，语句r 的变量x ( i t b + b o ) ， 其中，x 是一个n 维数组；a 是一个m 。x n 的矩阵；b 是一个m r n 的矩阵；a o 、岛是 栉个元素的整向量。这个算法判定这两个变量是否引起s 和r 之间的依赖关系。 找一个( m s + m t ) ( m 。切扣的幺模矩阵扩和一个( m s + m r ) h 的阶梯阵e 使得 叫二卜 亿s ， 如果语句s 的变量x ( i s a + a o ) 和语句t 的变量x ( i r b + b o ) 弓l 起一个s 和r 之间的依赖 关系，则可以求出一个( 怖+ 聊0 各元素的整向量t 满足方程 t e = b o - a o( 2 9 ) 如果用这个算法找不到f ，即找不到依赖方程的整数解，则依赖关系不存在。但若找 到整数解，则还不能说依赖关系就一定存在，因为这个解还必须满足依赖关系的约束条 件。对于幺模矩阵u 和阶梯阵e 可通过使用增广矩阵，利用线性代数的初等行变换来 求得，详细的算法见第4 章。 ( 3 ) b a n e r j e e 测试 通过广义g c d 测试能够检查线性方程组是否有整数解，如果线性方程组没有整数 解，那么一定不存在依赖，但即使线性方程组有整数解也不一定存在依赖，是否存在依 赖还要看存在的整数解是否满足线性不等式的约束。判断能否满足这种约束的一种方法 是采用b a n e r j e e 测试。在文献 1 3 】、【1 4 、【1 5 “1 6 】中对b a n e r j e e 测试测试详细的介绍。 对于规范化的单层循环，语句s 的一个变量a ( a i + a o ) 和语句r 的一个变量a ( b i + b o ) 导致的依赖方程为 印6 广| c( 2 1 0 ) 其中，c f f i b o a o 。而依赖约束为 0 。裟q s ，i 、 假定t s ，要测试r 是否依赖于就要知道方程是否有满足约束及f 广1 的解， 那么方程的左部定义了一个线性函数正s 埂x # ) = a x - b y ，要确定方程在三角形的区域中是否 有实数解，那么，当且仅当 大连理工大学硕士学位论文 n f i n f ( x ，力c 茎m a x f ( x ，力( 2 1 1 ) j y ) g p( j 。y ) g p 定义2 11 嘲一个实数a 的正部分表示为口+ ，负部分表示为旷。其定义如下： a + - - - m a x ( a ，o ) ，a = m a x ( - a ，0 ) ( 2 1 2 ) 定理2 1 2 1 3 1 令a 、b 、q 、8 为实数，q o ，o t q ，数f ：( x , y ) - - a x + b y 在由不等式 组 0 x q 1 0 y q z - y 一占- j 确定的直角三角形中的极小值和极大值是 m i n f ( x ，y ) = 6 占- ( q - 8 ) ( a 一- b ) + 。，7 扣，) ，) ：( 口+ + 6 ) + ( 2 1 3 m a x f ( xb c 4 - - s ) ( a ) ，) ，) =( 口+ + 6 ) + 。 ( j ，y ) g p 令： i t ( a ，b ，q ，占) = b 8 一( g 一占) ( 口。一6 ) +( 2 1 4 ) v ( a ，b ，q ，占) = b g 一( g 一占) ( 口+ + 6 ) + ( 2 1 5 ) 定理2 1 3 啪假定循环三中语句s 的一个变量彳( 珏，+ 口o ) 和语句t 的一个变a ( b l + b o ) 引起一个s 和丁之间的依赖关系。令c = b o a o ，那么 j 如果s t 且黝r ，则 4 a ，一6 ，q ，o ) c 兰v ( a ，- b ，q ，0 ) 如果乒，且s j s ，则 i z c a ，一b ，q ，一1 ) c v c a ，- b ，q ，1 ) 如果s t 且z 瓠，则 ( 一b ，a ，q ，1 ) c v ( 一6 ，a ，q ，1 ) 以上是一维单循环数组依赖关系的b a n e r j e e 的测试方法，对于多重循环的情况，相 关定理如下： 定理2 1 4 。1 如果在嵌套循环中语句s 的变量x ( a o + 口，) 和语句t 的变量 x ( b o + z b r i r + 6 ，l 一。) 导致丁在第，层上依赖于s ，则下述两个条件成立： 口l - b l ，砚一b 2 ，a 1 厂6 ma l ，b l , ，b r a t 的最大公约数g c d 整除( 6 0 - a o ) ； 嵌套循环的自动并行化及在m p i 平台上的实现 蔓b o - a o v 。其中 = “( 口，一以，0 ，p ，q o ) + ( 口，- b l ，p ，q ，1 ) ，0 ，p ，+ 吼，o ) + “1 “ ( 2 1 6 ) m ， 芝( 口r ，o ，p ，q ，o ) + ( 以，0 ，p ，q ，o ) + ( 6 ，0 ，p + 一，g + ，- 。，o ) ；：芝y ( q 一6 r ，o ，肼，g ，o ) + y ( q 一岛，乃，g ，1 ) 壹t ，( 口，0 , p r + 靠，o ) + “ ( 2 1 7 ) 艺v ( a r , o ，p ，g ，o ) + 矿( _ 6 ，0 ，p ，g ，o ) + y ( _ 6 0p m 扩。，o ) 定理2 1 5 嘲令盯- ( 们，o 2 ，) 表示一个其元素为集合 o ，1 ，1 ，木) 中的任一成员 的向量( “”表示1 、1 、o ) 。如果在嵌套循环语句中语句s 的变量x 以o + 口，) 和语 句t 的变量x ( b o + b ，+ b ，i m , 一，) 导致t 以方向向量盯依赖于s ，则下述两个条 件成立： 下面3 组数的g c d 整除( b o - a o ) ： a r - b ：1 ，m 且西= 0 a r ：1 ，m 且听0 或m + i s r s 肌s 6 r ：i ，m 且听o 或m + l ，g m r 6 0 - - a 0 p ，其中 a = p ( 口，- b e ，0 ，p ，g ，o ) + z l ( a ，一以，p ，q ，1 ) + ( 一6 ，口，p ，q ，1 ) + 口，a ，- 1a r 一t i ，m 1 甜如i 甜m 阻( 口。0p ，g ，o ) + ( _ 6 0p ，g ，o ) 】+ ( d ，o 。p q ，o ) + ( 2 1 8 ) a 一 r m + 、 ( 一b ，0 ，p + ，一。，q 恤+ ，。，o ) 大连理工大学硕士学位论文 y = y ( 口，- 6 ，o ，p ，g ，o ) + p ( 口，6 ，p ，g ，1 ) + v ( - b ，口，p ，g ，1 ) + 以盯。l o e ；一i l ，j 加1 f f r mi s r m m o e y ( 口，0 ，p ，q ，o ) + v ( - b ，0 ，p ，q ，o ) 】+ 乏：y ( 口，0 ，p ，q ，o ) + ( 2 1 9 ) 以f r f f i m + l i g 辨 m r y ( _ 6 ，0 ，p 啦+ ，。，q 帕+ ，一。，o ) r f f i m + l 对于多维数组，假设维数为珂，可以进行以次边界测试，如果有一次测试失败那就说 明不存在依赖，但反过来就不一定成立。其定理如下： 定理2 1 6 嘲考虑1 1 1 层嵌套循环l 中的两个语句s 和乃令x ( i a + a o ) 为s 中的一 个变量，x ( i b + b o ) 为t 中的一个变量，其中工是一个疗维数组，d 1 0 = ( a 0 1 ，a 0 2 ，e 1 0 。) 和 b o = ( b o l , b 0 2 ，6 曲为阼个元素的整向量，a f ( a , k ) 和b = 妒曲为m x n 的矩阵。如果这两个 变量导致，在第，层上依赖于s 则下述条件成立： 对于每个丘l k 栉，口i 一b 们，a ( - l 耻一6 ( f - 1 ) ，口盹，乩，如的最大公约 数整除( b o k - a o k ) ； 对于每个k , 1 k 疗，有 t b o 一口o t 蔓y 其中 一 ，一l 以= ( - b m ，0 ，p m q ，o ) + z ( a _ c k 一钆，p l 帅q1 ) + r = l 阻( ，0 ，p q ，o ) + ( - 6 庸，0 ，p q ) 】 ( 2 2 0 ) ( 2 2 1 ) v k = v ( a m - b m ，0 ，p m q ，o ) + y ( 一b l k ，p l m q1 ) + “1 ( 2 2 2 ) 【p ( ：o ，p q ，o ) + l ，( _ 6 ，0 ，p q ) 】 上面的定理对多下标的耦合情况，处理的结果不准确，要处理耦合情况需使用x t 6 1 测试。 ( 4 ) d e l 诅测试 d e l t a 测试是用来测试对下标依赖的一种直观的方法，可看成是x 测试的受限形式。 d e l t a 测试的主要思想是建立起关于距离向量交集的直觉。因为在实践中发现多数下标 嵌套循环的自动并行化及在m p i 平台上的实现 是s i v ，并且多数情况下s i v 下标是简单而精确的，所以从中收集到的信息能用来化简 相同耦合组中其他下标的测试。在d e l t 测试中检查耦合组中的每个s i v 下标，产生一 些约束条件并能传播给相同耦合组中的其他下标。通常传播是一种简化，产生一个精确 方向向量集合。因为在