高等计算机系统结构 Tomasulo 算法 ( 第四讲 ) 程旭 2005 年 3 月 21 日 上一讲小结 软件或硬件的指令级并行 (ILP) 循环级并行最容易判定 软件并行性取决于程序, 如果硬件不能支持就出现冒险 软件相关性 / 编译器复杂性决定编译中是否能展开循环 存储器相关是最难判定的 硬件开采 ILP 在编译时有些相关情况不能真正判定 针对某一机器产生的代码可以在另一机器上有效运行 记分板的核心思想 : 允许暂停之后的指令提前处理 ( 译码 => 发射指令 & 读取操作数 ) 允许乱序执行 => 乱序完成 ID 段检测所有的结构冒险 记分板体系结构 记分板的三个主要组成部分 Registers FP FP Mult Mult FP FP Mult Mult FP FP Divide Divide FP FP Add Add Integer Functional Units 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 ination register Fj, Fk Source-register numbers Qj, Qk Functional units producing source registers Fj, Fk Rj, Rk Flags indicating when Fj, Fk are ready SCOREBOARD 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 冒险 Instruction status Issue Read operands Execution complete Write result 记分板流水线控制的细节 Wait until Not busy (FU) and not result(d) Rj and Rk Functional unit done f((fj( f ) Fi(FU) or Rj( f )=No) & (Fk( f ) Fi(FU) or Rk( f )=No)) 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 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 记分板控制的四级 发射 指令译码并检测结构冒险 (ID1) 按照程序的次序发射指令 ( 进行冒险检测 ) 如果存在结构冒险暂停发射 如果带发射的指令与已发射但尚未完成的指令之间存在输出相关, 则暂停发射 ( 无 WAW 冒险 ) 读操作数 等待到没有数据冒险, 在读取操作数 (ID2) 由于将等待未完成指令写回其结果, 因而在该阶段, 可解决所有的真数据相关 (RAW 冒险 ) 在该模型中, 无数据前递! 记分板控制的四级 ( 续一 ) 执行 对操作数进行操作 (EX) 接收到操作数之后, 功能部件开始执行 当产生结果之后, 它通报记分板 : 已经完成执行 写结果 完成执行 (WB) 暂停直到与以前的指令没有 WAR 冒险 : 示例 : DIVD F0,F2,F4 ADDD F10,F0,F8 SUBD F8,F8,F14 CDC 6600 的记分板将暂停 SUBD 指令, 直到 ADDD 指令读取了操作数
另一个动态算法 : Tomasulo 算法 为 IBM 360/91 设计的 在 CDC 6600 三年之后 (1966) 目标 : 即使在没有特殊编译支持的情况下, 也能取得高性能 IBM 360 和 CDC 6600 指令系统体系结构之间的差异 IBM 的每条指令有两个寄存器描述符 (register specifiers), 而 CDC 6600 有三个 ; IBM 有四个浮点寄存器, 而 CDC 6600 有八个 为什么要学习 Tomasulo 算法? 由此产生了 Alpha 21264 HP 8000 MIPS 10000 Pentium II PowerPC 604, Tomasulo 算法与记分板 控制 & 缓冲器分布于功能部件 (FU) 与集中于记分板 ; 功能部件缓冲器称为 保留站 (reservation stations) ; 存放未决的操作数 指令中的寄存器被数值或者指向保留站的指针代替 ; 这一过程成为寄存器换名 (register renaming) ; 消除 WAR WAW 冒险 保留站比实际寄存器多, 因而可以完成优化编译器所不能完成的一些工作 结果从 RS 直接到 FU, 无需通过寄存器, 而是通过公共数据总线 (Common Data Bus) 把结果广播到所有 FU 装入 (Load) 和存储 (Stores) 也象其他功能部件一样使用保留站 Load Buffer Common Data Bus 6 5 4 3 2 1 From FP Add Res. Station Tomasulo 的结构图 Operation Bus 3 2 1 Adders FP Op Queue From Instruction Unit 1 2 1 Reservation Station Multers Common Data Bus(CDB) FP Registers 3 2 1 To FP Mul Res. Station Store Buffer 保留站的组成 Op 该部件将完成的具体操作 ( 例如, + or ) Vj, Vk 源操作数的实际数值 存储缓冲器 (Store buffers) 设有 V 域, 存放将存储的结果 Qj, Qk 将产生源寄存器值 ( 将写的值 ) 的保留站 注意 : 没有记分板中的就绪 (READY) 标志 ;Qj,Qk=0 ready 存储缓冲器 (Store buffers) 中只有存放 RS 产生结果的 Qi Busy 指明保留站或 FU 处于忙状态 指明哪个功能部件将写到哪个寄存器 (Qi); 如果没有将写入寄存器的未决指令, 该域为空
Tomasulo 算法的三段 1. Issue 从 FP Op Queue 中取出指令 如果保留站空闲 ( 无结构冒险 ), 控制机制发射指令 & 发送操作数 ( 对寄存器进行换名 ) 2. Execution 对操作数执行操作 (EX) 如果两个操作数都已就绪, 就执行 ; 如果没有就绪, 就观测公共数据总线等待所需结果 3. Write result 完成执行 (WB) 通过公共数据总线将结果写入到所有等待的部件 ; 标记保留站可用 正常的数据总线 : 数据 + 目的 ( 去向 总线 ) 公共数据总线 : 数据 + 源 ( 来源 总线 ) 64 位数据 + 4 位功能部件 源地址 如果与期望的功能部件匹配, 就 写 ( 产生结果 ) 进行广播 Tomasulo 示例第 0 周期 Execution Write LD F6 34+ R2 Load1 No LD F2 45+ R3 Load2 No MUL F0 F2 F4 Load3 No SUB F8 F6 F2 DIVDF10 F0 F6 ADD F6 F8 F2 LD: 0Add1No 0Add2No ADD: 0Add3No Mult: 0Mult1No 0Mult2No Divd: 2 cycles 2 cycles 10 cycles 40 cycles 0 FU Tomasulo 示例第 1 周期 Execution Write LD F6 34+ R2 1 Load1 Yes 34+R2 LD F2 45+ R3 Load2 No MUL F0 F2 F4 Load3 No SUB F8 F6 F2 DIVDF10 F0 F6 ADD F6 F8 F2 0 Add1 No 0 Add2 No Add3 No 0Mult1No 0Mult2No 1 FU Load1 Tomasulo 示例第 2 周期 Execution Write LD F6 34+ R2 1 Load1 Yes 34+R2 LD F2 45+ R3 2 Load2 Yes 45+R3 MULF0 F2 F4 Load3 No SUB F8 F6 F2 DIVDF10 F0 F6 ADD F6 F8 F2 0Add1No 0Add2No Add3 No 0Mult1No 0Mult2No 2 FU Load2 Load1 注意 : 与 CDC6600 不同, 可以有多个 loads 被发射 ; 记分板能否改进?
Tomasulo 示例第 3 周期 Execution Write LD F6 34+ R2 1 3 Load1 Yes 34+R2 LD F2 45+ R3 2 Load2 Yes 45+R3 MUL F0 F2 F4 3 Load3 No SUB F8 F6 F2 DIVDF10 F0 F6 ADD F6 F8 F2 0Add1No 0Add2No Add3 No 0Mult1Yes MULTD R(F4) Load2 0Mult2No 3 FU Mult1 Load2 Load1 注意 : 保留站中寄存器名被 换名 ; MULT 可发射 ( 与记分板比较 ) Tomasulo 示例第 4 周期 Execution Write LD F2 45+ R3 2 4 Load2 Yes 45+R3 MUL F0 F2 F4 3 Load3 No SUB F8 F6 F2 4 DIVDF10 F0 F6 ADD F6 F8 F2 0 Add1 Yes SUBDM(34+R2) Load2 0 Add2 No Add3 No 0Mult1Yes MULTD R(F4) Load2 0Mult2No 4 FU Mult1 Load2 M(34+R2) Add1 Load2 将完成 ; 哪些指令在等待 Load2? Load1 完成 ; 哪些指令在等待 Load1? Tomasulo 示例第 5 周期 Execution Write MUL F0 F2 F4 3 Load3 No SUB F8 F6 F2 4 DIVDF10 F0 F6 5 ADD F6 F8 F2 2 Add1 Yes SUBDM(34+R2) M(45+R3) 0 Add2 No Add3 No 10 Mult1 Yes MULTM(45+R3) R(F4) 0Mult2Yes DIVD M(34+R2) Mult1 5 FU Mult1 M(45+R3) M(34+R2) Add1 Mult2 Tomasulo 示例第 6 周期 Execution Write MUL F0 F2 F4 3 Load3 No SUB F8 F6 F2 4 DIVDF10 F0 F6 5 ADD F6 F8 F2 6 1Add1Yes SUBDM(34+R2) M(45+R3) 0Add2YesADDD M(45+R3) Add1 Add3 No 9Mult1Yes MULTM(45+R3) R(F4) 0Mult2Yes DIVD M(34+R2) Mult1 6 FU Mult1 M(45+R3) Add2 Add1 Mult2 发射 ADDD
Tomasulo 示例第 7 周期 Execution Write MULF0 F2 F4 3 Load3 No SUB F8 F6 F2 4 7 DIVDF10 F0 F6 5 ADD F6 F8 F2 6 0Add1Yes SUBDM(34+R2) M(45+R3) 0Add2YesADDD M(45+R3) Add1 Add3 No 8Mult1Yes MULTM(45+R3) R(F4) 0Mult2Yes DIVD M(34+R2) Mult1 7 FU Mult1 M(45+R3) Add2 Add1 Mult2 Add1 完成 ; 哪些指令在等待 Add1? Tomasulo 示例第 8 周期 Execution Write MUL F0 F2 F4 3 Load3 No SUB F8 F6 F2 4 7 8 DIVDF10 F0 F6 5 ADD F6 F8 F2 6 0Add1No 2Add2YesADDDM()-M() M(45+R3) 0Add3No 7Mult1Yes MULTM(45+R3) R(F4) 0Mult2Yes DIVD M(34+R2) Mult1 8 FU Mult1 M(45+R3) Add2 M()-M() Mult2 Tomasulo 示例第 9 周期 Execution Write MUL F0 F2 F4 3 Load3 No SUB F8 F6 F2 4 7 8 DIVDF10 F0 F6 5 ADD F6 F8 F2 6 0Add1No 1Add2YesADDDM()-M() M(45+R3) 0Add3No 6Mult1Yes MULTM(45+R3) R(F4) 0Mult2Yes DIVD M(34+R2) Mult1 9 FU Mult1 M(45+R3) Add2 M()-M() Mult2 Tomasulo 示例第 10 周期 Execution Write MULF0 F2 F4 3 Load3 No SUB F8 F6 F2 4 7 8 DIVDF10 F0 F6 5 ADD F6 F8 F2 6 10 0 Add1 No 0 Add2 Yes ADDDM()-M() M(45+R3) 0 Add3 No 5Mult1Yes MULTM(45+R3) R(F4) 0Mult2Yes DIVD M(34+R2) Mult1 10 FU Mult1 M(45+R3) Add2 M()-M() Mult2 Add2 完成 ; 哪些指令在等待 Add2?
Tomasulo 示例第 11 周期 Execution Write MULF0 F2 F4 3 Load3 No SUB F8 F6 F2 4 7 8 DIVDF10 F0 F6 5 ADD F6 F8 F2 6 10 11 0 Add1 No 0 Add2 No 0 Add3 No 4Mult1Yes MULTM(45+R3) R(F4) 0Mult2Yes DIVD M(34+R2) Mult1 11 FU Mult1 M(45+R3) (M-M)+M()M()-M( Mult2 ADDD 在该周期写结果 Tomasulo 示例第 12 周期 Execution Write MUL F0 F2 F4 3 Load3 No SUB F8 F6 F2 4 6 7 DIVDF10 F0 F6 5 ADD F6 F8 F2 6 10 11 0 Add1 No 0 Add2 No 0 Add3 No 3Mult1Yes MULTM(45+R3) R(F4) 0Mult2Yes DIVD M(34+R2) Mult1 12 FU Mult1 M(45+R3) (M-M)+M()M()-M() Mult2 注意 : 所有短周期指令都已经完成 Tomasulo 示例第 13 周期 Execution Write MULF0 F2 F4 3 Load3 No SUB F8 F6 F2 4 7 8 DIVDF10 F0 F6 5 ADD F6 F8 F2 6 10 11 0 Add1 No 0 Add2 No Add3 No 2Mult1Yes MULTM(45+R3) R(F4) 0Mult2Yes DIVD M(34+R2) Mult1 13 FU Mult1 M(45+R3) (M-M)+M()M()-M() Mult2 Tomasulo 示例第 14 周期 Execution Write MUL F0 F2 F4 3 Load3 No SUB F8 F6 F2 4 7 8 DIVDF10 F0 F6 5 ADD F6 F8 F2 6 10 11 0Add1No 0Add2No 0Add3No 1Mult1Yes MULTM(45+R3) R(F4) 0Mult2Yes DIVD M(34+R2) Mult1 14 FU Mult1 M(45+R3) (M-M)+M()M()-M( Mult2
Tomasulo 示例第 15 周期 Execution Write MULF0 F2 F4 3 15 Load3 No SUB F8 F6 F2 4 7 8 DIVDF10 F0 F6 5 ADD F6 F8 F2 6 10 11 0Add1No 0Add2No Add3 No 0Mult1Yes MULTM(45+R3) R(F4) 0Mult2Yes 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 MULF0 F2 F4 3 15 16 Load3 No SUB F8 F6 F2 4 7 8 DIVDF10 F0 F6 5 ADD F6 F8 F2 6 10 11 0 Add1 No 0 Add2 No Add3 No 0Mult1No 40 Mult2 Yes DIVD M*F4 M(34+R2) 16 FU M*F4 M(45+R3) (M-M)+M()M()-M() Mult2 注意 : 只有除法指令没有完成 Tomasulo 示例第 55 周期 Execution Write MUL F0 F2 F4 3 15 16 Load3 No SUB F8 F6 F2 4 7 8 DIVDF10 F0 F6 5 ADD F6 F8 F2 6 10 11 0 Add1 No 0 Add2 No Add3 No 0Mult1No 1Mult2Yes DIVD M*F4 M(34+R2) 55 FU M*F4 M(45+R3) (M-M)+M()M()-M() Mult2 Tomasulo 示例第 56 周期 Execution Write MUL F0 F2 F4 3 15 16 Load3 No SUB F8 F6 F2 4 7 8 DIVDF10 F0 F6 5 56 ADD F6 F8 F2 6 10 11 0 Add1 No 0 Add2 No Add3 No 0Mult1No 0Mult2Yes 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 MUL F0 F2 F4 3 15 16 Load3 No SUB F8 F6 F2 4 7 8 DIVDF10 F0 F6 5 56 57 ADD F6 F8 F2 6 10 11 0Add1No 0Add2No Add3 No 0Mult1No 0Mult2No 57 FU M*F4 M(45+R3) 也是, 按序发送 乱序执行 乱序完成 (M-M)+M()M()-M() M*F4/M 与记分板的第 62 周期相比 Read Execu Write Instruction j k IssueoperancompleResult LD F2 45+ R3 5 6 7 8 MULF0 F2 F4 6 9 19 20 SUBF8 F6 F2 7 9 11 12 DIVDF10 F0 F6 8 21 61 62 ADD F6 F8 F2 13 14 16 22 Functional unit status dest S1 S2 FU for FU for Fj? Fk? TimeName Busy Op Fi Fj Fk Qj Qk Rj Rk Integer No Mult1 No Mult2 No Add No 0 Divide No 62 FU CDC6600 的记分板为什么需要更长的时间? Tomasulo 与记分板 (IBM 360/91 与 CDC 6600) 流水化的功能部件多功能部件 (6 load, 3 store, 3 +, 2 x/ ) (1 load/store, 1 +, 2 x, 1 ) 窗口大小 : 14 指令 5 指令结构冒险暂停发射相同 WAR: 通过换名避免暂停到完成 WAW: 通过换名避免暂停发射从 FU 广播结果写 / 读寄存器控制 : 保留站集中控制的记分板 Tomasulo 算法的缺点 复杂 360/91 MIPS 10000 IBM PPC620 的延迟? 需要大量高速的相联存储 (CDB) 公共数据总线将成为制约性能增长的瓶颈 每个 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 周期 LD F0 0 R1 1 Load1 No MUL F4 F0 F2 1 Load2 No SD F4 0 R1 1 Load3 No Qi LD F0 0 R1 2 Store1 No MUL F4 F0 F2 2 Store2 No SD F4 0 R1 2 Store3 No 0Add2No MUL F4 F0 F2 0Mult1No SUB R1 R1 #8 0Mult2No BNEZR1 Loop 0 80 Qi 第 1 周期 LD F0 0 R1 1 1 Load1 Yes 80 MUL F4 F0 F2 1 Load2 No SD F4 0 R1 1 Load3 No Qi LD F0 0 R1 2 Store1 No MUL F4 F0 F2 2 Store2 No SD F4 0 R1 2 Store3 No 0 Add1 No LD F0 0 R1 0 Add2 No MUL F4 F0 F2 0 Add3 No SD F4 0 R1 0Mult1No SUB R1 R1 #8 0Mult2No BNEZR1 Loop 1 80 Qi Load1 第 2 周期 LD F0 0 R1 1 1 Load1 Yes 80 MULF4 F0 F2 1 2 Load2 No SD F4 0 R1 1 Load3 No Qi LD F0 0 R1 2 Store1 No MUL F4 F0 F2 2 Store2 No SD F4 0 R1 2 Store3 No 0Add2No MUL F4 F0 F2 0 Mult1 Yes MULTD R(F2) Load1 SUB R1 R1 #8 0 Mult2 No BNEZR1 Loop 2 80 Qi Load1 Mult1
第 3 周期 LD F0 0 R1 1 1 Load1 Yes 80 MULF4 F0 F2 1 2 Load2 No SD F4 0 R1 1 3 Load3 No Qi LD F0 0 R1 2 Store1 Yes 80 Mult1 MUL F4 F0 F2 2 Store2 No SD F4 0 R1 2 Store3 No 0 Add1 No LD F0 0 R1 0 Add2 No MUL F4 F0 F2 0 Add3 No SD F4 0 R1 0Mult1Yes MULTD R(F2) Load1 SUB R1 R1 #8 0Mult2No BNEZR1 Loop 3 80 Qi Load1 Mult1 第 4 周期 LD F0 0 R1 1 1 Load1 Yes 80 MULF4 F0 F2 1 2 Load2 No SD F4 0 R1 1 3 Load3 No Qi LD F0 0 R1 2 Store1 Yes 80 Mult1 MUL F4 F0 F2 2 Store2 No SD F4 0 R1 2 Store3 No 0Add2No MUL F4 F0 F2 0Mult1Yes MULTD R(F2) Load1 SUB R1 R1 #8 0Mult2No BNEZR1 Loop 4 72 Qi Load1 Mult1 注意 : 隐含的换名功能动态建立起 数据流 图 注意 : 发送 SUB 指令 第 5 周期 LD F0 0 R1 1 1 Load1 Yes 80 MULF4 F0 F2 1 2 Load2 No SD F4 0 R1 1 3 Load3 No Qi LD F0 0 R1 2 Store1 Yes 80 Mult1 MUL F4 F0 F2 2 Store2 No SD F4 0 R1 2 Store3 No 0Add2No MUL F4 F0 F2 0Mult1Yes MULTD R(F2) Load1 SUB R1 R1 #8 0Mult2No BNEZR1 Loop 5 72 Qi Load1 Mult1 第 6 周期 LD F0 0 R1 1 1 Load1 Yes 80 MUL F4 F0 F2 1 2 Load2 Yes 72 SD F4 0 R1 1 3 Load3 No Qi LD F0 0 R1 2 6 Store1Yes 80 Mult1 MUL F4 F0 F2 2 Store2 No SD F4 0 R1 2 Store3 No 0Add2No MUL F4 F0 F2 0Mult1Yes MULTD R(F2) Load1 SUB R1 R1 #8 0Mult2No BNEZR1 Loop 6 72 Qi Load2 Mult1 注意 : F0 一直看不到 Load1 的结果 注意 : 处理 BNEZ 指令
第 7 周期 LD F0 0 R1 1 1 Load1 Yes 80 MUL F4 F0 F2 1 2 Load2 Yes 72 SD F4 0 R1 1 3 Load3 No Qi LD F0 0 R1 2 6 Store1Yes 80 Mult1 MUL F4 F0 F2 2 7 Store2No SD F4 0 R1 2 Store3 No 0 Add1 No LD F0 0 R1 0 Add2 No MUL F4 F0 F2 0 Add3 No SD F4 0 R1 0 Mult1 Yes MULTD R(F2) Load1 SUB R1 R1 #8 0 Mult2 Yes MULTD R(F2) Load2 BNEZR1 Loop 7 72 Qi Load2 Mult2 Note: MULT2 has no registers names in RS 第 8 周期 LD F0 0 R1 1 1 Load1 Yes 80 MUL F4 F0 F2 1 2 Load2 Yes 72 SD F4 0 R1 1 3 Load3 No Qi LD F0 0 R1 2 6 Store1Yes 80 Mult1 MUL F4 F0 F2 2 7 Store2 Yes 72 Mult2 SD F4 0 R1 2 8 Store3No 0Add2No MUL F4 F0 F2 0Mult1Yes MULTD R(F2) Load1 SUB R1 R1 #8 0Mult2Yes MULTD R(F2) Load2 BNEZR1 Loop 8 72 Qi Load2 Mult2 第 9 周期 LD F0 0 R1 1 1 9 Load1 Yes 80 MUL F4 F0 F2 1 2 Load2 Yes 72 SD F4 0 R1 1 3 Load3 No Qi LD F0 0 R1 2 6 Store1Yes 80 Mult1 MUL F4 F0 F2 2 7 Store2 Yes 72 Mult2 SD F4 0 R1 2 8 Store3No 0Add2No MUL F4 F0 F2 0Mult1Yes MULTD R(F2) Load1 SUB R1 R1 #8 0Mult2Yes MULTD R(F2) Load2 BNEZR1 Loop Clock R1 F0 F2 F4 F6 F8 F10F12... F30 9 64 Qi Load2 Mult2 Load1 完成, 注意等待其结果的指令! 第 10 周期 LD F0 0 R1 1 1 9 10 Load1 No MULF4 F0 F2 1 2 Load2 Yes 72 SD F4 0 R1 1 3 Load3 No Qi LD F0 0 R1 2 6 10 Store1Yes 80 Mult1 MUL F4 F0 F2 2 7 Store2Yes 72 Mult2 SD F4 0 R1 2 8 Store3No 0Add2No MULT F4 F0 F2 4Mult1Yes MULTD M(80)R(F2) SUBI R1 R1 #8 0Mult2Yes MULTD R(F2) Load2 BNEZ R1 Loop 10 64 Qi Load2 Mult2 Load2 Load1 完成, 注意等待其结果的指令
第 11 周期 LD F0 0 R1 1 1 9 10 Load1 No MULF4 F0 F2 1 2 Load2 No SD F4 0 R1 1 3 Load3 Yes 64 Qi LD F0 0 R1 2 6 10 11 Store1Yes 80 Mult1 MUL F4 F0 F2 2 7 Store2Yes 72 Mult2 SD F4 0 R1 2 8 Store3No 0Add2No MULT F4 F0 F2 3Mult1Yes MULTD M(80)R(F2) SUBI R1 R1 #8 4Mult2Yes MULTD M(72)R(F2) BNEZ R1 Loop 11 64 Qi Load3 Mult2 12 64 Qi Load3 Mult2 第 12 周期 LD F0 0 R1 1 1 9 10 Load1 No MUL F4 F0 F2 1 2 Load2 No SD F4 0 R1 1 3 Load3 Yes 64 Qi LD F0 0 R1 2 6 10 11 Store1Yes 80 Mult1 MUL F4 F0 F2 2 7 Store2 Yes 72 Mult2 SD F4 0 R1 2 8 Store3No 0Add2No MULT F4 F0 F2 为什么不能发送第三次迭代的乘法? 2Mult1Yes MULTD M(80)R(F2) SUBI R1 R1 #8 3Mult2Yes MULTD M(72)R(F2) BNEZ R1 Loop 第 13 周期 LD F0 0 R1 1 1 9 10 Load1 No MULF4 F0 F2 1 2 Load2 No SD F4 0 R1 1 3 Load3 Yes 64 Qi LD F0 0 R1 2 6 10 11 Store1 Yes 80 Mult1 MUL F4 F0 F2 2 7 Store2 Yes 72 Mult2 SD F4 0 R1 2 8 Store3 No 0Add2No MULT F4 F0 F2 1Mult1Yes MULTD M(80)R(F2) SUBI R1 R1 #8 2Mult2Yes MULTD M(72)R(F2) BNEZ R1 Loop 13 64 Qi Load3 Mult2 第 14 周期 LD F0 0 R1 1 1 9 10 Load1 No MUL F4 F0 F2 1 2 14 Load2 No SD F4 0 R1 1 3 Load3Yes 64 Qi LD F0 0 R1 2 6 10 11 Store1Yes 80 Mult1 MUL F4 F0 F2 2 7 Store2 Yes 72 Mult2 SD F4 0 R1 2 8 Store3No 0Add2No MULT F4 F0 F2 0Mult1Yes MULTD M(80)R(F2) SUBI R1 R1 #8 1Mult2Yes MULTD M(72)R(F2) BNEZ R1 Loop 14 64 Qi Load3 Mult2 Mult1 完成
第 15 周期 LD F0 0 R1 1 1 9 10 Load1 No MUL F4 F0 F2 1 2 14 15 Load2 No SD F4 0 R1 1 3 Load3Yes 64 Qi LD F0 0 R1 2 6 10 11 Store1Yes 80 M(80)*R MUL F4 F0 F2 2 7 15 Store2 Yes 72 Mult2 SD F4 0 R1 2 8 Store3No 0Add2No MULT F4 F0 F2 0Mult1No SUBI R1 R1 #8 0Mult2Yes MULTD M(72)R(F2) BNEZ R1 Loop 15 64 Qi Load3 Mult2 Mult2 完成 16 64 Qi Load3 Mult1 第 16 周期 LD F0 0 R1 1 1 9 10 Load1 No MUL F4 F0 F2 1 2 14 15 Load2 No SD F4 0 R1 1 3 Load3 Yes 64 Qi LD F0 0 R1 2 6 10 11 Store1Yes 80 M(80)*R MUL F4 F0 F2 2 7 15 16 Store2 Yes 72 M(72)*R SD F4 0 R1 2 8 Store3No 0Add2No MULT F4 F0 F2 0 Mult1 Yes MULTD R(F2) Load3 SUBI R1 R1 #8 0Mult2No BNEZ R1 Loop 17 64 Qi Load3 Mult1 第 17 周期 LD F0 0 R1 1 1 9 10 Load1 No MUL F4 F0 F2 1 2 14 15 Load2 No SD F4 0 R1 1 3 Load3 Yes 64 Qi LD F0 0 R1 2 6 10 11 Store1Yes 80 M(80)*R MUL F4 F0 F2 2 7 15 16 Store2 Yes 72 M(72)*R SD F4 0 R1 2 8 Store3Yes 64 Mult1 0Add2No MULT F4 F0 F2 0 Mult1 Yes MULTD R(F2) Load3 SUBI R1 R1 #8 0Mult2No BNEZ R1 Loop 18 56 Qi Load3 Mult1 第 18 周期 LD F0 0 R1 1 1 9 10 Load1 No MUL F4 F0 F2 1 2 14 15 Load2 No SD F4 0 R1 1 3 18 Load3 Yes 64 Qi LD F0 0 R1 2 6 10 11 Store1Yes 80 M(80)*R MUL F4 F0 F2 2 7 15 16 Store2 Yes 72 M(72)*R SD F4 0 R1 2 8 Store3Yes 64 Mult1 0Add2No MULT F4 F0 F2 0 Mult1 Yes MULTD R(F2) Load3 SUBI R1 R1 #8 0Mult2No BNEZ R1 Loop
第 19 周期 LD F0 0 R1 1 1 9 10 Load1 No MULF4 F0 F2 1 2 14 15 Load2 No SD F4 0 R1 1 3 18 19 Load3 Yes 64 Qi LD F0 0 R1 2 6 10 11 Store1No MUL F4 F0 F2 2 7 15 16 Store2Yes 72 M(72)*R SD F4 0 R1 2 8 Store3Yes 64 Mult1 0Add2No MULT F4 F0 F2 0 Mult1 Yes MULTD R(F2) Load3 SUBI R1 R1 #8 0Mult2No BNEZ R1 Loop 19 56 Qi Load3 Mult1 20 56 Qi Load3 Mult1 第 20 周期 LD F0 0 R1 1 1 9 10 Load1 No MUL F4 F0 F2 1 2 14 15 Load2 No SD F4 0 R1 1 3 18 19 Load3 Yes 64 Qi LD F0 0 R1 2 6 10 11 Store1No MUL F4 F0 F2 2 7 15 16 Store2 Yes 72 M(72)*R SD F4 0 R1 2 8 20 Store3Yes 64 Mult1 0Add2No MULT F4 F0 F2 0 Mult1 Yes MULTD R(F2) Load3 SUBI R1 R1 #8 0Mult2No BNEZ R1 Loop 第 21 周期 LD F0 0 R1 1 1 9 10 Load1 No MULF4 F0 F2 1 2 14 15 Load2 No SD F4 0 R1 1 3 18 19 Load3 Yes 64 Qi LD F0 0 R1 2 6 10 11 Store1No MUL F4 F0 F2 2 7 15 16 Store2No SD F4 0 R1 2 8 20 21 Store3Yes 64 Mult1 0Add2No MULT F4 F0 F2 0 Mult1 Yes MULTD R(F2) Load3 SUBI R1 R1 #8 0Mult2No BNEZ R1 Loop 21 56 Qi Load3 Mult1 Tomasulo 算法小结 保留站 : 换名到巨大的寄存器空间 + 缓存源操作数 防止寄存器成为性能瓶颈 防止记分板中的 WAR WAW 冒险 具有硬件动态完成循环展开的功能 不局限在基本块内 ( 整数部件可以先行, 跨越基本块 ) 对于降低 cache 失效开销有利 对后续机型的影响 : 动态调度 寄存器换名 Load/store 别名分析 360/91 的后续包括 :Pentium III PowerPC 604 MIPS R10000 HP-PA 8000 Alpha 21264 等等
如何实现精确意外 / 中断处理? 记分板和 Tomasulo 算法都可实现 : 按序发送 乱序执行 乱序完成 如果中断或意外被称为 精确当且仅当对于单条指令 : 所有该指令之前的指令都已经提交其状态 所有后续指令 ( 包括产生中断的指令 ) 没有改变任何机器状态 需要一定措施将指令执行的次序与指令发射流进行再同步 对于按序完成的机制, 最容易实现 硬件对精确中断的支持 重排序缓冲器 (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 ROB 中硬件实现的复杂性 Reg Result Exceptions? Valid Reorder Table Program Counter FP Op Queue Res Stations FP Adder Compar network Reorder Buffer FP Regs Res Stations FP Adder 如何找到寄存器对应的最新内容? 需要相联比较网络 可以使用 未来文件 或使用寄存器结果状态缓冲器来跟踪哪个特定重排序缓冲器将接受具体数值 需要 ROB 具有寄存器堆那么多的端口 FP Op Queue 具有重排序缓冲器的 Tomasulo 算法 Reorder Buffer Registers FP FP adders adders Reservation Stations LD LD F0,10(R2) FP FP multipliers ROB7 ROB6 ROB5 ROB4 ROB3 ROB2 N ROB1 To from 1 10+R2 10+R2 Newest
FP Op Queue 具有重排序缓冲器的 Tomasulo 算法 Reorder Buffer F10 F10 ADDD ADDD F10,F4,F0 LD LD F0,10(R2) ROB7 ROB6 ROB5 ROB4 ROB3 N ROB2 N ROB1 Newest FP Op Queue 具有重排序缓冲器的 Tomasulo 算法 Reorder Buffer F2 F2 F10 F10 DIVD DIVD F2,F10,F6 ADDD ADDD F10,F4,F0 LD LD F0,10(R2) ROB7 ROB6 ROB5 ROB4 N ROB3 N ROB2 N ROB1 Newest 2 ADDD ADDD R(F4),ROB1 FP FP adders adders Registers Reservation Stations FP FP multipliers To from 1 10+R2 10+R2 2 ADDD ADDD R(F4),ROB1 FP FP adders adders Registers Reservation Stations 3 DIVD DIVD ROB2,R(F6) FP FP multipliers To from 1 10+R2 10+R2 FP Op Queue 具有重排序缓冲器的 Tomasulo 算法 Reorder Buffer ADDD ADDD F0,F4,F6 F4 F4 LD LD F4,0(R3) -- -- BNE BNE F2,< > F2 F2 DIVD DIVD F2,F10,F6 F10 F10 ADDD ADDD F10,F4,F0 LD LD F0,10(R2) ROB7 N ROB6 N ROB5 N ROB4 N ROB3 N ROB2 N ROB1 Newest FP Op Queue 具有重排序缓冲器的 Tomasulo 算法 Reorder Buffer -- -- ROB5 ROB5 ST ST 0(R3),F4 ADDD ADDD F0,F4,F6 F4 F4 LD LD F4,0(R3) -- -- BNE BNE F2,< > F2 F2 DIVD DIVD F2,F10,F6 F10 F10 ADDD ADDD F10,F4,F0 LD LD F0,10(R2) N ROB7 N ROB6 N ROB5 N ROB4 N ROB3 N ROB2 N ROB1 Newest 2 ADDD ADDD R(F4),ROB1 6 ADDD ADDD ROB5, ROB5, R(F6) R(F6) FP FP adders adders Registers Reservation Stations 3 DIVD DIVD ROB2,R(F6) FP FP multipliers To from 1 10+R2 10+R2 5 0+R3 0+R3 2 ADDD ADDD R(F4),ROB1 6 ADDD ADDD ROB5, ROB5, R(F6) R(F6) FP FP adders adders Registers Reservation Stations 3 DIVD DIVD ROB2,R(F6) FP FP multipliers To from 1 10+R2 10+R2 6 0+R3 0+R3
FP Op Queue 具有重排序缓冲器的 Tomasulo 算法 Reorder Buffer -- -- M[10] M[10] ST ST 0(R3),F4 ADDD ADDD F0,F4,F6 F4 F4 M[10] M[10] LD LD F4,0(R3) -- -- BNE BNE F2,< > F2 F2 DIVD DIVD F2,F10,F6 F10 F10 ADDD ADDD F10,F4,F0 LD LD F0,10(R2) Y ROB7 N ROB6 Y ROB5 N ROB4 N ROB3 N ROB2 N ROB1 Newest FP Op Queue 具有重排序缓冲器的 Tomasulo 算法 Reorder Buffer -- -- M[10] M[10] <val2> ST ST 0(R3),F4 ADDD ADDD F0,F4,F6 F4 F4 M[10] M[10] LD LD F4,0(R3) -- -- BNE BNE F2,< > F2 F2 DIVD DIVD F2,F10,F6 F10 F10 ADDD ADDD F10,F4,F0 LD LD F0,10(R2) Y ROB7 Ex ROB6 Y Ex ROB5 N ROB4 N ROB3 N ROB2 N ROB1 Newest 2 ADDD ADDD R(F4),ROB1 6 ADDD ADDD M[10],R(F6) FP FP adders adders Registers Reservation Stations 3 DIVD DIVD ROB2,R(F6) FP FP multipliers To from 1 10+R2 10+R2 2 ADDD ADDD R(F4),ROB1 FP FP adders adders Registers Reservation Stations 3 DIVD DIVD ROB2,R(F6) FP FP multipliers To from 1 10+R2 10+R2 FP Op Queue 具有重排序缓冲器的 Tomasulo 算法 Reorder Buffer What about memory hazards??? 2 ADDD ADDD R(F4),ROB1 FP FP adders adders Registers Reservation Stations -- -- M[10] M[10] <val2> ST ST 0(R3),F4 ADDD ADDD F0,F4,F6 F4 F4 M[10] M[10] LD LD F4,0(R3) -- -- BNE BNE F2,< > F2 F2 DIVD DIVD F2,F10,F6 F10 F10 ADDD ADDD F10,F4,F0 LD LD F0,10(R2) 3 DIVD DIVD ROB2,R(F6) FP FP multipliers Y ROB7 Ex ROB6 Ex Y ROB5 N ROB4 N ROB3 N ROB2 N ROB1 To from 1 10+R2 10+R2 Newest 存储器别名 : 消除关于存储器的 RAW 冒险 问题 : 对于程序序的跟在 STORE 后的 LOAD 操作, 它们是否相关? 例如 st 0(R2),R5 ld R6,0(R3) 能否提前启动执行 load? Store address could be delayed for a long time by some calculation that leads to R2 (divide?). We might want to issue/begin execution of both operations in same cycle. Now: Answer is that we are not allowed to start load until we know that address 0(R2) 0(R3) Next step: We might guess at whether or not they are dependent (called dependence speculation ) and use reorder buffer to fixup if we are wrong.
硬件对存储器歧义的支持 Need buffer to keep track of all outstanding stores to memory, in program order. Keep track of address (when becomes available) and value (when becomes available) FIFO ordering: will retire stores from this buffer in program order When issuing a load, record current head of store queue (know which stores are ahead of you). When have address for load, check store queue: If any store prior to load is waiting for its address, stall load. If load address matches earlier store address (associative lookup), then we have a memory-induced RAW hazard: store value available return value store value not available return ROB number of source Otherwise, send out request to memory Actual stores commit in order, so no worry about WAR/WAW hazards through memory. FP Op Queue Reorder Buffer FP FP adders adders Registers 存储器歧义 Reservation Stations F4 F4 LD LD F4, F4, 10(R3) -- -- ST ST 10(R3), F5 F5 LD LD F0,32(R2) -- -- <val <val 1> 1> ST ST 0(R3), F4 F4 FP FP multipliers ROB7 ROB6 ROB5 N ROB4 N ROB3 N ROB2 Y ROB1 To from 2 32+R2 32+R2 4 ROB3 ROB3 Newest 精确中断与推测式之间的关系 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 显式寄存器换名 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 FP Mult Mult FP FP Mult Mult FP FP Divide Divide FP FP Add Add Integer Functional Units 采用显式寄存器换名策略的记分板控制 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 Renamed Scoreboard 3 : Read Exec Write LD F6 34+ R2 1 2 3 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+ R3 2 3 4 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 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 MULTD F0 F2 F4 3 6 SUBD F8 F6 F2 4 6 DIVD F10 F0 F6 5 ADDD F6 F8 F2 10 Mult1 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 Renamed Scoreboard 7 : Read Exec Write MULTD F0 F2 F4 3 6 SUBD F8 F6 F2 4 6 DIVD F10 F0 F6 5 ADDD F6 F8 F2 9 Mult1 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 MULTD F0 F2 F4 3 6 SUBD F8 F6 F2 4 6 8 DIVD F10 F0 F6 5 ADDD F6 F8 F2 8 Mult1 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 MULTD F0 F2 F4 3 6 SUBD F8 F6 F2 4 6 8 9 DIVD F10 F0 F6 5 ADDD F6 F8 F2 7 Mult1 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 MULTD F0 F2 F4 3 6 SUBD F8 F6 F2 4 6 8 9 DIVD F10 F0 F6 5 ADDD F6 F8 F2 10 WAR Hazard gone! 6 Mult1 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 Renamed Scoreboard 11 : Read Exec Write MULTD F0 F2 F4 3 6 SUBD F8 F6 F2 4 6 8 9 DIVD F10 F0 F6 5 ADDD F6 F8 F2 10 11 5 Mult1 Yes Multd P36 P34 P4 Yes Yes 2 Add 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 MULTD F0 F2 F4 3 6 SUBD F8 F6 F2 4 6 8 9 DIVD F10 F0 F6 5 ADDD F6 F8 F2 10 11 4 Mult1 Yes Multd P36 P34 P4 Yes Yes 1 Add 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 MULTD F0 F2 F4 3 6 SUBD F8 F6 F2 4 6 8 9 DIVD F10 F0 F6 5 ADDD F6 F8 F2 10 11 13 3 Mult1 Yes Multd P36 P34 P4 Yes Yes 0 Add 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 MULTD F0 F2 F4 3 6 SUBD F8 F6 F2 4 6 8 9 DIVD F10 F0 F6 5 ADDD F6 F8 F2 10 11 13 14 2 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 Renamed Scoreboard 15 : Read Exec Write MULTD F0 F2 F4 3 6 SUBD F8 F6 F2 4 6 8 9 DIVD F10 F0 F6 5 ADDD F6 F8 F2 10 11 13 14 1 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 MULTD F0 F2 F4 3 6 16 SUBD F8 F6 F2 4 6 8 9 DIVD F10 F0 F6 5 ADDD F6 F8 F2 10 11 13 14 0 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 MULTD F0 F2 F4 3 6 16 17 SUBD F8 F6 F2 4 6 8 9 DIVD F10 F0 F6 5 ADDD F6 F8 F2 10 11 13 14 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 MULTD F0 F2 F4 3 6 16 17 SUBD F8 F6 F2 4 6 8 9 DIVD F10 F0 F6 5 18 ADDD F6 F8 F2 10 11 13 14 Mult1 No Add No 40 Divide Yes Divd P40 P36 P32 Mult1 Yes Yes 18 FU P36 P34 P4 P42 P38 P40 P12 P30 显式寄存器换名 Rapid access to a table of translations A physical register file that has more registers than specified by the ISA Ability to figure out which physical registers are free. No free registers stall on issue Thus, register renaming doesn t require reservation stations. However: Many modern architectures use explicit register renaming + Tomasulo-like reservation stations to control execution. Two Questions: How do we manage the free list? How does Explicit Register Renaming mix with Precise Interupts? P0 P0 P2 P2 显式寄存器换名 (R10000 Style) P4 P4 F6 F6 Current Map Table F8 F8 P10 P10 P32 P32P34 P34 P36 P36 P38 P38 P60 P60 P62 P62 Freelist P12 P12 P14 P14 P16 P16 P18 P18 P20 P20 P22 P22 P24 P24 p26 p26 P28 P28 P30 P30 Newest Physical register file larger than ISA register file On issue, each instruction that modifies a register is allocated new physical register from freelist
显式寄存器换名 (R10000 Style) 显式寄存器换名 (R10000 Style) P32 P32 P2 P2 P4 P4 F6 F6 F8 F8 P10 P10 P12 P12 P14 P14 P16 P16 P18 P18 P20 P20 P22 P22 P24 P24 p26 p26 P28 P28 P30 P30 P32 P32 P2 P2 P4 P4 F6 F6 F8 F8 P34 P34 P12 P12 P14 P14 P16 P16 P18 P18 P20 P20 P22 P22 P24 P24 p26 p26 P28 P28 P30 P30 Current Map Table Current Map Table Newest Newest P34 P34P36 P36 P38 P38 P40 P40 P60 P60 P62 P62 P36 P36P38 P38 P40 P40 P42 P42 P60 P60 P62 P62 Freelist P0 P0 LD LD P32,10(R2) N Freelist F10 F10P10 F0 ADDD ADDD P34,P4,P32 F0 P0 P0 LD LD P32,10(R2) N N N N Note that physical register P0 is dead (or not live ) past the point of this load. When we go to commit the load, we free up 显式寄存器换名 (R10000 Style) 显式寄存器换名 (R10000Style) P32 P32P36 P36 P4 P4 F6 F6 F8 F8 P34 P34 P12 P12 P14 P14 P16 P16 P18 P18 P20 P20 P22 P22 P24 P24 p26 p26 P28 P28 P30 P30 P40 P40P36 P36 P38 P38 F6 F6 F8 F8 P34 P34 P12 P12 P14 P14 P16 P16 P18 P18 P20 P20 P22 P22 P24 P24 p26 p26 P28 P28 P30 P30 Current Map Table P38 P38P40 P40 P44 P44 P48 P48 P60 P60 P62 P62 Freelist -- -- -- -- BNE BNE P36,< > F2 F2 P2 P2 DIVD DIVD P36,P34,P6 F10 F10P10 ADDD ADDD P34,P4,P32 P0 P0 LD LD P32,10(R2) N N N N Newest Current Map Table P42 P42P44 P44 P48 P48 P50 P50 P0 P0 P10 P10 Freelist -- -- ST ST 0(R3),P40 P32 P32 ADDD ADDD P40,P38,P6 F4 F4 P4 P4 LD LD P38,0(R3) -- -- BNE BNE P36,< > F2 F2 P2 P2 DIVD DIVD P36,P34,P6 F10 F10P10 ADDD ADDD P34,P4,P32 P0 P0 LD LD P32,10(R2) Y Y Y N N y y Newest P32 P32P36 P36 P4 P4 F6 F6 F8 F8 P34 P34 P12 P12 P14 P14 P16 P16 P18 P18 P20 P20 P22 P22 P24 P24 p26 p26 P28 P28 P30 P30 P32 P32P36 P36 P4 P4 F6 F6 F8 F8 P34 P34 P12 P12 P14 P14 P16 P16 P18 P18 P20 P20 P22 P22 P24 P24 p26 p26 P28 P28 P30 P30 P38 P38P40 P40 P44 P44 P48 P48 P60 P60 P62 P62 Checkpoint at BNE instruction P38 P38P40 P40 P44 P44 P48 P48 P60 P60 P62 P62 Checkpoint at BNE instruction
P32 P32P36 P36 P4 P4 Current Map Table Freelist P32 P32P36 P36 P4 P4 显式寄存器换名 (R10000 Style) F6 F6 F6 F6 F8 F8 F8 F8 P34 P34 P38 P38P40 P40 P44 P44 P48 P48 P60 P60 P62 P62 P34 P34 P38 P38P40 P40 P44 P44 P48 P48 P60 P60 P62 P62 P12 P12 P14 P14 P16 P16 P18 P18 P20 P20 P22 P22 P24 P24 p26 p26 P28 P28 P30 P30 F2 F2 P2 P2 DIVD DIVD P36,P34,P6 F10 F10P10 ADDD ADDD P34,P4,P32 P0 P0 LD LD P32,10(R2) N N y y y y P12 P12 P14 P14 P16 P16 P18 P18 P20 P20 P22 P22 P24 P24 p26 p26 P28 P28 P30 P30 Checkpoint at BNE instruction Newest Speculation error fixed by restoring map table and freelist 小结 Dynamic hardware schemes can unroll loops dynamically in hardware Form of limited dataflow Reorder Buffer In-order issue, Out-of-order execution, In-order commit Holds results until they can be commited in order Serves as source of info until instructions committed Provides support for precise exceptions/speculation: simply throw out instructions later than excepted instruction. Disambiguation: Tracking of RAW hazards through memory Keep program-order queue of stores When have address for load, check store queue: If any store prior to load is waiting for its address, stall load. If load address matches earlier store address (associative lookup), then we have a memory-induced RAW hazard: Otherwise, send out request to memory 小结 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