计算机科学与技术专业研讨

1、甘肃政法学院本科学年论文（设计） 题 目 _指令级并行技术研究 计算机科学学院计算机科学与技术专业08级计本2班学 号：_ 200881010227_姓 名：_祁云龙_ 指导教师：_ 王云峰_ 成 绩：_完成时间：_2011_年 _12_月目录一、引言1二.指令级并行处理2三.指令级并行度24.指令级并行体系结构3（一）指令级并行体系结构的分类3（二）各类指令级并行体系结构的特点4五.指令级并行编译的研究现状及发展4六.芯片的体系结构和编译器的总体结构5（一） M一MACHINE体系结构5（二） MCC总体结构6参 考 文 献8指令级并行技术研究祁云龙【摘 要】指

2、令级并行处理是提高处理器性能的关键，而编译器在其中的作用是至关重要的。近二十年来，指令级并行编译一直是工业界和学术界关注的热点，在这方面也已作了大量的工作，但许多问题仍未得到圆满解决。本文对包括中间表示设计、寄存器分配和指令调度等在内的指令级并行编译的关键技术作了较为深入的研究，并将研究成果应用于一个类VLIW处理器的指令级并行C编译器的设计和实现中，取得了比较好的效果。提出在编译器中采用多视图的中间表示:在中间表示的设计中引入视图的概念，利用同一对象的多个分立定义的视图，满足各遍算法对于中间表示的不同需求:分离对象的物理视图与逻辑视图，隐藏物理视图的实现细竹，使算法工作在高层的逻辑视图上，并

3、通过视图变换将高层算法映射到低层中间表示上。通过这种方法，可以简化算法表述，提高算法的抽象层次，从而达到降低开发代价，提高算法可重用性的目的。【关键字】指令级井行编译ABSTRACTInstruction-level parallel processing is the key technology to Promoting the performance of current processor，and compiler Plays a very important role in it .In the past 20 years，a lot of work has been done in

4、 this area . But there are still problems remaining unresolved .This paper discusses in depth the key techniques of instruction-level parallelizing compiler design，including : design of intermediate representation , register allocation , global instruction scheduling，etc . We applied the results in

5、the development of a prototype C compiler for a VLIW-like processor ,and acquired fairly good effect.Present the multi-view intermediate representation : we introduce the concept of view in the design of intermediate representation(IR).With multiple discretely defined views of a single object，we can

6、 satisfy the different requirements to IR of algorithms of different passes. We separate the physical view and logic view of IR，and make algorithms work on the high-level logic view，and map the high-level algorithms into low-level IR through view transformations. With this technique we can simplify

7、the formulation of algorithms and reduce the development cost，Promote the abstract level and reusability.Keywords :Instruction一Level Parallelism(ILP)一、引言对于计算能力的日益增长的需求推动着计算技术的发展，促使计算系统的设计和制造者不断发展并应用各种新技术。纵观计算机从诞生至今近半个世纪的发展历程，其性能价格比的提高主要源自两个方面:器件技术的进步和体系结构的创新。一方面，计算机系统的制造者通过使用具有更高速度和集成度的器件，来提高整个系统的运算

8、速度和存储容量，另一方面，体系结构设计者则致力于发掘系统内的并行性，通过使多个操作并行执行而达到缩短程序总的执行时间的目的。特别是近二十年来，并行处理技术取得了长足的进步，成为现代高性能计算机的关键技术。通常，在应用程序中存在着不同层次的并行性，按照其粒度大小，可以分为任务级并行性、循环级并行性和指令级并行性三类1，相应地，在体系结构上也发展了各种技术来利用这三类不同的并行性，如针对任务级并行性的并行计算机(又分为共享存储多处理机和消息传递多计算机)，针对循环级并行性的流水线向量机，以及针对指令级并行性而在单个处理器的设计中采用的流水线、多发射、乱序执行等技术。并行机和向量机需要编制并行程序或

9、并行化现有串行程序，完全由人来手工编写并行程序费时费力，代价过大，人们希望由自动并行化编译器检测串行程序中的并行性，完成存储的分配和计算过程的重构，并生成并行代码或向量代码，而对于单个处理器来说，由于指令级并行的复杂性，编译器更是被视为其基本能力，如RISC结构的设计目标之一就是便于编译器生成高效的目标码。由此可见，并行编译技术在高性能计算中的地位与重要性是毋庸置疑的。二.指令级并行处理指令级并行处王，l)(Instruction一LevelParallelism.ILP)是指为了实现多个操作的并行执行而在处理器和编译器的设计中采用的一系列技术2。八十年代以来，随着半导体技术的进步，在单个处理

10、器芯片上集成的晶体管数量大大增加，硬件已有能力实现多个功能部件以及大容量的寄存器堆和片上Cache。然而，为了真正作到多个操作并行执行，还需要对传统编译器产生的顺序的类RSIC操作流作依赖分析和指令调度，以发掘程序中潜在的指令级并行性。这部分工作可以由硬件完成(动态调度)，也可以由软件完成(静态调度)，相应的有代表性的处理器体系结构为超标量(superscalar)和超长指令字(VLIW)体系结构。对于VLIW结构，编译器包揽了从依赖分析、指令调度到资源分配的所有工作，即使是采用动态调度的超标量结构，也需要编译器预先把相互无关的操作集中在一起，以便硬件能够较容易地发现可以并行执行的操作。由此可

11、见，编译器在指令级并行处理中的地位是核心的。三.指令级并行度指令级并行处理面临的首要问题是:串行程序中潜在的指令级并行度有多大?换句话说，即在不考虑技术可行性的前提下，确定程序中固有的指令级并行度的上限。这个问题早在70年代就引起了一些研究者的注意，他们作了一系列的实验并得出了十分悲观的结论。其中最有名的是Tjdaen和Flynn的结果，他们发现在实际的应用程序中，指令级并行度的上限仅为2一3，即平均在每一周期可以并行执行的指令约为2一3条，这被称为“Flynn瓶颈”。现在我们知道，Flynn瓶颈仅在基本块内是正确的，限于当时优化编译技术的水平，刀dane和Flynn既没有考虑到(或者说没有想

12、象到)代码移动越过基本块边界的可能性，也没有考虑到编译器可能作的其他各种优化变换，因而得出了过于悲观的结论。Fosetr和Riesman在功能部件数量不限的前提下作了类似的实验tFos7t2，他们发现若在分支处利用重复的功能部件同时进行两个方向上的训·算，并随后丢弃错误方向上的结果，则对某些程序，指令级并行度可以提高一个数量级以上，但Foster和RISemna又发现，用这种方法，若想得到IO的指令级并行度，则在程序的某些点会出现多达16条的未解决的分支指令，在这种情况下，需要重复的硬件达2之多，Foster和Risnemna随之否定了这种方法，认为那是不现实的。实际上，Foster

13、和Risnemna的方法虽不现实，但却显示了“Fylnn瓶颈”作为指令级并行度的上限(不计实现可能性)是不正确的。80年代末90年代初，随着超标量技术的逐渐成熟，许多研究者对关于指令级并行度的结论感到怀疑，遂重新进行了关于指令级并行度上限的研究，其中以wall于1991年所做的实验最为全面2，他所使用的模型考虑了当时提出的各种先进的技术，包括投机执行、访存识别以及其他各种编译优化技术，根据他得到的数据，对于包括SPEC在内的一大类基准测试程序，平均能够得到的并行度的上限是5。Lam和Wlison比较了各种消除控制流影响的方法，得到了与wall相同的结论1。这些工作最终澄清了关于指令级并行度的误

14、解。4.指令级并行体系结构（一）指令级并行体系结构的分类为使一个串行程序能够以指令级并行的方式执行，必须先对程序进行分析，以确定操作之间的依赖关系，进而确定哪些操作彼此无关，可以并行执行，最终决定操作发出的时刻，并为其分配资源和寄存器。这一过程中涉及的各项工作，通常既可以由硬件完成，也可以由软件(编译器)完成，这些工作在硬件和软件间的划分方式，导致了各种指令级并行处理器在体系结构上的差异。按照这一标准，指令级并行体系结构可分为串行体系结构、相关体系结构、无关体系结构和TTA(TransportTriggeredArehiteeture)体系结构几类，如下图所示:隐式并行体系结构:编译器生成通常

15、的串行代码，由硬件作依赖分析、指令调度和资源分配，硬件通常有一固定大小的指令窗口，在执行时对窗口内的代码片段作依赖分析，动态构造依赖图，并使用记分牌、Tomasul 算法等技术调度指令执行，以保证指令间的依赖关系得到满足，此类结构中有代表性的包括流水线标量结构、超流水线结构和超标量结构等，采用此类结构的处理器系列有Pentium(Intel)，PowerPC(IBM)，Spare(Sun)，Alpha(DEC)等。所谓“隐式”，是指并行在体系结构界面上不可见。相关体系结构:通常称为数据流结构，此类结构的编译器需对串行代码作依赖分析，生成的目标码中通过标明操作在依赖图中的后继显式包含此信息，操作

16、的结果通过令牌(Token)进行传递，在执行时刻进行令牌匹配，即匹配操作的所有操作数，匹配成功且功能部件可用的操作即可投入执行。此类结构未能成功地产品化，但 ManChester 大学1和MIT均开发过研究性的原型系统。无关体系结构:编译器包揽从依赖分析、指令调度到资源分配的所有工作，目标码中显式标明哪些操作并行执行，分别使用哪些功能部件等，硬件仅需对超长指令进行译码，剥离日其中包含的操作，并按照操作码中指示的资源，分发到相应的功能部件去执行，因此其结构可大为简化，原则上用于动态检测并行性和指令调度的电路均可省去。有代表性的是超长指令字结构(VLIW)。采用此结构的处理器有Multiflow的

17、Trace系列Colw88和Cydrome的Cydra一5Beek931。Intel和HP不久前共同提出的作为其下一代处理器体系结构的”显式并行指令计算”体系结构(Explicitly parallel Instruction Computing，EPIC)2实际上也是这种结构的改进。TTA体系结构:TTA结构比vLIw结构走得更远，更多的硬件细节被暴露在体系结构界面上，如功能部件的操作数锁存器，结果锁存器等，均为体系可见，其指令集中可以说只有一种类型的操作，即数据移动，包括通用寄存器之间的移动、锁存器之间的移动、以及通用寄存器和锁存器之间的移动，运算操作实现为数据移动的副作用，当功能部件的所

18、有操作数锁存器中均有数据移入时，该功能部件则被触发，经过一定的延迟，结果在结果锁存器中变为可用。TTA结构由荷兰Detfl大学H.Corporaal等人提出C2，他们对这一新的体系结构作了大量研究，并实现了一个称为人了口VE了ZNIT的原型系统，但目前尚未产品化。（二）各类指令级并行体系结构的特点隐式并行结构在串行结构中加入指令级并行机制，但在体系结构界面上维持不变，从而保持了与串行结构的二进制兼容，这也是流水线和超标量结构成为主流处理器结构的重要原因，这种结构的问题是硬件复杂和动态调度的效果不够理想:限于硬件窗口的大小，依赖分析能够发现的无关指令条数十分有限，其次，硬件很难实现较为复杂的调度

19、算法，指令调度器的能力也很有限，故此类结构的处理器能够获得的指令级并行度多在2-4之间。数据流结构的特点在于其执行机制是数据驱动，即操作何时执行由其操作数就绪的时间决定，理论上说(不考虑资源)，所有操作都是在最早的时刻得到执行，因而这种结构应能发掘大量的指令级并行性，但实际上，这种结构所导致的运行时开销太大，如令牌的匹配等均为非常费时的操作，因此未能成功地产品化。TTA结构非常新颖，能够降低由于多个功能部件和多端口的大寄存器文件所带来的数据通路的复杂性，但其编译器实现复杂，目前尚处于实验室阶段。超长指令字结构大概是最早提出的指令级并行体系结构，其思想可以追溯到早期采用微程序控制的处理器中使用的

20、微码优化技术(水平微码)，通过将依赖分析、指令调度和资源分配等工作交由编译器完成，一方面简化了硬件设计，使得在芯片上集成更多的功能部件和更大容量的寄存器堆及片上Cache成为可能，另一方面，由编译器来完成某些工作，如指令调度和旁路，确能得到更好的效果，但这同时也对编译器的设计一提出了更高的要求。此外，由于硬件微体系结构的某些部分在体系结构界面上变为可见，因此二进制兼容性难以保持，不过Intel宣称在其即将推出IA一64结构中，通过保留部分硬件互锁机制，保持了一定程度的二进制兼容性Dulo98，其技术细节尚不清楚。五.指令级并行编译的研究现状及发展国外于70年代末、80年代初相继开展了指令级并行

21、编译方面的研究和开发，并有一些产品问世，如Multiflow公司的Traee系列和Cydrome公司的Cydra一5，作为第一代产品化的超长指令字结构的机器，两者在商业上都失败了，但这两种机器的编译器中所使用的技术却成为这个领域中开拓性的工作，对于其后这一领域中的研究工作影响和启发非常之大。进入90年代，这一领域成为工业界和学术界的研究热点，大量新的编译算法被提出，许多成熟的技术在产品级编译器中得到应用，HP公司编译与体系结构实验室联合Illinois大学IMPACT小组和NewYork大学ReaCT一ILP小组，共同开发了一个指令级并行编译研究的公共平台一TrmiarnaKath98，该系统

22、包括一组平台性质的基础设施:如参数化、可配置的目标体系结构及其上的cycle级模拟器、用于描述指令级并行体系结构的机器描述语言、可扩展的程序中问表示等。国内在这一领域起步较晚，而且基本上是处于跟踪国外先进技术的阶段，但在某些方面仍然作出了很好的工作，其中，清华大学在新型体系结构和软件流水方面的工作是比较有代表性的。下面我们对前面提到的几种有代表性的指令级并行编译器作简要介绍。Cydra5的主要设计目标之一是支持内层循环的流水方式执行，为此在体系结构和编译器的设计一上都采用了许多新的技术。Cydra5为异构多处理器系统，由一个专用于数值计算的数值处理器NP(Numeric Processor)和

23、一个同构的多处理器前端机子系统组成，NP为超长指令字结构，包含7个完全流水的功能部件，核心操作集为类RISC的Load/Store结构，扩展了一些特殊的与循环控制有关的操作，寄存器文件设计独特(旋转寄存器文介仁，Rotating Register File)，意在支持软件流水。Cydra5的编译器采用了两级中间表示，高层为抽象语法树，低层为四元式，全局性的优化包括公共子表达式删除、常数传播、代码外提、强度消减及死代码删除等，全局寄存器分配采用的是Chow和Hnenesys提出的优先级着色方法Chow90。最有特色的是对于内层循环的处理采用了Rau和Hsu等人提出的模调度方法Rua94(一种软件

24、流水技术)，但对于循环结构有较多的限制，包括:只能处理DO循环，循环必须是单出口的，循环体内不能有函数调用，等等。Multiflow的Traee系列也采用了VLIW结构，通常由多个群集(cluster)构成，每个群集中有4个流水的功能单元(两个定点单元和两个浮点单元)，以及5种共9个寄存器文件(定点2、浮点2、写回1、定点分支和浮点分支各2)，每条指令包含7个操作(定点2、浮点4、分支)l。编译器的核心技术是路径调度技术Lown93，这是第一种能够跨越基本块的全局指令调度技术，其想法是以某些执行频率很低的路径上代码长度的增加为代价，换得某些频繁执行的路径上代码长度的缩减。所谓路径，是指执行过程

25、中可能经过的一个基本块的线性序列。路径调度按执行频率的高低决定调度路径的先后次序。这种方法大致分为四个步骤，首先对每个操作，估算其执行频率，这一过程可以利用性能剖析的结果和用户提供的指导信它、。第二步是挑选TraCe。挑选一个执行频率最高且不在其它路径中的操作作为种子，然后让它向前(沿流图的方向)并向后生长，即将满足所使用的启发式规则且不在其它路径中的前驱和后继加入到路径中，若找不到这样的操作，则路径终止。第三步是使用某种局部指令调度方法一如表调度一对形成的路径进行调度，并用调度完的代码替换流图中原来的路径，如果在代码移动过程中越过了流图的分支点或合流点，那么还需要在路径之外插入相应的补偿代码

26、。最后，按深度优先序遍历调度后的流图并释放代码。对于循环，Trace系列的编译器未使用软件流水技术，而是采用了大规模展开的办法(在Tarec14/300系列_L可多达96次)，由于指令Cache很大(lMbytes)，故代码长度的增长未对性能造成太大影响。六.芯片的体系结构和编译器的总体结构（一） M一MACHINE体系结构目标机M一Machine基本上属于VLIW结构，带有TTA结构的某些特征，指令字宽度为128位，格式可变，执行部件中共有16个功能模块，包含22个独立、可并行执行的运算、逻辑部件，考虑到延时的操作，可同时执行4一16个操作。其结构如下图所示:从体系结构的角度看，目标机以_f

27、以卜一些部分组成:系统空间存贮管理部件:用于实现系统存贮空间的读写操作，该存贮空间包括:主存贮器DRAM以及各种外部存储设备。令局部存贮空间及其管理部件:用于实现片外局部存贮空间的读写操作。片内存贮空间及其管理部件:用一于实现片内存贮空间的读写操作，该空间以虚地址方式读写，用户不可见。寄存器堆:64个寄存器(64位)分为8组，寄存器可按64位访问，也可按32位、16位访问。数据通路:用于实现芯片中各个部件或存贮体之间的数据传送。功能部件:包括浮点运算部件、整数运算部件、译码控制及标识部件。在体系结构界而上，M一MACHINDJI被视为山功能部件(包含整数单元IU，浮点单元FPU)，寄存器堆等构

28、成的一组机器资源，M一MACHNE体系的汇编程序中显式指示程序中的并行性，CPU不必判断操作间是否相关。M一MACHINE体系结构的特点在于:Ø M一MACHINE体系结构的控制器和译码部件不必实现超标量处理器中必须实现的指令相关性分析，芯片结构简单，操作间的依赖由指令调度器保证满足。Ø 与超长指令字结构相比，M一MACHINE为了支持细粒度并行采用了独特的指令分派机制(如操作间的拼装，延时，替换，排序等宏加工连接符)。Ø 分离了操作设计和指令设计，增加了指令格式域，在指令设计中限制操作拼装的可能性，指令编码紧凑。令所有操作的延迟均为编译可见，实际上，编译器知道各

29、种操作读取操作数和产生结果的准确时刻(相对于操作发出时刻)。Ø 所有的功能部件流水线均无写回段，操作隐含地以执行段后的锁存器为结果寄存器，且所有这些锁存器均为体系可见。简而言之，M一MACHINE体系结构具有指令编码短，实现简单，可重组等优点。但编译器和其它系统软件需要做更多的工作适应其结构，体现其优点。为了生成正确且能够高效执行的目标代码，编译器必须:Ø 精确地分析处理器每一节拍的状态。Ø 发掘程序中潜在的并行性。Ø 优化使用寄存器和存储系统。Ø 进行针对机器特性的程序优化重构变换。以下介绍我们为M一MACHINE开发的指令级并行编译器MCC

30、的总体结构和各部分的功能。（二） MCC总体结构MCC包含两个层次的中间表示:Ø HLIR:高层中间表示面向源语言，适合依赖分析和并行化，用于编译器前端(包括常规的前端和中端)，其结构为抽象语法树。Ø LLIR:低层中间表示是编译器主体部分的基础，面向目标机，反映机器特性，支持各种指令级的分析和优化，低层中间表示中的操作在语义层次上与目标机汇编语言操作相同，同时为支持各遍有细微差异的需求，低层中间表示提供了多种预定义视图，并提供了用户自定义视图的能力。MCC在结构上分为三个部分，如下图所示:Ø 正规化:去掉C语言中的一些不规范的成分，如计算与赋值的连用，一个语句中的多个赋值，短路运算，问号表达式和逗号表达式。Ø HL