chx10_arch03_OoOIssue.ppt [兼容模式]

Transcription

1 高等计算机系统结构 Tomasulo 算法 ( 第三讲 ) 程旭 2010 年 4 月 12 日 上一讲小结 < 软件或硬件的指令级并行 (ILP) < 循环级并行最容易判定 < 软件并行性取决于程序, 如果硬件不能支持就出现冒险 < 软件相关性 / 编译器复杂性决定编译中是否能展开循环 = 存储器相关是最难判定的 < 硬件开采 ILP 动态调度 (dynamic scheduling) = 在编译时有些相关情况不能真正判定, 可以简化编译器 = 针对某一机器产生的代码可以在另一机器上有效运行 < 记分板的核心思想 : 允许暂停之后的指令提前处理 ( 译码 => 发射指令 & 读取操作数 ) = 允许乱序执行 => 乱序完成 = ID 段检测所有的结构冒险 相关和冒险 < Pipeline CPI = Ideal pipeline CPI + Structural stalls + Data hazard stalls + Control stalls < 数据相关和冒险 = 数据相关 (Data dependences) = 名称相关 (Name dependences) 反相关 (antidependence) 输出相关 (output dependence) = 数据冒险 RAW 冒险 ( 由数据相关引起 ) WAR 冒险 ( 由反相关引起 ) WAW 冒险 ( 由输出相关引起 ) = 存储器 (Memory-included) 相关和冒险 < 控制相关 Branch Exception and Interruption Registers 记分板体系结构 SCOREBOARD FP Mult FP Mult FP Divide FP Add Integer Functional Units Memory 1

2 记分板控制的四级 < 发射 指令译码并检测结构冒险 (ID1) = 按照程序的次序发射指令 ( 进行冒险检测 ) = 如果存在结构冒险暂停发射 = 如果带发射的指令与已发射但尚未完成的指令之间存在输出相关, 则暂停发射 ( 无 WAW 冒险 ) < 读操作数 等待到没有数据冒险, 再读取操作数 (ID2) = 由于将等待未完成指令写回其结果, 因而在该阶段, 可解决所有的真数据相关 (RAW 冒险 ) = 在该模型中, 无数据前递! 记分板控制的四级 ( 续一 ) < 执行 对操作数进行操作 (EX) = 接收到操作数之后, 功能部件开始执行 当产生结果之后, 它通报记分板 : 已经完成执行 < 写结果 完成执行 (WB) = 暂停直到与以前的指令没有 WAR 冒险 : 示例 : DIVDF0,F2,F4 ADDDF10,F0,F8 SUBD F8,F8,F14 CDC 6600 的记分板将暂停 SUBD 指令, 直到 ADDD 指令读取了操作数 记分板的三个主要组成部分 1. which of 4 steps the instruction is in 2. Functional unit status Indicates the state of the functional unit (FU). 9 fields for each functional unit Busy Indicates whether the unit is busy or not Op Operation to perform in the unit (e.g., + or ) Fi Destination register Fj, Fk Source-register numbers Qj, Qk Functional units producing source registers Fj, Fk Rj, Rk Flags indicating when Fj, Fk are ready 3. Indicates which functional unit will write each register, if one exists. Blank when no pending instructions will write that register CDC 6600 的记分板 < 来自编译的加速比 1.7; 手编代码的加速比 2.5, 但是由于存储速度慢 ( 没有 Cache) 限制了加速比的提高 <6600 记分板的局限性 : = 没有前递硬件 = 指令调度局限于基本块内 ( 指令窗口小 ) = 功能部件少 ( 结构冒险 ), 特别是 integer/load store 部件 = 存在结构冒险, 就暂停发射指令 = 等待到 WAR 冒险解决 = 防止 WAW 冒险 2

3 Instruction status Issue Read operands Execution complete 记分板流水线控制的细节 Wait until Not busy (FU) and not result(d) Rj and Rk Functional unit done Bookkeeping Busy(FU) yes; Op(FU) op; Fi(FU) `D ; Fj(FU) `S1 ; Fk(FU) `S2 ; Qj Result( S1 ); Qk Result(`S2 ); Rj not Qj; Rk not Qk; Result( D ) FU; Rj No; Rk No 思考 如何使处理器更快 更有效? Write result f((fj( f ) Fi(FU) or Rj( f)=no) & (Fk( f) Fi(FU) or Rk( f )=No)) f(if Qj(f)=FU then Rj(f) Yes); f(if Qk(f)=FU then Rj(f) Yes); Result(Fi(FU)) 0; Busy(FU) No q 算法 从算法到程序 qc Code example typedef enum {ADD, MULT, MINUS, DIV, MOD, BAD} op_type; qc Code example typedef enum {ADD, MULT, MINUS, DIV, MOD, BAD} op_type; 程序在计算机系统上处理 char unparse_symbol(op_type op) { switch (op) { case ADD : return '+'; case MULT: return '*'; case MINUS: return '-'; case DIV: return '/'; case MOD: return '%'; case BAD: return '?'; } } char unparse_symbol(op_type op) { switch (op) { case ADD : return '+'; case MULT: return '*'; case MINUS: return '-'; case DIV: return '/'; case MOD: return '%'; case BAD: return '?'; } } 处理器 控制 数据通路 存储器 输入 输出 3

4 静态程序流图到动态处理流图 计算机系统中的七种序列 提交序列 : 指令退离处理器 完成序列 : 指令操作完成 执行序列 : 指令开始执行 发送序列 : 指令发送到执行部件 译码序列 : 指令开始译码 取指序列 : 处理器访问存储器中的指令 存储序列 : 程序在存储器中的存放地址 按序发射的局限性 : 示例 latency 1 LD F2, 34(R2) 1 2 LD F4, 45(R3) long 3 MULTD F6, F4, F2 3 4 SUBD F8, F2, F2 1 5 DIVD F4, F2, F8 4 6 ADDD F10, F6, F4 1 按序 (In-order): 1 (2,1) 按序发射阻止了指令 4 的分发 (dispatched) 乱序发射 (Out-of-Order Issue) ALU IF ID Issue WB Fadd Fmul < 发射级的缓冲器中具有多个等待发射的指令 < 当上述缓冲器中有空位且该指令不会导致 WAR 和 WAW 冒险, 译码后就可将该指令加入到缓冲器中 < 缓冲器中任何满足 RAW 冒险要求的指令就可以被发射 ( 目前, 还是要求每个周期最多只能分发一条指令 ) 在 WB 级, 可能会多条指令同时抵达 Mem ( 下划线表明指令回写结果的周期 ) 4

5 按序发射的局限性 : 示例 latency 1 LD F2, 34(R2) 在流水线能够有多少指令? 一种指令系统体系结构中的哪些特征限制了流水线中的指令数? 2 LD F4, 45(R3) long 3 MULTD F6, F4, F 寄存器数量 4 SUBD F8, F2, F2 1 5 DIVD F4, F2, F8 4 5 程序的哪些特征限制了流水线中的指令数? 6 ADDD F10, F6, F4 1 6 Control transfers In-order: 1 (2,1) Out-of-order: 1 (2,1) 乱序执行并没有任何显著改进! 简单地单一应用乱序分发技术并不能为性能的改进提供显著支撑! 突破 ISA 中程序可用寄存器数目限制 浮点流水线通常由于寄存器数目少的原因不能满负荷运行 IBM 360 机器只有 4 个浮点寄存器 Little s Law Throughput (T) = Number in Flight (N) / Latency (L) 在保持 ISA 兼容的前提下, 能否通过微体系结构使用比 ISA 中指定寄存器更多的寄存器, 来突破上述限制? Issue Execution WB 1967 年,IBM 的 Robert Tomasulo 提出了一种通过程序执行时动态寄存器换名 (register renaming) 的独创解决方案 示例 : 4 floating point registers 8 cycles per floating point operation maximum of ½ issue per cycle! 5

6 指令级并行与换名技术 latency 1 LD F2, 34(R2) 1 2 LD F4, 45(R3) long 3 MULTD F6, F4, F2 3 4 SUBD F8, F2, F2 1 5 DIVD F4, F2, F8 4 6 ADDD F10, F6, F X 5 6 寄存器换名技术 ALU IF ID Issue WB Fadd Fmul < Decode does register renaming and adds instructions to the issue stage reorder buffer (ROB) renaming makes WAR or WAW hazards impossible Mem In-order: 1 (2,1) Out-of-order: 1 (2,1) (3,5) 任何反相关都可以通过换名来消除 ( 换名技术 额外的存储 ) 硬件能实现吗? 如何用硬件实现? < Any instruction in ROB whose RAW hazards have been satisfied can be dispatched. Out-of-order or dataflow execution 另一个动态算法 : Tomasulo 算法 < 为 IBM 360/91 设计的 在 CDC 6600 三年之后 (1966) < 目标 : 即使在没有特殊编译支持的情况下, 也能取得高性能 < IBM 360 和 CDC 6600 指令系统体系结构之间的差异 =IBM 的每条指令有两个寄存器描述符 (register specifiers), 而 CDC 6600 有三个 ; =IBM 有四个浮点寄存器, 而 CDC 6600 有八个 < 为什么要学习 Tomasulo 算法? = 由此产生了 Alpha HP 8000 MIPS Pentium II PowerPC 604, Tomasulo 算法与记分板 < 控制 & 缓冲器分布于功能部件 (FU) 与集中于记分板 ; = 功能部件缓冲器称为 保留站 (reservation stations) ; 存放未决的操作数 < 指令中的寄存器被数值或者指向保留站的指针代替 ; 这一过程称为寄存器换名 (register renaming) ; = 消除 WAR WAW 冒险 = 保留站比实际寄存器多, 因而可以完成优化编译器所不能完成的一些工作 < 结果从 RS 直接到 FU, 无需通过寄存器, 而是通过公共数据总线 (Common Data Bus) 把结果广播到所有 FU < 装入 (Load) 和存储 (Stores) 也象其他功能部件一样使用保留站 6

7 Load Buffer Common Data Bus Tomasulo 的结构图 From Memory FP Add Res. Station Operation Bus Adders FP Op Queue From Instruction Unit Reservation Station Multers Common Data Bus(CDB) FP Registers To Memory FP Mul Res. Station Store Buffer Tomasulo 算法的三段 1. Issue 从 FP Op Queue 中取出指令 如果保留站空闲 ( 无结构冒险 ), 控制机制发射指令 & 发送操作数 ( 对寄存器进行换名 ) 2. Execution 对操作数执行操作 (EX) 如果两个操作数都已就绪, 就执行 ; 如果没有就绪, 就观测公共数据总线等待所需结果 3. Write result 完成执行 (WB) 通过公共数据总线将结果写入到所有等待的部件 ; 标记保留站可用 < 正常的数据总线 : 数据 + 目的 ( 去向 总线 ) < 公共数据总线 : 数据 + 源 ( 来源 总线 ) = 64 位数据 + 4 位功能部件源地址 = 如果与期望的功能部件匹配, 就 写 ( 产生结果 ) = 进行广播 保留站的组成 Op 该部件将完成的具体操作 ( 例如, + or ) Vj, Vk 源操作数的实际数值 = 存储缓冲器 (Store buffers) 设有 V 域, 存放将存储的结果 Qj, Qk 将产生源寄存器值 ( 将写的值 ) 的保留站 注意 : 没有记分板中的就绪 (READY) 标志 ;Qj,Qk=0 ready = 存储缓冲器 (Store buffers) 中只有存放 RS 产生结果的 Qi Busy 指明保留站或 FU 处于忙状态 指明哪个功能部件将写到哪个寄存器 (Qi); 如果没有将写入寄存器的未决指令, 该域为空 Tomasulo 示例第 0 周期 Execution Write LD F6 34+ R2 Load1 No LD F2 45+ R3 Load2 No MULTD F0 F2 F4 Load3 No SUBDF8 F6 F2 DIVDF10 F0 F6 ADDDF6 F8 F2 0 0Mult1 No 0Mult2 No Time NameBusyOp Vj Vk Qj Qk LD: ADD: Mult: Divd: 2 cycles 2 cycles 10 cycles 40 cycles 0 FU 7

8 Tomasulo 示例第 1 周期 LD F6 34+ R2 1 2Load1 Yes 34+R2 LD F2 45+ R3 0Load2 No MULTD F0 F2 F4 0Load3 No SUBDF8 F6 F2 DIVDF10 F0 F6 ADDDF6 F8 F2 TimeNameBusyOp Vj Vk Qj Qk 0Mult1 No 0Mult2 No 1 FU Load1 Tomasulo 示例第 2 周期 Execution Write LD F6 34+ R2 1 1Load1 Yes 34+R2 LD F2 45+ R3 2 2Load2 Yes 45+R3 MULTD F0 F2 F4 0Load3 No SUBDF8 F6 F2 DIVDF10 F0 F6 ADDDF6 F8 F2 TimeNameBusyOp Vj Vk Qj Qk 0Mult1 No 0Mult2 No 2 FU Load2 Load1 注意 : 与 CDC6600 不同, 可以有多个 loads 被发射 ; 记分板能否改进? Tomasulo 示例第 3 周期 Instruction j k Issuecomplete Result Busy Address LD F6 34+ R Load1 Yes 34+R2 LD F2 45+ R3 2 1Load2 Yes 45+R3 MULTD F0 F2 F4 3 0Load3 No SUBDF8 F6 F2 DIVDF10 F0 F6 ADDDF6 F8 F2 TimeNameBusyOp Vj Vk Qj Qk 0Mult1 YesMULTD R(F4) Load2 0Mult2 No 3 FU Mult1 Load2 Load1 注意 : 保留站中寄存器名被 换名 ; MULT 可发射 ( 与记分板比较 ) Load1 完成 ; 哪些指令在等待 Load1? Tomasulo 示例第 4 周期 Instruction j k Issuecomplete Result Busy Address LD F6 34+ R Load1 No LD F2 45+ R Load2 Yes 45+R3 MULTD F0 F2 F4 3 0Load3 No SUBDF8 F6 F2 4 DIVDF10 F0 F6 ADDDF6 F8 F2 TimeNameBusyOp Vj Vk Qj Qk 0Add1 Yes SUBDM(34+R2) Load2 0Mult1 Yes MULTD R(F4) Load2 0Mult2 No 4 FU Mult1 Load2 M(34+R2) Add1 Load2 将完成 ; 哪些指令在等待 Load2? 8

9 Tomasulo 示例第 5 周期 Execution Write MULTD F0 F2 F4 3 Load3 No SUBDF8 F6 F2 4 DIVDF10 F0 F6 5 ADDDF6 F8 F2 TimeNameBusyOp Vj Vk Qj Qk 2Add1 Yes SUBDM(34+R2) M(45+R3) 10 Mult1 Yes MULTDM(45+R3) R(F4) 0Mult2 Yes DIVD M(34+R2) Mult1 Clock F0 F2 F4 F6 F8 F10 F12... F30 5 FU Mult1 M(45+R3) M(34+R2) Add1 Mult2 Tomasulo 示例第 6 周期 Execution Write MULTD F0 F2 F4 3 Load3 No SUBDF8 F6 F2 4 DIVDF10 F0 F6 5 ADDDF6 F8 F2 6 Time NameBusyOp Vj Vk Qj Qk 1Add1 Yes SUBDM(34+R2) M(45+R3) 0Add2 Yes ADDD M(45+R3) Add1 9Mult1 Yes MULTDM(45+R3) R(F4) 0Mult2 Yes DIVD M(34+R2) Mult1 6 FU Mult1 M(45+R3) Add2 Add1 Mult2 发射 ADDD Tomasulo 示例第 7 周期 Execution Write MULTD F0 F2 F4 3 Load3 No SUBDF8 F6 F2 4 7 DIVDF10 F0 F6 5 ADDDF6 F8 F2 6 Time Name BusyOp Vj Vk Qj Qk 0Add1 Yes SUBDM(34+R2) M(45+R3) 0Add2 Yes ADDD M(45+R3) Add1 8Mult1 Yes MULTDM(45+R3) R(F4) 0Mult2 Yes DIVD M(34+R2) Mult1 7 FU Mult1 M(45+R3) Add2 Add1 Mult2 Add1 完成 ; 哪些指令在等待 Add1? Tomasulo 示例第 8 周期 Execution Write MULTD F0 F2 F4 3 Load3 No SUBDF8 F6 F DIVDF10 F0 F6 5 ADDDF6 F8 F2 6 TimeNameBusyOp Vj Vk Qj Qk 2Add2 Yes ADDDM()-M() M(45+R3) 7Mult1 Yes MULTDM(45+R3) R(F4) 0Mult2 Yes DIVD M(34+R2) Mult1 Clock F0 F2 F4 F6 F8 F10 F12... F30 8 FU Mult1 M(45+R3) Add2 M()-M() Mult2 9

10 Tomasulo 示例第 9 周期 MULTD F0 F2 F4 3 Load3 No SUBDF8 F6 F DIVDF10 F0 F6 5 ADDDF6 F8 F2 6 TimeNameBusyOp Vj Vk Qj Qk 1Add2 Yes ADDDM()-M() M(45+R3) 6Mult1 Yes MULTDM(45+R3) R(F4) 0Mult2 Yes DIVD M(34+R2) Mult1 9 FU Mult1 M(45+R3) Add2 M()-M() Mult2 Button 3 Button4 Button5 Button 6 Tomasulo 示例第 10 周期 Execution Write Instruction j k Issuecomplete Result Busy Address MULTD F0 F2 F4 3 Load3 No SUBDF8 F6 F DIVDF10 F0 F6 5 ADDDF6 F8 F TimeNameBusyOp Vj Vk Qj Qk 0Add2 Yes ADDDM()-M() M(45+R3) 5Mult1 Yes MULTDM(45+R3) R(F4) 0Mult2 Yes DIVD M(34+R2) Mult1 10 FU Mult1 M(45+R3) Add2 M()-M() Mult2 Add2 完成 ; 哪些指令在等待 Add2? Tomasulo 示例第 11 周期 Execution Write Instruction j k Issuecomplete Result Busy Address MULTD F0 F2 F4 3 Load3 No SUBDF8 F6 F DIVDF10 F0 F6 5 ADDDF6 F8 F TimeNameBusyOp Vj Vk Qj Qk 4Mult1 Yes MULTDM(45+R3) R(F4) 0Mult2 Yes DIVD M(34+R2) Mult1 Clock F0 F2 F4 F6 F8 F10 F12... F30 11 FU Mult1 M(45+R3) (M-M)+M()M()-M()Mult2 Tomasulo 示例第 12 周期 Execution Write MULTD F0 F2 F4 3 Load3 No SUBDF8 F6 F DIVDF10 F0 F6 5 ADDDF6 F8 F TimeNameBusyOp Vj Vk Qj Qk 3Mult1 Yes MULTDM(45+R3) R(F4) 0Mult2 Yes DIVD M(34+R2) Mult1 12 FU Mult1 M(45+R3) (M-M)+M()M()-M() Mult2 注意 : 所有短周期指令都已经完成 ADDD 在该周期写结果 10

11 Tomasulo 示例第 13 周期 Execution Write Instruction j k Issuecomplete Result Busy Address MULTD F0 F2 F4 3 Load3 No SUBDF8 F6 F DIVDF10 F0 F6 5 ADDDF6 F8 F TimeNameBusyOp Vj Vk Qj Qk 2Mult1 Yes MULTDM(45+R3) R(F4) 0Mult2 Yes DIVD M(34+R2) Mult1 Clock F0 F2 F4 F6 F8 F10 F12... F30 13 FU Mult1 M(45+R3) (M-M)+M()M()-M() Mult2 Tomasulo 示例第 14 周期 Execution Write MULTD F0 F2 F4 3 Load3 No SUBDF8 F6 F DIVDF10 F0 F6 5 ADDDF6 F8 F TimeNameBusyOp Vj Vk Qj Qk 1Mult1 Yes MULTDM(45+R3) R(F4) 0Mult2 Yes DIVD M(34+R2) Mult1 14 FU Mult1 M(45+R3) (M-M)+M()M()-M()Mult2 Tomasulo 示例第 15 周期 Execution Write MULTD F0 F2 F Load3 No SUBDF8 F6 F DIVDF10 F0 F6 5 ADDDF6 F8 F Time Name BusyOp Vj Vk Qj Qk 0Mult1 Yes MULTDM(45+R3) R(F4) 0Mult2 Yes DIVD M(34+R2) Mult1 15 FU Mult1 M(45+R3) (M-M)+M()M()-M() Mult2 Mult1 completing; what is waiting for it? Tomasulo 示例第 16 周期 Execution Write MULTD F0 F2 F Load3 No SUBDF8 F6 F DIVDF10 F0 F6 5 ADDDF6 F8 F Time NameBusyOp Vj Vk Qj Qk 0Mult1 No 40 Mult2 Yes DIVD M*F4 M(34+R2) 16 FU M*F4 M(45+R3) (M-M)+M()M()-M() Mult2 注意 : 只有除法指令没有完成 11

12 Tomasulo 示例第 55 周期 Execution Write MULTD F0 F2 F Load3 No SUBDF8 F6 F DIVDF10 F0 F6 5 ADDDF6 F8 F Time NameBusyOp Vj Vk Qj Qk 0Mult1 No 1Mult2 Yes DIVD M*F4 M(34+R2) 55 FU M*F4 M(45+R3) (M-M)+M()M()-M() Mult2 Tomasulo 示例第 56 周期 Execution Write MULTD F0 F2 F Load3 No SUBDF8 F6 F DIVDF10 F0 F ADDDF6 F8 F Time NameBusyOp Vj Vk Qj Qk 0Mult1 No 0Mult2 Yes DIVD M*F4 M(34+R2) 56 FU M*F4 M(45+R3) (M-M)+M()M()-M() Mult2 Mult 2 完成 Tomasulo 示例第 57 周期 Execution Write MULTD F0 F2 F Load3 No SUBDF8 F6 F DIVDF10 F0 F ADDDF6 F8 F Time NameBusyOp Vj Vk Qj Qk 0Mult1 No 0Mult2 No 57 FU M*F4 M(45+R3) 也是, 按序发送 乱序执行 乱序完成 (M-M)+M()M()-M() M*F4/M 与记分板的第 62 周期相比 Read Execution Write Instruction j k Issueoperands complete Result LD F2 45+ R MULTD F0 F2 F SUBDF8 F6 F DIVDF10 F0 F ADDDF6 F8 F Functional unit status dest S1 S2 FU for jfu for kfj? Fk? Integer No Mult1 No Mult2 No Add No 0Divide No 62 FU CDC6600 的记分板为什么需要更长的时间? 12

13 Tomasulo 与记分板 (IBM 360/91 与 CDC 6600) 流水化的功能部件 (6 load, 3 store, 3 +, 2 x/ ) 窗口大小 : 14 指令结构冒险暂停发射 WAR: 通过换名避免 WAW: 通过换名避免从 FU 广播结果控制 : 保留站 多功能部件 (1 load/store, 1 +, 2 x, 1 ) 5 指令相同 暂停完成暂停发射 写 / 读寄存器集中控制的记分板 Tomasulo 算法的缺点 < 复杂 = 360/91 MIPS IBM PPC620 的延迟? < 需要大量高速的相联存储 (associative buffer) < 公共数据总线将成为制约性能增长的瓶颈 = 每个 CDB 必须广播到多个功能部件单元 大容量 写操作密集 = 每个周期可以同时完成的功能部件数量可能由于单总线而受限 ( 最坏情况为 1 )! 多个 CDB => 为完成并行相联存储, 功能部件 FU 需要更复杂的逻辑控制 Tomasulo 循环示例 Loop: LD F0 0 R1 MULTD F4 F0 F2 SD F4 0 R1 SUBI R1 R1 #8 BNEZ R1 Loop < 假设乘法需 4 个周期 < 假设第一次 load 需要 8 个周期 (cache 失效 ), 第二次 load 需要 1 个周期 ( 命中 ) < 为了简明, 将示意 SUBI BNEZ 的周期数 < 实际上, 整数指令先行 0 80 Qi 循环示例第 0 周期 LD F0 0 R1 1 Load1 No MULTD F4 F0 F2 1 Load2 No SD F4 0 R1 1 Load3 No Qi LD F0 0 R1 2 Store1 No MULTD F4 F0 F2 2 Store2 No SD F4 0 R1 2 Store3No TimeNameBusyOp Vj Vk Qj Qk Code: MULTD F4 F0 F2 0Mult1 No SUBIR1 R1#8 0Mult2 No BNEZR1 Loop 13

14 循环示例第 1 周期 LD F0 0 R1 1 1 Load1 Yes 80 MULTD F4 F0 F2 1 Load2 No SD F4 0 R1 1 Load3 No Qi LD F0 0 R1 2 Store1 No MULTD F4 F0 F2 2 Store2 No SD F4 0 R1 2 Store3 No TimeNameBusyOp Vj Vk Qj Qk Code: MULTD F4 F0 F2 0Mult1 No SUBIR1 R1#8 0Mult2 No BNEZR1 Loop 1 80 Qi Load1 循环示例第 2 周期 Instruction j k iteration Issue completeresult Busy Address LD F0 0R1 1 1 Load1 Yes 80 MULTD F4 F0 F2 1 2 Load2 No SD F4 0R1 1 Load3 No Qi LD F0 0R1 2 Store1 No MULTD F4 F0 F2 2 Store2 No SD F4 0R1 2 Store3 No TimeNameBusyOp Vj Vk Qj Qk Code: MULTD F4 F0 F2 0Mult1 Yes MULTD R(F2) Load1 SUBIR1 R1 #8 0Mult2 No BNEZR1 Loop 2 80 Qi Load1 Mult1 循环示例第 3 周期 LD F0 0R1 1 1 Load1 Yes 80 MULTD F4 F0 F2 1 2 Load2 No SD F4 0R1 1 3 Load3 No Qi LD F0 0R1 2 Store1 Yes 80 Mult1 MULTD F4 F0 F2 2 Store2 No SD F4 0R1 2 Store3No TimeNameBusyOp Vj Vk Qj Qk Code: MULTD F4 F0 F2 0Mult1 Yes MULTD R(F2) Load1 SUBIR1 R1#8 0Mult2 No BNEZR1 Loop 3 80 Qi Load1 Mult1 循环示例第 4 周期 Instruction j k iteration Issue completeresult Busy Address LD F0 0R1 1 1 Load1 Yes 80 MULTD F4 F0 F2 1 2 Load2 No SD F4 0R1 1 3 Load3 No Qi LD F0 0R1 2 Store1 Yes 80 Mult1 MULTD F4 F0 F2 2 Store2 No SD F4 0R1 2 Store3 No TimeNameBusyOp Vj Vk Qj Qk Code: MULTD F4 F0 F2 0Mult1 Yes MULTD R(F2) Load1 SUBIR1 R1 #8 0Mult2 No BNEZR1 Loop 4 72 Qi Load1 Mult1 注意 : 隐含的换名功能动态建立起 数据流 图 注意 : 发送 SUB 指令 14

15 循环示例第 5 周期 LD F0 0R1 1 1 Load1 Yes 80 MULTD F4 F0 F2 1 2 Load2 No SD F4 0R1 1 3 Load3 No Qi LD F0 0R1 2 Store1 Yes 80 Mult1 MULTD F4 F0 F2 2 Store2 No SD F4 0R1 2 Store3No TimeName BusyOp Vj Vk Qj Qk Code: MULTD F4 F0 F2 0Mult1 Yes MULTD R(F2) Load1 SUBIR1 R1#8 0Mult2 No BNEZR1 Loop 5 72 Qi Load1 Mult1 循环示例第 6 周期 LD F0 0R1 1 1 Load1 Yes 80 MULTD F4 F0F2 1 2 Load2 Yes 72 SD F4 0R1 1 3 Load3 No Qi LD F0 0R1 2 6 Store1 Yes 80 Mult1 MULTD F4 F0 F2 2 Store2 No SD F4 0R1 2 Store3 No TimeNameBusyOp Vj Vk Qj Qk Code: MULTD F4 F0 F2 0Mult1 Yes MULTD R(F2) Load1 SUBIR1 R1#8 0Mult2 No BNEZR1 Loop 6 72 Qi Load2 Mult1 注意 : F0 一直看不到 Load1 的结果 注意 : 处理 BNEZ 指令 循环示例第 7 周期 LD F0 0R1 1 1 Load1 Yes 80 MULTD F4 F0 F2 1 2 Load2 Yes 72 SD F4 0R1 1 3 Load3 No Qi LD F0 0R1 2 6 Store1 Yes 80 Mult1 MULTD F4 F0 F2 2 7 Store2 No SD F4 0R1 2 Store3No TimeName BusyOp Vj Vk Qj Qk Code: MULTD F4 F0 F2 0Mult1 Yes MULTD R(F2) Load1 SUBIR1 R1#8 0Mult2 Yes MULTD R(F2) Load2 BNEZR1 Loop 7 72 Qi Load2 Mult2 Note: MULT2 has no registers names in RS 循环示例第 8 周期 LD F0 0R1 1 1 Load1 Yes 80 MULTD F4 F0 F2 1 2 Load2 Yes 72 SD F4 0R1 1 3 Load3 No Qi LD F0 0R1 2 6 Store1 Yes 80 Mult1 MULTD F4 F0 F2 2 7 Store2 Yes 72 Mult2 SD F4 0R1 2 8 Store3No TimeName BusyOp Vj Vk Qj Qk Code: MULTD F4 F0 F2 0Mult1 Yes MULTD R(F2) Load1 SUBIR1 R1#8 0Mult2 Yes MULTD R(F2) Load2 BNEZR1 Loop 8 72 Qi Load2 Mult2 15

16 循环示例第 9 周期 LD F0 0R Load1 Yes 80 MULTD F4 F0F2 1 2 Load2 Yes 72 SD F4 0R1 1 3 Load3 No Qi LD F0 0R1 2 6 Store1 Yes 80 Mult1 MULTD F4 F0 F2 2 7 Store2 Yes 72 Mult2 SD F4 0R1 2 8 Store3 No TimeNameBusyOp Vj Vk Qj Qk Code: MULTD F4 F0 F2 0Mult1 Yes MULTD R(F2) Load1 SUBIR1 R1#8 0Mult2 Yes MULTD R(F2) Load2 BNEZR1 Loop Clock R1 F0 F2 F4 F6 F8 F10F12... F Qi Load2 Mult2 Load1 完成, 注意等待其结果的指令! 循环示例第 10 周期 LD F0 0R Load1 No MULTD F4 F0F2 1 2 Load2 Yes 72 SD F4 0R1 1 3 Load3 No Qi LD F0 0R Store1 Yes 80 Mult1 MULTD F4 F0 F2 2 7 Store2 Yes 72 Mult2 SD F4 0R1 2 8 Store3No TimeName BusyOp Vj Vk Qj Qk Code: MULTDF4 F0 F2 4Mult1 Yes MULTD M(80)R(F2) SUBI R1 R1 #8 0Mult2 Yes MULTD R(F2) Load2 BNEZ R1 Loop Qi Load2 Mult2 Load2 Load1 完成, 注意等待其结果的指令 注意 : 发送 SUB 指令 循环示例第 11 周期 Instruction j k iteration Issue completeresult Busy Address LD F0 0R Load1 No MULTD F4 F0 F2 1 2 Load2 No SD F4 0R1 1 3 Load3 Yes 64 Qi LD F0 0R Store1 Yes 80 Mult1 MULTD F4 F0 F2 2 7 Store2 Yes 72 Mult2 SD F4 0R1 2 8 Store3 No TimeNameBusyOp Vj Vk Qj Qk Code: MULTDF4 F0 F2 3Mult1 Yes MULTD M(80)R(F2) SUBI R1 R1 #8 4Mult2 Yes MULTD M(72)R(F2) BNEZ R1 Loop Qi Load3 Mult2 循环示例第 12 周期 LD F0 0R Load1 No MULTD F4 F0 F2 1 2 Load2 No SD F4 0R1 1 3 Load3 Yes 64 Qi LD F0 0R Store1 Yes 80 Mult1 MULTD F4 F0 F2 2 7 Store2 Yes 72 Mult2 SD F4 0R1 2 8 Store3No TimeName BusyOp Vj Vk Qj Qk Code: 为什么不能发送第三次迭代的乘法? MULTDF4 F0 F2 2Mult1 Yes MULTD M(80)R(F2) SUBI R1 R1 #8 3Mult2 Yes MULTD M(72)R(F2) BNEZ R1 Loop Qi Load3 Mult2 16

17 循环示例第 13 周期 LD F0 0R Load1 No MULTD F4 F0 F2 1 2 Load2 No SD F4 0R1 1 3 Load3 Yes 64 Qi LD F0 0R Store1 Yes 80 Mult1 MULTD F4 F0 F2 2 7 Store2 Yes 72 Mult2 SD F4 0R1 2 8 Store3 No TimeNameBusyOp Vj Vk Qj Qk Code: MULTDF4 F0 F2 1Mult1 Yes MULTD M(80)R(F2) SUBI R1 R1 #8 2Mult2 Yes MULTD M(72)R(F2) BNEZ R1 Loop Qi Load3 Mult2 循环示例第 14 周期 LD F0 0R Load1 No MULTD F4 F0 F Load2 No SD F4 0R1 1 3 Load3 Yes 64 Qi LD F0 0R Store1 Yes 80 Mult1 MULTD F4 F0 F2 2 7 Store2 Yes 72 Mult2 SD F4 0R1 2 8 Store3No TimeNameBusyOp Vj Vk Qj Qk Code: MULTDF4 F0 F2 0Mult1 Yes MULTD M(80)R(F2) SUBI R1 R1 #8 1Mult2 Yes MULTD M(72)R(F2) BNEZ R1 Loop Qi Load3 Mult2 Mult1 完成 循环示例第 15 周期 LD F0 0R Load1 No MULTD F4 F0 F Load2 No SD F4 0R1 1 3 Load3 Yes 64 Qi LD F0 0R Store1 Yes 80 M(80)*R(F2) MULTD F4 F0 F Store2 Yes 72 Mult2 SD F4 0R1 2 8 Store3No TimeNameBusyOp Vj Vk Qj Qk Code: MULTDF4 F0 F2 0Mult1 No SUBI R1 R1 #8 0Mult2 Yes MULTD M(72)R(F2) BNEZ R1 Loop Qi Load3 Mult2 Mult2 完成 循环示例第 16 周期 LD F0 0R Load1 No MULTD F4 F0 F Load2 No SD F4 0R1 1 3 Load3 Yes 64 Qi LD F0 0R Store1 Yes 80 M(80)*R(F2) MULTD F4 F0 F Store2 Yes 72 M(72)*R(72) SD F4 0R1 2 8 Store3No TimeName BusyOp Vj Vk Qj Qk Code: MULTDF4 F0 F2 0Mult1 Yes MULTD R(F2) Load3 SUBI R1 R1 #8 0Mult2 No BNEZ R1 Loop Qi Load3 Mult1 17

18 循环示例第 17 周期 LD F0 0R Load1 No MULTD F4 F0 F Load2 No SD F4 0R1 1 3 Load3 Yes 64 Qi LD F0 0R Store1 Yes 80 M(80)*R(F2) MULTD F4 F0 F Store2 Yes 72 M(72)*R(72) SD F4 0R1 2 8 Store3Yes 64 Mult1 TimeName BusyOp Vj Vk Qj Qk Code: MULTDF4 F0 F2 0Mult1 Yes MULTD R(F2) Load3 SUBI R1 R1 #8 0Mult2 No BNEZ R1 Loop Qi Load3 Mult1 循环示例第 18 周期 LD F0 0R Load1 No MULTD F4 F0F Load2 No SD F4 0R Load3 Yes 64 Qi LD F0 0R Store1 Yes 80 M(80)*R(F2) MULTD F4 F0 F Store2 Yes 72 M(72)*R(72) SD F4 0R1 2 8 Store3 Yes 64 Mult1 TimeNameBusyOp Vj Vk Qj Qk Code: MULTDF4 F0 F2 0Mult1 Yes MULTD R(F2) Load3 SUBI R1 R1 #8 0Mult2 No BNEZ R1 Loop Qi Load3 Mult1 循环示例第 19 周期 LD F0 0R Load1 No MULTD F4 F0 F Load2 No SD F4 0R Load3 Yes 64 Qi LD F0 0R Store1 No MULTD F4 F0 F Store2 Yes 72 M(72)*R(72) SD F4 0R1 2 8 Store3Yes 64 Mult1 TimeName BusyOp Vj Vk Qj Qk Code: MULTDF4 F0 F2 0Mult1 Yes MULTD R(F2) Load3 SUBI R1 R1 #8 0Mult2 No BNEZ R1 Loop Qi Load3 Mult1 循环示例第 20 周期 LD F0 0R Load1 No MULTD F4 F0F Load2 No SD F4 0R Load3 Yes 64 Qi LD F0 0R Store1 No MULTD F4 F0 F Store2 Yes 72 M(72)*R(72) SD F4 0R Store3 Yes 64 Mult1 TimeNameBusyOp Vj Vk Qj Qk Code: MULTDF4 F0 F2 0Mult1 Yes MULTD R(F2) Load3 SUBI R1 R1 #8 0Mult2 No BNEZ R1 Loop Qi Load3 Mult1 18

19 循环示例第 21 周期 Instruction j k iteration Issue completeresult Busy Address LD F0 0R Load1 No MULTD F4 F0 F Load2 No SD F4 0R Load3 Yes 64 Qi LD F0 0R Store1 No MULTD F4 F0 F Store2 No SD F4 0R Store3 Yes 64 Mult1 TimeNameBusyOp Vj Vk Qj Qk Code: MULTDF4 F0 F2 0Mult1 Yes MULTD R(F2) Load3 SUBI R1 R1 #8 0Mult2 No BNEZ R1 Loop Qi Load3 Mult1 寄存器换名技术 ALU IF ID Issue WB Fadd Fmul <Decode does register renaming and adds instructions to the issue stage reorder buffer (ROB) renaming makes WAR or WAW hazards impossible <Any instruction in ROB whose RAW hazards have been satisfied can be dispatched. Out-of-order or dataflow execution Mem 数据流 (Dataflow) 执行 ptr 2 next to deallocate prt 1 next available Instruction slot is candidate for execution when: It holds a valid instruction ( use bit is set) It has not already started execution ( exec bit is clear) Both operands are available (p1 and p2 are set) Ins# use exec op p1 src1 p2 src2 Reorder buffer t 1 t 2... t n v1 换名 & 乱序发射 : 示例 Renaming table p data F1 F2 v1 t1 F3 F4 t2t5 F5 F6 t3 F7 F8 v4 t4 data / t i 1 LD F2, 34(R2) 2 LD F4, 45(R3) 3 MULTD F6, F4, F2 4 SUBD F8, F2, F2 5 DIVD F4, F2, F8 6 ADDD F10, F6, F4 Reorder buffer Ins# use exec op p1 src1 p2 src LD LD MUL 10 v2 t2 1 v SUB 1 v1 1 v DIV 1 v1 01 t4 v4 t 1 t 2 t 3 t 4 t 5.. When are names in sources replaced by data? Whenever an FU produces data When can a name be reused? Whenever an instruction completes 19

20 数据驱动 (Data-Driven) 执行 Renaming table & reg file Reorder buffer Replacing the tag by its value is an expensive operation Ins# use exec op p1 src1 p2 src2 t 1 t 2.. t n Load Unit FU FU Store Unit Instruction template (i.e., tag t) is allocated by the Decode stage, which also stores the tag in the reg file When an instruction completes, its tag is deallocated < t, result > 简化分配 / 回收 Simplifying Allocation/Deallocation ptr 2 next to deallocate prt 1 next available Ins# use exec op p1 src1 p2 src2 Reorder buffer Instruction buffer is managed circularly exec bit is set when instruction begins execution When an instruction completes, its use bit is marked free ptr 2 is incremented only if the use bit is marked free t 1 t 2... t n Tomasulo 算法小结 < 保留站 : 换名到巨大的寄存器空间 + 缓存源操作数 = 防止寄存器成为性能瓶颈 = 防止记分板中的 WAR WAW 冒险 = 具有硬件动态完成循环展开的功能 < 不局限在基本块内 ( 整数部件可以先行, 跨越基本块 ) < 对于降低 cache 失效开销有利 < 对后续机型的影响 : = 动态调度 = 寄存器换名 = Load/store 别名分析 < 360/91 的后续包括 :Pentium III PowerPC 604 MIPS R10000 HP-PA 8000 Alpha 等等 有效性 (Effectiveness)? Renaming and Out-of-order execution was first implemented in 1969 in IBM 360/91 but did not show up in the subsequent models until mid-nineties. Why? Reasons 1. Effective on a very small class of programs 2. Memory latency a much bigger problem 3. Exceptions not precise! One more problem needed to be solved Control transfers 20

21 精确中断 (Precise Interrupts) It must appear as if an interrupt is taken between two instructions (say I i and I i+1 ) the effect of all instructions up to and including I i is totally complete no effect of any instruction after I i has taken place The interrupt handler either aborts the program or restarts it at I i+1. 中断的影响乱序完成 (Out-of-order Completion) I 1 DIVD f6, f6, f4 I 2 LD f2, 45(r3) I 3 MULTD f0, f2, f4 I 4 DIVD f8, f6, f2 I 5 SUBD f10, f0, f6 I 6 ADDD f6, f8, f2 out-of-order comp restore f2 restore f10 Consider interrupts Precise interrupts are difficult to implement at high speed -want to start execution of later instructions before exception checks finished on earlier instructions 精确中断与推测式之间的关系 < Speculation is a form of guessing = Branch prediction, data prediction = If we speculate and are wrong, need to back up and restart execution to point at which we predicted incorrectly = This is exactly same as precise exceptions! < Branch prediction is a very important = Need to take our best shot at predicting branch direction. = If we issue multiple instructions per cycle, lose lots of potential instructions otherwise: Consider 4 instructions per cycle If take single cycle to decide on branch, waste from 4-7 instruction slots! < Technique for both precise interrupts/exceptions and speculation: in-order completion or commit = This is why reorder buffers in all new processors 硬件对精确中断的支持 < 重排序缓冲器 (Reorder Buffer:ROB) 的概念 : = 按 FIFO 的次序存放指令, 即 指令发射的次序每个 ROB 的表项包括 :PC 目标寄存器 结果 意外状态 = 当指令执行完成, 将结果放在 ROB 向其他介于读操作数 执行 完成和提交的指令提供操作数 就像保留站将结果用重排序缓冲器 ( 就像保留站 ) 的编号来标记 = 指令提交 (commit) 将 ROB 顶部的数值放到寄存器中 = 这样, 就易于实现错误预测路径或一次意外中的推测 FP Op Queue Res Stations FP Adder Commit path Reorder Buffer FP Regs Res Stations FP Adder 21

22 ptr 2 next to commit ptr 1 next available 支持精确中断的 ROB 扩展 Inst# use exec op p1 src1 p2 src2 pd dest data cause Reorder buffer add <pd, dest, data, cause> fields in the instruction template commit instructions to reg file and memory in program order buffers can be maintained circularly on exception, clear reorder buffer by resetting ptr 1 =ptr 2 (stores must wait for commit before updating memory) Register File (now holds only committed state) Reorder buffer 回卷和换名 Rollback and Renaming Ins# use exec op p1 src1 p2 src2 pd dest data Load Unit FU FU FU Store Unit Commit < t, result > Register file does not contain renaming tags any more. How does the decode stage find the tag of a source register? Search the dest field in the reorder buffer t 1 t 2.. t n Rename Table Reorder buffer 换名表 (Renaming Table) r 1 t v r 2 Load Unit tag valid bit FU FU FU Register File Ins# use exec op p1 src1 p2 src2 pd dest data Store Unit Commit < t, result > Renaming table is a cache to speed up register name look up. It needs to be cleared after each exception taken. When else are valid bits cleared? Control transfers t 1 t 2.. t n 转移开销 (Branch Penalty) Next fetch started How many instructions need to be killed on a misprediction? Modern processors may have > 10 pipeline stages between next pc calculation and branch resolution! Branch executed PC I-cache Fetch Buffer Issue Buffer Func. Units Result Buffer Arch. State Fetch Decode Execute Commit 22

23 转移之间的平均指令运行长度 Average dynamic instruction mix from SPEC92: SPECint92 SPECfp92 ALU 39 % 13 % FPU Add 20 % FPU Mult 13 % load 26 % 23 % store 9 % 9 % branch 16 % 8 % other 10 % 12 % SPECint92: SPECfp92: compress, eqntott, espresso, gcc, li doduc, ear, hydro2d, mdijdp2, su2cor What is the average run length between branches? 显式寄存器换名 < Make use of a physical register file that is larger than number of registers specified by ISA < Key insight: Allocate a new physical destination register for every instruction that writes = Very similar to a compiler transformation called Static Single Assignment (SSA) form but in hardware! = Removes all chance of WAR or WAW hazards = Like Tomasulo, good for allowing full out-of-order completion = Like hardware-based dynamic compilation? < Mechanism? Keep a translation table: = ISA register physical register mapping = When register written, replace entry with new register from freelist. = Physical register becomes free when not used by any active instructions 显式寄存器换名的优点 < Decouples renaming from scheduling: = Pipeline can be exactly like standard DLX pipeline (perhaps with multiple operations issued per cycle) = Or, pipeline could be tomasulo-like or a scoreboard, etc. = Standard forwarding or bypassing could be used < Allows data to be fetched from single register file = No need to bypass values from reorder buffer = This can be important for balancing pipeline < Many processors use a variant of this technique: = R10000, Alpha 21264, HP PA8000 < Another way to get precise interrupt points: = All that needs to be undone for precise break point is to undo the table mappings = This provides an interesting mix between reorder buffer and future file Results are written immediately back to register file Registers names are freed in program order (by ROB) 能够在记分板中使用显式寄存器换名策略 Registers Rename Table SCOREBOARD FP Mult FP Mult FP Divide FP Add Integer Functional Units Memory 23

24 采用显式寄存器换名策略的记分板控制 < Issue decode instructions & check for structural hazards & allocate new physical register for result = Instructions issued in program order (for hazard checking) = Don t issue if no free physical registers = Don t issue if structural hazard < Read operands wait until no hazards, read operands = All real dependencies (RAW hazards) resolved in this stage, since we wait for instructions to write back data. < Execution operate on operands = The functional unit begins execution upon receiving operands. When the result is ready, it notifies the scoreboard < Write result finish execution < Note: No checks for WAR or WAW hazards! Scoreboard With Explicit : Renaming Read Exec Write LD F6 34+ R2 LD F2 45+ R3 MULTD F0 F2 F4 SUBD F8 F6 F2 DIVD F10 F0 F6 ADDD F6 F8 F2 Int1 Int2 Mult1 Add Divide No No No No No FU P0 P2 P4 P6 P8 P10 P12 P30 Initialized Rename Table Renamed Scoreboard 1 : Read Exec Write LD F6 34+ R2 1 LD F2 45+ R3 MULTD F0 F2 F4 SUBD F8 F6 F2 DIVD F10 F0 F6 ADDD F6 F8 F2 Int1 Yes Load P32 R2 Yes Mult1 No Add No Divide No 1 FU P0 P2 P4 P32 P8 P10 P12 P30 Each instruction allocates free register Similar to single-assignment compiler transformation Renamed Scoreboard 2 : Read Exec Write LD F6 34+ R2 1 2 LD F2 45+ R3 2 MULTD F0 F2 F4 SUBD F8 F6 F2 DIVD F10 F0 F6 ADDD F6 F8 F2 Int1 Yes Load P32 R2 Yes Int2 Yes Load P34 R3 Yes Mult1 No Add No Divide No 2 FU P0 P34 P4 P32 P8 P10 P12 P30 24

25 Renamed Scoreboard 3 : Read Exec Write LD F6 34+ R LD F2 45+ R3 2 3 MULTD F0 F2 F4 3 SUBD F8 F6 F2 DIVD F10 F0 F6 ADDD F6 F8 F2 Int1 Yes Load P32 R2 Yes Int2 Yes Load P34 R3 Yes Mult1 Yes Multd P36 P34 P4 Yes Add No Divide No 3 FU P36 P34 P4 P32 P8 P10 P12 P30 Renamed Scoreboard 4 : Read Exec Write LD F2 45+ R MULTD F0 F2 F4 3 SUBD F8 F6 F2 4 DIVD F10 F0 F6 ADDD F6 F8 F2 Int2 Yes Load P34 R3 Yes Mult1 Yes Multd P36 P34 P4 Yes Add Yes Sub P38 P32 P34 Int2 Yes No Divide No 4 FU P36 P34 P4 P32 P38 P10 P12 P30 Renamed Scoreboard 5 : Read Exec Write LD F2 45+ R MULTD F0 F2 F4 3 SUBD F8 F6 F2 4 DIVD F10 F0 F6 5 ADDD F6 F8 F2 Mult1 Yes Multd P36 P34 P4 Yes Yes Add Yes Sub P38 P32 P34 Yes Yes Divide Yes Divd P40 P36 P32 Mult1 No Yes 5 FU P36 P34 P4 P32 P38 P40 P12 P30 Renamed Scoreboard 6 : Read Exec Write LD F2 45+ R MULTD F0 F2 F4 3 6 SUBD F8 F6 F2 4 6 DIVD F10 F0 F6 5 ADDD F6 F8 F2 10Mult1 Yes Multd P36 P34 P4 Yes Yes 2Add Yes Sub P38 P32 P34 Yes Yes Divide Yes Divd P40 P36 P32 Mult1 No Yes 6 FU P36 P34 P4 P32 P38 P40 P12 P30 25

26 Renamed Scoreboard 7 : Read Exec Write LD F2 45+ R MULTD F0 F2 F4 3 6 SUBD F8 F6 F2 4 6 DIVD F10 F0 F6 5 ADDD F6 F8 F2 9Mult1 Yes Multd P36 P34 P4 Yes Yes 1Add Yes Sub P38 P32 P34 Yes Yes Divide Yes Divd P40 P36 P32 Mult1 No Yes 7 FU P36 P34 P4 P32 P38 P40 P12 P30 Renamed Scoreboard 8 : Read Exec Write LD F2 45+ R MULTD F0 F2 F4 3 6 SUBD F8 F6 F DIVD F10 F0 F6 5 ADDD F6 F8 F2 8Mult1 Yes Multd P36 P34 P4 Yes Yes 0Add Yes Sub P38 P32 P34 Yes Yes Divide Yes Divd P40 P36 P32 Mult1 No Yes 8 FU P36 P34 P4 P32 P38 P40 P12 P30 Renamed Scoreboard 9 : Read Exec Write LD F2 45+ R MULTD F0 F2 F4 3 6 SUBD F8 F6 F DIVD F10 F0 F6 5 ADDD F6 F8 F2 7Mult1 Yes Multd P36 P34 P4 Yes Yes Add No Divide Yes Divd P40 P36 P32 Mult1 No Yes 9 FU P36 P34 P4 P32 P38 P40 P12 P30 Renamed Scoreboard 10 : Read Exec Write LD F2 45+ R MULTD F0 F2 F4 3 6 SUBD F8 F6 F DIVD F10 F0 F6 5 ADDD F6 F8 F2 10 WAR Hazard gone! 6Mult1 Yes Multd P36 P34 P4 Yes Yes Add Yes Addd P42 P38 P34 Yes Yes Divide Yes Divd P40 P36 P32 Mult1 No Yes 10 FU P36 P34 P4 P42 P38 P40 P12 P30 Notice that P32 not listed in Rename Table Still live. Must not be reallocated by accident 26

27 Renamed Scoreboard 11 : Read Exec Write LD F2 45+ R MULTD F0 F2 F4 3 6 SUBD F8 F6 F DIVD F10 F0 F6 5 ADDD F6 F8 F Mult1 Yes Multd P36 P34 P4 Yes Yes 2Add Yes Addd P42 P38 P34 Yes Yes Divide Yes Divd P40 P36 P32 Mult1 No Yes 11 FU P36 P34 P4 P42 P38 P40 P12 P30 Renamed Scoreboard 12 : Read Exec Write LD F2 45+ R MULTD F0 F2 F4 3 6 SUBD F8 F6 F DIVD F10 F0 F6 5 ADDD F6 F8 F Mult1 Yes Multd P36 P34 P4 Yes Yes 1Add Yes Addd P42 P38 P34 Yes Yes Divide Yes Divd P40 P36 P32 Mult1 No Yes 12 FU P36 P34 P4 P42 P38 P40 P12 P30 Renamed Scoreboard 13 : Read Exec Write LD F2 45+ R MULTD F0 F2 F4 3 6 SUBD F8 F6 F DIVD F10 F0 F6 5 ADDD F6 F8 F Mult1 Yes Multd P36 P34 P4 Yes Yes 0Add Yes Addd P42 P38 P34 Yes Yes Divide Yes Divd P40 P36 P32 Mult1 No Yes 13 FU P36 P34 P4 P42 P38 P40 P12 P30 Renamed Scoreboard 14 : Read Exec Write LD F2 45+ R MULTD F0 F2 F4 3 6 SUBD F8 F6 F DIVD F10 F0 F6 5 ADDD F6 F8 F Mult1 Yes Multd P36 P34 P4 Yes Yes Add No Divide Yes Divd P40 P36 P32 Mult1 No Yes 14 FU P36 P34 P4 P42 P38 P40 P12 P30 27

28 Renamed Scoreboard 15 : Read Exec Write LD F2 45+ R MULTD F0 F2 F4 3 6 SUBD F8 F6 F DIVD F10 F0 F6 5 ADDD F6 F8 F Mult1 Yes Multd P36 P34 P4 Yes Yes Add No Divide Yes Divd P40 P36 P32 Mult1 No Yes 15 FU P36 P34 P4 P42 P38 P40 P12 P30 Renamed Scoreboard 16 : Read Exec Write LD F2 45+ R MULTD F0 F2 F SUBD F8 F6 F DIVD F10 F0 F6 5 ADDD F6 F8 F Mult1 Yes Multd P36 P34 P4 Yes Yes Add No Divide Yes Divd P40 P36 P32 Mult1 No Yes 16 FU P36 P34 P4 P42 P38 P40 P12 P30 Renamed Scoreboard 17 : Read Exec Write LD F2 45+ R MULTD F0 F2 F SUBD F8 F6 F DIVD F10 F0 F6 5 ADDD F6 F8 F Mult1 No Add No Divide Yes Divd P40 P36 P32 Mult1 Yes Yes 17 FU P36 P34 P4 P42 P38 P40 P12 P30 Renamed Scoreboard 18 : Read Exec Write LD F2 45+ R MULTD F0 F2 F SUBD F8 F6 F DIVD F10 F0 F ADDD F6 F8 F Mult1 No Add No 40Divide Yes Divd P40 P36 P32 Mult1 Yes Yes 18 FU P36 P34 P4 P42 P38 P40 P12 P30 28

29 小结 < 动态硬件策略能够在硬件层面动态展开循环 (unroll loops) < 重排序缓冲器 (Reorder Buffer) = 按序发射 乱序执行 按序提交 (In-order issue, Out-of-order execution, In-order commit) = 只有在按序提交时, 才存储结果 ; = 可支持精确中断 / 推测式执行 : 仅需将被中断的指令之后的指令丢弃即可 小结 < Explicit Renaming: more physical registers than needed by ISA. = Separates renaming from scheduling Opens up lots of options for resolving RAW hazards = Rename table: tracks current association between architectural registers and physical registers = Potentially complicated rename table management Tomasulo 算法的相关技术 Score Board Tomasolu Reorder Buffer Store Queue Register Renaming 结构冒险发射, Stall 保留站 RAW 冒险 译码 保留站 WAR 冒险 WB, Stall 保留站 / 换名 WAW 冒险 发射, Stall 保留站 / 换名 Memory 冒险? Store Buffer? 精确例外 / 推测执行 非精确? 29