计算机体系结构第四章-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）：定义为一个时 钟周期内

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

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

5、n4.2 指令的动态调度 4.2 4.2 指令的动态调度指令的动态调度 关键知识回顾：关键知识回顾： 1.相关相关 u相关是指两条指令之间存在某种依赖关系，是程序固有的一种 属性。 u相关包括：名相关，数据相关，控制相关。 2.冲突（冲突（ HAZARDS，也称为冒险），也称为冒险） u冲突是指由于相关的存在，使得指令流中的下一条指令不能在 指定的时钟周期执行。 u具体一次相关是否会导致实际冲突的发生以及该冲突会带来多 长的停顿，则是流水线的属性。 u流水线冲突包括：结构冲突，数据冲突，控制冲突。 3. 冲突的解决冲突的解决 （1 1）结构冲突：）结构冲突：停顿（流水线气泡） （2 2）数据冲

6、突：）数据冲突： 定向传送技术 定向传送与停顿相结合 指令调度（编译器）（编译器） 前提：在乱序流动的流水线中。 不足：可能会产生新的WAR或WAW冲突。 （3 3）控制冲突）控制冲突： 预测分支失败 预测分支成功 延迟转移技术 （编译器）（编译器） 静态调度静态调度 4.2 指令的动态调度指令的动态调度 n静态调度静态调度 依靠编译器对代码进行静态调度，以减少相关和冲突。 它不是在程序执行的过程中，而是在编译期间进行代码 调度和优化。 通过把相关的指令拉开距离来减少可能产生的停顿。 n动态调度动态调度 在程序的执行过程中，依靠专门硬件对代码进行调度， 减少数据相关导致的停顿。 4.2 指令的

7、动态调度指令的动态调度 一、动态调度的基本思想一、动态调度的基本思想 考虑下面一段代码： DIV.D F4F4，F0，F2 SUB.D F10，F4F4，F6 ADD.D F12，F6，F14 SUB.DSUB.D指令与DIV.DDIV.D指令关于F4F4相关，导致流水线停顿。 ADD.DADD.D指令与流水线中的任何指令都没有关系，但也因此受但也因此受 阻阻。 4.2 指令的动态调度指令的动态调度 在前面的基本流水线中：指令在译码阶段判断相关关 系。 ID 检测结构冲突 检测数据冲突 一旦一旦一条指令受阻，一条指令受阻，其后的指令都将停顿其后的指令都将停顿。 4.2 指令的动态调度指令的动态

8、调度 n动态调度的基本思想是前面指令的阻塞不影响后面的 指令的继续前进。具体做法是流水线的译码阶段再分为 两个阶段： n流出流出( (Issue, IS) )：指令译码，并检查结构冲突。(in- order issue) n读操作数（读操作数（Read Operands, RO）：）：等待数据冲突消失 (如果有冲突)，然后读操作数。(out of order execution) IS RO 检测结构冲突检测数据冲突 4.2 指令的动态调度指令的动态调度 n有的代码在采用乱序执行后可能会发生WAR冲突和WAW冲突。 n例如，考虑下面的代码 DIV.D F4, F0, F2 SUB.D F10,

9、 F4, F6 ADD.D F6, F8, F14 DIV.D F10, F1, F3 反相关反相关 输出相关输出相关 数据相关数据相关 SUB.D SUB.D F10F10, , F4F4, , F6F6 WARWAR冲突冲突 WAWWAW冲突冲突 TomasuloTomasulo算法算法可以通过使用寄存器重命名来消除。可以通过使用寄存器重命名来消除。 4.2 指令的动态调度指令的动态调度 回顾：寄存器换名可以消除WAR冲突和WAW冲突。 考虑之前的代码： DIV.D F4, F0, F2 SUB.D F10,F4, F6 ADD.D F6, F8, F14 DIV.D F10, F1, F

10、3 反相关反相关,F6,F6 输出相关输出相关,F10,F10 数据相关数据相关,F4,F4 消除名相关：消除名相关：引入两个临时寄存器引入两个临时寄存器S S和和T T，分别将第一个，分别将第一个F10F10 换成换成S S，将后一个，将后一个F6F6换成换成T T。 S, T, 4.2 指令的动态调度指令的动态调度 二、二、Tomasulo算法算法 1.1.基本思想基本思想 核心思想： n记录和检测指令相关，操作数一旦就绪就立即执 行，把发生RAW冲突的可能性减少到最小； n通过寄存器换名来消除WAR冲突和WAW冲突。 4.2 指令的动态调度指令的动态调度 nIBM 360/91首先采用了

11、Tomasulo算法。 nIBM 360/91的设计目标是基于整个360系列的统一指令 集和编译器来实现高性能，而不是设计和利用专用的 编译器来提高性能。 需要更多地依赖于硬件。 nIBM 360体系结构只有4 4个双精度浮点寄存器，限制了 编译器调度的有效性。 n360/91360/91的访存时间和浮点计算时间都很长。 （也是Tomasulo算法要解决的问题） 4.2 指令的动态调度指令的动态调度 n基于Tomasulo算法的MIPS处理器浮点部件的基本结构 从从指指令令部部件件来来 浮浮点点寄寄存存器器FP store缓缓冲冲器器 load缓缓冲冲器器 地地址址部部件件 load/stor

12、e操操作作 浮浮点点操操作作 操操作作数数总总线线 操操作作总总线线 数数据据 1 1 存存储储部部件件 浮浮点点加加法法器器 浮浮点点乘乘法法器器 指指令令队队列列 地地址址 2 3 2 3 4 5 6 公公共共数数据据总总线线（CDB） 1 2 保保留留站站 标标识识 标标识识 1 1）保留站（保留站（reservation stationreservation station） 设置在运算部件入口，每个保留站中保存一条已经流出并 等待到本功能部件执行的指令执行的指令（相关信息）。 包括：包括：操作码、操作数以及用于检测和解决冲突的信息。 n在一条指令“流出”到保留站的时候，如果该指令 的

13、源操作数已经在寄存器中就绪，则将之取到该保 留站中。 n如果操作数还没有计算出来，则在该保留站中记录 将产生这个操作数的保留站的标识。 浮点加法器有3个保留站：ADD1，ADD2，ADD3 浮点乘法器有2个保留站：MULT1，MULT2 每个保留站都有一个标识字段，唯一地标识了该保留站。 4.2 指令的动态调度指令的动态调度 n基于Tomasulo算法的MIPS处理器浮点部件的基本结构 从从指指令令部部件件来来 浮浮点点寄寄存存器器FP store缓缓冲冲器器 load缓缓冲冲器器 地地址址部部件件 load/store操操作作 浮浮点点操操作作 操操作作数数总总线线 操操作作总总线线 数数据

14、据 1 1 存存储储部部件件 浮浮点点加加法法器器 浮浮点点乘乘法法器器 指指令令队队列列 地地址址 2 3 2 3 4 5 6 公公共共数数据据总总线线（CDB） 1 2 保保留留站站 标标识识 标标识识 2 2）公共数据总线公共数据总线CDBCDB (Common Data Bus) 所有功能部件的计算结果都是送到CDB上，由它把这些结 果直接送到（播送到）各个需要该结果的地方。 3 3）loadload缓冲器和缓冲器和storestore缓冲器缓冲器 存放读/写存储器的数据或地址 （与保留站类似） 4 4）浮点寄存器）浮点寄存器FPFP n共有16个浮点寄存器：F0，F2，F4，F30。

15、 n它们通过一对总线连接到功能部件，并通过CDB连接到 store缓冲器。 4.2 指令的动态调度指令的动态调度 5）指令队列）指令队列 n指令部件送来的(译码后)指令放入指令队列 n指令队列中的指令按先进先出的顺序流出 6）运算部件）运算部件 n浮点加法器完成加法和减法操作 n浮点乘法器完成乘法和除法操作 4.2 指令的动态调度指令的动态调度 从从指指令令部部件件来来 浮浮点点寄寄存存器器FP 缓缓冲冲器器 浮浮点点操操作作 操操作作数数总总线线 操操作作总总线线 1 浮浮点点加加法法器器 浮浮点点乘乘法法器器 指指令令队队列列 2 3 公公共共数数据据总总线线（CDB） 1 2 保保留留站

16、站 标标识识 标标识识 F8F8 F6F6 F4F4 F2F2 C C B B A A ADD1ADD1 MUL1MUL1 MUL2MUL2 ADD2ADD2 ADD3ADD3 ADD F2,ADD F2,F0F0,F6,F6 MUL MUL FOFO,F2,F4,F2,F4 Qi F0F0 D D SUB SUB F6,F8,F4F6,F8,F4 MUL MUL FOFO,F2,F4,F2,F4 ADD F2,ADD F2,F0F0, ,F6F6 SUB SUB F6F6,F8,F4,F8,F4 从从指指令令部部件件来来 浮浮点点寄寄存存器器FP 缓缓冲冲器器 浮浮点点操操作作 操操作作数数

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

18、标识识 MUL A, BMUL A, B ADD F2,F0,F6ADD F2,F0,F6 F8F8 F6F6 F4F4 F2F2 D D C C B B ADD1ADD1 MUL1MUL1 MUL2MUL2 ADD2ADD2 ADD3ADD3 Qi SUB SUB F6,F8,F4F6,F8,F4 F0F0 A A MUL1MUL1 寄存器寄存器 状态表状态表 从从指指令令部部件件来来 浮浮点点寄寄存存器器FP 缓缓冲冲器器 浮浮点点操操作作 操操作作数数总总线线 操操作作总总线线 1 浮浮点点加加法法器器 浮浮点点乘乘法法器器 指指令令队队列列 2 3 公公共共数数据据总总线线（CDB）

19、1 2 保保留留站站 标标识识 标标识识 MUL MUL FOFO,F2,F4,F2,F4 ADD F2,ADD F2,F0F0, ,F6F6 SUB SUB F6F6,F8,F4,F8,F4 从从指指令令部部件件来来 浮浮点点寄寄存存器器FP 缓缓冲冲器器 浮浮点点操操作作 操操作作数数总总线线 操操作作总总线线 1 浮浮点点加加法法器器 浮浮点点乘乘法法器器 指指令令队队列列 2 3 公公共共数数据据总总线线（CDB） 1 2 保保留留站站 标标识识 标标识识 MUL A, BMUL A, B ADD CADD C F8F8 F6F6 F4F4 F2F2 D D C C B B ADD1A

20、DD1 MUL1MUL1 MUL2MUL2 ADD2ADD2 ADD3ADD3 MUL1MUL1 ADD1ADD1 Qi F0F0 A A SUB D BSUB D B ADD2ADD2 SUB SUB F6,F8,F4F6,F8,F4 MUL1 从从指指令令部部件件来来 浮浮点点寄寄存存器器FP 缓缓冲冲器器 浮浮点点操操作作 操操作作数数总总线线 操操作作总总线线 1 浮浮点点加加法法器器 浮浮点点乘乘法法器器 指指令令队队列列 2 3 公公共共数数据据总总线线（CDB） 1 2 保保留留站站 标标识识 标标识识 MUL MUL FOFO,F2,F4,F2,F4 ADD F2,ADD F2

21、,F0F0, ,F6F6 SUB SUB F6F6,F8,F4,F8,F4 从从指指令令部部件件来来 浮浮点点寄寄存存器器FP 缓缓冲冲器器 浮浮点点操操作作 操操作作数数总总线线 操操作作总总线线 1 浮浮点点加加法法器器 浮浮点点乘乘法法器器 指指令令队队列列 2 3 公公共共数数据据总总线线（CDB） 1 2 保保留留站站 标标识识 标标识识 MUL A, BMUL A, B ADD MUL1, CADD MUL1, C F8F8 F6F6 F4F4 F2F2 D D C C B B ADD1ADD1 MUL1MUL1 MUL2MUL2 ADD2ADD2 ADD3ADD3 MUL1MUL

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

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

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

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

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

27、的内容。 L.DF6,34（R2） L.DF2,45（R3） MUL.DF0,F2,F4 SUB.DF8,F2,F6 DIV.DF10,F0,F6 ADD.DF6,F8,F2 4.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 指令

28、的动态调度指令的动态调度 名称名称 保留站保留站 Load1Load1 Load2Load2 Add1Add1 Add2Add2 Add3Add3 Mult1Mult1 Mult2Mult2 BusyBusy nono no no no no no no nono nono nono OpOp VjVj VkVk 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缓冲器、保留站以及寄存器状态表中的内容如下表缓冲器、保留站以及寄存器状态表

29、中的内容如下表 RegsRegsR2R23434LDLDyesyes Load1Load1 名称名称 保留站保留站 Load1Load1 Load2Load2 Add1Add1 Add2Add2 Add3Add3 Mult1Mult1 Mult2Mult2 BusyBusy yes yes no no no no no no nono nono nono OpOp LD LD VjVj VkVk QjQj QkQk A A 34+RegsR234+RegsR2 寄存器状态表寄存器状态表 F0 F2 F4 F6 F8 F10 F30F0 F2 F4 F6 F8 F10 F30 Qi Qi Loa

30、d1 Load1 loadload缓冲器、保留站以及寄存器状态表中的内容如下表缓冲器、保留站以及寄存器状态表中的内容如下表 L.D F6,34(R2) 执行执行 计算有效地址计算有效地址 名称名称 保留站保留站 Load1Load1 Load2Load2 Add1Add1 Add2Add2 Add3Add3 Mult1Mult1 Mult2Mult2 BusyBusy nono no no no no no no nono nono nono OpOp VjVj VkVk QjQj QkQk A A 寄存器状态表寄存器状态表 F0 F2 F4 F6 F8 F10 F30F0 F2 F4 F6 F8 F10 F30 Qi Qi loadload缓冲器、保留站以及寄存器状态表中的内容如