计算机系统结构课件第4章

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