第5章指令级并行及其开发硬件方法

1/137▲第5章指令级并行及其开发——硬件方法2/137▲5.1指令级并行的概念5.2相关与指令级并行5.3指令的动态调度5.4动态分支预测技术5.5多指令流出技术3/137▲指令级并行：指指令之间存在的一种并行性，利用它，计算机可以并行执行两条或两条以上的指令。（ILP：Instruction-LevelParallelism）开发ILP的途径有两种资源重复，重复设置多个处理部件，让它们同时执行相邻或相近的多条指令；采用流水线技术，使指令重叠并行执行。本章研究：如何利用各种技术来开发更多的指令级并行（硬件的方法）4/137▲1.开发ILP的方法可以分为两大类主要基于硬件的动态开发方法基于软件的静态开发方法2.流水线处理机的实际CPI理想流水线的CPI加上各类停顿的时钟周期数：CPI流水线=CPI理想+停顿结构冲突+停顿数据冲突+停顿控制冲突理想CPI是衡量流水线最高性能的一个指标。IPC：InstructionsPerCycle（每个时钟周期完成的指令条数）5.1指令级并行的概念5/137▲5.1指令级并行的概念3.基本程序块基本程序块：一串连续的代码除了入口和出口以外，没有其他的分支指令和转入点。程序平均每4～7条指令就会有一个分支。4.循环级并行：使一个循环中的不同循环体并行执行。开发循环的不同叠代之间存在的并行性最常见、最基本是指令级并行研究的重点之一6/137▲5.1指令级并行的概念例如，考虑下述语句：for（i=1；i=500；i=i＋1）a[i]=a[i]＋s；每一次循环都可以与其它的循环重叠并行执行；在每一次循环的内部，却没有任何的并行性。5.最基本的开发循环级并行的技术循环展开（loopunrolling）技术采用向量指令和向量数据表示7/137▲1.相关与流水线冲突相关有三种类型：数据相关、名相关、控制相关流水线冲突是指对于具体的流水线来说，由于相关的存在，使得指令流中的下一条指令不能在指定的时钟周期执行。流水线冲突有三种类型：结构冲突、数据冲突、控制冲突5.2相关与指令级并行8/137▲5.2相关与指令级并行相关是程序固有的一种属性，它反映了程序中指令之间的相互依赖关系。具体的一次相关是否会导致实际冲突的发生以及该冲突会带来多长的停顿，则是流水线的属性。2.可以从两个方面来解决相关问题：保持相关，但避免发生冲突。指令调度通过代码变换，消除相关。3.程序顺序：由原来程序确定的在完全串行方式下指令的执行顺序。只有在可能会导致错误的情况下，才保持程序顺序。9/137▲5.2相关与指令级并行4.控制相关并不是一个必须严格保持的关键属性。5.对于正确地执行程序来说，必须保持的最关键的两个属性是：数据流和异常行为。保持异常行为是指：无论怎么改变指令的执行顺序，都不能改变程序中异常的发生情况。即原来程序中是怎么发生的，改变执行顺序后还是怎么发生。弱化为：指令执行顺序的改变不能导致程序中发生新的异常。数据流：指数据值从其产生者指令到其消费者指令的实际流动。10/137▲5.2相关与指令级并行分支指令使得数据流具有动态性，因为一条指令有可能数据相关于多条先前的指令。分支指令的执行结果决定了哪条指令真正是所需数据的产生者。有时，不遵守控制相关既不影响异常行为，也不改变数据流。可以大胆地进行指令调度，把失败分支中的指令调度到分支指令之前。11/137▲5.2相关与指令级并行举例：DADDUR1，R2，R3BEQZR12，SkipnextDSUBUR4，R5，R6DADDUR5，R4，R9Skipnext：ORR7，R8，R912/137▲静态调度依靠编译器对代码进行静态调度，以减少相关和冲突。它不是在程序执行的过程中、而是在编译期间进行代码调度和优化。通过把相关的指令拉开距离来减少可能产生的停顿。动态调度在程序的执行过程中，依靠专门硬件对代码进行调度，减少数据相关导致的停顿。5.3指令的动态调度13/137▲5.3指令的动态调度能够处理一些在编译时情况不明的相关（比如涉及到存储器访问的相关），并简化了编译器；能够使本来是面向某一流水线优化编译的代码在其它的流水线（动态调度）上也能高效地执行。以硬件复杂性的显著增加为代价优点：14/137▲5.3指令的动态调度1.到目前为止我们所使用流水线的最大的局限性:指令是按序流出和按序执行的考虑下面一段代码：DIV.DF4，F0，F2ADD.DF10，F4，F6SUB.DF12，F6，F14ADD.D指令与DIV.D指令关于F4相关，导致流水线停顿。SUB.D指令与流水线中的任何指令都没有关系，但也因此受阻。5.3.1动态调度的基本思想15/137▲5.3指令的动态调度在前面的基本流水线中：ID检测结构冲突检测数据冲突一旦一条指令受阻，其后的指令都将停顿。16/137▲5.3指令的动态调度为了使上述指令序列中的SUB.D指令能继续执行下去，必须把指令流出的工作拆分为两步：检测结构冲突等待数据冲突消失只要检测到没有结构冲突，就可以让指令流出。并且流出后的指令一旦其操作数就绪就可以立即执行。2.乱序执行指令的执行顺序与程序顺序不相同指令的完成也是乱序完成的即指令的完成顺序与程序顺序不相同。17/137▲5.3指令的动态调度3.为了支持乱序执行，我们将5段流水线的译码阶段再分为两个阶段：流出（Issue，IS）：指令译码，检查是否存在结构冲突。（in-orderissue)读操作数（ReadOperands，RO）：等待数据冲突消失，然后读操作数。(outoforderexecution)ISRO检测结构冲突检测数据冲突18/137▲5.3指令的动态调度4.在前述5段流水线中，是不会发生WAR冲突和WAW冲突的。但乱序执行就使得它们可能发生了。例如，考虑下面的代码DIV.DF10,F0,F2ADD.DF10,F4,F6SUB.DF6,F8,F14存在反相关存在输出相关可以通过使用寄存器重命名来消除。19/137▲5.3指令的动态调度5.动态调度的流水线支持多条指令同时处于执行当中。要求：具有多个功能部件、或者功能部件流水化、或者兼而有之。我们假设具有多个功能部件。6.指令乱序完成带来的最大问题:异常处理比较复杂（精确异常处理、不精确异常处理）动态调度的处理机要保持正确的异常行为对于一条会产生异常的指令来说，只有当处理机确切地知道该指令将被执行时，才允许它产生异常。20/137▲5.3指令的动态调度即使保持了正确的异常行为，动态调度处理机仍可能发生不精确异常。不精确异常：当执行指令i导致发生异常时，处理机的现场（状态）与严格按程序顺序执行时指令i的现场不同。发生不精确异常的原因：因为当发生异常（设为指令i）时：流水线可能已经执行完按程序顺序是位于指令i之后的指令；流水线可能还没完成按程序顺序是指令i之前的指令。21/137▲5.3指令的动态调度不精确异常使得在异常处理后难以接着继续执行程序。精确异常：如果发生异常时，处理机的现场跟严格按程序顺序执行时指令i的现场相同。记分牌算法和Tomasulo算法是两种比较典型的动态调度算法。22/137▲5.3指令的动态调度1.基本思想CDC6600计算机最早采用此功能该机器用一个称为记分牌的硬件实现了对指令的动态调度。该硬件中维护着3张表，分别用于记录指令的执行状态、功能部件状态、寄存器状态以及数据相关关系等。它把前述5段流水线中的译码段ID分解成了两个段：流出和读操作数，以避免当某条指令在ID段被停顿时挡住后面无关指令的流动。5.3.2记分牌动态调度算法23/137▲5.3指令的动态调度记分牌的目标：在没有结构冲突时，尽可能早地执行没有数据冲突的指令，实现每个时钟周期执行一条指令。要发挥指令乱序执行的好处，必须有多条指令同时处于执行阶段。CDC6600具有16个独立的功能部件4个浮点部件5个访存部件7个整数操作部件假设所考虑的处理器有2个乘法器、1个加法器、1个除法部件和1个整数部件。24/137▲5.3指令的动态调度整数部件用来处理所有的存储器访问、分支处理和整数操作。采用了记分牌的MIPS处理器的基本结构每条指令都要经过记分牌。记分牌负责相关检测并控制指令的流出和执行。每条指令的执行过程分为4段（主要考虑浮点操作）流出如果当前流出指令所需的功能部件空闲，并且所有其他正在执行的指令的目的寄存器与该指令的不同，记分牌就向功能部件流出该指令，并修改记分牌内部的记录表。解决了WAW冲突25/137▲5.3指令的动态调度26/137▲5.3指令的动态调度读操作数记分牌监测源操作数的可用性，如果数据可用，它就通知功能部件从寄存器中读出源操作数并开始执行。动态地解决了RAW冲突，并导致指令可能乱序开始执行。执行取到操作数后，功能部件开始执行。当产生出结果后，就通知记分牌它已经完成执行。在浮点流水线中，这一段可能要占用多个时钟周期。写结果27/137▲5.3指令的动态调度记分牌一旦知道执行部件完成了执行，就检测是否存在WAR冲突。如果不存在，或者原有的WAR冲突已消失，记分牌就通知功能部件把结果写入目的寄存器，并释放该指令使用的所有资源。如果检测到WAR冲突，就不允许该指令将结果写到目的寄存器。这发生在以下情况：前面的某条指令（按顺序流出）还没有读取操作数；而且：其中某个源操作数寄存器与本指令的目的寄存器相同。在这种情况下，记分牌必须等待，直到该冲突消失。28/137▲5.3指令的动态调度记分牌中记录的信息由3部分构成指令状态表：记录正在执行的各条指令已经进入到了哪一段。功能部件状态表：记录各个功能部件的状态。每个功能部件有一项，每一项由以下9个字段组成：Busy：忙标志，指出功能部件是否忙。初值为“no”；Op：该功能部件正在执行或将要执行的操作；Fi：目的寄存器编号；Fj，Fk：源寄存器编号；Qj，Qk：指出向源寄存器Fj、Fk写数据的功能部件；29/137▲5.3指令的动态调度Rj，Rk：标志位，为“yes”表示Fj，Fk中的操作数就绪且还未被取走。否则就被置为“no”。结果寄存器状态表Result：每个寄存器在该表中有一项，用于指出哪个功能部件（编号）将把结果写入该寄存器。如果当前正在运行的指令都不以它为目的寄存器，则其相应项置为“no”。Result各项的初值为“no”（全0）。2.举例MIPS记分牌所要维护的数据结构下列代码运行过程中记分牌保存的信息30/137▲5.3指令的动态调度L.DF6,34(R2)L.DF2,45(R3)MULT.DF0,F2,F4SUB.DF8,F6,F2DIV.DF10,F0,F6ADD.DF6,F8,F2MIPS记分牌中的信息32/137▲5.3指令的动态调度例5.1假设浮点流水线中各部件的延迟如下：加法需2个时钟周期乘法需10个时钟周期除法需40个时钟周期代码段和记分牌信息的起始点状态如上图。分别给出MULT.D和DIV.D准备写结果之前的记分牌状态。解图中的代码段存在以下相关性：（1）先写后读相关：第二条L.D指令到MULT.D和SUB.D之间，MULT.D到DIV.D之间，SUB.D到ADD.D之间；（2）先读后写相关：DIV.D和ADD.D之间，SUB.D和ADD.D之间；（3）结构相关：ADD.D和SUB.D指令关于浮点加法部件。程序段执行到MULT.D将要写结果时记分牌的状态程序段执行到DIV.D将要写结果时记分牌的状态35/137▲5.3指令的动态调度3.具体算法约定：FU：表示当前指令所要用的功能部件；D：目的寄存器的名称；S1、S2：源操作数寄存器的名称；Op：要进行的操作；Fj[FU]：功能部件FU的Fj字段（其他字段依此类推）；Result[D]：结果寄存器状态表中与寄存器D相对应的内容。其中存放的是将把结果写入寄存器D的功能部件的名称。36/137▲5.3指令的