计算机系统结构第四章.ppt

《计算机系统结构第四章.ppt》由会员分享，可在线阅读，更多相关《计算机系统结构第四章.ppt（63页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第四章第四章 指令级并行指令级并行4.1指令级并行的概念指令级并行的概念4.2指令的动态调度指令的动态调度4.3动态分支预测技术动态分支预测技术4.4多指令流出技术多指令流出技术4.5循环展开和指令调度循环展开和指令调度4.1 指令级并行的概念指令级并行的概念n几乎所有的处理机都利用流水线来使指令重几乎所有的处理机都利用流水线来使指令重叠并行执行，以达到提高性能的目的。这种叠并行执行，以达到提高性能的目的。这种指令之间存在的潜在并行性称为指令之间存在的潜在并行性称为指令级并行。指令级并行。（ILPILP：Instruction-Level ParallelismInstruction-Leve

2、l Parallelism）n本章研究：本章研究：如何通过各种可能的技术，获得如何通过各种可能的技术，获得更多的指令级并行性。更多的指令级并行性。硬件软件技术硬件软件技术 必须要硬件技术和软件技术互相配合，才必须要硬件技术和软件技术互相配合，才能够最大限度地挖掘出程序中存在的指令能够最大限度地挖掘出程序中存在的指令级并行。级并行。4.1 指令级并行的概念指令级并行的概念n流水线处理机的实际流水线处理机的实际CPICPI理想流水线的理想流水线的CPICPI加上各类停顿的时钟周期加上各类停顿的时钟周期数：数：CPICPI流水线流水线=CPI=CPI理想理想+停顿停顿结构冲突结构冲突+停顿停顿数据冲

3、突数据冲突 +停顿停顿控制冲突控制冲突理想理想CPICPI是衡量流水线最高性能的一个指标。是衡量流水线最高性能的一个指标。通过减少右边各项，就能减小总的通过减少右边各项，就能减小总的CPICPI，从，从而提高而提高IPC。IPCIPC：Instructions Per CycleInstructions Per Cycle （每个时钟周期完成的指令条数）（每个时钟周期完成的指令条数）4.1 指令级并行的概念指令级并行的概念1.循环级并行：循环级并行：n使一个循环中的不同循环体并行执行。使一个循环中的不同循环体并行执行。n开发循环体中存在的并行性是指令级并行研开发循环体中存在的并行性是指令级并行

4、研究的重点之一究的重点之一n最基本的开发循环级并行的技术最基本的开发循环级并行的技术循环展开（循环展开（loop unrollingloop unrolling）技术）技术采用向量指令和向量数据表示采用向量指令和向量数据表示2.相关与流水线冲突相关与流水线冲突n静态指令调度静态指令调度n动态指令调度动态指令调度4.1 指令级并行的概念指令级并行的概念3.对于正确地执行程序来说，必须保持的最关键对于正确地执行程序来说，必须保持的最关键的两个属性是：的两个属性是：数据流数据流和和异常行为异常行为。n数据流数据流：指数据值从其产生者指令到其消：指数据值从其产生者指令到其消费者指令的实际流动。费者指令

5、的实际流动。n保持异常行为保持异常行为是指：无论怎么改变指令的是指：无论怎么改变指令的执行顺序，都不能改变程序中异常的发生执行顺序，都不能改变程序中异常的发生情况。情况。即原来程序中是怎么发生的，改变执行即原来程序中是怎么发生的，改变执行顺序后还是怎么发生。顺序后还是怎么发生。弱化为：指令执行顺序的改变不能导致弱化为：指令执行顺序的改变不能导致程序中发生新的异常。程序中发生新的异常。4.2 指令的动态调度指令的动态调度内容回顾：内容回顾：1.相关相关2.相关是指两条指令之间存在某种依赖关系，是程序相关是指两条指令之间存在某种依赖关系，是程序固有的一种属性。固有的一种属性。3.相关包括：名相关，

6、数据相关，控制相关。相关包括：名相关，数据相关，控制相关。2.冲突（冲突（HAZARDS，也称为冒险），也称为冒险）3.冲突是指由于相关的存在，使得指令流中的下一条冲突是指由于相关的存在，使得指令流中的下一条指令不能在指定的时钟周期执行。指令不能在指定的时钟周期执行。4.4.具体一次相关是否会导致实际冲突的发生以及该冲具体一次相关是否会导致实际冲突的发生以及该冲突会带来多长的停顿，则是流水线的属性。突会带来多长的停顿，则是流水线的属性。5.流水线冲突包括：流水线冲突包括：结构冲突，数据冲突，控制冲突结构冲突，数据冲突，控制冲突。4.2 指令的动态调度指令的动态调度3.冲突的解决冲突的解决1 1

7、）结构冲突：）结构冲突：停顿（流水线气泡）停顿（流水线气泡）2 2）数据冲突：）数据冲突：定向传送技术定向传送技术定向传送与停顿相结合定向传送与停顿相结合指令调度（依靠编译器）：指令调度（依靠编译器）：前提：在乱序流动的流水线中。前提：在乱序流动的流水线中。不足：可能会产生新的不足：可能会产生新的WAR或或WAW冲突。冲突。3 3）控制冲突）控制冲突：预测分支失败预测分支失败预测分支成功预测分支成功延迟转移技术延迟转移技术都是通过编译器来实现都是通过编译器来实现静态调度静态调度4.2 指令的动态调度指令的动态调度n静态调度静态调度依靠编译器对代码进行静态调度，以减依靠编译器对代码进行静态调度，

8、以减少相关和冲突。少相关和冲突。它不是在程序执行的过程中，而是在编它不是在程序执行的过程中，而是在编译期间进行代码调度和优化。译期间进行代码调度和优化。通过把相关的指令拉开距离来减少可能通过把相关的指令拉开距离来减少可能产生的停顿。产生的停顿。n动态调度动态调度在程序的执行过程中，依靠专门硬件对在程序的执行过程中，依靠专门硬件对代码进行调度，减少数据相关导致的停代码进行调度，减少数据相关导致的停顿。顿。4.2 指令的动态调度指令的动态调度一、动态调度的基本思想一、动态调度的基本思想考虑下面一段代码：考虑下面一段代码：DIV.DDIV.DF4F4，F0F0，F2F2SUB.DSUB.DF10F1

9、0，F4F4，F6 F6 ADD.DADD.DF12F12，F6F6，F14F14SUB.DSUB.D指令与指令与DIV.DDIV.D指令关于指令关于F4F4相关，导致流相关，导致流水线停顿。水线停顿。ADD.DADD.D指令与流水线中的任何指令都没有关系，指令与流水线中的任何指令都没有关系，但也因此受阻但也因此受阻。4.2 指令的动态调度指令的动态调度n在前面的基本流水线中：在前面的基本流水线中：ID检测结构冲突检测数据冲突 一旦一条指令受阻，其后的指令都将停顿。一旦一条指令受阻，其后的指令都将停顿。解决办法：解决办法：允许乱序执行允许乱序执行4.2 指令的动态调度指令的动态调度n为了允许乱

10、序执行，我们将为了允许乱序执行，我们将5 5段流水线的译码段流水线的译码阶段再分为两个阶段：阶段再分为两个阶段：流出流出（IssueIssue，ISIS）：指令译码，检查是否）：指令译码，检查是否存在结构冲突。存在结构冲突。（in-order issuein-order issue)读操作数读操作数（Read OperandsRead Operands，RORO）：等待数）：等待数据冲突消失，然后读操作数。据冲突消失，然后读操作数。(out of order executionout of order execution)ISRO检测结构冲突检测数据冲突4.2 指令的动态调度指令的动态调度n有

11、的代码在采用乱序执行后可能会发生有的代码在采用乱序执行后可能会发生WARWAR冲突冲突和和WAWWAW冲突。冲突。n例如，考虑下面的代码例如，考虑下面的代码 DIV.D DIV.D F4F4,F0,F2,F0,F2 SUB.D SUB.D F10F10,F4F4,F6F6 ADD.D ADD.D F6F6,F8,F14 F8,F14 DIV.D DIV.D F10F10,F1,F3,F1,F3存在反相关存在反相关存在输出相关存在输出相关存在数据相关存在数据相关SUB.D SUB.D F10F10,F4F4,F6F6WARWAR冲突冲突WAWWAW冲突冲突TomasuloTomasulo算法算法

12、可以通过使用寄存器重命名来消除。可以通过使用寄存器重命名来消除。4.2 指令的动态调度指令的动态调度二、二、Tomasulo算法算法1.1.基本思想基本思想n核心思想：核心思想：记录和检测指令相关，操作数一旦就绪就记录和检测指令相关，操作数一旦就绪就立即执行，把发生立即执行，把发生RAWRAW冲突冲突的可能性减少到的可能性减少到最小；最小；通过寄存器换名来消除通过寄存器换名来消除WARWAR冲突冲突和和WAWWAW冲突冲突。4.2 指令的动态调度指令的动态调度nIBM 360/91IBM 360/91首先采用了首先采用了TomasuloTomasulo算法。算法。IBM 360/91IBM 3

13、60/91的设计目标是基于整个的设计目标是基于整个360360系列系列的统一指令集和编译器来实现高性能，而的统一指令集和编译器来实现高性能，而不是设计和利用专用的编译器来提高性能。不是设计和利用专用的编译器来提高性能。需要更多地依赖于硬件。需要更多地依赖于硬件。IBM 360IBM 360体系结构只有体系结构只有4 4个双精度浮点寄存个双精度浮点寄存器，限制了编译器调度的有效性。器，限制了编译器调度的有效性。360/91360/91的访存时间和浮点计算时间都很长。的访存时间和浮点计算时间都很长。（也是（也是TomasuloTomasulo算法要解决的问题）算法要解决的问题）4.2 指令的动态调

14、度指令的动态调度n寄存器换名寄存器换名可以消除可以消除WARWAR冲突和冲突和WAWWAW冲突。冲突。考虑之前的代码：考虑之前的代码：DIV.D DIV.D F4F4,F0,F2,F0,F2 SUB.D SUB.D F10F10,F4F4,F6F6 ADD.D ADD.D F6F6,F8,F14 F8,F14 DIV.D DIV.D F10F10,F1,F3,F1,F3存在反相关存在反相关F6F6存在输出相关存在输出相关F10F10存在数据相关存在数据相关F4F4消除名相关：消除名相关：引入两个临时寄存器引入两个临时寄存器S和和T，分别，分别将第一个将第一个F10换成换成S，将后一个，将后一个

15、F6换成换成T。S,T,n基于基于TomasuloTomasulo算法的算法的MIPSMIPS处理器浮点部件的处理器浮点部件的基本结构基本结构1 1）保留站（保留站（reservation stationreservation station）每个保留站中保存一条已经流出并等待到本每个保留站中保存一条已经流出并等待到本功能部件执行的指令（相关信息）。功能部件执行的指令（相关信息）。包括：包括：操作码、操作数以及用于检测和解决操作码、操作数以及用于检测和解决冲突的信息。冲突的信息。在一条指令流出到保留站的时候，如果该在一条指令流出到保留站的时候，如果该指令的源操作数已经在寄存器中就绪，则将指令的

16、源操作数已经在寄存器中就绪，则将之取到该保留站中。之取到该保留站中。如果操作数还没有计算出来，则在该保留如果操作数还没有计算出来，则在该保留站中记录将产生这个操作数的保留站的标识。站中记录将产生这个操作数的保留站的标识。浮点加法器有浮点加法器有3 3个保留站：个保留站：ADD1ADD1，ADD2ADD2，ADD3ADD3浮点乘法器有浮点乘法器有两两个保留站：个保留站：MULT1MULT1，MULT2MULT2 每个保留站都有一个标识字段，唯一地标每个保留站都有一个标识字段，唯一地标识了该保留站。识了该保留站。2 2）公共数据总线公共数据总线CDB CDB 所有功能部件的计算结果都是送到所有功能

17、部件的计算结果都是送到CDBCDB上，由它把这些上，由它把这些结果直接送到（播送到）各个需要该结果的地方。结果直接送到（播送到）各个需要该结果的地方。3 3）loadload缓冲器和缓冲器和storestore缓冲器缓冲器 存放读存放读/写存储器的数据或地址写存储器的数据或地址 4 4）浮点寄存器）浮点寄存器FPFP共有共有1616个浮点寄存器：个浮点寄存器：F0F0，F2F2，F4F4，F30F30。它们通过一对总线连接到功能部件，并通过它们通过一对总线连接到功能部件，并通过CDBCDB连连接到接到storestore缓冲器缓冲器。5）指令队列）指令队列指令部件送来的指令放入指令队列指令部件

18、送来的指令放入指令队列指令队列中的指令按先进先出的顺序流出指令队列中的指令按先进先出的顺序流出6）运算部件）运算部件浮点加法器完成加法和减法操作浮点加法器完成加法和减法操作浮点乘法器完成乘法和除法操作浮点乘法器完成乘法和除法操作4.2 指令的动态调度指令的动态调度n在在TomasuloTomasulo算法中，寄存器换名是通过保留算法中，寄存器换名是通过保留站和流出逻辑来共同完成的。站和流出逻辑来共同完成的。当指令流出时，如果其操作数还没有计算当指令流出时，如果其操作数还没有计算出来，则将该指令中相应的寄存器号出来，则将该指令中相应的寄存器号换名换名为将产生这个操作数的保留站的标识为将产生这个操

19、作数的保留站的标识。指令流出到保留站后，其操作数寄存器号指令流出到保留站后，其操作数寄存器号或者换成了数据本身（如果该数据已经就或者换成了数据本身（如果该数据已经就绪），或者换成了保留站的标识，绪），或者换成了保留站的标识，不再与不再与寄存器有关系。寄存器有关系。MUL MUL FOFO,F2,F4,F2,F4ADD F2,ADD F2,F0F0,F6F6SUB SUB F6F6,F8,F4,F8,F4F8F8F6F6F4F4F2F2C CB BA AADD1ADD1MUL1MUL1MUL2MUL2ADD2ADD2ADD3ADD3ADD F2,ADD F2,F0F0,F6,F6MUL MUL

20、FOFO,F2,F4,F2,F4QiF0F0D DSUB SUB F6,F8,F4F6,F8,F4MUL MUL FOFO,F2,F4,F2,F4ADD F2,ADD F2,F0F0,F6F6SUB SUB F6F6,F8,F4,F8,F4MUL A,BMUL A,BADD F2,F0,F6ADD F2,F0,F6F8F8F6F6F4F4F2F2D DC CB BADD1ADD1MUL1MUL1MUL2MUL2ADD2ADD2ADD3ADD3QiSUB SUB F6,F8,F4F6,F8,F4F0F0A AMUL1MUL1MUL MUL FOFO,F2,F4,F2,F4ADD F2,ADD F

21、2,F0F0,F6F6SUB SUB F6F6,F8,F4,F8,F4MUL A,BMUL A,BADD MUL1,CADD MUL1,CF8F8F6F6F4F4F2F2D DC CB BADD1ADD1MUL1MUL1MUL2MUL2ADD2ADD2ADD3ADD3MUL1MUL1ADD1ADD1QiF0F0A ASUB D,BSUB D,BADD2ADD2SUB SUB F6,F8,F4F6,F8,F4MUL MUL FOFO,F2,F4,F2,F4ADD F2,ADD F2,F0F0,F6F6SUB SUB F6F6,F8,F4,F8,F4MUL A,BMUL A,BADD MUL1,C

22、ADD MUL1,CF8F8F6F6F4F4F2F2D DC CB BADD1ADD1MUL1MUL1MUL2MUL2ADD2ADD2ADD3ADD3MUL1MUL1ADD1ADD1QiF0F0A ASUB D,BSUB D,BADD2ADD2E EADD E,CADD E,C4.2 指令的动态调度指令的动态调度nTomasuloTomasulo算法具有以下算法具有以下两个特点：两个特点：1 1）冲突检测和指令执行控制是分布的。）冲突检测和指令执行控制是分布的。每个功能部件的保留站中的信息决定了每个功能部件的保留站中的信息决定了什么时候指令可以在该功能部件开始执什么时候指令可以在该功能部件开始

23、执行行。2 2）计算结果通过计算结果通过CDBCDB直接从产生它的保留站直接从产生它的保留站传送到所有需要它的功能部件，而不用经传送到所有需要它的功能部件，而不用经过寄存器。过寄存器。4.2 指令的动态调度指令的动态调度2.2.指令执行的步骤指令执行的步骤使用使用TomasuloTomasulo算法的流水线需算法的流水线需3 3段：段：1 1）流出：从指令队列的头部取一条指令。流出：从指令队列的头部取一条指令。如果没有空闲的保留站，指令就不能流出。如果没有空闲的保留站，指令就不能流出。（发生了结构冲突）（发生了结构冲突）如果该指令的操作所要求的保留站有空闲的，如果该指令的操作所要求的保留站有空

24、闲的，就把该指令送到该保留站。就把该指令送到该保留站。（寄存器换名和对操作数进行缓冲，消除（寄存器换名和对操作数进行缓冲，消除WARWAR冲突）冲突）完成对目标寄存器的预约工作完成对目标寄存器的预约工作（消除了（消除了WAWWAW冲突）冲突）4.2 指令的动态调度指令的动态调度2）执行）执行 当两个操作数都就绪后，本保留站就当两个操作数都就绪后，本保留站就用相应的功能部件开始执行指令规定用相应的功能部件开始执行指令规定的操作。的操作。（消除了（消除了R RAWAW冲突）冲突）3）写结果）写结果 功能部件计算完毕后，就将计算结果功能部件计算完毕后，就将计算结果放到放到CDBCDB上，所有等待该计

25、算结果的上，所有等待该计算结果的寄存器和保留站（包括寄存器和保留站（包括storestore缓冲器）缓冲器）都同时从都同时从CDBCDB上获得所需要的数据。上获得所需要的数据。3.Tomasulo3.Tomasulo算法举例算法举例 每个保留站有以下每个保留站有以下6 6个字段：（个字段：（P121 P121 图图4.24.2）BusyBusy：为为“yesyes”表示本保留站或缓冲单元表示本保留站或缓冲单元“忙忙”。OpOp：要对源操作数进行的操作。要对源操作数进行的操作。VjVj，VkVk：源操作数的值。源操作数的值。QjQj，QkQk：将产生源操作数的保留站号。将产生源操作数的保留站号。

26、等于等于0 0表示操作数已经就绪且在表示操作数已经就绪且在VjVj或或VkVk中，或者中，或者不需要操作数。不需要操作数。对于每一个操作数来说，对于每一个操作数来说，V V或或Q Q字段只有一个有效。字段只有一个有效。A A：仅仅loadload和和storestore缓冲器有该字段。开始是存放指缓冲器有该字段。开始是存放指令中的立即数字段，地址计算后存放有效地址。令中的立即数字段，地址计算后存放有效地址。QiQi：寄存器状态表。寄存器状态表。每个寄存器在该表中有对应的一项，用于存放将每个寄存器在该表中有对应的一项，用于存放将把结果写入该寄存器的保留站的站号。把结果写入该寄存器的保留站的站号。

27、为为0 0表示当前没有正在执行的指令要写入该寄存表示当前没有正在执行的指令要写入该寄存器，也即该寄存器中的内容就绪。器，也即该寄存器中的内容就绪。4.2 指令的动态调度指令的动态调度 对于下述指令序列，给出当第一条指令完成对于下述指令序列，给出当第一条指令完成并写入结果时，并写入结果时，TomasuloTomasulo算法所用的各信息算法所用的各信息表中的内容。表中的内容。L.D L.DF6,34F6,34（R2R2）L.D L.DF2,45F2,45（R3R3）MUL.D MUL.DF0,F2,F4F0,F2,F4 SUB.D SUB.DF8,F2,F6F8,F2,F6 DIV.D DIV.

28、DF10,F0,F6F10,F0,F6 ADD.D ADD.DF6,F8,F2F6,F8,F24.2 指令的动态调度指令的动态调度 当采用当采用Tomasulo算法时，在上述给定的时刻，算法时，在上述给定的时刻，load缓冲器、保留站以及寄存器状态表中的缓冲器、保留站以及寄存器状态表中的内容内容。指指 令令 指令状态表指令状态表 流出流出 执行执行 写结果写结果 L.D F6,34(R2)L.D F2,45(R3)MUL.DF0,F2,F4 SUB.D F8,F6,F2 DIV.DF10,F0,F6 ADD.D F6,F8,F2 名称名称 保留站保留站 Load1Load1Load2Load2

29、Add1Add1Add2Add2Add3Add3Mult1Mult1Mult2Mult2BusyBusy no no yes yes yes yes yes yes no no yes yes yes yesOpOp LD LD SUB SUB ADD ADD MUL MUL DIV DIVVjVj VkVk Mem34+RegsR2 Mem34+RegsR2 RegF4 RegF4 Mem34+RegsR2 Mem34+RegsR2QjQj Load2Load2 Add1 Add1 Load2 Load2 Mult1 Mult1QkQk Load2Load2A A 45+RegsR345+R

30、egsR3 寄存器状态表寄存器状态表 F0 F2 F4 F6 F8 F10 F30F0 F2 F4 F6 F8 F10 F30 Qi Qi Mult1Mult1 Load2 Add2 Load2 Add2 Add1 Mult2Add1 Mult2 L.DF6,34（R2）L.DF2,45（R3）MUL.D F0,F2,F4SUB.D F8,F2,F6DIV.D F10,F0,F6ADD.D F6,F8,F24.3 动态分支预测技术动态分支预测技术n动态分支预测：动态分支预测：在程序运行时，根据分支指令过去的表现来在程序运行时，根据分支指令过去的表现来预测其将来的行为。预测其将来的行为。如果分支

31、行为发生了变化，预测结果也跟如果分支行为发生了变化，预测结果也跟着改变。着改变。有更好的预测准确度和适应性。有更好的预测准确度和适应性。n需要解决的关键问题需要解决的关键问题 如何记录分支的历史信息；如何记录分支的历史信息；如何根据这些信息来预测分支的去向（甚如何根据这些信息来预测分支的去向（甚至取到指令）。至取到指令）。4.3 动态分支预测技术动态分支预测技术一一.采用分支历史表采用分支历史表BHTBHT（Branch History Branch History TableTable）n又称为分支预测缓冲器（又称为分支预测缓冲器（Branch Branch Prediciton Buffe

32、rPrediciton Buffer）n最简单的动态分支预测方法。最简单的动态分支预测方法。n用用BHTBHT来记录分支指令最近一次或几次的执来记录分支指令最近一次或几次的执行情况（成功或不成功），并据此进行预测。行情况（成功或不成功），并据此进行预测。1.1.只有只有1 1个预测位的分支预测缓冲个预测位的分支预测缓冲 记录分支指令最近一次的历史，记录分支指令最近一次的历史，BHTBHT中只中只需要需要1 1位二进制位。（最简单）位二进制位。（最简单）4.3 动态分支预测技术动态分支预测技术2.2.采用两位二进制位来记录历史采用两位二进制位来记录历史提高预测的准确度提高预测的准确度研究结果表明

33、：研究结果表明：两位分支预测的性能与两位分支预测的性能与n n位位（n2n2）分支预测的性能差不多。）分支预测的性能差不多。1）两位分支预测的状态转换如下所示：）两位分支预测的状态转换如下所示：4.3 动态分支预测技术动态分支预测技术2）操作步骤：）操作步骤：分支预测。分支预测。当分支指令到达译码段当分支指令到达译码段（IDID）时，时，根据从根据从BHTBHT读出的信息进行分支预测读出的信息进行分支预测 。若预测正确，就继续处理后续的指若预测正确，就继续处理后续的指令，流水线没有断流。否则，就要令，流水线没有断流。否则，就要作废已经预取和分析的指令，恢复作废已经预取和分析的指令，恢复现场，并

34、从另一条分支路径重新取现场，并从另一条分支路径重新取指令。指令。状态修改。状态修改。4.3 动态分支预测技术动态分支预测技术3.BHT方法只在以下情况下才有用：方法只在以下情况下才有用：判定分支是否成功所需的时间大于确定分支目标地判定分支是否成功所需的时间大于确定分支目标地址所需的时间。址所需的时间。前述前述5 5段经典流水线：由于判定分支是否成功和计段经典流水线：由于判定分支是否成功和计算分支目标地址都是在算分支目标地址都是在IDID段完成，所以段完成，所以BHTBHT方法不方法不会给该流水线带来好处。会给该流水线带来好处。4.4.研究结果表明：研究结果表明：对于对于SPEC89SPEC89

35、测试程序来说，具测试程序来说，具有大小为有大小为4K4K的的BHTBHT的预测准确率为的预测准确率为82%82%99%99%。一般来说，采用一般来说，采用4K4K的的BHTBHT就可以了。就可以了。5.BHTBHT可以跟分支指令一起存放在指令可以跟分支指令一起存放在指令CacheCache中，中，也可以用一个专门的硬件来实现。也可以用一个专门的硬件来实现。4.3 动态分支预测技术动态分支预测技术二二.采用采用分支目标缓冲器分支目标缓冲器BTBn目标：目标：将分支的开销降为将分支的开销降为 0 0n方法：方法：分支目标缓冲分支目标缓冲将分支成功的分支指令的地址和它的分支将分支成功的分支指令的地址

36、和它的分支目标地址都放到一个缓冲区中保存起来，目标地址都放到一个缓冲区中保存起来，缓冲区以分支指令的地址作为标识。缓冲区以分支指令的地址作为标识。这个缓冲区就是这个缓冲区就是分支目标缓冲器分支目标缓冲器（Branch-Target BufferBranch-Target Buffer，简记为，简记为BTBBTB，或者或者Branch-Target CacheBranch-Target Cache）。）。4.3 动态分支预测技术动态分支预测技术1.1.BTB的结构的结构BTB是用专门的是用专门的硬件实现的一张表硬件实现的一张表格。格。表格中的每一项表格中的每一项至少有两个字段：至少有两个字段：执

37、行过的成功分执行过的成功分支指令的地址；支指令的地址；（作为该表的匹配作为该表的匹配标识标识）预测的分支目标预测的分支目标地址。地址。2.2.采用采用BTBBTB后，在流水线各个阶段所进行的相后，在流水线各个阶段所进行的相关操作：关操作：4.3 动态分支预测技术动态分支预测技术三三.基于硬件的前瞻执行基于硬件的前瞻执行1.1.前瞻执行前瞻执行（speculationspeculation）的基本思想：的基本思想：对分支指令的结果进行猜测，并假设这个猜对分支指令的结果进行猜测，并假设这个猜测总是对的，然后按这个猜测结果继续取、测总是对的，然后按这个猜测结果继续取、流出和执行后续的指令。只是执行指

38、令的结流出和执行后续的指令。只是执行指令的结果不是写回到寄存器或存储器，而是放到一果不是写回到寄存器或存储器，而是放到一个称为个称为ROBROB（ReOrder BufferReOrder Buffer）的缓冲器中。的缓冲器中。等到相应的指令得到等到相应的指令得到“确认确认”（commitcommit）（即确实是应该执行的）之后，才将结果写（即确实是应该执行的）之后，才将结果写入寄存器或存储器。入寄存器或存储器。4.3 动态分支预测技术动态分支预测技术2.2.基于硬件的前瞻执行结合了基于硬件的前瞻执行结合了三种思想：三种思想：1）动态分支预测。用来选择后续执行的指令。）动态分支预测。用来选择后

39、续执行的指令。2）在控制相关的结果尚未出来之前，前瞻地）在控制相关的结果尚未出来之前，前瞻地执行后续指令。执行后续指令。3）用动态调度对基本块的各种组合进行跨基）用动态调度对基本块的各种组合进行跨基本块的调度。本块的调度。3.3.对对TomasuloTomasulo算法加以扩充，就可以支持前瞻执算法加以扩充，就可以支持前瞻执行。行。把把TomasuloTomasulo算法的写结果和指令完成加以区算法的写结果和指令完成加以区分，分成两个不同的段：分，分成两个不同的段：写结果，指令确认写结果，指令确认 n写结果段写结果段把前瞻执行的结果写到把前瞻执行的结果写到ROBROB中；中；通过通过CDBCD

40、B在指令之间传送结果，供需要用到这在指令之间传送结果，供需要用到这些结果的指令使用。些结果的指令使用。n指令确认段指令确认段 在分支指令的结果出来后，对相应指令的前瞻在分支指令的结果出来后，对相应指令的前瞻执行给予确认。执行给予确认。如果前面所做的猜测是对的，把在如果前面所做的猜测是对的，把在ROBROB中的结中的结果写到寄存器或存储器。果写到寄存器或存储器。如果发现前面对分支结果的猜测是错误的，那如果发现前面对分支结果的猜测是错误的，那就不予以确认，并从那条分支指令的另一条路就不予以确认，并从那条分支指令的另一条路径开始重新执行。径开始重新执行。n支持前瞻执行的浮点部件的结构持前瞻执行的浮点

41、部件的结构换名功能是由换名功能是由ROB来完来完成的。成的。实现前瞻的关键思想：实现前瞻的关键思想：允许指令乱序执行，但允许指令乱序执行，但必须顺序确认。必须顺序确认。4.4 多指令流出技术多指令流出技术一一.单流出（单发射）处理机和多流出（多发射）单流出（单发射）处理机和多流出（多发射）处理机处理机 1.单流出处理机单流出处理机只有一套指令部件（取指只有一套指令部件（取指部件和译码部件），并且每个时钟周期只取部件和译码部件），并且每个时钟周期只取一条指令，只对一条指令进行译码。一条指令，只对一条指令进行译码。4.4 多指令流出技术多指令流出技术 IF 1 2 3 4 5 6 7 时钟周期时钟

42、周期 指令指令 I1 I2 I3 ID EX MEM WB IF ID EX MEM WB IF ID EX MEM WB 单流出时空图单流出时空图 2.多流出处理机多流出处理机n一个时钟周期内流出多条指令，一个时钟周期内流出多条指令，CPICPI1 1。n有多套（有多套（m m）指令部件（取指部件和译码部件）指令部件（取指部件和译码部件），能在每个时钟周期同时取出多条指令，并，能在每个时钟周期同时取出多条指令，并同时对多条指令进行译码。同时对多条指令进行译码。4.4 多指令流出技术多指令流出技术 1 2 3 4 5 6 7 时钟周期时钟周期 指令指令 I1 I2 I3 IF ID EX ME

43、M WB IF IF ID ID EX EX MEM MEM WB WB IF ID EX MEM WBIF ID EX MEM WBIF ID EX MEM WB IF ID EX MEM WBIF ID EX MEM WBIF ID EX MEM WB多流出时空图多流出时空图 4.4 多指令流出技术多指令流出技术二二.多流出处理机有两种基本风格：多流出处理机有两种基本风格：1.1.超标量超标量处理机（空间并行）：处理机（空间并行）：n把一个时钟周期内能够把一个时钟周期内能够同时同时发射多条指令的发射多条指令的处理机称为超标量处理机。处理机称为超标量处理机。n超标量处理机最基本的要求是有两套

44、或两套超标量处理机最基本的要求是有两套或两套以上完整的指令执行部件。以上完整的指令执行部件。n为了能够在一个时钟周期内同时发射多条指为了能够在一个时钟周期内同时发射多条指令，超标量处理机必须有两条或两条以上能令，超标量处理机必须有两条或两条以上能够同时工作的指令流水线。够同时工作的指令流水线。4.4 多指令流出技术多指令流出技术n在每个时钟周期流出的指令条数在每个时钟周期流出的指令条数不固定不固定，依，依代码的具体情况而定。（有上限）代码的具体情况而定。（有上限）n设这个上限为设这个上限为n n，就称该处理机为，就称该处理机为n n流出。流出。n可以通过编译器进行静态调度，也可以基于可以通过编

45、译器进行静态调度，也可以基于TomasuloTomasulo算法进行动态调度。算法进行动态调度。2.2.超长指令字超长指令字VLIWVLIW（Very Long Very Long Instruction WordInstruction Word）依靠编译器把能并行执行的多条指令组装成依靠编译器把能并行执行的多条指令组装成一条很长的指令一条很长的指令（100100多位到几百位），并多位到几百位），并设设置多个功能部置多个功能部 件。指令字被分割成一些字段，件。指令字被分割成一些字段，每个字段称为一个每个字段称为一个操作槽操作槽，直接独立地控制，直接独立地控制一个功能部件。一个功能部件。第第k条

46、指令条指令第第k+1条指令条指令第第k+2条指令条指令4.4 多指令流出技术多指令流出技术n在每个时钟周期流出的指令条数是在每个时钟周期流出的指令条数是固定的固定的，这些指令构成一条长指令或者一个指令包。这些指令构成一条长指令或者一个指令包。n指令包中，指令之间的并行性是通过指令显指令包中，指令之间的并行性是通过指令显式地表示出来的。式地表示出来的。n指令调度是由编译器静态完成的。指令调度是由编译器静态完成的。三三.多流出流水线的调度问题（例子说明）多流出流水线的调度问题（例子说明）（1 1）顺序发射顺序完成）顺序发射顺序完成6 6条指令共用了条指令共用了1010个时钟周期才完成。个时钟周期才

47、完成。有有8 8个空闲的时钟周期个空闲的时钟周期 （2 2）顺序发射乱序完成）顺序发射乱序完成共需共需9 9个周期。仅有个周期。仅有3 3个空闲周期。个空闲周期。（3 3）乱序发射乱序完成）乱序发射乱序完成共需共需8 8个周期。无空闲周期。个周期。无空闲周期。先行指令窗口：先行指令窗口：能够从指令中预取多条指令。能够从指令中预取多条指令。能够对窗口内的指令进行数据相关能够对窗口内的指令进行数据相关性分析和功能部件冲突的检测。性分析和功能部件冲突的检测。四、超流水线处理机四、超流水线处理机 在一个时钟周期内能够在一个时钟周期内能够分时分时发射多条指令发射多条指令的处理机称为的处理机称为超流水线处

48、理机。超流水线处理机。1典型结构典型结构nR4000的指令流水线有的指令流水线有8级，级，采用超流水线结构，采用超流水线结构，取指令和访问数据都要跨越两个流水级；取指令和访问数据都要跨越两个流水级；n每个时钟周期包含两个流水级，处理器取第一条每个时钟周期包含两个流水级，处理器取第一条指令（指令（IF）和取第二条指令（）和取第二条指令（IS）4.4 多指令流出技术多指令流出技术n两个流水级都要访问指令两个流水级都要访问指令CacheCache，这两个流水级，这两个流水级为一个时钟周期。为一个时钟周期。4.4 多指令流出技术多指令流出技术n指令执行时序指令执行时序一台并行度一台并行度ILPILP为

49、为n n的超流水线处理机，它在一的超流水线处理机，它在一个时钟周期内能够分时发射个时钟周期内能够分时发射n n条指令。但这条指令。但这n n条条指令不是同时发射的，而是每隔指令不是同时发射的，而是每隔1/n1/n个时钟周期个时钟周期发射一条指令。发射一条指令。n每个时钟周期分时发射每个时钟周期分时发射2 2条指令的超流水线处理条指令的超流水线处理机的指令执行时空图如下：机的指令执行时空图如下：2 2、与超标量机提高性能的途径不同：、与超标量机提高性能的途径不同：超标量处理机超标量处理机通过重复设置多个通过重复设置多个“取指令取指令”部部件，多个件，多个“译码译码”、“执行执行”和和“写回结果写

50、回结果”部件部件，使其，使其同时工作来提高指令的执行速度，同时工作来提高指令的执行速度，以增加硬件资源为代价来换取处理机性能以增加硬件资源为代价来换取处理机性能。超流水线处理机超流水线处理机只需要增加少量硬件，是通过只需要增加少量硬件，是通过各部分硬件的充分重叠工作来提高处理机性能各部分硬件的充分重叠工作来提高处理机性能的。的。4.4 多指令流出技术多指令流出技术 从流水线从流水线的时空图的时空图上看，超上看，超标量处理标量处理机采用的机采用的是空间并是空间并行性，而行性，而超流水线超流水线处理机采处理机采用的是时用的是时间并行性。间并行性。4.5 循环展开和指令调度循环展开和指令调度 在编译