计算机体系结构(张晨曦)第4章-PPT

1/134▲ComputerArchitecture第4章指令级并行兰州理工大学计算机与通信学院包仲贤2/134▲ComputerArchitecture4.1指令级并行的概念4.2指令的动态调度4.3动态分支预测技术4.4多指令流出技术4.5循环展开和指令调度3/134▲ComputerArchitecture几乎所有的处理机都利用流水线来使指令重叠并行执行，以达到提高性能的目的。这种指令之间存在的潜在并行性称为指令级并行。（ILP：Instruction-LevelParallelism）本章研究：如何通过各种可能的技术，获得更多的指令级并行性。硬件＋软件技术必须要硬件技术和软件技术互相配合，才能够最大限度地挖掘出程序中存在的指令级并行。4.1指令级并行4.1.1指令级并行的概念4/134▲ComputerArchitecture4.1指令级并行1.流水线处理机的实际CPI理想流水线的CPI加上各类停顿的时钟周期数：CPI流水线=CPI理想+停顿结构冲突+停顿数据冲突+停顿控制冲突理想CPI是衡量流水线最高性能的一个指标。IPC：InstructionsPerCycle（每个时钟周期完成的指令条数）2.基本程序块基本程序块：一段除了入口和出口以外不包含其他分支的线性代码段。程序平均每5～7条指令就会有一个分支。5/134▲ComputerArchitecture4.1指令级并行3.循环级并行：使一个循环中的不同循环体并行执行。开发循环体中存在的并行性最常见、最基本是指令级并行研究的重点之一例如，考虑下述语句：for（i=1；i=500；i=i＋1）a[i]=a[i]＋s；每一次循环都可以与其他的循环重叠并行执行；在每一次循环的内部，却没有任何的并行性。6/134▲ComputerArchitecture4.1指令级并行4.最基本的开发循环级并行的技术循环展开（loopunrolling）技术采用向量指令和向量数据表示5.相关与流水线冲突相关有三种类型：数据相关、名相关、控制相关流水线冲突是指对于具体的流水线来说，由于相关的存在，使得指令流中的下一条指令不能在指定的时钟周期执行。流水线冲突有三种类型：结构冲突、数据冲突、控制冲突7/134▲ComputerArchitecture4.1指令级并行相关是程序固有的一种属性，它反映了程序中指令之间的相互依赖关系。具体的一次相关是否会导致实际冲突的发生以及该冲突会带来多长的停顿，则是流水线的属性。6.可以从两个方面来解决相关问题：保持相关，但避免发生冲突。指令调度通过代码变换，消除相关。7.程序顺序：由源程序确定的在完全串行方式下指令的执行顺序。必须保持程序顺序8/134▲ComputerArchitecture4.1指令级并行8.控制相关并不是一个必须严格保持的关键属性。9.对于正确地执行程序来说，必须保持的最关键的两个属性是：数据流和异常行为。保持异常行为是指：无论怎么改变指令的执行顺序，都不能改变程序中异常的发生情况。即原来程序中是怎么发生的，改变执行顺序后还是怎么发生。弱化为：指令执行顺序的改变不能导致程序中发生新的异常。如果我们能做到保持程序的数据相关和控制相关，就能保持程序的数据流和异常行为。9/134▲ComputerArchitecture4.1指令级并行举例说明DADDUR2，R3，R4BEQZR2，L1LWR1，0（R2）L1：数据流：指数据值从其产生者指令到其消费者指令的实际流动。分支指令使得数据流具有动态性，因为它使得给定指令的数据可以有多个来源。仅仅保持数据相关性是不够的，只有再加上保持控制顺序，才能够保持程序顺序。10/134▲ComputerArchitecture4.1指令级并行举例：DADDUR1，R2，R3BEQZR4，L1DSUBUR1，R5，R6L1：…ORR7，R1，R8有时，不遵守控制相关既不影响异常行为，也不改变数据流。可以大胆地进行指令调度，把失败分支中的指令调度到分支指令之前。11/134▲ComputerArchitecture4.1指令级并行举例：DADDUR1，R2，R3BEQZR12，SkipnextDSUBUR4，R5，R6DADDUR5，R4，R9Skipnext：ORR7，R8，R912/134▲ComputerArchitecture1.标量处理机普通标量流水线处理机：一条指令流水线，一个多功能操作部件，每个时钟周期平均执行指令的条数小于1。多操作部件标量处理机：一条指令流水线，多个独立的操作部件，指令级并行度小于1。提高处理机性能的两种方法：通过增加硬件资源来提高处理机性能通过各部分硬件的重叠工作来提高处理机性能13/134▲ComputerArchitecture超标量处理机典型结构：多条并行工作的指令流水线，多个独立的操作部件，指令级并行度（ILP）大于1。每个周期同时取多条指令、同时译码多条指令，同时执行多条指令，同时写回多个运算结果。多个取指令部件，多个指令译码部件和多个写结果部件。设置多个指令执行部件，有些指令执行部件采用流水线结构。目标是每个时钟周期平均执行多条指令，ILP的期望值大于1。14/134▲ComputerArchitecture单发射处理机的指令流水线时空图123456I1IFIDEXWR时钟周期I2IFIDEXWRI3IFIDEXWR指令多发射处理机的指令流水线时空图123456I1IFIDEXWR时钟周期I2IFIDEXWRI3IFIDEXWRI4IFIDEXWRI5IFIDEXWRI6IFIDEXWRI7IFIDEXWRI8IFIDEXWRI9IFIDEXWR指令超标量处理机采用的是空间并行性。15/134▲ComputerArchitecture超流水线处理机的两种定义：在一个周期内分时发射多条指令的处理机指令流水线的段数大于等于8的流水线处理机提高处理机性能的两种方法：通过增加硬件资源来提高处理机性能通过各部分硬件的重叠工作来提高处理机性能16/134▲ComputerArchitecture每个时钟周期分时发射3条指令的超流水线处理机的指令执行时空图123456I1IFIDEXWR时钟周期I2IFIDEXWRI3IFIDEXWRI4IFIDEXWRI5IFIDEXWRI6IFIDEXWRI7IFIDEXWRI8IFIDEXWR指令I9IFIDEXWR超流水线处理机采用的是时间并行性。17/134▲ComputerArchitecture1.超标量超流水线处理机一个时钟周期发射m次，每次发射n条指令。每个时钟周期发射3次，每次同时发射3条指令的超标量超流水线处理机的指令执行时空图123456I1IFIDEXWR时钟周期I2IFIDEXWRI3IFIDEXWRI4IFIDEXWRI5IFIDEXWRI6IFIDEXWRI7IFIDEXWRI8IFIDEXWRI9IFIDEXWRI10IFIDEXWRI11IFIDEXWRI12IFIDEXWR指令IF：取指令，ID：指令译码，EX：执行指令，WR：写回结果超标量超流水线处理机采用的是时间和空间并行性。18/134▲ComputerArchitecture静态调度依靠编译器对代码进行静态调度，以减少相关和冲突。它不是在程序执行的过程中、而是在编译期间进行代码调度和优化。通过把相关的指令拉开距离来减少可能产生的停顿。动态调度在程序的执行过程中，依靠专门硬件对代码进行调度，减少数据相关导致的停顿。4.2指令的动态调度19/134▲ComputerArchitecture4.2指令的动态调度能够处理一些在编译时情况不明的相关（比如涉及到存储器访问的相关），并简化了编译器；能够使本来是面向某一流水线优化编译的代码在其他的流水线（动态调度）上也能高效地执行。以硬件复杂性的显著增加为代价优点：20/134▲ComputerArchitecture4.2指令的动态调度到目前为止我们所使用流水线的最大的局限性:指令必须按序流出和执行考虑下面一段代码：DIV.DF4，F0，F2SUB.DF10，F4，F6ADD.DF12，F6，F14SUB.D指令与DIV.D指令关于F4相关，导致流水线停顿。ADD.D指令与流水线中的任何指令都没有关系，但也因此受阻。4.2.1动态调度的基本思想21/134▲ComputerArchitecture4.2指令的动态调度在前面的基本流水线中：ID检测结构冲突检测数据冲突一旦一条指令受阻，其后的指令都将停顿。解决办法：允许乱序执行22/134▲ComputerArchitecture4.2指令的动态调度1.为了允许乱序执行，我们将5段流水线的译码阶段再分为两个阶段：流出（Issue，IS）：指令译码，检查是否存在结构冲突。（in-orderissue)读操作数（ReadOperands，RO）：等待数据冲突消失，然后读操作数。(outoforderexecution)ISRO检测结构冲突检测数据冲突23/134▲ComputerArchitecture4.2指令的动态调度2.在前述5段流水线中，是不会发生WAR冲突和WAW冲突的。但乱序执行就使得它们可能发生了。例如，考虑下面的代码DIV.DF10,F0,F2SUB.DF10,F4,F6ADD.DF6,F8,F14存在反相关存在输出相关Tomasulo算法可以通过使用寄存器重命名来消除。24/134▲ComputerArchitecture4.2指令的动态调度3.动态调度的流水线支持多条指令同时处于执行当中。要求：具有多个功能部件、或者流水功能部件、或者兼而有之。我们假设具有多个功能部件。4.指令乱序完成带来的最大问题:异常处理比较复杂（精确异常处理、不精确异常处理）动态调度要保持正确的异常行为只有那些在程序严格按程序顺序执行时会发生的异常，才能真正发生。25/134▲ComputerArchitecture4.2指令的动态调度保持正确的异常行为：对于一条会产生异常的指令来说，只有当处理机确切地知道该指令将被执行后，才允许它产生异常。即使保持了正确的异常行为，动态调度处理机仍可能发生不精确异常。不精确异常：当执行指令i导致发生异常时，处理机的现场（状态）与严格按程序顺序执行时指令i的现场不同。发生不精确异常的原因：因为当发生异常（设为指令i）时：流水线可能已经执行完按程序顺序是位于指令i之后的指令；26/134▲ComputerArchitecture4.2指令的动态调度流水线可能还没完成按程序顺序是指令i之前的指令。不精确异常使得在异常处理后难以接着继续执行程序。精确异常：如果发生异常时，处理机的现场跟严格按程序顺序执行时指令i的现场相同。记分牌算法和Tomasulo算法是两种比较典型的动态调度算法。我们只介绍Tomasulo算法。27/134▲ComputerArchitecture4.2指令的动态调度1.核心思想记录和检测指令相关，操作数一旦就绪就立即执行，把发生RAW冲突的可能性减少到最小；通过寄存器换名来消除WAR冲突和WAW冲突。2.IBM360/91首先采用了Tomasulo算法。IBM360/91的设计目标是基于整个360系列的统一指令集和编译器来实现高性能，而不是设计和利用专用的编译器来提高性能。需要更多地依赖于硬件。4.2.2Tomasulo算法Tomasulo算法基本思想28/134▲ComputerArchitecture4.2指令的动态调度IBM360体系结构只有4个双精度浮点寄存器，限制了编译器调度的有效性。360/91的访存时间和浮点计算时间都很长。（也是Tomasulo算法要解决的问题）3.寄存器换名可以消除WAR冲突和WAW冲突。考虑以下代码：DIV.DF0，F2，F4ADD.DF6，F0，F8S.DF6，0（R1）SUB.DF8，F10，F14MUL.DF6，F10，F8输出相关（F6