（计算机科学与技术专业论文）ia64指令调度研究.pdf

国防科学技术大学研究生院学位论文 摘要 随着计算机技术的发展，达到高性能的任务从硬件转向软件已成为现代体系结构发展 的趋势，编译器作为基础的系统软件越来越重要。在现代系统结构中，指令调度是最重要 的编译优化之一，对提高计算机性能有着重大的影响，同时指令调度由于其复杂性，对它 的研究充满了挑战。 i a 一6 4 体系结构的特点是紧密结合编译器和硬件来提升性能，它提供丰富的支持机制 开发指令级并行。随着r a 一6 4 体系结构的实现产品l t a n i u m 系列处理器在高端服务器的使 用，通过指令调度开发i a 6 4 体系结构上的高性能成为许多研究者关注的热点问题。 本文以i a - 6 4 体系结构目标平台，对指令调度展开研究。首先，从程序语义的角度对 指令调度中开发并行性进行了分析，研究了主流的指令调度技术，对各种技术的优缺点进 行了比较，提出了基于区域的指令调度算法的框架。 本文分析了i a 一6 4 体系结构的技术特征，深入研究了i a 一6 4 体系结构指令调度相关特 性。在此基础上，剖析了g n uc o m p i l e r c o l l e c t i o n ( g c c ) 编译器在i a 一6 4 平台的指令调 度过程，结合对o p e nr e s e a r c hc o m p i l e r ( o r c ) 与i n t e l 商用编译器指令调度部分的分析， 总结出i a 6 4 平台进行指令调度的一些关键因素。最后，指出了g c c 现有指令调度算法的 优点，分析了g c c 指令调度算法有待改迸的地方，同时对其有待改进的地方，提出了改 进的调度算法，实验数据表明改进算法改善了输出代码，对程序性能有一定的提升。 关键词：编译优化，i a 一6 4 体系结构，指令调度，g c c 国防科学技术大学研究生院学位论文 a b s t r a c t w i t ht h ed e v e l o p m e n to fc o m p u t e rt e c h n o l o g y ，i ti st h et e n d e n c yt h a tt h er e s p o n s i b i l i t yo f a c h i e v i n gh i g hp e r f o r m a n c ei st r a n s f e r r e df r o mh a r d w a r et os o f t w a r e a sb a s i cs y s t e ms o f t w a r e c o m p i l e rb e c o m e sm o r ea n dm o r ei m p o r t a n t i nm o d e mc o m p u t e ra r c h i t e c t u r e s ，i n s t r u c t i o n s c h e d u l i n gi so n eo ft h em o s ti m p o r t a n tc o m p i l i n go p t i m i z a t i o n ，a n di n f l u e n c e st h ei m p r o v e m e n t o fc o m p u t e rp e r f o r m a n c ed e e p l y a tt h es a m et i m e ，i n s t r u c t i o ns c h e d u l i n gi sv e r yc o m p l i c a t e d a n df u l lo fc h a l l e n g e i ti st h ec h a r a c t e ro fi a - 6 4a r c h i t e c t u r et oi m p r o v ec o m p u t e rp e r f o r m a n c eb yd e p e n d i n gb o t h o nc o m p i l e ra n dh a r d w a r e i a - 6 4a r c h i t e c t u r ep r o v i d e sr i c hf e a t u r e st os u p p o r tt h ee x p l o i t a t i o n o fi n s t r u c t i o nl e v e lp a r a l l e l ( i l p ) w 曲t h ea p p l i c a t i o no fi t a n i u mf a m i l yp r o c e s s o r s t h e r e a l i z a t i o no fi a 一6 4a r c h i t e c t u r e ，o nh i g he n ds e r v e r s ，i tb e c o m e saf o c u s e dp r o j e c tt oo b t a i nh i g h p e r f o r m a n c eb yi n s t r u c t i o ns c h e d u l i n g 一 w ed or e s e a r c h e so ni n s t r u c t i o ns c h e d u l i n gt a k i n gi a - 6 4a r c h i t e c t u r ea st h et a r g e tp l a t f o r m f i r s t l y ，w ea n a l y z eh o wt oe x p l o i ti l pf r o mp r o g r a ms e m a n t i ca s p e c t b ys t u d y i n gp o p u l a r i n s t r u c t i o ns c h e d u l i n gt e c h n i q u e sa n dc o m p a r i n gt h e i rc h a r a c t e r s ，w ep u tf o r w a r dam o d e lo f i n s t r u c t i o ns c h e d u l i n gb a s e do ns c h e d u l i n gr e g i o n s t h e nw ea n a l y z et e c h n i c a lc h a r a c t e r so fi a 一6 4a r c h i t e c t u r ea n de s p e c i a l l yf o c u so nt h e c h a r a c t e r st ow h i c hi n s t r u c t i o ns c h e d u l i n gr e l a t e s a f t e rw es t u d yi n s t r u c t i o ns c h e d u l i n g p r o c e d u r eo fg n uc o m p i l e rc o l l e c t i o n ( 6 c c ) c o m p i l e rf o ri a - 6 4a r c h i t e c t u r ea n dc o m p a r ei tw i t h t h ec o u n t e r p a r t so fi n t e lc o m m e r c i a lc o m p i l e ra n do p e nr e s e a r c hc o m p i l e r ( o r c ) ，w ei n d e m i f y k e yf a c t o r so fi n s t r u c t i o ns c h e d u l i n go ni a 一6 4a r c h i t e c t u r e f i n a l l y ，w ei n d i c a t et h em e r i t so f g c ci n s t r u c t i o ns c h e d u l i n gp r o c e d u r e ，a n da n a l y z et h ep o i n t sw h e r ei m p r o v e m e n ti sn e c e s s a r y ， a n dp u tf o r w a r da na m e n d e di n s t r u c t i o ns c h e d u l i n ga l g o r i t h m t h ee x p e r i m e n tr e s u l t ss h o wt h a t t h ea m e n d e da l g o r i t h mc a ni m p r o v ec o d es i z ea n do b t a i nb e t t e rp e r f o r m a n c e k e y w o r d s ：c o m p i l e ro p t i m i z a t i o n ，i a 一6 4a r c h i t e c t u r e ，i n s t r u c t i o ns c h e d u l i n g ，g c c 国防科学技术大学研究生院学位论文 图目录 图2 1 指令调度流程图 图2 2 指令调度核心部分 图2 3 t r a c e 调度例子 图2 ，4 s u p e r b l o c k 调度的控制流图 图2 5 h y p e r b l o c k 的形成 图2 6t r e e g i o n 调度的控制流图 图2 7 w a v e f r o n t 调度区域 图2 8 指令格式 图2 9 指令束格式 图2 1 0 指令柬与指令组的构成。 图3 1 g c c 结构图 图3 2 g c c 工作流程图 图3 | 3 指令样板的作用 图3 4 i a 6 4 平台优化过程对指令调度过程的调用时序 图3 5 指令跨基本块移动类型 图4 1 测试数据 一1 4 1 5 1 8 1 9 2 0 2 1 2 2 2 7 2 7 2 9 3 4 4 1 5 1 弱弘弛 国防科学技术大学研究生院学位论文 表目录 表2 1 指令类型与执行单元类型之间的关系 表2 2 模板字段编码及指令槽分布 表4 i i a 6 4 汇编代码比较 2 7 2 8 5 3 独创性声明 本人声明所呈交的学位论文是我本人在导师指导下进行的研究工作及取得 的研究成果尽我所知，除了文中特别加以标注和致谢的地方外，论文中不包含 其他人已经发表和撰写过的研究成果，也不包含为获得国防科学技术大学或其它 教育机构的学位或证书而使用过的材料与我一同工作的同志对本研究所做的任 何贡献均已在论文中作了明确的说明并表示谢意 学位论文题目： ! ! = 指佥遇废硒窒 学位论文作者签名：壹圭硷 日期：功护啦年，月，r 日 学位论文版权使用授权书 本人完全了解国防科学技术大学有关保留，使用学位论文的规定本人授权 国防科学技术大学可以保留并向国家有关部门或机构送交论文的复印件和电子 文档，允许论文被查阅和借阅；可以将学位论文的全部或部分内容编入有关数据 库进行检索，可以采用影印、缩印或扫描等复制手段保存、汇编学位论文。 ( 保密学位论文在解密后适用本授权书。) 学位论文题目：! 筮i ! 指佥遇鏖班趋 学位论文作者签名： 作者指导教师签名： 重登 壑荭巨 日期：劢口4 年，月，n 日期：加 年1 1 月侈日 国防科学技术大学研究生院学位论文 1 1 1 课题研究背景 第一章绪论 1 1 课题研究背景与现状 近二十年来，微处理器发展迅速，性能得到了很大的提升，同时由于其性价比高，应 用范围不断扩大，现在大部分的计算机系统都是基于微处理器的。探究微处理器的迅速发 展的原因，主要有两个：首先是计算机体系结构的创新。表现为各种体系结构的提出以及 相应技术的发展：应用技术的发展，包括器件技术在内的计算机制造技术的进步，也有力 的推动微处理器的发展。 经典计算机体系结构的实质是计算机系统中软硬件界面的确定，界面之上是软件的功 能，界面之下是硬件和回件的功能。在计算机体系结构的发展过程中，这种软件与硬件的 分工一直在变化发展之中。 指令系统是计算机体系结构的一个基本组成部分，它的设计好坏直接影响着处理器的 性能，处理器在很大程度上是围绕着指令系统进行设计的。在计算机体系结构的发展过程 中，出现了通过增强指令功能来提高计算机性能的c i s c 体系结构，人们发现这样的设计 理念在实际中并没有带来进一步的性能提升，反而给指令系统的设计以及编译的实现和优 化等带来了困难。于是有了r i s c 体系结构的出现，它采用简单的指令以达到快速执行指 令的目的，并且指令系统由使用频率高的指令组成。从指令系统的角度来看，将原来复杂 的指令由多条简单的指令来实现，将一个复杂的操作分解成多个简单的操作，将有利用开 发更多的并行性。 人们进行指令级并行( i n s t r u c t i o n l e v e lp a r a l l e l i s mi p l ) 的研究，以获取计算机系统的 高性能。指令级并行是一系列的处理器和编译器设计技术，通过使单个机器指令能够并行 运行获得加速。指令级并行所涉及的机器指令是具有r i s c 风格的指令，并且这些技术用 于处理单个程序，这些程序在书写的时候被认为会在顺序执行的处理器上执行【1 ，这是指 令级并行不同于多处理器并行和大规模并行处理的一个重要特征，而且指令级并行多数情 况下对于程序员来说是透明的。 要获取指令级并行，编译器和处理器硬件要解决三个问题： 1 要确定指令之间的依赖关系； 2 要确定哪些指令不依赖于任何未计算指令； 3 要确定对这些独立的指令的调度，使得它们能够在特定的时间，在某些功能部件 上运行，并且有分配的寄存器来存放结果。 这三个问题实际上涉及编译器和处理器硬件之间的分工。从编译器与处理器分工的角 度看，计算机体系结构发展到现在，主要经历了三种风格： 国防科学技术大学研究生院学位论文 1 程序不需要明确指出任何并行信息，所有指令依赖关系的判断和调度工作由处理 器硬件完成，通过硬件重新安排指令的执行顺序，来调整相关指令实际执行时的 关系，减少处理器空转。这大大增加了处理器硬件设计的复杂度，而且也限制了 指令级并行度的进一步提高。超标量机器是这种体系结构的代表，从某种程度上 说，向量机也具有以上的特征。 2 硬件不提供互锁机制，完全依赖编译器静态的分析程序中指令的依赖关系并指定 执行顺序，通过调度导致阻塞的相关指令，减少处理器空转。这类结构的典型就 是超长指令字( v l i w ) 机器，它把传统上由硬件实现或部分实现的功能完全交由 软件实现，因此简化了硬件的设计，使机器能够达到较高的并行性能。 3 主要依靠编译器分析，同时提供必要的硬件支持，确定指令执行顺序，通过软硬 件协同工作，获取高性能。这类结构的典型就是e p i c 体系结构，通过编译器的作 用，简化硬件设计，提供大量的硬件资源获得更大的指令级并行。 可以看出，对程序中的指令进行调度是提高微处理器性能极其重要的一个环节，在开 发指令级并行时，编译器和微处理器硬件的分工也在围绕着这个问题。当然指令级并行的 获取是一个复杂的系统的问题，需要利用各面的技术来实现。 对于超标量处理器，编译器在其上的主要作用只是对程序代码进行重排，使得硬件在 进行分析和调度的时候能够更有效，即指令之间的依赖关系的分析、硬件资源的分配、最 终执行时进行的动态指令调度都是由处理器来完成的。随着研究的进一步深入，人们发现 超标量技术难以开发出程序中更大的指令级并行，超标量技术的实现复杂度随着规模的增 加，增长很快。超标量处理器中资源利用率极低，不断增长的处理器和主存性能差对超标 量处理器的性能影响很大。资源利用率低的根本原因是由于程序中存在的数据相关、控制 相关使得超标量结构的指令调度窗口往往非常低效，其中的空操作指令比较多。虽然还有 许多改进和替代结构可以进一步提高超标量处理器的性能，但是都非常有限，以上这些因 素都限制了超标量处理器的发展。 1 9 8 3 年耶鲁大学的f i s h e r 教授提出了水平微程序设计原理，与超标量处理技术相结合 产生了超长指令字( v l l w ) p j 体系结构，提供较高的指令级并行度，同时又具有简单的硬 件译码和控制逻辑。由于编译可以对程序进行全局的指令分析，在个( 虚拟的) 很大的 指令窗口中调度指令，所以有可能开发出比超标量技术更大的指令级并行；而且指令调度 完全由编译完成，所以硬件设计简单，不会出现超标量中实现复杂的问题。只要编译可以 开发出更大的指令级并行，v l l w 处理器就可以简单的靠增大处理器规模柬提高性能。正 是由于以上两个突出的优点，v l l w 被许多人看好作为超标量的下一代替代技术。众多研 究单位一直在广泛研究v u w 技术，许多公司已经推出基于v l l w 的主流产品，如f p s a p 1 2 0 b 、m u l t i f l o w 、c y d r o m ec y d r a5 、e 2 k 等，v l i w 逐渐成为当今流行的体系结构。 v l l w 将指令级并行的组织工作完全交给编译器，但是对编译器开发潜在指令级并行的支 持甚少，使得编译器难于有效地实现较充分的指令级并行。 第2 页 国防科学技术大学研究生院学位论文 1 9 8 9 年到1 9 9 3 年h e w l e t t p a c k a r d ( h p ) 实验室进一步发展了v l l w 的思想，并采用 了超标量处理器中的一系列技术，提出了显性并行指令技术e p i c ( e x p l i c i t l vp a r a l l e l i n s t r u c t i o nc o m p u t i n g ) 1 2 】的体系结构框架。e p i c 体系结构框架在把更多的系统特性暴露给 编译器的同时，也提供相应的硬件支持，希望通过编译器和硬件的协同配合来获得更高的 性能。 在硬件设计方面，随着工艺技术的发展，晶体管集成度在不断上升，为设计高性能微 处理器提供了有力支持。在微处理器设计上，出现了两种设计的理念：一个是充分依靠硬 件，把尽可能多的工作交给硬件处理，开发复杂的控制逻辑；另外一种就是充分利用软件 的能力，硬件设计朝着规整简单的方向发展。人们发现随着芯片晶体管集成度的上升，通 过开发复杂的硬件控制逻辑来提高处理器性能，难度越来越大，于是人们转向另外一个方 向。i n t e l 公司提出的i a 6 4 【4 】微处理器体系结构属于后一种设计理念，可以认为它是e p i c 体系结构框架在通用处理器领域的实例化。目前i n t e l 公司已经推出了i t a n i u m 和i t a n i u m 2 两代i a 一6 4 体系结构的商品化微处理器，主要应用于高端服务器。i n t e l 公司同时推出配套 的系统软件i n t e l 商用编译器，随着对该编译器的不断开发与改进，r a n i u m 系列处理器 性能不断提升。 1 1 2 研究现状 不论是v l i w ，还是与其关系密切的e p i c ，从编译器与处理器硬件的分工角度上来看， 都极大的依赖于编译系统的支持，以保证程序的正确运行及获取高性能，编译器的重要性 更加突出。它们降低了硬件设计的复杂性，同时对编译器提出了很高的要求。其中一个非 常重要的方面就是指令调度的工作，包括对指令间依赖关系的分析、对硬件功能部件使用 的分配、对指令进行调度和变换来隐藏延迟等内容，使得程序能够正确高效的在处理器上 运行。如何更好的利用新体系结构的功能特性，提高程序执行效率，成为了近年来国内外 编译研究的一个热点。 现在支持i a 6 4 体系结构的编译器主要有i n t e l 公司的商用编译器【j ”、g n uc o m p i l e r c o l l e c t i o n ( g c c ) 2 9 1 、o p e nr e s e a r c hc o m p i l e r ( o r c ) 【3 6 1 等，并且它们分别针对i a 6 4 体系结构的特性采用了不同的技术来获取性能的提升，目前i n t e l 公司的商用编译器在 i a 6 4 的微处理器上获得的性能是最好的。 在这些编译器的研究开发中，指令调度是一个非常重要的方面。i a 一6 4 体系结构为了 更好的开发指令级并行，提供了许多的硬件支持，如对数据投机和控制投机的支持、对指 令谓词执行的支持、对软流水的支持等等，指令调度可以充分利用这些体系结构的支持来 提高性能；i a 一6 4 体系结构同时提出了指令束( b u n d l e ) 、指令模板( t e m p l a t e ) 、停止( s t o p ) 等一系列新概念，这些概念的提出实际上是提出新的硬件约束，使得指令调度过程要处理 的情况变得复杂。 i n t e l 的商用编译器在开发利用i a 一6 4 的特性方面表现出色实现了投机及软流水等功 国防科学技术大学研究生院学位论文 能。该编译器中采用了种称为波阵面( w a v e f r o n t ) 的指令调度技术，改变了控制依赖和 数据依赖的表示方式，改进了指令调度的调度区域，提高了效率，开发出程序中更多的指 令级并行以及充分利用了i a 6 4 体系结构的特性【6 1 。 o r c 是由中国科学院计算技术研究所与i n t e l 公司联合开发的i a 一6 4 开放源码编译器， 它以s g i 公司的开放源码编译器p r 0 6 4 为基础，新增了编译研究的基础设施与面向显式并 行体系结构的编译优化技术。o r c 采用的编译技术包括集成资源管理的全局指令调度，条 件执行，谓词关系数据库，控制和数据投机执行等；同时提供了个公共编译研究平台， 包括基于区域的编译优化，机器模型，程序运行信息的收集与反馈机制等。现在已有大学、 研究单位用此开放源码编译器作为他们的研发平台。 g c c 作为一个开发源代码的自由软件，有着清晰的前端语法树结构、高度概括的抽象 机中间语言、简洁有力的后端机器描述以及开放式的整体结构，为实现多种语种开发、多 平台移植提供了有力的支持。近年来各学术机构都把g c c 作为研究对象，同时一些著名 的i t 企业，如i b m 和r e dh a t 等也支持g c c 的发展，人们正在把各种先进的编译技术往 g c c 中集成，使得g c c 在各方面都得到迅速的发展。目前g c c 已经成功的移植到了i a 6 4 平台。 丰富的硬件资源和指令级并行支持机制，以及指令流出的复杂要求，都成为编译器在 队- 6 4 平台需要面对的挑战。对于i a 6 4 体系结构提出的指令束、指令模板、停止等一系 列对于指令输出序列的要求，为了在i a 6 4 平台获得高效的目标代码，人们进行了深入的 研究。用有限自动机( d f a ) 来模拟i a 6 4 处理器的硬件资源约束的方法被广泛采用，g c c 和o r c 均采用了这种技术，但是在两个编译器中的具体实现方式存在很大区别【7 ，8 】。由于 程序本身有限的并行性，目标代码中插入的空操作指令数目多是v u w 这类处理器的普遍 情况，空操作指令的插入导致代码量变大，而i a 一6 4 体系结构的目标代码量由于各种原因， 比其他体系结构的要大。有人【9 1 针对i a 6 4 特有的指令模板情况，推导出关于不同类型的 指令在调度时的约束关系，在指令调度时根据指令类型，依次满足相应的约束关系，以尽 可能少的插入空操作，这个过程采用递归搜索的方法，并采用一系列的启发式策略减少搜 索时间。该方法关注于静态的代码情况，明显的减少了代码量，但是没有对指令的动态执 行予以足够的考虑。整数线形规划在i a 6 4 平台指令调度的应用也有了深入的研究f 1 0 】，该 技术的能够获得较高质量的目标代码，但是由于它的复杂性，开销比较大，在工程应用上 存在一定的难度。 在指令调度过程中结合使用l a 一6 4 体系结构提供的对投机的支持也成为了一个重要的 研究点，目前在i n t e l 的商用编译器和o r c 中已经支持在指令调度过程中应用这一体系结 构特性。i f 转换将控制相关转化为数据相关，使指令调度能够开发出更大的指令级并行， i a 6 4 体系结构为此提供了谓词执行的机制，以上三款编译器都不同程度的应用了这一特 性，如何有效的发挥谓词执行机制的优势值得进一步探讨。软流水技术在处理对循环的调 度上有其独到的优势，i a - 6 4 体系结构为编译器进行软流水调度提供了相应的硬件支持， 第4 页 1 2 1 课题来源 1 2 课题研究内容 本课题来源于8 6 3 软件重大专项( 项目编号：2 0 0 2 a a i z 2 1 0 5 ) ，该项目的主要研究内 容是针对当前主流微处理器，研发一个高性能微处理器优化编译器。受该项目的支持，本 课题重点对i a 6 4 指令调度进行研究。 1 2 2 课题研究重点 在人们长期的研究中，开发出了各种指令调度技术，指令调度的主体基本上已经确定 下来，但是随着编译其他方面技术的发展，在不同的体系结构以及应用环境中，指令调度 的进一步研究，对达到不同的目标而言，如进一步获取高性能和降低处理器功耗等，仍然 有重要意义。基于这种情况，本课题把研究重点放在以下几个方面： 1 研究已有的各种主流指令调度方法，并从指令调度的关键方面对这些指令调度方 法予以分析比较，以期能够对指令调度的有一个较深入的理解 2 对目标平台i a 一6 4 体系结构进行研究，获取指令调度的目标环境信息，在指令调度 时充分利用体系结构提供的支持来进一步获取高性能 3 根据课题来源项目，对g c c 指令调度进行剖析， o r c 在指令调度方面的技术特点 4 结合对于指令调度方法和i a 6 4 体系结构的研究， 问题进行改进 1 2 3 课题研究难点 同时研究i n t e l 商用编译器以及 针对g c c 指令调度目前存在的 指令调度涉及的方面比较多，包括目标机器环境、编译器的一些后端功能、源程序的 分析、指令调度算法以及一些启发式策略的应用等，可以说指令调度已成为现在的编译器 中最复杂的部分之一。具体到本课题，主要难点表现在： 1 指令调度研究具有较强的理论性，指令调度算法看起来似乎并不是那么复杂，但 是在基本的算法背后，进行具体的指令调度需要进行许多复杂的分析。 2 i a 6 4 具有丰富的硬件资源，提供强大的处理麓力，同时它也是一个复杂的体系结 构，有效的利用资源成为了指令调度必须解决的一个问题。目标机器环境的复杂性给指令 调度带来了困难，如i a 6 4 体系结构有大量的功能部件，有复杂的指令流出规则，这些需 要深入的研究。 3 对于开放源代码的编译器，要深入了解其指令调度及其相关部分的具体实现，需 第5 页 国防科学技术大学研究生院学位论文 要阅读源代码，进行分析来获取相关信息，以对其进行有关的改进，总的来说需要的工作 量较大。 1 3 本课题的主要工作 本文研究了指令调度的理论，分析了i a 6 4 体系结构的指令调度解决方案。对g c c 的指令调度部分，分析了存在的问题，提出改进的算法，并给出了相应的测试数据。本文 具体的工作主要体现在： i 指令调度理论方面 指令调度是人们进行编译研究的重点，研究角度多样。本文从程序语义的角度对指令 调度中开发并行性进行了分析，研究了指令调度的主流技术，对各种技术的优缺点进行了 比较，总结提出了基于区域的指令调度算法的模型。把指令调度与两个相关领域的异同进 行了比较。 2 i a 6 4 体系结构方面 作为目标平台的i a - 6 4 ，具有丰富的硬件资源，为开发指令级并行提供了相当多的支 持机制，同时也对指令的流出提出了来自硬件的要求。针对i a ，6 4 体系结构这些特征，本 文指出了在指令调度过程中应该注意的点。 3 指令调度实现方面 根据课题来源项目，分析了g c c 的基本结构和工作流程，着重对g c c 的指令调度部 分进行了剖析，对实际的编译器指令调度过程中涉及的各种关键技术因素进行讨论。深入 研究了g c c 在认- 6 4 平台下采用的技术，同时结合o r c 与i n t e l 商用编译器的指令调度部 分，进行了分析比较，得出了在i a 6 4 平台进行指令调度的一些关键因素。 4 g c c 在i a 一6 4 平台指令调度的改进 指出g c c 现有指令调度算法的优点，分析了g c c 指令调度算法有待改进的地方，同 时对其有待改进的地方，提出了改进的调度算法，实验得到的数据说明了改进算法具有一 定的效果，并根据实验数据分析了原因。 1 4 论文结构 全文共分五章。 第一章为绪论，首先介绍了课题背景；然后说明了课题来源和研究内容，包括课题研 究重点与难点；概述了国内外相关领域的研究工作，以及本文的主要工作；最后介绍了论 文的结构安排。 第二章对指令调度的理论进行了研究，对指令调度的主要技术进行了比较和总结，提 出了基于区域的指令调度算法的框架。介绍了i a 6 4 体系结构，研究了i a 一6 4 体系结构与 指令调度相关的特性。 第6 页 国防科学技术大学研究生院学位论文 第三章分析了g c c 的基本结构，着重对g c c 的指令调度部分深入进行了剖析，对 g c c 指令调度部分在i a 一6 4 平台采用的技术进行t n 讨论，指出了g c c 指令调度部分 的优点。同时对o r c 与i m e l 商用编译器的指令调度部分进行了相应的分析，得出一些在 i a 一6 4 平台指令调度的关键因素。探讨了g c c 有待进一步改进的地方，给出g c c 指令调 度的改进算法。 第四章在i t a n i u m 2 的服务器上，对改进算法以及g c c 原有算法等算法，采用s p e c c p u 2 0 0 0 进行了测试，实验得到的数据说明了改进算法具有一定的效果，并对实验结果 进行了进一步的分析。 第五章对本文的工作进行了总结，并展望了下一步的工作。 第7 页 国防科学技术大学研究生院学位论文 第二章指令调度理论与i a 6 4 体系结构研究 指令调度是人们进行编译研究的重点，研究角度多样。本章首先给出了指令调度的形 式化定义以及指令调度的基本特征，分析了依赖关系以及依赖图，从语义的角度研究了程 序中指令级并行的开发，讨论了两种硬件资源冲突判别的方法，然后提出了一个基于区域 的指令调度模型，将主流的指令调度算法纳入这个模型。根据这个模型，我们总结了在指 令调度过程的采用的技术，并对各种技术的优势与劣势进行了分析比较，还把指令调度与 两个相关的领域进行了比较。最后对i a 6 4 体系结构指令调度相关特征，结合指令调度中 的一些特点进行分析。 2 1 1指令调度的定义 2 1 指令调度的定义与特征 指令调度的框架可以做如下的描述： 1 对于一个机器m ，具有一个功能部件的集合f = f i ，f m ) ； 2 对功能部件的集合有一个配置向量f m ，表示为l t t 维向量n “，其中第k 维( f m ( k ) ) 表示功能部件f k 的数目； 3 n 条指令的集合o = o p l ，o p 2 ，o p 。) ； 4 延迟函数l ：o f n 1 ，l ( o p i ，) 表示指令o p i 在功能部件f j 上执行获得结果需 要的时间； 5 流出时间间隔函数i t ：o f n ，i t ( o p ，f j ) 表示指令o p 在功能部件f j 开始执行 后，另外一条指令能够在功能部件开始执行的时间间隔； 6 功能部件使用函数f u ：0 一 f ) ，f u ( o p i ) 表示能够执行指令o n 的功能部件的集 合； 7 依赖图p d g = ( o ，e ) ，表示指令集合。上的一个偏序关系，一条边( u ，v ) e 表示指令u 在调度中必须保持先于指令v ； 指令调度可以做如下描述： 一个正确的指令调度是依赖图p d g 的各节点( 指令) 到表示处理器时序( 假设起始 时间为1 ) 的自然数集的一个映射s ：o n ，满足： 1 对于所有的o p o ，s ( o p ) 1 ， 2 如果( u ，v ) e ，s ( u ) + d e l a y ( u ，v ) s ( v ) ， 3 对任意使用功能部件f k 的节点，最多只有f m ( k ) 个节点被映射到给定的 整数。 n 为自然数 第8 页 国防科学技术人学研究生院学位论文 其中d e l a y ( u ，v ) 根据依赖关系不同取不同的值：当v 使用u 产生的结果时，取值为 l ( u ，5 ) ；当v 等待t l 使用的功能部件时，取值为i t ( u ，五) ，其他情况根据目标机器的 处理方式取不同的值，往往为1 。 条件l 保证所有的指令均会在某时刻被执行；条件2 保证没有依赖关系被破坏；条件 3 保证在任意周期内所使用的硬件资源未超过目标机器所提供的资源。调度s 的长度记为 l ( s ) ，定义为l ( s ) = m a x ( s ( o p ) + i ( o p ，价1 。 口 一 这个指令调度的定义对超标量处理器和v l l w 处理器都是适用的。指令调度就是要找 出最合适的指令排列顺序，使得程序执行的时间最短，不幸的是寻找这种排列顺序的过程 是n p 完全的，其证明可以参考【2 ”。 对于现在的处理器，指令调度是一种代码的重排和转换，用来隐藏微处理器中的执行 延迟，充分发掘程序中存在的并行性和发挥硬件体系结构提供的指令级并行能力。指令调 度的目标是以这样一种顺序生成指令，把有依赖的指令放置足够远，同时使尽可能多的功 能部件在每一个机器时钟周期内处于忙的状态。 2 1 2 指令调度的特征 指令调度是面向代码生成的编译优化技术，在编译的各优化遍中处于靠后的位置。指 令调度过程需要使用来自源程序和目标机器的信息，所以指令调度器处理的指令序列通常 是某种低级的中间语言，这种中间语言接近于目标机器指令集，能够提供来自于源程序的 信息和目标机器的信息，g c c 中这种中间语言是r t l 语言 2 4 j 。 在指令调度这个优化过程中，必须保持程序原来语义不变，即在指令调度后，程序运 行的结果应当与末调度时程序运行的结果保持一致。指令调度获得的指令序列比较未调度 的指令序列，在执行时应当有相应的加速，可能在程序的某些部分执行速度会下降，但是 程序整体的性能应当是提升的。进行指令调度必须对程序进行分析，然后采用一定的调度 算法对代码进行改进，在某些情况下，这种分析和改进的时间和空间复杂度是很大的。因 此进行指令调度必须在一个可以接受的代价下进行。实现一个指令调度器要做到以上的三 个方面。 2 2 依赖关系与依赖图 上一节对指令调度进行了形式化描述，具体的编译器中要实现描述中各函数的功能， 并完成对l ( s ) 的求解，其中一个重要的部分就是建立依赖图，建立依赖图需要对程序代 码进行依赖分析。 2 2 1 依赖关系 程序员使用串行程序设计语言编写程序，通过程序说明他所希望的指令执行顺序。严 第9 页 国防科学技术大学研究生院学位论文 格按照源程序的说明来开发并行性几乎是不可能的，在指令调度中开发并行性要改变操作 的顺序。 实际上只要一个保证能够与程序顺序代码计算结果相同的执行顺序就可以满足要求。 对原来指令序列进行任何不破坏依赖关系的重新排序，可以保证获得的指令序列与原来指 令序列有相同的计算结果。依赖关系是程序中指令之间的关系，包括数据依赖和控制依赖， 每一对存在依赖关系的指令称为个依赖。依赖关系抓住了命令式语言中正确性的一个重 要策略：它们保持程序中对每个存储单元取数和存数的相对顺序。 数据依赖是能够保证数据按正确的顺序产生和消费的约束。严格的定义可以表述为： 从指令s 1 到指令s 2 存在数据依赖( 指令s 2 依赖于指令s 1 ) ，当且仅当 1 两个指令同时访问相同的存储单元，并且其中至少有一条指令存入此单元， 2 存在条从s 1 到s 2 的可能的运行时执行路径。 可以直观的认为指令对间的数据依赖要求该指令对保持相对的执行顺序不变，在数据 依赖图中，存在数据依赖的指令对之间的依赖关系表示为从先执行指令到后执行指令的有 向边。 具体数据依赖又可以分成以下三类：真依赖，第一条指令对一个单元( 寄存器或者内 存单元) 存入数据而后由第二条指令读出。反依赖，第一条指令从一个单元( 寄存器或 者内存单元) 读出数据，随后第二条指令对此单元存入数据。输出依赖，两条指令对同一 个单元( 寄存器或者内存单元) 写入数据。 对于直线形代码，数据依赖关系是直观的，我们要注意到循环的不同迭代之间也存在 着数据依赖。为此，循环依赖的定义为： 在公共嵌套循环中存在从指令s 1 到指令s 2 的数据依赖，当且仅当此嵌套循环存在两 个迭代向量i 和j ，使得 i ，i j ，或者译i 并且在循环体中有一条从s 1 到s 2 的路径， 2 在迭代i 中指令s 1 访问存储单元m ( 寄存器或者内存单元) ，而在迭代j 中也指 令s 2 访问存储单元m ( 寄存器或者内存单元) ， 3 这个两个访问中至少有个是写入。 在程序的指令中有这样一些指令，它们能够改变程序计数器( p c ) 的值，从而决定下 条被执行的指令，这些指令包括条件分支指令、无条件分支指令、过程调用指令、过程 调用返回指令。使用这样的指令，程序员能够明确的表达所希望的计算机执行指令顺序， 要保持程序的语义，就必须保证这类依赖关系不被破坏。程序中控制流可以映射到一个有 向图。如果 1 存在一条从指令s 1 到指令s 2 的非空路径，使得在这条路径上的每条指令s 3 ( s 3 s 1 ) 被指令s 2 后支配， 2 s 】不被s 2 后支配，就说指令s 2 控制依赖于指令s 1 。 这个定义的直观含义是s 1 必须是一个条件分支，这样的分支转向一个方向时s 2 必然 第1 0 页 被执行，如果分支转向另外的方向，控制流就不会执行到s 2 。 在编译器中，基本块是一个广泛应用的概念。基本块是一个连续语句的最长序列，如 果其中的一条指令执行了，其他指令都会被执行。从基本块的定义，我们可以知道，在基 本块中控制流是没有变化的，所以一个基本块中的每条语句有相同的控制依赖，可以把控 制依赖作为基本块的性质来讨论，从而可以得到这样一个有向图：每个节点表示个基本 块，每条边表示一个可能的控制转移，即控制流图。 无条件分支指令、过程调用指令、过程调用返回指令没有给出依赖关系的定义，是考 虑到这些指令的特殊性：它们的目标地址处指令是一定会被执行的。对于这些指令虽然没 有对它们给出控制依赖关系，但是它们仍然会改变控制流，在形成控制流图时必须予以考 虑。过程调用、过程调用返回隐式的包含在控制流图中，而无条件分支指令产生的控制流 转移则要显示的表示出来。 2 2 2 依赖图 依赖图的获取是基于数据依赖关系和控制依赖关系的，另外我们还要考虑目标机器上 的指令执行情况。为了加入硬件资源的约束指导指令调度，要根据不同的依赖边，在依赖 边上标记来自硬件的信息，如当依赖边表示真依赖时，我们要在依赖边上标记指令的执行 延迟。 指令间的数据依赖分析【1 1 1 ，对于寄存器形式的操作数来说是比较容易的，但是对于内 存单元形式的操作数分析变的困难。因为很多情况下，编译器不能够确定具体的内存单元 地址，此时只能采用保守的策略，对不能判明的依赖，认为这种依赖关系存在。 指令的控制依赖关系直接体现为控制流图，并且通过形成调度区域的形式使得控制依 赖关系在指令调度过程中得到满足，然而情况往往要复杂一些。 在实际的编译器中，某些情况下要保持一些改变控制流的指令与其他指令的相对执行 顺序不变。对包含在基本块中的过程调用，如果该过程调用指令和其他指令存在某种数据 依赖关系，或者该过程可能对当前环境的变量有副作用，那么我们就要注意在改变它和其 他相关指令的执行顺序时进行判断，保证程序的语义不被该变。无条件分支和过程调用返 回指令般是基本块的最后一条指令，条件分支指令也是如此，显然在调度后它们也必须 仍然是基本块最后条指令，否则就可能导致某些语句不被执行，破坏程序的语义。在控 制流图中这种信息是不会被体现的，在实际中，编译器会把这种约束关系体现在数据依赖 图中，通过增加和基本块中每条指令的依赖边，保证这些指令在指令调度后仍然是基本块 最后一条指令，更有效的做法是和数据依赖图中每条数据依赖路径的最后一条指令建立依 赖边。 2 2 3 依赖关系的变换 篇1 1 页 国防科学技术大学研究生院学位论文 有些依赖关系可以通过某种程序变换技术而消除，在些情况下，当系统支持投机执 行时，可允许突破某些保守的依赖关系的限制，这有利于并行性的进一步开发，许多技术 可以实现这种功能。其中i f 转换( 也叫谓词技术或者条件执行) 【j l 】和投机代码移动 ( s p e c u l a t i v ec o d em o t i o n ) 【2 ”常被指令调度过程用来改变或者消除控制依赖，其中投机代 码移动如果有体系结构的支持能够突破保守的依赖关系的限制。变量扩张1 7 1 将被展开的循 环体中的变量扩张成每个循环体的拷贝都有一个该变量的拷贝；循环执行完成之后，这些 拷贝