计算机体系结构第四章-1

1、第四章第四章 指令级并行指令级并行 主要内容n4.1 指令级并行的概念n4.2 指令的动态调度n4.3 动态分支预测技术n4.4 多指令流出技术 n4.5 循环展开和指令调度n4.1指令级并行的概念4.1 4.1 指令级并行的概念指令级并行的概念n指令级并行指令级并行(ILP：Instruction-Level Parallelism)：是指指令之间存在的一种并行性，利用它计算机可以执行两条或两条以上的指令。n途径：资源重复资源重复-设置多个处理部件 时间重叠时间重叠-几乎所有的处理机都利用流水线来使指令重叠并行执行，以达到提高性能的目的。n本章研究：本章研究：如何通过各种可能的技术，获得更多

2、的指令级并行性。 硬件软件技术硬件软件技术必须要硬件技术和软件技术互相配合，才能够最大限度地挖掘出程序中存在的指令级并行。n流水线处理机的实际流水线处理机的实际CPICPI理想流水线的CPI加上各类停顿的时钟周期数： CPICPI流水线流水线 = CPI= CPI理想理想 + + 停顿停顿结构冲突结构冲突 + + 停顿停顿数据冲突数据冲突 + + 停顿停顿控制冲突控制冲突理想CPI是衡量流水线最高性能的一个指标。通过减少右边各项，就能减小总的CPI，从而提高IPC。IPC（Instructions Per Cycle）：定义为一个时钟周期内流水线上完成的指令条数。4.1 指令级并行的概念指令级

3、并行的概念1. 循环级并行循环级并行n使一个循环中的不同循环体并行执行。n开发循环体中存在的并行性是指令级并行研究的重点之一n最基本的开发循环级并行的技术n循环展开（loop unrolling）技术 （4.5节介绍） n采用向量指令和向量数据表示 （向量章节介绍）2. 相关与流水线冲突相关与流水线冲突n静态指令调度n动态指令调度4.1 指令级并行的概念指令级并行的概念相关是程序固有的相关是程序固有的一种属性，它反映一种属性，它反映了程序中指令之间了程序中指令之间的相互依赖关系。的相互依赖关系。相关是否会导致实际冲相关是否会导致实际冲突的发生以及该冲突会突的发生以及该冲突会带来多长的停顿，则是

4、带来多长的停顿，则是流水线的属性。流水线的属性。不保持不保持“程序顺序程序顺序”3. 对于正确地执行程序来说，必须保持的最关键的两个属性是：数据流数据流和异常行为。异常行为。n数据流：数据流：指数据值从其产生者指令到其消费者指令的实际流动。n保持异常行为保持异常行为是指：无论怎么改变指令的执行顺序，都不能改变程序中异常的发生情况。l即原来程序中是怎么发生的，改变执行顺序后还是怎么发生。l弱化为：指令执行顺序的改变不能导致程序中发生新的异常。4.1 指令级并行的概念指令级并行的概念n4.2 指令的动态调度4.2 4.2 指令的动态调度指令的动态调度关键知识回顾：关键知识回顾：1.相关相关u相关是

5、指两条指令之间存在某种依赖关系，是程序固有的一种属性。u相关包括：名相关，数据相关，控制相关。2.冲突（冲突（ HAZARDS，也称为冒险），也称为冒险）u冲突是指由于相关的存在，使得指令流中的下一条指令不能在指定的时钟周期执行。u具体一次相关是否会导致实际冲突的发生以及该冲突会带来多长的停顿，则是流水线的属性。u流水线冲突包括：结构冲突，数据冲突，控制冲突。3. 冲突的解决冲突的解决（1 1）结构冲突：）结构冲突：停顿（流水线气泡）（2 2）数据冲突：）数据冲突：定向传送技术定向传送与停顿相结合指令调度（编译器）（编译器） 前提：在乱序流动的流水线中。 不足：可能会产生新的WAR或WAW冲突

6、。（3 3）控制冲突）控制冲突：预测分支失败预测分支成功延迟转移技术（编译器）（编译器）静态调度静态调度4.2 指令的动态调度指令的动态调度n静态调度静态调度依靠编译器对代码进行静态调度，以减少相关和冲突。它不是在程序执行的过程中，而是在编译期间进行代码调度和优化。通过把相关的指令拉开距离来减少可能产生的停顿。n动态调度动态调度在程序的执行过程中，依靠专门硬件对代码进行调度，减少数据相关导致的停顿。4.2 指令的动态调度指令的动态调度一、动态调度的基本思想一、动态调度的基本思想 考虑下面一段代码： DIV.D F4F4，F0，F2 SUB.D F10，F4F4，F6 ADD.D F12，F6，

7、F14SUB.DSUB.D指令与DIV.DDIV.D指令关于F4F4相关，导致流水线停顿。ADD.DADD.D指令与流水线中的任何指令都没有关系，但也因此受但也因此受阻阻。4.2 指令的动态调度指令的动态调度在前面的基本流水线中：指令在译码阶段判断相关关系。ID检测结构冲突检测数据冲突 一旦一旦一条指令受阻，一条指令受阻，其后的指令都将停顿其后的指令都将停顿。4.2 指令的动态调度指令的动态调度n动态调度的基本思想是前面指令的阻塞不影响后面的指令的继续前进。具体做法是流水线的译码阶段再分为两个阶段：n流出流出( (Issue, IS) )：指令译码，并检查结构冲突。(in-order issu

8、e)n读操作数（读操作数（Read Operands, RO）：）：等待数据冲突消失(如果有冲突)，然后读操作数。(out of order execution)ISRO检测结构冲突检测数据冲突4.2 指令的动态调度指令的动态调度n有的代码在采用乱序执行后可能会发生WAR冲突和WAW冲突。n例如，考虑下面的代码 DIV.D F4, F0, F2 SUB.D F10, F4, F6 ADD.D F6, F8, F14 DIV.D F10, F1, F3 反相关反相关输出相关输出相关数据相关数据相关SUB.D SUB.D F10F10, , F4F4, , F6F6WARWAR冲突冲突WAWWAW

9、冲突冲突TomasuloTomasulo算法算法可以通过使用寄存器重命名来消除。可以通过使用寄存器重命名来消除。 4.2 指令的动态调度指令的动态调度回顾：寄存器换名可以消除WAR冲突和WAW冲突。考虑之前的代码： DIV.D F4, F0, F2 SUB.D F10,F4, F6 ADD.D F6, F8, F14 DIV.D F10, F1, F3反相关反相关,F6,F6输出相关输出相关,F10,F10数据相关数据相关,F4,F4消除名相关：消除名相关：引入两个临时寄存器引入两个临时寄存器S S和和T T，分别将第一个，分别将第一个F10F10换成换成S S，将后一个，将后一个F6F6换成

10、换成T T。S,T,4.2 指令的动态调度指令的动态调度二、二、Tomasulo算法算法1.1.基本思想基本思想 核心思想：n记录和检测指令相关，操作数一旦就绪就立即执行，把发生RAW冲突的可能性减少到最小；n通过寄存器换名来消除WAR冲突和WAW冲突。 4.2 指令的动态调度指令的动态调度nIBM 360/91首先采用了Tomasulo算法。nIBM 360/91的设计目标是基于整个360系列的统一指令集和编译器来实现高性能，而不是设计和利用专用的编译器来提高性能。 需要更多地依赖于硬件。nIBM 360体系结构只有4 4个双精度浮点寄存器，限制了编译器调度的有效性。n360/91360/9

11、1的访存时间和浮点计算时间都很长。 （也是Tomasulo算法要解决的问题） 4.2 指令的动态调度指令的动态调度n基于Tomasulo算法的MIPS处理器浮点部件的基本结构 从从指指令令部部件件来来 浮浮点点寄寄存存器器FP store缓缓冲冲器器 load缓缓冲冲器器 地地址址部部件件 load/store操操作作 浮浮点点操操作作 操操作作数数总总线线 操操作作总总线线 数数据据 1 1 存存储储部部件件 浮浮点点加加法法器器 浮浮点点乘乘法法器器 指指令令队队列列 地地址址 2 3 2 3 4 5 6 公公共共数数据据总总线线（CDB） 1 2 保保留留站站 标标识识 标标识识 1 1

12、）保留站（保留站（reservation stationreservation station） 设置在运算部件入口，每个保留站中保存一条已经流出并等待到本功能部件执行的指令执行的指令（相关信息）。 包括：包括：操作码、操作数以及用于检测和解决冲突的信息。n在一条指令“流出”到保留站的时候，如果该指令的源操作数已经在寄存器中就绪，则将之取到该保留站中。n如果操作数还没有计算出来，则在该保留站中记录将产生这个操作数的保留站的标识。浮点加法器有3个保留站：ADD1，ADD2，ADD3浮点乘法器有2个保留站：MULT1，MULT2 每个保留站都有一个标识字段，唯一地标识了该保留站。 4.2 指令的动

13、态调度指令的动态调度n基于Tomasulo算法的MIPS处理器浮点部件的基本结构 从从指指令令部部件件来来 浮浮点点寄寄存存器器FP store缓缓冲冲器器 load缓缓冲冲器器 地地址址部部件件 load/store操操作作 浮浮点点操操作作 操操作作数数总总线线 操操作作总总线线 数数据据 1 1 存存储储部部件件 浮浮点点加加法法器器 浮浮点点乘乘法法器器 指指令令队队列列 地地址址 2 3 2 3 4 5 6 公公共共数数据据总总线线（CDB） 1 2 保保留留站站 标标识识 标标识识 2 2）公共数据总线公共数据总线CDBCDB (Common Data Bus)所有功能部件的计算结

14、果都是送到CDB上，由它把这些结果直接送到（播送到）各个需要该结果的地方。3 3）loadload缓冲器和缓冲器和storestore缓冲器缓冲器 存放读/写存储器的数据或地址 （与保留站类似）4 4）浮点寄存器）浮点寄存器FPFPn共有16个浮点寄存器：F0，F2，F4，F30。n它们通过一对总线连接到功能部件，并通过CDB连接到store缓冲器。4.2 指令的动态调度指令的动态调度5）指令队列）指令队列n指令部件送来的(译码后)指令放入指令队列n指令队列中的指令按先进先出的顺序流出6）运算部件）运算部件n浮点加法器完成加法和减法操作n浮点乘法器完成乘法和除法操作4.2 指令的动态调度指令的

15、动态调度从从指指令令部部件件来来 浮浮点点寄寄存存器器FP 缓缓冲冲器器 浮浮点点操操作作 操操作作数数总总线线 操操作作总总线线 1 浮浮点点加加法法器器 浮浮点点乘乘法法器器 指指令令队队列列 2 3 公公共共数数据据总总线线（CDB） 1 2 保保留留站站 标标识识 标标识识 F8F8F6F6F4F4F2F2C CB BA AADD1ADD1MUL1MUL1MUL2MUL2ADD2ADD2ADD3ADD3ADD F2,ADD F2,F0F0,F6,F6MUL MUL FOFO,F2,F4,F2,F4QiF0F0D DSUB SUB F6,F8,F4F6,F8,F4MUL MUL FOFO

16、,F2,F4,F2,F4ADD F2,ADD F2,F0F0, ,F6F6SUB SUB F6F6,F8,F4,F8,F4从从指指令令部部件件来来 浮浮点点寄寄存存器器FP 缓缓冲冲器器 浮浮点点操操作作 操操作作数数总总线线 操操作作总总线线 1 浮浮点点加加法法器器 浮浮点点乘乘法法器器 指指令令队队列列 2 3 公公共共数数据据总总线线（CDB） 1 2 保保留留站站 标标识识 标标识识 MUL MUL FOFO,F2,F4,F2,F4ADD F2,ADD F2,F0F0, ,F6F6SUB SUB F6F6,F8,F4,F8,F4从从指指令令部部件件来来 浮浮点点寄寄存存器器FP 缓缓

17、冲冲器器 浮浮点点操操作作 操操作作数数总总线线 操操作作总总线线 1 浮浮点点加加法法器器 浮浮点点乘乘法法器器 指指令令队队列列 2 3 公公共共数数据据总总线线（CDB） 1 2 保保留留站站 标标识识 标标识识 MUL A, BMUL A, BADD F2,F0,F6ADD F2,F0,F6F8F8F6F6F4F4F2F2D DC CB BADD1ADD1MUL1MUL1MUL2MUL2ADD2ADD2ADD3ADD3QiSUB SUB F6,F8,F4F6,F8,F4F0F0A AMUL1MUL1寄存器寄存器状态表状态表从从指指令令部部件件来来 浮浮点点寄寄存存器器FP 缓缓冲冲器器

18、 浮浮点点操操作作 操操作作数数总总线线 操操作作总总线线 1 浮浮点点加加法法器器 浮浮点点乘乘法法器器 指指令令队队列列 2 3 公公共共数数据据总总线线（CDB） 1 2 保保留留站站 标标识识 标标识识 MUL MUL FOFO,F2,F4,F2,F4ADD F2,ADD F2,F0F0, ,F6F6SUB SUB F6F6,F8,F4,F8,F4从从指指令令部部件件来来 浮浮点点寄寄存存器器FP 缓缓冲冲器器 浮浮点点操操作作 操操作作数数总总线线 操操作作总总线线 1 浮浮点点加加法法器器 浮浮点点乘乘法法器器 指指令令队队列列 2 3 公公共共数数据据总总线线（CDB） 1 2

19、保保留留站站 标标识识 标标识识 MUL A, BMUL A, BADD CADD CF8F8F6F6F4F4F2F2D DC CB BADD1ADD1MUL1MUL1MUL2MUL2ADD2ADD2ADD3ADD3MUL1MUL1ADD1ADD1QiF0F0A ASUB D BSUB D BADD2ADD2SUB SUB F6,F8,F4F6,F8,F4MUL1从从指指令令部部件件来来 浮浮点点寄寄存存器器FP 缓缓冲冲器器 浮浮点点操操作作 操操作作数数总总线线 操操作作总总线线 1 浮浮点点加加法法器器 浮浮点点乘乘法法器器 指指令令队队列列 2 3 公公共共数数据据总总线线（CDB）

20、1 2 保保留留站站 标标识识 标标识识 MUL MUL FOFO,F2,F4,F2,F4ADD F2,ADD F2,F0F0, ,F6F6SUB SUB F6F6,F8,F4,F8,F4从从指指令令部部件件来来 浮浮点点寄寄存存器器FP 缓缓冲冲器器 浮浮点点操操作作 操操作作数数总总线线 操操作作总总线线 1 浮浮点点加加法法器器 浮浮点点乘乘法法器器 指指令令队队列列 2 3 公公共共数数据据总总线线（CDB） 1 2 保保留留站站 标标识识 标标识识 MUL A, BMUL A, BADD MUL1, CADD MUL1, CF8F8F6F6F4F4F2F2D DC CB BADD1A

21、DD1MUL1MUL1MUL2MUL2ADD2ADD2ADD3ADD3MUL1MUL1ADD1ADD1QiF0F0A ASUB D, BSUB D, BADD2ADD2E EADD E, ADD E, C C硬件重命名硬件重命名F Fn在Tomasulo算法中，寄存器换名是通过保留站和流出逻辑来共同完成的。n当指令流出时，如果其操作数还没有计算出来，则将该指令中相应的寄存器号换名为将产生这个操作数的保留站换名为将产生这个操作数的保留站的标识的标识。n指令流出到保留站后，其操作数寄存器号或者换成了数据本身（如果该数据已经就绪），或者换成了保留站的标识，不再与寄存器有关系不再与寄存器有关系。4.2

22、 指令的动态调度指令的动态调度nTomasulo算法具有以下两个特点：两个特点：1）冲突检测和指令执行控制是分布的。 每个功能部件的保留站中的信息决定了什么时候指每个功能部件的保留站中的信息决定了什么时候指令可以在该功能部件开始执行。令可以在该功能部件开始执行。2）计算结果通过CDB直接从产生它的保留站传送到所有需要它的功能部件，而不用经过寄存器。4.2 指令的动态调度指令的动态调度2.2.指令执行的步骤指令执行的步骤使用Tomasulo算法的流水线需3步：(1)流出：流出：从指令队列的头部取一条指令。n如果没有空闲的保留站，指令就不能流出。(结构冲突)n如果该指令的操作所要求的保留站有空闲的

23、，就把该指令送到该保留站（设为r）。n如果其操作数在寄存器中已经就绪，就将这些操作数送入保留站如果其操作数在寄存器中已经就绪，就将这些操作数送入保留站r r。n如果其操作数还没有就绪，就把将产生该操作数的保留站的标识送入如果其操作数还没有就绪，就把将产生该操作数的保留站的标识送入保留站保留站r r。 （寄存器换名和对操作数进行缓冲，消除WARWAR冲突）n完成对目标寄存器的预约目标寄存器的预约工作（消除了WAWWAW冲突）4.2 指令的动态调度指令的动态调度(2) 执行执行 n当两个操作数都就绪后，本保留站就用相应的功能部件开始执行指令规定的操作。 （消除了R RAWAW冲突）nload和st

24、ore指令的执行需要两个步骤：n计算有效地址（要等到基地址寄存器就绪）n把有效地址放入load或store缓冲器(3) 写结果写结果 功能部件计算完毕后，就将计算结果放到CDBCDB上，所有等待该计算结果的寄存器和保留站（包括storestore缓冲器）都同时从CDBCDB上获得所需要的数据。 4.2 指令的动态调度指令的动态调度3. Tomasulo3. Tomasulo算法举例算法举例 每个保留站有以下6个字段：（P121 图4.2）nBusy：为“yes”表示本保留站或缓冲单元“忙”。 nOp：要对源操作数进行的操作。 nVj，Vk：源操作数的值。nQj，Qk：将产生源操作数的保留站号。

25、n等于0 0表示操作数已经就绪且在VjVj或VkVk中，或者不需要操作数。 （起“标志字段”作用）n对于每一个操作数来说，V V或Q Q字段只有一个有效。nA：仅loadload和storestore缓冲器有该字段。开始是存放指令中的立即数字段，地址计算后存放有效地址。 nQi：寄存器状态表。n每个寄存器在该表中有对应的一项，用于存放将把结果写入该寄存器的保留站的站号。n为0 0表示当前没有正在执行的指令要写入该寄存器，也即该寄存器中的内容就绪。 （起“标志字段”作用） 例：对于下述指令序列，给出当第一条指令完成并写入结果时，Tomasulo算法所用的各信息表中的内容。 L.DF6,34（R2

26、） L.DF2,45（R3） MUL.DF0,F2,F4 SUB.DF8,F2,F6 DIV.DF10,F0,F6 ADD.DF6,F8,F24.2 指令的动态调度指令的动态调度n当采用Tomasulo算法时，当第一条指令完成并写入结果时， 各条指令所处阶段如下表。指指 令令 指令状态表指令状态表 流出流出 执行执行 写结果写结果 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 4.2 指令的动态调度指令的动态调度名称名称 保留站

27、保留站 Load1Load1Load2Load2Add1Add1Add2Add2Add3Add3Mult1Mult1Mult2Mult2BusyBusy nono no no no no no no nono nono nonoOpOp VjVj Vk Vk QjQj QkQk A A 寄存器状态表寄存器状态表 F0 F0 F2 F2 F4 F4 F6 F8 F6 F8 F10 F30F10 F30 Qi Qi L.D F6,34(R2) 流出流出loadload缓冲器、保留站以及寄存器状态表中的内容如下表缓冲器、保留站以及寄存器状态表中的内容如下表RegsR2RegsR23434LDLDye

28、syesLoad1Load1名称名称 保留站保留站 Load1Load1Load2Load2Add1Add1Add2Add2Add3Add3Mult1Mult1Mult2Mult2BusyBusy yes yes no no no no no no nono nono nonoOpOp LD LD VjVj Vk Vk QjQj QkQk A A 34+RegsR234+RegsR2 寄存器状态表寄存器状态表 F0 F2 F4 F6 F8 F10 F30F0 F2 F4 F6 F8 F10 F30 Qi Qi Load1 Load1 loadload缓冲器、保留站以及寄存器状态表中的内容如下表

29、缓冲器、保留站以及寄存器状态表中的内容如下表L.D F6,34(R2) 执行执行计算有效地址计算有效地址名称名称 保留站保留站 Load1Load1Load2Load2Add1Add1Add2Add2Add3Add3Mult1Mult1Mult2Mult2BusyBusy nono no no no no no no nono nono nonoOpOp VjVj Vk Vk QjQj QkQk A A 寄存器状态表寄存器状态表 F0 F2 F4 F6 F8 F10 F30F0 F2 F4 F6 F8 F10 F30 Qi Qi loadload缓冲器、保留站以及寄存器状态表中的内容如下表缓冲器、保留站以及寄存器