（计算机科学与技术专业论文）高级循环变换技术研究及实现.pdf

国防科学技术大学研究生院学位论文 摘要 高级循环变换( h i g h l e v e ll o o pt m n s f o m a t i o n s ) 是在程序的高级表示形式上改 变程序中循环的语句实例( s t a t e m e n ti n s t a n c e s ) 的( 顺序) 执行次序，而不改变语句 实例集合的一种程序优化技术。在不改变程序语义的前提下，通过变换程序中局部性 不好的循环迭代方式，高级循环变换可以提高程序的空间局部性和时间局部性，因此 它是一种充分开发存储层次系统高性能的关键编译优化技术。 本文从实现高级循环变换的角度研究了影响高级循环变换的主要因素，深入分析 了g c c 中线性循环变换框架的原理和特点，针对其不足，提出并实现了改进算法。 本文的创新工作主要体现在： 1 、研究了各种高级循环变换技术之间的相互影响，提出了一个不受程序语言制 约的循环变换算法。 2 、研究了f o r t r a n 语言程序数组线性化给循环变换带来的影响，提出了一个 完全恢复线性化f o r t r a n 程序数组下标的算法。 3 、以g c c 编译器为基础平台，完善了其线性循环变换系统。s p e c f p 2 0 0 0 和科 学计算与模拟基准程序的测试表明优化效果良好。 关键词：编译优化，循环变换，局部性，g c c 第1 页 国防科学技术大学研究生院学位论文 a b s t r a c t h i 曲一1 e v e l l o o pt r a i l s f o m a t i o n si sap r o g r 锄o p t i m i z a t i o nm e c h a i l i s m 恤a tc h a n g e s 廿1 e ( s e q u e n t i a l ) e x e c u t i o no r d e ro fm es t a t e m e mi 1 1 s t a n c e s 州t h o u tc h a n g i n gt h es e to f s t a t e m e n ti i l s t a i l c e st 1 1 a tb a s e do nl l i g h 一1 e v e l r e p r e s e n t a t i o n so fap r o g r 锄h i g h - l e v e l i o o p 仃 m s f o n n a t i o n sc 趾i m p r o v et l l e s p a t i a l a n dt e m p o r a l l o c a l i t yo fap r o g r a mb y n a i l s f o 舯i n gl o 叩sw l l i c hp o s s e s s e so fp o o rl o c a 】i 哆u n d e rm ec o n d i t i o nt h a ta s s 嘣n gt 1 1 e c o r r e c ts e m a n t i c so fn 锄s f o 皿e dp r o g 姗s oi ti sap a r 锄o u l l to p t i l i l i z a t i o nm e c h a i l i s m a n di su s e dt oe x p k i tm eg o o dp e 订o r m a n c eo fm e m o r yh i e r a r c h i e se n t i r e l y 1 1 1 et h e s i ss t u d i e sm em a i nf a c t o r s 血a ta f f e c t t h eh i 曲一l e v e l l o o pt r a n s f o m a t i o n s d l l r i r 培i m p l e m e n t a t i o n t h e n ，i t 棚l y z e st 1 1 ep r i n c i p l ea n di n l p l e m e m a t i o n 丘衄e w o r ko f l 遍e a rl o o p 扛锄s f o m l a t i o 璐i ng c c ，w m c hs u p p o n sm u l t i p l ep f o g 五a m m i n gl 龃斟a g e s l a s t b u tn o tl e a s t ，t l l et h e s i si m p i e m e m saf e wa l g o r i n l m si ng c ct oi m p m v el i n e a rl o o p 乜部f b r n l a t i o 璐 p r i m a r yi i m o v a t i v cw o r ki i lt h i sp a p e rc a l lb es 啪m a r i z e da sf 0 1 l o 们n g ： 1 ) t h e t l l e s i ss t u d i e s 廿l em a i nf 如t o r s l a ta f f e c tt 1 1 eh i g h i e v e l l o o p 仃a i l s f o 姗a t i o 璐 f b mt 1 1 ep o i n to f v i e wo f i m p i 锄e n t a t i o n s 2 ) t h et h c s i ss t u d i e s 也ef h c t o r s 盛c t i i l gl o o p 缸a i l s f o 姗a t i o n sw l l i c ha r eb r o u g h tb y l i n e 骶i z e da r r a yr e f e r e n c es u b s c r i p t si nf o r t ra np r o 醪吼s ，a n dd e v e l o p sa n a l g o r i m mt o 糟c o v e rm u l t i d i m e n s i o na m yr e f c r e n c es u b s c 啦t so fl i n e 撕z e d f o r t r a na m yr e f e r e n c es u b s c r i p t s 3 )b y 廿1 0 r o u g 蝴ys m d y i n g a n d a i i a i y z i n gt h ei i n e a rl o o p 仃a n s 内m l a t i o n s i n f 协m l c t u r eo fg c c ，m e 也e s i si m p r o v e s “s i m p l e m e m a t i o n s o u rw o r k i m p r o v e st h ep e r f o r i n a n c eo f b e n c h m a r ki ns p e c 却2 0 0 0a n da 伽e rs c i e m i f i c 肌d s i m u l a t i v ep m g r a m s k e y w o r d s ：c o m p n e ro p t i m i z i n g ，l o o pt r a n s f o r m a t i o n ，l o c a i i 衄，g c c 第王i 页 国防科学技术大学研究生院学位论文 图目录 图2 1 紧嵌套循环的一般形式9 图2 _ 2 循环交换与方向向量的关系1 0 图2 3 循环交换示例1 0 图2 4 循环偏斜示例1l 图2 5 循环逆转示例1 2 图2 6 循环放缩示例1 3 图2 7 循环分布示例1 3 图2 8 矩阵乘法程序1 6 图2 9 一个数组线性化示例程序2 3 图2 1 0 一个数组定义维长为程序输入参数的线性化数组访问示例程序2 8 图3 1g c c4 o 的整体框架31 图3 2g c c 中循环变换调用时序3 4 图3 3g c c 线性循环变换的总体流程3 5 图3 4 一个小示例程序3 8 图3 5g c c 标量演化算法调用关系3 9 图3 6 标量演化示例4 0 图3 7g c c 数据依赖分析流程4 3 图3 8 c o m p u t e m l d e p e n d e n c e s 的调用关系4 5 图4 1恢复f o r t r a n 线性化数组访问的多维下标递归链函数4 9 图4 ，2 元素为订e e 类型的i 锄b d a 向量和l 唧b d a 矩阵5 0 图4 3 计算访问矩阵的算法5 l 图4 4 计算偏移向量的算法5 2 图4 5 恢复线性化数组访问的多维下标访问递归链的算法5 2 图4 6 改进后的下标依赖分析函数5 4 图4 7 约束传播算法5 5 图4 8 改进后的确定变换矩阵函数算法5 7 图4 9 确定最佳访问次序算法5 8 图4 1 0 计算步长向量函数算法5 9 图4 1 1 计算映射向量算法6 0 图5 11 0 2 4 x 1 0 2 4 矩阵乘法程序改进前后执行时间对比6 l 图5 21 7 1 s w i m 改进前后执行时间对比( 数据集：r e f ) 6 2 第i i i 页 国防科学技术大学研究生院学位论文 图5 3c a 口f 改进前后执行时间对比6 2 图5 4 矩阵乘法程序的时钟周期分布6 2 图5 5 不同循环组织结构的矩阵乘法程序的执行时钟周期分布6 3 图5 61 7 1 s 、v i m 执行时钟周期分布6 4 图5 7c a p 改进前后执行时钟周期分布6 5 第i v 页 独创性声明 本人声明所呈交的学位论文是我本人在导师指导下进行的研究工作及取得 的研究成果。尽我所知，除了文中特别加以标注和致谢的地方外，论文中不包含 其他人已经发表和撰写过的研究成果，也不包含为获得国防科学技术大学或其它 教育机构的学位或证书而使用过的材料与我一同工作的同志对本研究所做的任 何贡献均已在论文中作了明确的说明并表示谢意。 学位论文题目：直熟煎丕变选挂盔婴蕉区塞理 学位论文作者签名：j 蜓一日期：埘年应月夕日 学位论文版权使用授权书 本人完全了解国防科学技术大学有关保留、使用学位论文的规定。本人授权 国防科学技术大学可以保留并向国家有关部门或机构送交论文的复印件和电子 文档，允许论文被查阅和借阅；可以将学位论文的全部或部分内容编入有关数据 库进行检索，可以采用影印、缩印或扫描等复制手段保存、汇编学位论文。 ( 保密学位论文在解密后适用本授权书) 学位论文题目：直盈缰至蛮拯挂盔盈窥丛塞望 学位论文作者签名：暨空! 基日期：埘矿年肛月夕日 作者指导教师签名： 盗l ! 生互日期：沙年，b 月j 日 国防科学技术大学研究生院学位论文 第一章绪论 1 1研究背景 从1 9 8 0 年到现在的二十多年当中，处理器性能以每年5 5 的速度平稳增长，而 内存性能却只以每年7 左右的速度增长【1 】。为了填补处理器和存储器之间越来越大 的性能差距，计算机体系结构设计人员通常在处理器和存储器之间加入多级c a c h e ， 构成一个多级存储器层次结构。为了充分发挥多级存储层次结构的高性能，应用程序 就必须具有充分的局部性，使其大部分的数据访问都在最高一级c a c h e 内进行。但是 大部分程序是按照算法直接编写的，它们并不具有充分的局部性，因此编译器必须优 化程序的局部性使得已装入c a c h e 的数据得到重用。研究人员对实际应用中典型程序 的执行时间进行了统计，发现程序的执行时间有8 0 以上用于执行循环。所以充分优 化程序中循环的局部性是提高程序局部性的主要途径。 高级循环变换( h i 曲l e v e ll o o pt r a i l s f o 衄a t i o n s ) 是在程序的高级表示形式( 源 语言程序或接近源语言程序的中间表示形式) 上改变程序中循环的语句实例 ( s 协t e m e m 访s 切n c e s ) 的( 顺序) 执行次序，而不改变语句实例集合的一种程序优化 技术【2 1 。除了在程序的高级表示形式上对循环进行变换之外，高级循环变换与通常的 循环变换( l 0 0 pt m s f o r n l a t i o i l s ) 相同。所以后文中如果不特别指出，循环变换都是 指高级循环变换。虽然循环变换可能因为违反循环中的数据依赖关系而产生不正确的 结果，但是在不改变程序的正确语义的前提下，循环变换通过将访问相邻或相同存储 单元的语句实例的执行次序重排在一起，它不但能够优化程序的时间局部性和空间局 部性，而且它的影响范围是在循环内部。因此循环变换是提高程序的局部性的关键编 译优化技术。 随着g n u l i n l l ) 【的应用越来越广泛，g n i ，i ，i n u x 正面临高性能计算和企业计算 的挑战。高性能计算和企业计算要求应用程序充分发挥计算机系统的高性能，从而获 得较快的程序执行速度。g c c 嘲作为g m i i ，i n l l 】( 的基础编译器也面临同样的挑战。 g c c ( 即g n uc o m p i l e rc 0 1 i e c t i o n 的简称) 是自由软件基金会( f r e es o f t w a r e f o 蚰d a t i o n ) 负责维护的一个免费、开放源代码的编译器。它采用模块化结构，支持 多种源程序语言和众多硬件平台，是开源( 0 p e ns o u r c e ) 领域使用最广泛的编译器。 因为循环变换是一种提高程序局部性，充分发挥计算机系统高性能的关键编译优化技 术，所以循环变换是g c c 应对当前面临的挑战，提高编译性能，生成快速运行的目 标代码不可缺少的优化技术。 以前提出的循环变换方法大部分都局限于使用f o r 廿a 1 1 和c 语言编写的程序，都 第l 页 国防科学技术大学研究生院学位论文 是在程序的源代码或抽象语法树上进行循环变换，所以其变换性能取决于对源程序中 特定模式的识别。因为g c c 是一个支持多种源程序语言的编译系统，所以g c c 实现 循环变换是基于统一的g 蹦p l e 中间表示形式( 一种派生于m c c a t 编译器口”的 s m 口l e 的三地址中间代码) 。与抽象语法树相比，g i m p l e 是一种比较低级的中间 表示形式，它主要有以下四个特点： 1 1 它是一种优化的与程序语言无关的三地址中间表示； 2 1 它不允许有副作用： 3 ) 它只用两个结构来表示控制流，一个i f 条件语句和一个g o t o 语句； 4 ) 下标表达式，循环边界和循环步长分散在g i m p l e 中的许多基本指令和基本 块中。 因此在g c c 中实现循环变换与原来实现循环变换的方法有很大的差别，深入研 究在g c c 这样一个支持多语言的编译系统中实现各种循环变换技术是十分有必要 的。 g c c4 o 以前没有循环变换的框架，g c c4 o 以n e e s s a 【2 4 】框架为基础实现了一 个高级循环变换2 研的基本框架。但是这个高级循环变换框架还很不完善，只能对一些 简单循环进行循环交换。由于数组访问下标线性化的原因，g c c 的高级循环变换框 架对f o r t r a n 语言程序进行循环变换更加困难。因此必须分析g c c 的循环变换框 架及相关部分，找出其不足，以便有针对性地进行改进，提高g c c 循环变换的性能。 1 2 研究内容 1 _ 2 1 课题来源 本课题来源于8 6 3 软件重大专项( 项目编号：2 0 0 4 a a l z 2 2 l o ) ，该项目的主要 研究内容是针对当前主流微处理器，研发一个高性能微处理器优化编译器。受该项目 的支持，本课题重点对高级循环变换进行研究。 1 2 2 课题研究重点 编译研究人员已对循环变换做了长期大量的研究，提出了很多循环变换理论和算 法。可是大多数循环变换理论和算法都基于某一种特定语言源程序或其抽象语法树表 示，都有各自的局限性，研究广泛适用于各种源程序语言程序的循环变换及其实现技 术仍有重要意义。因此，本课题的研究重点放在以下四个方面： 1 研究已有的循环变换理论与算法，并从实现循环变换的角度对这些循环变换 方法进行深入分析和比较。 2 根据课题来源项目，解剖g c c 中的循环变换框架。深入分析g c c 的循环变 换框架和相关设施，主要包括以下内容：首先是分析程序数据结构，分析 第2 页 国防科学技术大学研究生院学位论文 g c c 中循环变换相关的主要数据结构，给出数据结构描述和各成员作用的说 明；其次是分析循环变换算法，分析循环变换的识别条件以及变换方法；最 后是分析接口，给出循环变换算法中关键函数的功能描述、调用接口以及调 用关系。 3 结合对循环变换理论和算法的研究，针对g c c 中循环变换的不足，对其进 行改进。 4 评测被实现和改进的循环变换算法的有效性。利用s p e c 邱2 0 0 0 和科学计算 与模拟中的基准程序，对改进后的g c c 循环变换算法进行较全面的测试， 通过测试评价完善后的g c c 循环变换框架的性能。 1 t 2 3 课题研究难点 循环变换具有较深的理论基础，涉及到数据依赖关系分析、循环交换算法以及指 导进行循环变换的启发式规则的选择，总之循环变换是重构编译器中一种复杂而重要 的程序优化技术。 本课题的难点主要体现在以下几点： 1 循环变换具有很强的理论性。为了提高程序的性能，进行循环变换，需要对 程序进行深入分析，这要用到有关数论、整数规划和矩阵等数学知识。因此 需要补充大量的数学理论知识。 2 循环变换不仅具有很强的理论性，而且具有很强的工程实践性。改进的循环 变换算法不能影响已有的优化措施，必须保证编译器的完整性和正确性。 3 编译器是一个复杂的大型系统程序，要深入了解g c c 这样的开放源代码编 译器中循环变换及其具体实现，就要阅读大量的源代码，总结循环变换在 g c c 中实现的原理和方法，找出其存在问题的原因，对其进行改进，这需要 做大量的工作。 1 3 研究现状 w o l f em e 和l 锄m s 例以一个重用向量空间( r e u s ev e c t o rs p a c e ) 的c a c h e 局部 性模型为基础，利用幺模变换( u n i i n o d u i a rt r a l l s f o m a t i o n ) 选择最合适的内层循环 来进行循环分片以提高程序的c a c h e 局部性。他们将依赖表示为循环迭代空间中的向 量，利用矩阵变换来表示循环交换、循环逆转、循环偏斜等幺模变换，并用一个复合 矩阵变换来表示多个循环变换的组合。他们对局部性的评价包括三个部分：( 1 ) 使 用重用向量空间来表示数据局部性优化的潜在可能性；( 2 ) 使用局部化向量空间 ( l o c a l i z e d v e c t o rs p a c e ) 来表示复合循环变换可开发的潜在局部性；( 3 ) 最后通过 求解重用向量空间和局部化向量空间的交集来评价循环变换后程序的局部性。他们对 第3 页 国防科学技术大学研究生院学位论文 重用向量空间和局部化向量空间的求解过程在很大程度上依赖于源程序语言数组在 内存中的布局方式。而且其求解过程需要进行穷举搜索，因而时间复杂性也比较高。 m c k i l l l e yk s 等【4 】以他们的循环访问代价模型为基础，提出了一个综合循环变换 算法。他们提出的循环访问代价模型是首先假设将当前考虑的循环移到最内层，再计 算这个循环的以c a c h e 行为单位的访问代价。通过计算循环的c a c h e 行访问代价，他 们的循环变换算法将循环按照其c a c h e 行访问代价从小到大排序得到理想的循环组织 结构，即按访问代价的排列顺序确定从内到外的理想循环嵌套层次。然后再利用循环 交换将程序中的嵌套循环变换为理想的循环组织结构。如果循环中有数据依赖阻止循 环交换，那么利用循环分布和循环融合等循环变换获得既满足数据依赖，又最接近理 想结构的嵌套循环结构。循环访问代价的计算与数组在内存中的布局方式紧密相关， 因此他们的方法受到程序的语言类型很大的制约。 l i w 【5 】提出了高度降低( h e i g h tr e ( h l c t i o n ) 和宽度收缩( 、i d 恤r e d u c t i o n ) 的循环 变换算法，优化循环的时间局部性和空间局部性。他通过建立一个基于重用距离( r e u s e d i s t a l l c e s ) 的c a c h e 模型，用非平凡矩阵变换表示a 变换来实现他的循环变换算法。 a 变换是指循环交换、循环逆转、循环偏斜和循环放缩( l o o ps c a l i n g ) 四种循环变 换的任意组合的复合循环变换。高度降低算法首先求出循环中所有数组访问的全局数 据重用矩阵( g l o b a ld a t ar e u s em a 订i ) 【) ，然后通过循环变换矩阵来尽量降低全局数据 重用矩阵列的高度，从而达到优化循环局部性的目的。对于迭代范围比较大的循环， 经过高度降低算法后，局部性没有充分开发。通过循环分片变换减小单个循环的宽度 ( 即迭代范围) ，从而进一步开发循环的局部性。全局数据重用矩阵的计算复杂度很 高，如果紧嵌套循环体内有玎个数组访问，那么需要进行2 ”次对数组访问重用向量空 间交集的基向量的计算，而每次计算都需要求解一个线性方程组。在确定了全局数据 重用矩阵后，只有采用尝试的方法由上至下逐行求解循环变换矩阵。总之高度降低和 宽度收缩算法的复杂度很高。 l 。4 本文的主要工作 本文不但对循环变换理论进行了研究，而且对在实际的产品编译器中实现循环变 换进行深入分析和探讨。总的来说，本文的工作体现在以下几个方面： l 、循环变换理论方面 循环变换是人们研究提高程序局部性的重点，从优化程序性能的各个角度提出了 许多循环变换方法。本文从循环变换的实现角度，研究多种循环变换方法及其相互影 响，总结了它们的优缺点，提出了一个不受限于程序语言类型的循环变换算法。此外 探讨了直接制约循环交换的数据依赖分析技术，提出了一个完全恢复线性化数组访问 第4 页 国防科学技术大学研究生院学位论文 的多维下标信息的算法。 2 、循环变换实现方面 本文分析了g c c 的基本结构和工作流程，其中着重分析了g c c 高级循环变换 框架及相关部分，探讨了在支持多语言编译器中实现循环变换所涉及的各种因素。 3 、g c c 中循环变换的改进 经过深入分析，本文指出了g c c 中循环变换以及数据依赖分析的优缺点，针对 所发现的不足，提出并实现了改进算法。实验数据表明，改进算法具有一定的效果。 1 5 论文结构 全文共分六章。 第一章为绪论，首先介绍了课题背景；接着说明了课题研究内容，包括课题研究 重点与难点；然后概述了国内外相关领域的研究现状；随后介绍了本文的主要工作； 最后介绍了论文的结构安排。 第二章是循环变换技术研究。首先给出了与循环变换相关的概念和定义；然后从 实现循环变换的角度，研究了多种循环变换技术和它们之间的相互影响；接着提出了 一个不受程序语言类型制约的循环变换的算法：接着研究了与循环变换紧密相关的数 据依赖分析技术；最后提出了一个完全恢复线性化数组访问下标信息的算法。 第三章是分析g c c 的循环变换。首先分析了g c c 的基本结构；然后分析了g c c 中循环变换的实现现状；接着分析了与循环变换密切相关的归纳变量分析和数据依赖 分析。其中着重对循环变换和数据依赖分析的关键数据结构和函数进行了详细分析。 通过深入分析和研究，指出了他们的优缺点。 第四章是改进g c c 的循环变换。根据第三章所做的分析，针对影响g c c 循环变 换不足的原因，提出并实现了改进算法。 第五章是实验数据和分析结果。利用改进前和改进后的g c c 编译器，测试 s p e c 审2 0 0 0 和科学计算与模拟中的基准测试程序，给出了测试报告并分析了产生测 试结果的原因。 第六章是结束语，总结全文并对未来的工作做出了展望。 第5 页 国防科学技术大学研究生院学位论文 第二章循环变换技术研究 并行化、向量化和提高程序的局部性是提高现代计算机系统性能特别是其存储系 统性能的关键编译优化技术。无论是对程序进行并行化和向量化，还是提高程序的局 部性，循环变换都是其中必不可少的关键程序变换技术。这一章我们首先引入与循环 变换密切相关的概念和定义；随后从实现的角度，深入研究各种常用循环变换的适用 条件和作用，以及影响实现它们的各种因素，提出了一个不受程序语言制约的循环变 换算法；最后探讨了约束循环变换的数据依赖分析技术，提出了一个完全恢复线性化 数组访问下标算法。 2 1 循环变换相关的概念和定义 本节将本文中将要大量使用的基本术语列举如下，后面章节中不再做具体说明。 紧嵌套循环是如下形式的嵌套循环，它是指深度为h 的嵌套循环，循环体的语句 日( ，l ) 只出现在最内层循环当中。 f o r 厶= 厶，u f o r 厶= 厶， 妇j ，= l ，u ， 日( ，l ) e n d f o r e n d f o r e n d f o r 循环体内的语句日( ，l ) 的一次执行实例称为循环的次迭代( i i e r a t i o n ) 。 深度为n 的紧嵌套循环的所有迭代可以用一个称之为迭代向量的工具来描述，即 7 = 厶，厶，l ，这是一个整数向量，它包含按照嵌套层次顺序排列的每层循环的迭 代号。循环迭代向量j = ，i ，厶，厶 组成个n 维空间中的多面体，这个多面体称为 循环迭代空间。每一次迭代对应于循环迭代空间中的一个点， 循环依赖是指在公共嵌套循环中存在从语句s 到语句是的依赖，当且仅当此嵌 套循环存在两个迭代向量和，使得下面三个条件满足：( 1 ) ， 0 如果d ( ，) k = o 如果d ( ，) k o ( 即d ( f ，d 包含一个“ ”作为它的最左非“= ”分量) 。 当存在两个迭代向量和，使得( 1 ) s 在迭代j 中引用存储单元，是在迭代j 中 引用m ，且，= ，；并且( 2 ) 迭代中有一条从s 到足的控制流路径，称语句是对语 句s 有一个循环无关依赖。如果一个距离向量( 盔，吐，以) 至少有一个非。元素，并 且它的第一个非o 元素为正，那么这个距离向量是词法序为正的( i e x i c o g m p l l i c a i i y p o s i t i v e ) 。 对于一个h 层嵌套循环中的某个m 维数组的某次访问，如果此次访问的数组下标 为仿射下标，那么该数组访问可以表示为4 7 + 孑，其中，7 为迭代向量，m ”维矩 阵彳被称作访问矩阵，具有柳个元素的列向量占被称为偏移向量。 2 2 循环变换技术 上世纪8 0 年代1 1 1 j n o i s 大学和鼬c e 大学的学者们提出了循环变换。w o l fm e 【列 在他的博士论文中进一步完善了循环变换理论。他将循环置换、循环偏斜、循环逆转 和循环分片综合考虑，提出了一个综合应用这些循环变换提高循环的局部性或循环并 行性的算法。本文从实现循环变换的角度研究提高循环数据局部性的循环变换技术， 即在不改变源程序语义的前提下，通过使用多种循环变换，改变程序中空间、时间局 部性不高的循环迭代方式，使循环迭代中访问的数据集尽可能在c a c h e 中找到。人们 对循环变换进行了长期深入的研究，提出了很多循环变换方法，如循环展开( l o o p 第7 页 国防科学技术大学研究生院学位论文 u n r o i l i f l g ) 、循环交换( l o o pi 拄f e r c h a n g e ) 、循环偏斜( l o o ps k e w i n g ) 、循环逆转 ( l o o pr e v e r s a l ) 、循环放缩( l o o ps c a l i n g ) 、循环分布( l o o pd i s t r i b u t i o n ) 、循环融 合( l o o pf u s i o n ) 、循环分片( l o o pt i l i l l g ) 等等。其中循环交换、循环逆转和循环 偏斜对应的循环变换矩阵的模的绝对值都为1 ，所以又把它们统称为幺模循环变换 【3 】【8j 【9 】【1o 】【1 1 】f 1 2 1 ( u m m o d l l l a r l o o pt r a l l s f o 彻a t i o n s ) 。因为幺模变换和循环偏斜可以统 一用循环迭代空间或者循环迭代向量的线性变换来实现，所以又把它们统称为线性循 环变换【8 】( l i n e a rl o o p1 r a n s f o 蛳a t i o n s ) 。下面从实现多种循环变换的角度分析和研 究线性循环变换、循环分布，其他的循环变换请见参考文献【1 0 1 。 2 2 1 线性循环变换 为了完全开发存储器层次系统的高性能，一般情况下需要运用多种循环变换技术 才能获得程序最佳的循环局部性。如果将多种循环变换由每次进行一个简单循环变换 来完成就会存在以下三个问题：一是循环变换之间的相互影响，如某个循环变换后可 能会导致其他的循环变换难以进行甚至不可能进行；二是确定一个合法的变换序列可 能需要搜索一个很大的循环变换集合，如确定嵌套循环中的一个目标循环置换需要搜 索由这个嵌套循环中所有可能的循环交换组成的集合；三是很难确定与一个特定目标 相关的一组最优循环变换。因此用一种统一的框架来表示多种循环变换，编译器就可 以一次进行多种循环变换，从而降低了循环变换的复杂度。线性循环变换3 习1 8 】【9 j 【l l 】 就是这样的一种循环变换框架。 线性循环变换原来包括循环交换、循环偏斜、循环逆转，后来l iw 【5 】通过用非 平凡矩阵变换来表示循环变换，将循环放缩( l o o ps c a l i n g ) 也包括在线性循环变换 当中。一个循环变换可以视为循环迭代的重组，因此可以用迭代空间的交换来表示循 环变换。一个线性循环变换定义为一个n 一的非平凡矩阵z t ，它将迭代向量，映射到 一个新的迭代向量j = ，以) 7 ，即口= j 。与此同时依赖矩阵d 中的每个依赖距离 向量d i 也映射为一个新的向量d l ：尬= d f 。线性循环变换是合法的当且仅当每个 依赖距离向量口1 是词法序为正的，即变换后的依赖距离向量词法序为正是循环变换 合法的充分必要条件。下面从矩阵变换的角度研究组成线性循环变换的各种循环变换 技术。不失般性，将图2 1 的嵌套循环作为本文的一个循环结构模型。 第8 页 国防科学技术大学研究生院学位论文 f o r 厶= 厶，u f o r ，2 = ：( ) ，u ：( ) f o r = 上。( ，l ，) ，u 。( ，l 1 ) h ( j ，j 。) e n d f b r 图2 1 紧嵌套循环的一般形式 其中，l ，l 为迭代索引；厶和u 为循环的下界和上界，它们是迭代索引 ，t 一。的线性函数；并且假设循环的步长为1 。= ( 五，) 7 为迭代向量。日是嵌 套循环的循环体。一般来说，循环体内对m 维数组爿的一个访问有如下形式 彳( 彳( 五，) ，厶( 五，) ) ，其中，是迭代索引的函数，称之为下标函数。所有数 组访问下标函数为线性函数的循环称为线性循环。 2 2 ，1 1 循环交换 顾名思义，循环交换就是交换两层紧嵌套循环中两层循环的相对位置。循环置换 ( l o o pp e m u t a t i o n ) 是循环交换的推广形式，它是将循环交换推广到两层以上的嵌 套循环，循环置换等价于对循环层次( l 0 0 pl e v e l s ) 进行一组循环交换。交换两个循 环就会将迭代向量( f ，) 变换为( j ，f ) ，从矩阵变换的角度，可以用如下的线性变换来 表示：( o ：) c i ，2 ( j i ) 。其变换矩阵为幺模矩阵t = ( ? ： 。 一般来说，如果要交换两个循环就存在三个主要问题【i3 】：第一是合法性，循环交 换后的程序与原来的程序是否等价? 第二是形式，即循环交换后循环的正确形式是什 么? 第三是有用性，如果一个循环交换是合法的，那么循环交换后的程序比原来的程 序运行速度更快吗? 循环交换的合法性是通过依赖约束来保证的，即循环交换不能改 变循环中依赖关系的依赖方向。如果循环厶和厶是紧嵌套循环中的两个循环，且厶包 含l ，那么这两个循环能被交换当且仅当不存在厶中的两个语句s 和r ( s 和r 不一 定是两个不同的语句，可能是同一个语句) 满足s 占r ( 即s 流依赖于? ) 并且他们 的依赖方向向量是( ) 。摧而广之任意多层紧嵌套循环中依赖方向向量和循环交换 第9 页 国防科学技术大学研究生院学位论文 的之间存在如图2 2 所示的关系 1 4 】。循环交换后的正确形式包括变换循环边界和重写 循环体，这可以通过矩阵变换理论来实现。循环中依赖关系和数据局部性特征的改变 可以用来衡量循环交换的有用性。 k pk r + = = s + s += ( a )( b ) ( a ) 为循环交换安全的依赖方向向量形式 ( b ) 为循环交换不安全的依赖方向向量形式 其中表示任意依赖方向上标“+ ”表示任意多个，“”表示“c 图2 2 循环交换与方向向量的关系 循环交换是编译优化中最有用的变换之一，它可以从多个方面提高程序的性能。 循环交换不但可用于向量化和并行化，而且可以通过减少数组访问的步长来提高局部 性。但是不同的优化目标之间可能发生冲突，如增加并行性就要将没有依赖关系的循 环向外层移动，而向量化则要求将没有依赖关系的循环向内层移动，所以循环交换与 具体的优化目标紧密相关。步长是某个循环的相邻两次迭代访问的数组元素之间的距 离。由于c a c h e 是以行为单位进行管理的，所以一次存储访问当中，多个数组元素被 装载进一个c a c h e 行。如果数组的容量比c a c h e 行的容量大，那么较大的访问步长将 只使用该c a c h e 行中的一个元素，装载进该c a c h e 行中的其他元素将在他们被重用前 淘汰出c a c h e 。因此循环交换通过减少数组访问步长，增加了c a c h c 重用，从而提高 了循环的数据局部性。 图2 3 是一个循环交换的例子。假设数组的布局方式为按列优先顺序存放。本文 的示例程序都遵循这个假设。交换前循环体中对数组a 的访问是按行优先顺序来访问 的，这与它在内存中的布局存放方式正好相反。如果数组日的行数较大，那么每次循 环迭代，对数组口的访问都将产生一次c a c h e 失效。如果交换嵌套循环中两个循环的 迭代次序，那么循环迭代访问数组口的次序与数组口在内存中的存放次序相一致。因 此数组口的每个元素在c a c h e 中都得到了重用，极大地提高了该循环的c a c h e 局部性。 r lo 、 d o j = 1 ，n 卜l j 。竺芸。嘲诅1 0 卜岬舯 交换前的循环 图2 3 d o j = 1 ，n f 8 = 器一娟， e n d d o e n d d o 交换后的循环 循环交换示例 第1 0 页 国防科学技术大学研究生院学位论文 在循环的上、下界彼此相互独立的情况下，循环交换是很简单的。当内层循环的 上、下界是外层循环上、下界的线性函数时，循环交换就可能生成复杂的循环边界。 这样可能为进行其他循环变换增加了难度甚至使其他循环变换无法进行。所以最理想 的情况是一次确定所要进行复合变换的变换矩阵，一次生成新的循环边界。 2 2 1 2 循环偏斜 循环偏斜是把外层循环索引乘上一个偏斜因子厂后加到内层迭代变量的迭代上、 下界，然后再将循环的内层迭代变量的每次使用减去一个相同的数，从而改变循环的 迭代方式。从矩阵变换的角度，循环偏斜可以用如下的线性变换来表示： ( ：) ( ：f ) = ( ，。；+ ，其中变换矩阵为幺模矩阵t _ ( ；： 。 循环偏斜是内层循环相对于外层循环的偏斜，它虽然改变了内层循环的依赖距 离，但并不改变数组元素的访问顺序，所以循环偏斜可以无条件进行。循环偏斜是一 种功能强大的变换，它主要与循环交换一起结合使用。如通过循环偏斜变换，可以消 除某些阻止循环交换的依赖条件，使得循环交换的条件得到满足。 下面的嵌套循环当中，存在依赖距离向量分别为( 1 ，一1 ) ，( 0 ，1 ) 的依赖，其中第一 个依赖( 1 ，一1 ) 阻止循环交换，如果直接交换循环，那么将会使口 f ，刀对a i - l ，j + 1 】之间 的反依赖，变换为a i l ，j + l 】对口【f ，刀的流依赖。将循环相对于循环f 偏斜后，得到 新的依赖距离向量为( 1 ，o ) ，( 0 ，1 ) ，循环交换可以顺利进行。 豢州峥， 2 2 1 3 循环逆转 d o i = 2 n l d 揣蒜州m 刨i 。， l lo e n d d o 图2 4 循环偏斜示例 循环逆转是改变循环的迭代执行顺序。用变换矩阵来表示循环逆转，逆转一个循 第1 l 页 国防科学技术大学研究生院学位论文 环，就是将变换矩阵中这个循环对应的一行乘以一l 。如在两层紧嵌套循环中，逆转 外层循环可以表示为：( ：。 e = g ，其变换矩阵为丁= ( ：。 。 如果一个顺序循环携带了一个依赖关系，循环逆转将改变这个依赖关系的依赖方 向，从而违反依赖关系。因此仅当循环不携带依赖关系时循环逆转才是合法的。 循环逆转有两方面的作用：第一它可以便迭代变量从循环迭代上界递减到零而结 束循环的执行，利用一条不等于零跳转指令( b n e z ) 作为执行循环迭代的条件，从 而减少一条比较指令，使得在没有复合的比较并转移指令的体系结构上，减少循环开 销；第二它可以改变依赖方向向量，使得某些循环交换的条件得到满足。因此循环逆 转常常与循环交换结合使用。 下面是一个两层紧嵌套循环，对数组口的两次访问存在一个依赖距离向量为 ( 1 ，一1 ) 的依赖，由于这个依赖距离向量对应的方向向量为( ) ，阻止循环交换。将 循环逆转后，依赖距离向量变为( 1 ，1 ) ，循环交换可以顺利进行。 d o i 1 。n 如淼删哪。 e n dd o 原来的嵌套循环 图2 5 2 2 1 4 循环放缩 d o j = l m 口三) d o j i 嚣川m e n d d o e n dd o 内层循环逆转。 循环逆转示例 循环放缩5 1 ( l 0 0 ps c a l i n g ) 是用循环迭代变量的整数倍替换这个循环迭代变量， 从面改变循环迭代的步长。用变换矩阵来表示对一个循环进行循环放缩变换，就是用 放缩因子乘以变换矩阵中该循环对应的一行。如在两层紧嵌套循环中，对内层循环进 行放缩因子为七的循环放缩变换，其变换矩阵为：r = g ： 。 循环放缩并不改变依赖方向，所以它总是可以进行。单独应用循环放缩并不能起 到什么作用，它的主要作用是作为其他循环变换的增进器，通过改变循环迭代步长， 使其他循环变换可以进行。 下面是一个对内层循环进行放缩因子为2 的循环放缩的示例： 第1 2 页 国防科学技术大学研究生院学位论文 d o i _ 1 3 ( ：? ) 赫闩 原来的嵌套循环 d o u = 1 3 ：黔 图2 6 循环放缩示例 循环放缩会使代码生成过程中目标循环边界的计算复杂化。根据线性代数学可 知，一个整数非平凡矩阵r 能被分解为一个对角元素为正整数的下三角矩阵h 和一个 幺模矩阵u 的乘积。用u 作为变换矩阵与用丁作为变换矩阵得到的程序的执行词法序 相同，而且h 的对角元素与循环步长相对应。l iw 【5 】根据这一特点给出了一般线性 循环变换的高效代码生成算法，具体算法见参考文献1 5 j 。 2 2 2 循环分布 循环分布