（计算机软件与理论专业论文）数组的非线性方法及其在编译器中的应用.pdf

摘要( 近年来，随着对并行编译技术研究的进一步深入，数组非线性化技术的重要性日谥突出。数组非线性化技术将并行编译的主要处理对象一一数组，重构成适合并行分析和优化要求的表达形式：它是进一步并行优化的基础，在相关性分析和数据流分析中有着普遍的应用。国际上对数组重构技术的研究开始未久。在并行编译领域中，这还是一个比较新的研究课题 本文提出了在当前阶段数组重构技术研究中两个最重要方向上我们的研究成果，包括对于恢复线性化数组多维形式的研究，以及虚实数组参数引用状态结合映射的研究。与国内外已有的研究成果相比，本文提出的两个算法都具有较大的创新与突破。( 非线性化算法是指把线性化的数组恢复成它原有的多维形式的数组重构方法。通过多维恢复，可以大大提高相关性测试乃至并行优化的准确性和效率。本文的算法实现简单，充分考虑了算法的通用性，使它能够适用于更一般性的数组引用形式。我们的算法还同时提出了数组的一致化技术，可以统一在同一程序不同位置上所恢复的同一数组的形式。虚实结合算法是指在过程间的构考弦万丽我们提出了基于数据流分析中，虚实数组参数一致化的数组重三元组表示法的结合算法。与一般的不等式表示法相比较，用三元组来表示数组的引用状态更为直观。在对引用状态进行分析和操作时，三元组表示法更方便，并且还能处理一些不等式表示法所无法处理的情况，算法通过先拆分后合并两个步骤完成从虚参数组的引用状态到实参数组的引用状态的映射工作。关键词数组非线性化i 多维恢复? 虚实结合：一致化，正则化大a b s t r a c tt h et e c h n i q u eo fd e l i n e a r i z i n ga r r a yi sm o r ea n dm o l ei m p o r t a n t 、v i t l lt h ei m p r o v i n go ft h ep a r a l l e lc o m p i l i n g a r r a y sa l et h em a i no b j e c t sp r o c e s s e db yt h ep a r a l l e lc o m p i l e r w eu s et h ed e l i n e a r i z i n gt e c h n i q u e st or e s h a p et h ea r r a y st os o m en e wm o d e l s ，w h i c ha l em o r es u i t a b l et ot h ep a r a l l e la n a l y s i s ，a n do p t i m i z i n g t h i st e c h n i q u ei sv e r yu s e f u li nd e p e n d e n c ea n a l y s i sa n dd a t a f l o wa n a l y s i s i nt h i sp a p e r , w ep r e s e n to u ra c h i e v e m e n ti nt w om a i nf i e l d so fr e s h a p i n gt e c h n i q u e ：r e c o v e r i n gl i n e a r i z e dr e f e r e n c ea n dc o m b i n i n gt h ef o r m a la n dr e a lp a r a m e t e r s c o m p a r e dw i t hp r e v i o u sm e t h o d s ，o u ra l g o r i t h m sa l ec r e a t i v em e t h o d s r e c o v e r i n ga l g o r i t h mi st or e c o v e rl i n e a r i z e dr e f e r e n c e si nt h ea p p l i c a t i o np r o g r a m si n t ot h e i ro w nl o g i c a lm u l t i d i m e n s i o ns t r u c t u r e w ec a ni m p r o v et h ea c c u r a c ya n de f f i c i e n c yo f t h ef o l l o w i n ga n a l y s i sp r o c e s sb yr e c o v e r i n gt h el i n e a r i z e dr e f e r e n c e c o m p a r e dw i t hp r e v i o u sr e c o v e r i n gm e t h o d s ，o u ra l g o r i t h mi ss i m p l e ra n dm o r eg e n e r a l w ea c h i e v ean e wu n i f y i n gm e t h o di no u ra l g o r i t h m ，s oo u ra l g o r i t h mw i l lb es u i t a b l et ol a r g e rs c a l e c o m b i n i n ga l g o r i t h mi st oc o m b i n et h ef o r m a la n dr e a lp a r a m e t e r si nt h ed a t a f l o wa n a l y s i s i nt h i sp a p e r , w ep r e s e n tac o m b i n i n ga l g o r i t h mb a s e do nt h et r i p l e tr e p r e s e n t a t i o n c o m p a r e dw i t ht h ei n e q u a l i t yr e p r e s e n t a t i o n ，t h et r i p l e tr e p r e s e n t a t i o ni sm o r es i m p l ea n de a s i e rt op r o c e s s b e s i d e s ，t h et r i p l e tr e p r e s e n t a t i o nc a nw o r ki ns o m es i t u a t i o n st h ei n e q u a l i t ys i t u a t i o n sc a n tw o r k o u ra l g o r i t h mc o m b i n e st h ef o r m a la n dr e a lp a r a m e t e r sb yt w os t e p s ：s p l i t m a p p i n ga n dc o m b i n e m a p p i n g k e y w o r dd e l i n e a r i z e ，r e c o v e rl i n e a r i z e dr e f e r e n c e ，c o m b i n ep a r a m e t e r su n i f y , r e g u l a r i z e致谢光阴荏苒，逝者如斯，三年的研究生生活有如白驹过隙，转眼就到了毕业的时候了；在我读研的这三年期间，导师徐公权教授在学习、科研、工作、生活等各方面都给予了我精心的指导、帮助和关心，使我在专业学习和社会经验方面都有了长足的进步，这必将是对我一生起关键作用的三年，在此深表感谢。在此，我还要感谢实验室的周天爵副教授，自学峰讲师等老师，在我这三年的学习科研期间，他们也给予了我许多的指导和帮助。我要感谢并行所的臧斌宇教授、朱嘉华博士以及马国凯、张沁峰等同学，他们在本文的写作过程中，给予了我很多的指导和帮助。其中。特别要感谢朱嘉华博士，他帮我确定了论文的方向，并且帮我审查了关键的内容。我要感谢同实验室的方乐、张忱、曹水、周伟等师兄以及和我一起进入实验室的王有伟，瞿瑾同学，在这三年的时间里，我们一起学习、讨论、成长、进步，是你们陪我度过了这段愉快的时光，祝愿你们将来工作顺利、生活幸福!我要感谢其他和我起度过这三年快乐时光的伙伴们：王晓萍、施宇宏、陈荣华、周逸群、薛云皎，还有许多，在此无法一一列举。感谢你们这些年来对我的关心、帮助和爱护，希望你们在将来的日子里顺利平安!最后，我要感谢我的父亲母亲，是你们给予了我生命，并且在这二十几年中不断的养育、教育和鼓励我，没有你们，我决不可能取得今天的成绩! 在我临近毕业之际，我向你们表示深深的谢意!_ _ _ - _ _ 一数组的非线性方法及其在编译器中的应用引论一、数组非线性化的目的和意义几乎在每个应用程序中，都会出现大量的数组。在自动程序并行化中，数组是主要的处理对象，因此对数组的并行化分析和处理是否准确有效，可以说是影响程序并行化效果的关键因素。一般情况下，数组的逻辑意义决定了它的定义和使用形式。一个在逻辑上是多维的数组，如果将它定义成一个一维数组，不但会造成使用上的不便，更会引发逻辑上的混乱，就这一意义而言，同一数组在程序任何地方的定义和引用形式应该是完全一样的。然而实际应用中，情况却要复杂得多。在相当多的实用程序中，许多逻辑上是多维的数组，会被人为地线性化成一维数组。一个原始定义是三维的数组，也有可能在一些函数中以二维形式被引用。数组的定义可能会偏离它原本的逻辑意义，同一数组的引用也可能会出现很多不同的表示方法。在程序中，同一数组可能会有很多不同的表示形式，而这些表示形式实质上是等价的。但是，当我们对程序进行并行化的分析和处理时，这些等价的表示形式，所能得到的并行效果却往往是不等价的。这种情形使我们很自然地希望，如果能够把某些数组的表示形式替换成与之等价的，容易进行并行化处理的数组表示形式，将会大大促进程序的自动并行化。这种替换，也就是我们要在本文中讨论的数组非线性化。我们将在下面几节中，进一步讨论在哪些具体情况下，需要进行数组非线性化。二、线性化数组的非线性化对相关性分析的影响程序中，许多逻辑上是多维的数组，由于考虑到种种与实现程序功能无关的因素，被人为地线性化成一维数组。我们把这类一维数组称为线性化数组，把与之相对应的线性化前的多维数组称为线性化数组的原型。多维数组被改写成一维数组常常发生在以下两种情况下：一种通常的情况是在早期的程序中，程序员为了提高程序的效率，将多维的数组手工优化成一维的形式。这主要是由于在一些早期的编译优化中，一维数组能获得比多维数组更高的执行效率 1 。另一种情况则出现在通用模块中，程序员为了使他们编写出的功能模块能够处理不同维数的数组，而将所有的数组都一致化成一维线性形式。这些考虑使得程序中充满了很多原本应该是多维数组的线性化一维数组。在大型第1 页共3 8 页数组的非线性方法及其在编译器中的应用的f o r t r a n 应用程序中，这类线性化数组尤为常见。这些人为的线性化一维数组给程序的并行化带来了很多麻烦。在多维数组线性化成一维数组的过程中。许多原来分离在各个维中、彼此独立自q 信息被混合在同一个式子中，这使得数组的表达变得更为复杂；而一些原本是彼此独立的变量，由于被放到了同一个表达式中，使得它们的相互关系变得模糊不清。数组的下标表达式复杂性的增加，对于相关性分析显得尤为不利。例如，常用的b a n e r j e e 测试方法【2 】在处理一些多维数组时，分别测试数组的各维，可以得到准确的结果。但当这些多维数组被线性化为一维数组后，由于表达式变得复杂，同样的方法却往往会得到不确定的结果。o m e g a 测试【3 】对于数组的多维形式的测试效率也大大高于对一维形式的测试效率。线性化一维数组同时也会对数据流分析造成危害。多维数组表示了数组的规整结构。而当它被线性化成一维数组时，这种规整结构就被破坏了。例如，用正则段( r e g u l a rs e c t i o n ) 4 表示数组结构时，多维数组可以得到清晰的表述，但要表述线性化的一维数组却有很大的困难。可见，我们如果能把线性化的数组恢复成它原来的多维形式，将会大大提高相关性测试乃至并行优化的准确性和效率。三、数据流分析中虚实数组参数的一致化数据流分析中虚实数组参数的一致化，是数组重构的另一个重要应用方向。在函数之间进行数据流分析时，我们需要把子程序定义中的虚参数与实际函数调用时的实参数相结合，才能知道实际的数据在子程序中进行了哪些引用，发生了什么变化。但在实际程序中进行数组参数的虚实结合时，常常会出现虚实参数的数组形式不统一的情况。例如，我们时常会在应用程序中发现，予程序定义中以三维形式被使用的数组参数，当程序被调用时，相对应的实际参数可能是一个以二维形式被定义的数组。在这种情况下，要进行有效的数据流分析，必须首先完成数组参数的一致化。一致化主要是指对数组引用的一致化。我们通过数组重构的过程，把在过程内分析中得到的虚参数组的引用状态映射到相应的实参数组中，对应成实参数组定义的引用状态，才能使过程间的数据流分析得以准确进行。第2 页共3 8 页数组的非线性方法及其在编译器中的应用第一章数组的定义引用与等价性数组的定义与引用作为一种基本的数据结构，数组在各种应用软件中被程序员广泛地采用。因而编译器能否对数组进行有效地优化，在很大程度上决定了最终程序的执行效率及稳定性。而在针对并行计算机的自动并行化编译系统中，数组分析和数组优化就显得更为重要。因为本文所讨论的对象是数组，所以我们首先就数组给出以下这些相关的基本概念：定义1 - 1 - 1 ：逻辑数组程序员在使用数组的时候，必须首先给出数组的定义，定义提供了数组的维数，每一维的长度等信息：我们称这个定义为数组的逻辑定义。而程序员使用数组结构时，必然对数组进行一些读写引用，在程序中，这些引用都是建立在程序员先前所给出的数组逻辑定义基础之上的，因此我们称这些引用为数组的逻辑引用。一个由数组逻辑引用组成的集合我们称之为引用集。同时，我们称这个程序员所见并使用的数组为逻辑数组。例1 - 1 。1 ：逻辑数组d i m e n s i o nb e t a ( 1 0 0 ，2 0 0 )b e r a ( 1 ，3 ) 2 b e t a ( 2 ，3 ) + b e t a ( 2 0 ，3 0 )例1 - l l 给出了一个简单的数组逻辑定义与逻辑引用的例子，在例l 一1 1 中，我们定义了一个名为b e t a 的数组，在逻辑上它是一个两维的数组，第一维的长度为1 0 0 ，第二维的长度为2 0 0 ，并且在随后的程序中对这个数组进行了引用。定义1 1 2 ：物理数组当我们在程序中定义数组时，编译系统会给每个数组分配一块存储空间，我们称这块存储空间为一个物理数组，对于一个逻辑数组来说有唯一确定的物理数组与之相对应。我们也称数组的这块存储空间为数组的物理定义。定义1 1 - 3 ：单点引用如果数组的引用下标中不包含变量，即在这个引用点上只有一个唯一确定的数组单元被应用，则我们称这样的引用为单点引用。第3 页共3 8 页数组的非线性方法及其在编译器中的应用定义1 - 1 4 ：簇引用与引用簇通过分析测试程序，我们发现多数数组引用是出现在循环体之中的，而且常常是与循环变量相关的，这样在一个引用点上就会有多个数组单元被引用。我们称这些引用为簇引用，而在一个引用点上被引用到的所有数组单元组成一个引用簇。引用簇可以用引用点上数组的下标，循环变量的上下界以及循环步长来描述。例1 1 2 ：引用簇d i m e n s i o na ( 1 0 0 )d 0 1 1 = 0 ，9 ，id ob = o ，1 9 ，ib = b + a ( i + 2 i i + 4 1 2 )( )e n d d oe n d d o在循环中引用点( ) 处引用了数组a 的一簇数组单元，我们使用如下标记来描述这个引用簇：a ( 1 + 2 i i + 4 1 2 ) ：i t ：( 0 ：9 ：1 ) ；1 2 ：( 0 ：1 9 ：1 )这里我们用一个三元i ：( l ：u ：s ) 来描述循环变量的下界，上界和步长，其中l 为下界，u 为上界，s 为步长，i 为三元式名。定义1 - 1 5 ：引用集如果存在这样的一个集合，该集合内的元素都是某个逻辑数组a 的引用或弓用簇，则我们称这个集合为逻辑数组a 的一个引用集。例1 - 1 3 ：对于逻辑数组a 0 0 0 ) ，集合( 【a ( 1 + 2 1 1 + 4 1 2 ) ；i i ：( o ：9 ：1 ) ：1 2 ：( 0 ：1 9 ：1 ) ；：a ( s 0 ) l即一个引用集。我们知道，程序员给出了数组的一个逻辑定义后，编译系统就会为这个数组分配块固定的存储空间，也就是说，给出了这个数组的物理定义。但是在很多时候，由于种种原因，一个物理数组可能会与多个逻辑数组发生对应关系。例i - i 一4 ：虚实参数数组所造成的一个物理数组对应多个逻辑数组( s p e c 2 0 0 t u r b 0 3 d )第4 页共3 8 页数组的非线性方法及其在编译嚣中的应用在例1 1 - 4 中，过程x y f f t 调用了过程d r c f t ，对于数组虚参数y ，x y f f t传入的实参数是一个三维的逻辑定义，而在过程d c r f t 中程序员却给出了这个数组的一个二维的逻辑定义，显然这个两个逻辑定义是不同的，而作为传地址的过程参数，在过程x y f f t 和过程d c r f t 中，所引用的存储空间必然是同一块。这就导致了一个存储空间，对应了两个数组的逻辑定义，也就是说，一个物理数组对应了两个逻辑数组。例l 一1 5 ：由等价语句造成的一个物理数组对应多个逻辑数组e q u i v a l e n c e ( a ( 4 0 ，1 0 0 ) ，b ( 2 0 ，1 6 ，2 s ) )在f o r t r a n 语言中提供了一种等价语句e q u i v a l e n c e ，使多个变量可以使用同一块存储空间。这也会造成同个物理数组对应多个逻辑数组的情况。在例1 - 1 5 中数组a 和数组b 显然有着不同的逻辑定义，但却使用着同一块存储空间。虽然一个物理数组可以与多个逻辑数组相对应，但是任意一个物理数组所对应的一维逻辑数组却是唯一的，因此我们可以认为任何数组的一维逻辑定义就是其物理定义，而在一维逻辑数组上的逻辑引用就是其物理引用。二、数组线性化方法数组的线性化方法是一个相当成熟的技术，利用该技术我们可以为一个逻辑数组确定它的物理数组，并将逻辑数组上的逻辑引用线性化为物理引用。第5 页菸3 8 页数组的非线性方法及其在编译器中的应用通常来说数组线性化是指将一个r l 维的数组线性化为一个一维数组，并为r l维数组上的引用找到一维数组上的等价引用。但是，其实我们真正需要考虑的只是如何将一个二维数组线性化成为一个一维数组，并为二维数组的逻辑引用找到一维数组上的等价引用。这是因为对于任何一个n 维数组来说，我们只要进行n 一1 次二维到一维的数组线性化，就可以将一个n 维的数组线性化成为一个一维数组，这其中每次线性化都是将数组的第一和第二维线性化成一维。所以我们下面只给出二维数组的线性化方法：假设二维数组定义为b m m z ，其引用为b b 。，b ： ，其线性化之后得到的一维数组为a ，则a 的定义为：a m 。m ： ，而对应的引用为：a b + m 。b ： 。例卜2 一l ：有数组a 1 0 0 ，5 0 ，4 0 及其引用a 8 ，2 4 ，3 3 ，求该数组所对应的物理数组b ，以及该引用所对应的物理引用。解：我们首先将数组a 的第一、第二维线性化成一维，则我们得到数组a 1 5 0 0 0 ，4 0 ，其引用为a 1 8 + 1 0 0 2 4 ，3 3 ，即a 2 4 0 8 ，3 3 ：再将a 1 线性化为b 2 0 0 0 0 0 ，其引用为b 2 4 0 8 + 3 3 * 5 0 0 0 ，即b 1 6 7 4 0 8 ：于是数组引用a 。 2 4 0 8 ，3 3 在b 2 0 0 0 0 0 3 下的等价引用为b 1 6 7 4 0 8 。上面我们通过两次将二维数组线性化为一维数组，最终将三维数组a 1 0 0 ，5 0 ，4 0 线性化为等价的一维数组b 2 0 0 0 0 0 ，并将其引用a 8 ，2 4 ，3 3 转换成等价的引用b 1 6 7 4 0 8 。也就是说数组aa 1 0 0 ，5 0 ，4 0 所对应的物理数组是b 2 0 0 0 0 0 ，而引用a 8 ，3 ，2 4 所对应的物理引用为b 1 6 7 4 0 8 。三、数组的等价关系定义1 3 1 ：等价定义如果两个逻辑数组对应了同一个物理数组，也就是说两个逻辑数组有着相同的酋地址和占用相同的存储空间，而且每一个数组单元的类型也是一致的( 本文所讨论的数组其数组单元的类型都是一致的) 。那么我们称这两个逻辑数组的逻辑定义是等价的。在例1 1 4 中的实参数u 和虚参数y ，例1 一l 一5 中的数组a 与b 的逻辑定义都是等价定义。定义1 3 2 ：等价单点引用假设有两个逻辑数组a 、b 他们的逻辑定义是等价的，而在逻辑数组a 上有单点引用a m l ，m 2 ，n l p 】，在逻辑数组b 上有单点引用b n i ，i 1 2 ，第6 页共3 8 页数组的非线性方法及其在编译器中的应用n d 。如果a m l ，m 2 ，m p 】和b n l元，则我们称单点引用a m l ，m 2 ，是等价单点引用。n 2 ，蝴指向的是同一块存储单m p 】和单点引用b i n t ，1 1 2 ，i l q 】性质1 - 3 1 ：逻辑数组a 上的某一个单点引用在确定的逻辑数组b 上存在且仅存在一个与之等价的单点引用。证明：利用反证法，假设逻辑数组a ( a l ，a 2 ，a p ) 上的某一个单点引用a ( m l ，m 2 ，m 。) 在确定的逻辑数组b ( b l ，b 2 ，b q ) 上存在两个与之等价的单点引用b ( n 1 1 ，n 2 l ，n q l ) 、b ( n 1 2 ，n 2 2 ，o q 2 ) 。因为引用b ( n l l ，n 2 1 ，n q l ) 与b ( n i 2 ，n 2 2 ，n q 2 ) 弓i 用a ( m j ，m 2 ，m p ) 是等价的，所以a ( m l ，m 2 ，m p ) 、b ( n h ，n 2 t ，1 1 q 1 ) 与b ( n n ，1 1 2 2 ，n q 2 ) 指向了物理数组中的同一个数组单元。也就是说当数组a 、b 被线性化为一维数组c 后，a ( m l ，m 2 ，n a p ) 、b ( n 1 1 ，n 2 1 ，n a i ) 与b ( n 1 2 ，n 2 2 ，n q 2 ) - qc上的某一个引用c ( c ) 是等价的。因此我们将b 线性化为一维数组c ，得到b ( n n 2 l ，n q l ) 与b ( n 1 2 ，n 2 2 ，n q 2 ) 的等价引用为：c ( n h + b l n 2 1 + + b i b 2 b q 1 1 1 q 1 )c ( n 1 2 + b t n 2 2 + + b i b 2 b q _ i m 2 )因为这两个引用实际上是同一个数组单元，所以我们可以得到等式：n i l + b i n 2 1 + + b i b 2 b q i n q l = n 1 2 + b l n 2 2 + + b i b 2 b q , t n q 2( 1 )又因为b ( n h ，1 1 2 1 ，n q l ) 、b ( n 1 2 ，n 2 2 ，n q 2 ) 是不同的数组引用，所以至少存在一个i ( 1 i q ) 使得n i l n 不妨假设j 是这样的i 中最大的一个，对任何k j 都有n k l = n k 2 。且n l j n 2 j ，则等式( 1 ) 可以简化成为：n t l + b l n 2 t + + b i b 2 b j 1 n j l = n 1 2 + b l n 2 2 + + b i b 2 b j 1 n i 2( 2 )( n i l n 1 2 ) + b l ( n 2 1 1 1 2 2 ) + + b i b 2 b j 2 ( n o a ) 1 - n ( t l p ) 2 b i b 2 b i ( n jr n j 2 )( 3 )又因为b ( n h ，i 1 2 1 ，n q l ) 、b ( n 1 2 ，n 2 2 ，n q 2 ) 是对数组b ( b i ，b 2 ，b q ) 的引用，所以有不等式组因为n j n 2 j ，所以有0 n l l b lo - n2 l b l b 2 - 。b j 将不等式( 6 ) 代入等式( 3 ) 得到0 n 1 2 b 10 n 2 2 b 2( ) jo n q 2 b q( n i l n 1 2 ) + b l ( n 2 i - n 2 2 ) + + b i b 2 b j - 2 ( n ( 一t ) i - n o 1 ) 2 ) b l b 2 b j ( 6 )( 7 )第7 页共3 8 页数组的非线性方法及其在编译器中的应用( n 1 1 n 1 2 ) + b l ( n 2 l n 2 2 ) + + b i b 2 b j - 3 ( n o 2 ) 1 一n o - 2 ) 2 ) b l b 2 b j - 3 ( 2 一( _ 2 ) l - 1 1 ( i 2 ) 2 ) )( 8 )又因为0 一 n 0 2 ) 1 b j 2 ，0 一 n 0 2 ) 2 一 b j a ，所以有不等式n a 2 ) 1 一n o - 2 ) 2 r b l b 2 b 3( 1 0 )反复上述的不等式迭代，我们最终可以得到：( n rn ：) b 。( 1 1 )这与不等式o n 。b ，o n ，。b 。是矛盾的。因此假设不成立，即b ( n ，r t ：l i “，n 。) 、b ( n 。n ：。，n 。：) 是同一个引用。唯一性得证，相对得存在性是显然得，我们就不再给出证明了。例1 3 1 ：等价引用假设数组a ( 4 0 ，l o o ) ，b ( 2 0 ，1 6 ，2 5 ) 是等价的逻辑数组，逻辑数组a 有引用a ( 1 5 ，5 0 ) ，逻辑数组b 有引用b ( 1 5 ，6 ，6 ) 。我们看与a 和b 相对应的物理数组c ( 4 0 0 0 ) ，a ( 1 5 ，5 0 ) 所引用的实际上是c ( 2 0 1 5 ) ，而b ( 1 5 ，6 ，6 ) 所引用的也是c ( 2 0 1 5 ) 。因此引用a ( 1 5 ，5 0 ) 和b ( 1 5 ，6 ，6 ) 是等价的。定义1 。3 3 ：等价引用簇假设有两个逻辑数组a 、b ，以及a 的引用簇中和b 的引用簇v中：a f i ( i i ，1 2 ，i 。) ，f 2 ( i i ，1 2 ，i 。) ，f d ( i l ，1 2 ，i 。) 】：又有i i ：( l 1 ：u l ：s i ) ；1 2 ( l 2 ：u 2 ：s 2 ) ；i n ：( l n ：u 。：s 。) 。q j ：b f l ( i i ，1 2 ，i n ) ，f 2 ( i , ，1 2 ，i 。) ，f q ( i i ，1 2 ，l n ) 】；又有i v ( l i ：u i ：s 1 ) ；1 2 ：( l 2 ：u 2 ：s 2 ) ：；i n ：( l n ：u n ：s n ) 。如果数组a 与b 的逻辑定义是等价的，而且对 i i 的任意一个取值引用a f i ( i i ，1 2 ，i 。) ，f ( i , ，1 2 ，i 。) ，f p ( i , ，1 2 ，i 。) b f l ( i i ，1 2 ，i ，) ，f 2 ( i , ，1 2 ，i 。) ，f q ( i l ，1 2 ，i 。) 是等价引用。则我们称逻辑数组a ，b 的引用簇中，v 是等价引用簇。定义l 一3 4 ：等价引用集与等价数组如果两个逻辑数组a 、b ，以及a 的引用集中和b 的引用集v 满足以下条件：( i ) a 和b 的逻辑定义是等价的：( 2 ) 在引用集中中任何一个引用或引用簇都可以在引用集v 中找到唯一一个与之等价的引用或引用簇，同时在引用集v 中任何一个引用或引用簇也都可以在引用集巾中找到唯一一个与之等价的引用或引用簇；第8 页，共3 8 页数组的非线性方法及其在编译器中的应用则我们称这样的两个引用集。和平是等价引用集。我们也称数组a 与b 是关于引用集巾和v 的等价数组。四、数组的线性化及非线性化对编译系统的影响作为一种基本的数据结构，数组在各种应用软件中被程序员广泛地所采用，因此编译器能否对数组进行有效地优化，将在很大程度上决定最终程序的执行效率和稳定性。而在针对并行计算机的自动并行化编译系统中，数组分析和数组优化就显得更为重要了。从数组的逻辑定义来看，一个n 维的数组( 逻辑数组，以下如无特殊说明，数组即指逻辑数组) 就是一个n 维的有限空间；而从分配存储空间的角度来看，数组就是一块连续的存储空间，它可以被划分为若干单元，每一个单元就是一个数组元素。因而一般的编译器，甚至早期的程序员都倾向于将多维数组转换成一维数组来使用，以使得该数组更贴近于它在存储空间中的结构，从而获得更高的效率。这种将多维数组转换成一维数组使用的方法就被称为数组的线性化。然而随着并行化技术的发展，线性化的数组逐渐成为数组分析和优化的障碍。这是因为在多维数组线性化成一维数组的过程中，许多原来分离在各个维中、彼此独立的信息被混合在了同一个式子中，从而使得数组的表达变得更为复杂；而一些原本是彼此独立的变量，由于被放到了同一个表达式中，使得它们的相互关系变得模糊不清。数组的下标表达式复杂性的增加，对于相关性分析显得尤为不利。例如，常用的b a n e r j e e 测试方法 2 在处理一些多维数组时，分别测试数组的各维，可以得到准确的结果；但当这些多维数组被线性化为一维数组后，由于表达式变得复杂，同样的方法却往往会得不到确定的结果。o m e g a 测试 3 对于数组的多维形式的测试效率也大大高于对一维形式的测试效率。线性化了的数组也会对数据流分析造成危害。多维数组表示了数组的规整结构。而当它被线性化成一维数组时，这种规整结构就被破坏了，例如，用正则段( r e , u a rs e c t i o n ) 4 表示数组结构时，多维数组可以得到清晰的表述，但要表述线性化的一维数组却有很大的困难。可见，我们如果能把线性化的数组恢复成它原来的多维形式，将会大大地提高相关性测试乃至并行优化的准确性和效率。我们将这种一维数组还原成多维数组方法称作数组的非线性化方法。第9 页，共3 8 页数组的非线性方法及其在编译器中的应用数据流分析中虚实数组参数的一致化，是数组非线性化方法的另一个重要应用方向。在函数之间进行数据流分析时，我们需要把子程序定义中的虚参数与实际函数调用时的实参数相结合，才能知道实际的数据在子程序中进行了哪些引用，发生了什么变化。但在实际程序中进行数组参数的虚实结合时，常常会出现虚实参数的数组形式不统一的情况。例如，我们时常会在应用程序中发现，子程序定义中以三维形式被使用的数组参数，当程序被调用时，相对应的实际参数可能是一个以二维形式被定义的数组。这种情形通常出现在一些通用模块中，当一个通用模块在不同的引用点被引用时所传入的数组参数往往有着不同的结构和定义。在这种情况下，要进行有效的数据流分析，必须首先完成数组参数的一致化。一致化主要是指对数组引用的一致化。我们结合数组线性化和非线性化方法，把在过程内分析中得到的虚参数组的引用状态映射到相应的实参数组中，对应成实参数组定义的引用状态，这样才能使过程间的数据流分析得以准确进行。五、数组非线性化的可行性上两节中我们提到。如果能够把存在于现有应用程序中的线性化数组恢复成它原来的逻辑上的多维形式，将会对程序的自动并行优化大有益处。而程序中原有的线性化数组常常在两种情况下出现：一种是在早期的程序中，程序员为了提高程序的效率，将多维的数组手工优化成一维的形式：另一种情况是程序员为了使他们编写出的通用功能模块能够处理不同维数的数组，将所有的数组引用都写成一维线性形式。下面我们首先将粗略的说明，在大多数情况下，把程序中的线性化数组恢复成多维形式都是可行的。我们先看为提高执行效率而产生的手工线性化数组的情况。对于这部分数组来说，由于硬件和编译器的发展，手工线性化优化的重要性大大减弱，在高速硬件上，多维数组在程序中是否手工线性化，已几乎不会再造成执行效率的显著差异。显然，这一类的线性化数组完全可以恢复成它原有的多维形式。通用模块的情形则稍微复杂一些。这些模块设计的初衷是为了能够处理任何维数的数组，然而在实际的应用程序中，很多模块所真正处理的往往只是一两种固定维界的数组。在这种情况下，编译器的优化系统往往会通过一般的过程繁衍处理，把这类通用模块繁衍成一组针对某个固定维数的数组作处理的专用模块。第1 0 贞i 共3 8 页_ _ _ _ _ _ _ 一一数组的非线性方法及其在编译器中的应用在这组优化系统生成的专用模块中，每个模块的数组则可以用固定的多维形式来表示。所以，我们也可以把这些模块中的线性化数组恢复成相应的多维形式，而不会影响程序的实现。六、当前非线性化方法在编译器中的应用现在数组的非线性化常常与相关性测试和过程间分析同时实现，这就使得数组的非线性化在很大程度上受到那些与相关性测试以及过程间分析相关的数据结构的限制。所以目前在数据流分析和相关性分析中数组非线性化方法并为被很好地采用，即使有所涉及也只是在最简单的情况下有所应用而已。例如在斯坦福大学的s u i f 系统中，它的数组重构便仅是面向不等式结构的，从而使得分析的结果相当的不精确。第l l 页共3 8 页数组的非线性方法及其在编译器中的应用第二章数组的非线性化方法一、数组非线性化及其简化与困难上一章我们提到，随着体系结构以及编译优化技术的发展，相对于维数较少、每维长度较大、引用表达式较复杂的数组来说，维数较多、每维长度较小、引用表达式较简单的数组更有利于分析和优化。因此我们希望能够找到一种数组线性化的逆运算，使我们能够将数组改造得更适应新的分析和优化技术。这种逆运算就是数组非线性化。如果我们有一个一维数组a 和a 的某个引用ae f ，还有一个与a 有着等价定义的多维数组b ，数组非线性化所要完成的工作就是为引用a f 找出与之等价的在数组b 上的引用。与线性化方法一样，我们可以通过不断地将数组的某一维非线性化成为二维数组来完成一维数组到多维数组的非线性化。例2 一卜1 ：如果我们想将一维数组a ( 3 0 0 0 ) 非线性化为b ( 2 5 ，3 0 ，4 0 ) 我们完全可以将数组a 先非线性化为a 1 ( 2 5 ，1 2 0 ) 或者a ( 7 5 0 ，4 0 ) 。然后再进行一次非线性化将数组a 1 非线性化成为b ( 2 5 ，3 0 ，4 0 )从理论上讲，数组非线性化与数组线性化一样，其工作的重点都是在等价的数组定义下为一个与已知的引用寻找其等价的引用。对于一般的单点引用来说确定其等价引用是一定能获得成功的，然而当数组的引用为簇引用时问题就不是那么容易了。因为虽然对一簇引用中的每一个引用来说，我们都能找到与之等价的引用，但是我们并不能将簇引用完全改造成单点引用，因为这意味着将循环完全展开，从而使程序完全丧失其潜在的并行性，这样不但会造成程序规模的急剧膨胀，还会导致优化的完全失败。因此我们必须保持一个引用簇的等价引用仍然是一个引用簇。这个问题不存在于数组线性化中，却存在于数组非线性化之中。因为数组的线性化方法本身就保证了引用簇的等价引用仍然是一个引用簇。另一方面，我们虽然可以将引用簇的等价引用维持一个形式的引用簇，但在实际使用这个引用簇的时候，很可能会遇到引用会越界的情况。这个问题同样不第1 2 页麸3 8 页一一数组的非线性方法及其在编译器中的应用存在于数组的线性化中，而存在于数组的非线性化中。因此我们在进行数组非线性化的时候，需要将单点引用和簇引用分开考虑。二、单点引用的非线性化在上一节中我们已经提到过，对于单点引用来说非线性化是简单而且必然有解的。本节中我们就简单介绍一下单点引用的非线性化方法，同时单点应用的非线性化方法也是簇引用非线性化方法的基础。此外，因为一维数组非线性化为多维数组可以通过多次以为数组非线性化为两维数组来完成，所以本节只给出一维数组到两维数组的非线性化方法。现在我们的问题为：对于一维数组a ( m , m ：) ，以及该数组上的单点引用a ( a ) ，要将这个维数组非线性化为一个二维数组b ( m ，m ：) ，同时，我们要为引用a ( a )找出在数组b ( m 。，i l l 2 ) 下的等价引用b ( b ，b t ) 。我们利用逆向思维方法，首先假设我们已经找到了等价引用b ( b ，b ：) ，于是我们利用数组线性化方法将二维数组b ( m 。，i l l 。) 线性化为一维数组a ( m 。b ) 。根据第一章第二节提出的数组线性化方法，我们可以很方便地知道当数组二维b ( m 。，啦) 线性化为一维数组a ( i i 。j l l 。) 时，引用b ( b 、，b ：) 在数组a ( m m ) 上的等价引用是a ( b 。+ i l l 。b ：) 。然后我们再根据这个结论来求解我们的问题。首先，由于b ( b 。，b 。) 是对数组b ( m ，m ：) 的引用，所以有不等式io 妯l m l( 1 2 )f0 b ，s m ，随后，我们来比较数组引用a ( a ) 与数组引用a ( b + i n b ：) 。根据第一章给出的性质1 ，我们知道a ( a ) 与a ( b + m 。b 。) 都是引用b ( b 。，b 。) 的等价引用，所以a ( a )与a ( b + m 。b ：) 实际上是同一个引用，也就是说，有b 。+ m ，b 。= a( 1 3 )下面我们将方程( 1 3 ) 和不等式( 1 2 ) 联立得到：lb o t + m l b 0 2 。8 。( 1 4 )l0 b o l m l因为o b m ，所以我们可以将等式( 1 3 ) 解释为一个带余数除法的逆运算，也就是：a 为除法的被除数，m ，是除法的除数，b 。是除法的商，而b 则是除法的第1 3 页共3 8 页数组的非线性方法及其在编译器中的应用余数。此时我们发现a 和m 。是我们已知条件的一部分，而b t 、b 2 正是我们所要求的数组引用。因此，我们最后得到如下结论：如果将一维数组a ( m m ：) 非线性化为二维数组b ( m 。，m 2 ) ，则数组a 上的单点引用a ( a ) ，与数组b 上的单点引用b ( b 。，b ：) 是等价的。其中：jb l = a m o d m l卜引n 鄙对于单点引用来说，我们无须验证b 。，b ：是否越界，这是因为用上述方法求得的b ，b ：是不会越界的。证明如下：因为b 。是a 除以m 。的余数，所以b 一定是小于m 。的，不可能越界；又因为a ( a ) 是数组a ( m 。m 2 ) 的引用，所以有：a m l m 2( 1 6 )将不等式( 1 6 ) 代入( 1 5 ) 我们得到b 。+ m b 2 m l m 2( 1 7 )b 2 m 2 生m 2( 1 8 )也就是说，b 。也一定是小于m 2 的，不可能越界。三、簇引用的非线性化与单点引用的非线性化相比，簇引用的非线性化要复杂得多，但他们的基本思路还是一致的。首先我们将簇引用的非线性化问题描述如下：对于一维数组a ( m t m 。m 。) 和该数组上的簇引用a ( 岛+ a l i l + a 2 i2 + a 。i 。) ：i i ：( l 1 ：u i ：s i ) ；i2 ：( l 2 ：u 2 ：s 2 ) ；i 。：( l 。：u 。：n ) ；所谓将这个一维数组非线性化为一个多维数组b ( m ，m ：，m 。) ，就是为簇引用a ( a f + a i ，+ a 。iz + a 。i 。) 找出在数组b ( m 。，m ：，) 下的等价引用：1 3 ( b0 - + b i i i l + b 2 i i2 + b 。1 i 。，b 。z + b 1 2 i i + b 2 2 i2 + b 。2 i 。，b o 。+ b l 。i i + b 却i2 + b 叩i 。) 。这里我们有必要说明一下，我们所处理的簇引用，其引用下标都是线性的表达式。这是因为非线性的引用很难对其做出精确的分析，从而也无法取得良好的第1 4 页，共3 8 页数组的非线性方法及其在编译器中的应用优化效果；同时在多数情况下数组引用都是线性的，因此我们没必要花更多的代价去处理非线性的引用。另外，对于所有i t 我们都可以进行正规化处理，使l t 2 0 ，s 。= 1 。至于如何进行正规化处理则不在本文讨论的范围之内，我们在此不再针对这一问题加以展开。和单点引用的非线性化一样，我们可以通过多次将一维数组非线性化成二维数组，来完成一维数组到多维数组的非线性化。因此我们可以只考虑如下的一维数组到二维数组的非线性化问题：对于一维数组a ( m 。m ：) 及该数组上的簇引用a ( a o + a i i i + a ：i2 + 砜i 。) ；i 。：( 0 ：u i ：1 ) ；i2 ：( 0 ：u 2 ：1 ) ；i 。：( 0 ：u 。：1 ) ：将此一维数组非线性化为一个多维数组b ( m 。，m ：) 。为此我们要为簇引用a ( a o +a 。i ，+ a 。i ：+ 巩i ) 找出数组b ( m ，m 2 ) 下的等价引用：b ( b o i + b i l i l + b2 1 1 2 + b i i 。，b 0 2 + b i 2 i l + b 2 2 i2 + b n 2 i 。) 。与单点引用的非线性化类似的，我们进行逆向思考：假设b ( b 。+ b ，i 。+ b ：。i 。+ b 。i 。，b 。+ b 。i ，+ b 。：i 。+ b 。i ) 是非线性化以后与簇引用a ( + a t i 。+ a ：i ：+ 巩i 。) 等价的簇引用。将b 线性化以后，利用数组线性化方法，我们可以得到与簇引用b ( b 。，+ b 。i ，+ b 。i ：+ b 。i 。b 。：+ b 。i 。+ b ：。i 。+ b 。：i 。)等价的簇引用a ( b 。+ b 。i 。+