没有幻灯片标题

Transcription

1 高等计算机系统结构 Tomasulo 算法 ( 第四讲 ) 程旭 2004 年 3 月 8 日

2 上一讲小结 软件或硬件的指令级并行 (ILP) 循环级并行最容易判定 软件并行性取决于程序, 如果硬件不能支持就出现冒险 软件相关性 / 编译器复杂性决定编译中是否能展开循环 存储器相关是最难判定的 硬件开采 ILP 动态调度 (dynamic scheduling) 在编译时有些相关情况不能真正判定, 可以简化编译器 针对某一机器产生的代码可以在另一机器上有效运行 记分板的核心思想 : 允许暂停之后的指令提前处理 ( 译码 => 发射指令 & 读取操作数 ) 允许乱序执行 => 乱序完成 ID 段检测所有的结构冒险 北京大学计算机科学技术系

3 相关和冒险 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

4 记分板体系结构 Registers FP FP Mult Mult FP FP Mult Mult FP FP Divide Divide FP FP Add Add Integer Functional Units SCOREBOARD Memory

5 记分板控制的四级 发射 指令译码并检测结构冒险 (ID1) 按照程序的次序发射指令 ( 进行冒险检测 ) 如果存在结构冒险暂停发射 如果带发射的指令与已发射但尚未完成的指令之间存在输出相关, 则暂停发射 ( 无 WAW 冒险 ) 读操作数 等待到没有数据冒险, 再读取操作数 (ID2) 由于将等待未完成指令写回其结果, 因而在该阶段, 可解决所有的真数据相关 (RAW 冒险 ) 在该模型中, 无数据前递! 北京大学计算机科学技术系

6 记分板控制的四级 ( 续一 ) 执行 对操作数进行操作 (EX) 接收到操作数之后, 功能部件开始执行 当产生结果之后, 它通报记分板 : 已经完成执行 写结果 完成执行 (WB) 暂停直到与以前的指令没有 WAR 冒险 : 示例 : DIVD F0,F2,F4 ADDD F10,F0,F8 SUBD F8,F8,F14 CDC 6600 的记分板将暂停 SUBD 指令, 直到 ADDD 指令读取了操作数

7 记分板的三个主要组成部分 1. Instruction status 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. Register result status Indicates which functional unit will write each register, if one exists. Blank when no pending instructions will write that register 北京大学计算机科学技术系

8 CDC 6600 的记分板 来自编译的加速比 1.7; 手编代码的加速比 2.5, 但是由于存储速度慢 ( 没有 Cache) 限制了加速比的提高 6600 记分板的局限性 : 没有前递硬件 指令调度局限于基本块内 ( 指令窗口小 ) 功能部件少 ( 结构冒险 ), 特别是 integer/load store 部件 存在结构冒险, 就暂停发射指令 等待到 WAR 冒险解决 防止 WAW 冒险

9 记分板流水线控制的细节 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

10 另一个动态算法 : 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, 北京大学计算机科学技术系

11 Tomasulo 算法与记分板 控制 & 缓冲器分布于功能部件 (FU) 与集中于记分板 ; 功能部件缓冲器称为 保留站 (reservation stations) ; 存放未决的操作数 指令中的寄存器被数值或者指向保留站的指针代替 ; 这一过程称为寄存器换名 (register renaming) ; 消除 WAR WAW 冒险 保留站比实际寄存器多, 因而可以完成优化编译器所不能完成的一些工作 结果从 RS 直接到 FU, 无需通过寄存器, 而是通过公共数据总线 (Common Data Bus) 把结果广播到所有 FU 装入 (Load) 和存储 (Stores) 也象其他功能部件一样使用保留站

12 Load Buffer Common Data Bus From Memory FP Add Res. Station Tomasulo 的结构图 Operation Bus Adders FP Op Queue From Instruction Unit Reservation Station Multers FP Registers To Memory FP Mul Res. Station Store Buffer Common Data Bus(CDB)

13 Tomasulo 算法的三段 1. Issue 从 FP Op Queue 中取出指令 如果保留站空闲 ( 无结构冒险 ), 控制机制发射指令 & 发送操作数 ( 对寄存器进行换名 ) 2. Execution 对操作数执行操作 (EX) 如果两个操作数都已就绪, 就执行 ; 如果没有就绪, 就观测公共数据总线等待所需结果 3. Write result 完成执行 (WB) 通过公共数据总线将结果写入到所有等待的部件 ; 标记保留站可用 正常的数据总线 : 数据 + 目的 ( 去向 总线 ) 公共数据总线 : 数据 + 源 ( 来源 总线 ) 64 位数据 + 4 位功能部件源地址 如果与期望的功能部件匹配, 就 写 ( 产生结果 ) 进行广播 北京大学计算机科学技术系

14 保留站的组成 Op 该部件将完成的具体操作 ( 例如, + or ) Vj, Vk 源操作数的实际数值 存储缓冲器 (Store buffers) 设有 V 域, 存放将存储的结果 Qj, Qk 将产生源寄存器值 ( 将写的值 ) 的保留站 注意 : 没有记分板中的就绪 (READY) 标志 ;Qj,Qk=0 ready 存储缓冲器 (Store buffers) 中只有存放 RS 产生结果的 Qi Busy 指明保留站或 FU 处于忙状态 Register result status 指明哪个功能部件将写到哪个寄存器 (Qi); 如果没有将写入寄存器的未决指令, 该域为空 北京大学计算机科学技术系

15 Tomasulo 示例第 0 周期 Instruction status Execution Write Instruction j k Issue complete Result Busy Address 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 Reservation Stations S1 S2 RS for j RS for k Time Name BusyOp Vj Vk Qj Qk LD: 0Add1No 0Add2No ADD: 0Add3No Mult: 0Mult1No 0Mult2No Divd: Register result status 2 cycles 2 cycles 10 cycles 40 cycles Clock F0 F2 F4 F6 F8 F10 F12... F30 0 FU

16 Tomasulo 示例第 1 周期 Instruction status Execution Write Instruction j k Issue complete Result Busy Address LD F6 34+ R2 1 2 Load1 Yes 34+R2 LD F2 45+ R3 0 Load2 No MUL F0 F2 F4 0 Load3 No SUB F8 F6 F2 DIVDF10 F0 F6 ADD F6 F8 F2 Reservation Stations S1 S2 RS for j RS for k TimeNameBusyOp Vj Vk Qj Qk 0Add1No 0Add2No Add3 No 0Mult1No 0Mult2No Register result status Clock F0 F2 F4 F6 F8 F10 F12... F30 1 FU Load1

17 Tomasulo 示例第 2 周期 Instruction status Execution Write Instruction j k Issue complete Result Busy Address LD F6 34+ R2 1 1 Load1 Yes 34+R2 LD F2 45+ R3 2 2 Load2 Yes 45+R3 MUL F0 F2 F4 0Load3No SUB F8 F6 F2 DIVDF10 F0 F6 ADD F6 F8 F2 Reservation Stations S1 S2 RS for j RS for k TimeNameBusyOp Vj Vk Qj Qk 0Add1No 0Add2No Add3 No 0Mult1No 0Mult2No Register result status Clock F0 F2 F4 F6 F8 F10 F12... F30 2 FU Load2 Load1 注意 : 与 CDC6600 不同, 可以有多个 loads 被发射 ; 记分板能否改进?

18 Tomasulo 示例第 3 周期 Instruction status Execution Write Instruction j k Issue complete Result Busy Address LD F6 34+ R Load1 Yes 34+R2 LD F2 45+ R3 2 1 Load2 Yes 45+R3 MUL F0 F2 F4 3 0 Load3 No SUB F8 F6 F2 DIVDF10 F0 F6 ADD F6 F8 F2 Reservation Stations S1 S2 RS for j RS for k TimeNameBusyOp Vj Vk Qj Qk 0Add1No 0Add2No Add3 No 0Mult1Yes MULTD R(F4) Load2 0Mult2No Register result status Clock F0 F2 F4 F6 F8 F10 F12... F30 3 FU Mult1 Load2 Load1 注意 : 保留站中寄存器名被 换名 ; MULT 可发射 ( 与记分板比较 ) Load1 完成 ; 哪些指令在等待 Load1?

19 Tomasulo 示例第 4 周期 Instruction status Execution Write Instruction j k Issue complete Result Busy Address LD F6 34+ R Load1 No LD F2 45+ R Load2 Yes 45+R3 MUL F0 F2 F4 3 0 Load3 No SUB F8 F6 F2 4 DIVDF10 F0 F6 ADD F6 F8 F2 Reservation Stations S1 S2 RS for j RS for k TimeNameBusyOp Vj Vk Qj Qk 0 Add1 Yes SUBDM(34+R2) Load2 0 Add2 No Add3 No 0Mult1Yes MULTD R(F4) Load2 0Mult2No Register result status Clock F0 F2 F4 F6 F8 F10 F12... F30 4 FU Mult1 Load2 M(34+R2) Add1 Load2 将完成 ; 哪些指令在等待 Load2?

20 Instruction status Tomasulo 示例第 5 周期 Execution Write Instruction j k Issue complete Result Busy Address LD F6 34+ R Load1 No LD F2 45+ R Load2 No MUL F0 F2 F4 3 Load3 No SUB F8 F6 F2 4 DIVDF10 F0 F6 5 ADD F6 F8 F2 Reservation Stations S1 S2 RS for j RS for k TimeNameBusyOp Vj Vk Qj Qk 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 Register result status Clock F0 F2 F4 F6 F8 F10 F12... F30 5 FU Mult1 M(45+R3) M(34+R2) Add1 Mult2

21 Tomasulo 示例第 6 周期 Instruction status Execution Write Instruction j k Issue complete Result Busy Address LD F6 34+ R Load1 No LD F2 45+ R Load2 No MUL F0 F2 F4 3 Load3 No SUB F8 F6 F2 4 DIVDF10 F0 F6 5 ADD F6 F8 F2 6 Reservation Stations S1 S2 RS for j RS for k Time Name BusyOp Vj Vk Qj Qk 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 Register result status Clock F0 F2 F4 F6 F8 F10 F12... F30 6 FU Mult1 M(45+R3) Add2 Add1 Mult2 发射 ADDD

22 Tomasulo 示例第 7 周期 Instruction status Execution Write Instruction j k Issue complete Result Busy Address LD F6 34+ R Load1 No LD F2 45+ R Load2 No MULF0 F2 F4 3 Load3 No SUB F8 F6 F2 4 7 DIVDF10 F0 F6 5 ADD F6 F8 F2 6 Reservation Stations S1 S2 RS for j RS for k Time Name BusyOp Vj Vk Qj Qk 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 Register result status Clock F0 F2 F4 F6 F8 F10 F12... F30 7 FU Mult1 M(45+R3) Add2 Add1 Mult2 Add1 完成 ; 哪些指令在等待 Add1?

23 Tomasulo 示例第 8 周期 Instruction status Execution Write Instruction j k Issue complete Result Busy Address LD F6 34+ R Load1 No LD F2 45+ R Load2 No MUL F0 F2 F4 3 Load3 No SUB F8 F6 F DIVDF10 F0 F6 5 ADD F6 F8 F2 6 Reservation Stations S1 S2 RS for j RS for k TimeNameBusyOp Vj Vk Qj Qk 0Add1No 2Add2YesADDDM()-M() M(45+R3) Add3 No 7Mult1Yes MULTM(45+R3) R(F4) 0Mult2Yes DIVD M(34+R2) Mult1 Register result status Clock F0 F2 F4 F6 F8 F10 F12... F30 8 FU Mult1 M(45+R3) Add2 M()-M() Mult2

24 Tomasulo 示例第 9 周期 Instruction j k Issue complete Result Busy Address LD F6 34+ R Load1 No LD F2 45+ R Load2 No MUL F0 F2 F4 3 Load3 No SUB F8 F6 F DIVDF10 F0 F6 5 ADD F6 F8 F2 6 Reservation Stations S1 S2 RS for j RS for k TimeNameBusyOp Vj Vk Qj Qk 0Add1No 1Add2YesADDDM()-M() M(45+R3) Add3 No 6Mult1Yes MULTM(45+R3) R(F4) 0Mult2Yes DIVD M(34+R2) Mult1 Register result status Clock F0 F2 F4 F6 F8 F10 F12... F30 9 FU Mult1 M(45+R3) Add2 M()-M() Mult2 Button 3 Button 4 Button 5 B tt 6 北京大学计算机科学技术系

25 Instruction status Execution Write Instruction j k Issue complete Result Busy Address LD F6 34+ R Load1 No LD F2 45+ R Load2 No MUL F0 F2 F4 3 Load3 No SUB F8 F6 F DIVDF10 F0 F6 5 ADD F6 F8 F Reservation Stations S1 S2 RS for j RS for k TimeNameBusyOp Vj Vk Qj Qk 0Add1No 0Add2YesADDDM()-M() M(45+R3) Add3 No 5Mult1Yes MULTM(45+R3) R(F4) 0Mult2Yes DIVD M(34+R2) Mult1 Register result status Clock F0 F2 F4 F6 F8 F10 F12... F30 10 FU Mult1 M(45+R3) Add2 M()-M() Mult2 Add2 完成 ; 哪些指令在等待 Add2? 北京大学计算机科学技术系 Tomasulo 示例第 10 周期

26 Tomasulo 示例第 11 周期 Instruction status Execution Write Instruction j k Issue complete Result Busy Address LD F6 34+ R Load1 No LD F2 45+ R Load2 No MUL F0 F2 F4 3 Load3 No SUB F8 F6 F DIVDF10 F0 F6 5 ADD F6 F8 F Reservation Stations S1 S2 RS for j RS for k TimeNameBusyOp Vj Vk Qj Qk 0Add1No 0Add2No Add3 No 4 Mult1 Yes MULT M(45+R3) R(F4) 0Mult2Yes DIVD M(34+R2) Mult1 Register result status Clock F0 F2 F4 F6 F8 F10 F12... F30 11 FU Mult1 M(45+R3) (M-M)+M()M()-M( Mult2 ADDD 在该周期写结果

27 Instruction status 北京大学计算机科学技术系 Tomasulo 示例第 12 周期 Execution Write Instruction j k Issue complete Result Busy Address LD F6 34+ R Load1 No LD F2 45+ R Load2 No MUL F0 F2 F4 3 Load3 No SUB F8 F6 F DIVDF10 F0 F6 5 ADD F6 F8 F Reservation Stations S1 S2 RS for j RS for k TimeNameBusyOp Vj Vk Qj Qk 0Add1No 0Add2No Add3 No 3Mult1Yes MULTM(45+R3) R(F4) 0Mult2Yes DIVD M(34+R2) Mult1 Register result status Clock F0 F2 F4 F6 F8 F10 F12... F30 12 FU Mult1 M(45+R3) (M-M)+M()M()-M() Mult2 注意 : 所有短周期指令都已经完成

28 Tomasulo 示例第 13 周期 Instruction status Execution Write Instruction j k Issue complete Result Busy Address LD F6 34+ R Load1 No LD F2 45+ R Load2 No MUL F0 F2 F4 3 Load3 No SUB F8 F6 F DIVDF10 F0 F6 5 ADD F6 F8 F Reservation Stations S1 S2 RS for j RS for k TimeNameBusyOp Vj Vk Qj Qk 0Add1No 0Add2No Add3 No 2Mult1Yes MULTM(45+R3) R(F4) 0Mult2Yes DIVD M(34+R2) Mult1 Register result status Clock F0 F2 F4 F6 F8 F10 F12... F30 13 FU Mult1 M(45+R3) (M-M)+M()M()-M() Mult2

29 Tomasulo 示例第 14 周期 Instruction status Execution Write Instruction j k Issue complete Result Busy Address LD F6 34+ R Load1 No LD F2 45+ R Load2 No MUL F0 F2 F4 3 Load3 No SUB F8 F6 F DIVDF10 F0 F6 5 ADD F6 F8 F Reservation Stations S1 S2 RS for j RS for k TimeNameBusyOp Vj Vk Qj Qk 0Add1No 0Add2No Add3 No 1Mult1Yes MULTM(45+R3) R(F4) 0Mult2Yes DIVD M(34+R2) Mult1 Register result status Clock F0 F2 F4 F6 F8 F10 F12... F30 14 FU Mult1 M(45+R3) (M-M)+M()M()-M( Mult2

30 Tomasulo 示例第 15 周期 Instruction status Execution Write Instruction j k Issue complete Result Busy Address LD F6 34+ R Load1 No LD F2 45+ R Load2 No MULF0 F2 F Load3 No SUB F8 F6 F DIVDF10 F0 F6 5 ADD F6 F8 F Reservation Stations S1 S2 RS for j RS for k Time Name BusyOp Vj Vk Qj Qk 0Add1No 0Add2No Add3 No 0Mult1Yes MULTM(45+R3) R(F4) 0Mult2Yes DIVD M(34+R2) Mult1 Register result status Clock F0 F2 F4 F6 F8 F10 F12... F30 15 FU Mult1 M(45+R3) (M-M)+M()M()-M() Mult2 Mult1 completing; what is waiting for it?

31 Instruction status 北京大学计算机科学技术系 Tomasulo 示例第 16 周期 Execution Write Instruction j k Issue complete Result Busy Address LD F6 34+ R Load1 No LD F2 45+ R Load2 No MULF0 F2 F Load3 No SUB F8 F6 F DIVDF10 F0 F6 5 ADD F6 F8 F Reservation Stations S1 S2 RS for j RS for k Time Name BusyOp Vj Vk Qj Qk 0 Add1 No 0 Add2 No Add3 No 0Mult1No 40 Mult2 Yes DIVD M*F4 M(34+R2) Register result status Clock F0 F2 F4 F6 F8 F10 F12... F30 16 FU M*F4 M(45+R3) (M-M)+M()M()-M() Mult2 注意 : 只有除法指令没有完成

32 Instruction status Tomasulo 示例第 55 周期 Execution Write Instruction j k Issue complete Result Busy Address LD F6 34+ R Load1 No LD F2 45+ R Load2 No MUL F0 F2 F Load3 No SUB F8 F6 F DIVDF10 F0 F6 5 ADD F6 F8 F Reservation Stations S1 S2 RS for j RS for k Time Name BusyOp Vj Vk Qj Qk 0 Add1 No 0 Add2 No Add3 No 0Mult1No 1Mult2Yes DIVD M*F4 M(34+R2) Register result status Clock F0 F2 F4 F6 F8 F10 F12... F30 55 FU M*F4 M(45+R3) (M-M)+M()M()-M() Mult2

33 Instruction status 北京大学计算机科学技术系 Tomasulo 示例第 56 周期 Execution Write Instruction j k Issue complete Result Busy Address LD F6 34+ R Load1 No LD F2 45+ R Load2 No MUL F0 F2 F Load3 No SUB F8 F6 F DIVDF10 F0 F ADD F6 F8 F Reservation Stations S1 S2 RS for j RS for k Time Name BusyOp Vj Vk Qj Qk 0 Add1 No 0 Add2 No Add3 No 0Mult1No 0Mult2Yes DIVD M*F4 M(34+R2) Register result status Clock F0 F2 F4 F6 F8 F10 F12... F30 56 FU M*F4 M(45+R3) (M-M)+M()M()-M() Mult2 Mult 2 完成

34 Instruction status 北京大学计算机科学技术系 Tomasulo 示例第 57 周期 Execution Write Instruction j k Issue complete Result Busy Address LD F6 34+ R Load1 No LD F2 45+ R Load2 No MUL F0 F2 F Load3 No SUB F8 F6 F DIVDF10 F0 F ADD F6 F8 F Reservation Stations S1 S2 RS for j RS for k Time Name BusyOp Vj Vk Qj Qk 0Add1No 0Add2No Add3 No 0Mult1No 0Mult2No Register result status Clock F0 F2 F4 F6 F8 F10 F12... F30 57 FU M*F4 M(45+R3) 也是, 按序发送 (M-M)+M()M()-M() M*F4/M 乱序执行 乱序完成

35 与记分板的第 62 周期相比 Instruction status Read Execu Write Instruction j k IssueoperancompleResult LD F6 34+ R LD F2 45+ R MULF0 F2 F SUBF8 F6 F DIVDF10 F0 F ADD F6 F8 F 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 Register result status Clock F0 F2 F4 F6 F8 F10 F12... F30 62 FU CDC6600 的记分板为什么需要更长的时间?

36 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 指令相同暂停完成暂停发射写 / 读寄存器集中控制的记分板 北京大学计算机科学技术系

37 Tomasulo 算法的缺点 复杂 360/91 MIPS IBM PPC620 的延迟? 需要大量高速的相联存储 (associative buffer) 公共数据总线将成为制约性能增长的瓶颈 每个 CDB 必须广播到多个功能部件单元 大容量 写操作密集 每个周期可以同时完成的功能部件数量可能由于单总线而受限 ( 最坏情况为 1 )! 多个 CDB => 为完成并行相联存储, 功能部件 FU 需要更复杂的逻辑控制

38 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 的周期数 实际上, 整数指令先行 北京大学计算机科学技术系

39 循环示例 第 0 周期 Instruction status Executi Write Instruction j k iteration Issue comple Result BusyAddress 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 Reservation Stations S1 S2 RS forrs for k TimeName BusyOp Vj Vk Qj Qk Code: 0Add1No LD F0 0 R1 0Add2No MUL F4 F0 F2 0Add3No SD F4 0 R1 0Mult1No SUB R1 R1 #8 0Mult2No BNEZR1 Loop Register result status Clock R1 F0 F2 F4 F6 F8 F10 F12... F Qi

40 循环示例 第 1 周期 Instruction status Executi Write Instruction j k iteration Issue comple Result BusyAddress 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 Reservation Stations S1 S2 RS forrs for k TimeName BusyOp Vj Vk Qj Qk Code: 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 Register result status Clock R1 F0 F2 F4 F6 F8 F10 F12... F Qi Load1

41 Instruction status 北京大学计算机科学技术系 循环示例 第 2 周期 Executi Write Instruction j k iteration Issue comple Result BusyAddress 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 Reservation Stations S1 S2 RS forrs for k TimeName BusyOp Vj Vk Qj Qk Code: 0Add1No LD F0 0 R1 0Add2No MUL F4 F0 F2 0Add3No SD F4 0 R1 0 Mult1 Yes MULTD R(F2) Load1 SUB R1 R1 #8 0 Mult2 No BNEZR1 Loop Register result status Clock R1 F0 F2 F4 F6 F8 F10 F12... F Qi Load1 Mult1

42 循环示例 第 3 周期 Instruction status Executi Write Instruction j k iteration Issue comple Result BusyAddress 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 Reservation Stations S1 S2 RS forrs for k TimeName BusyOp Vj Vk Qj Qk Code: 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 Register result status Clock R1 F0 F2 F4 F6 F8 F10 F12... F Qi Load1 Mult1 注意 : 隐含的换名功能动态建立起 数据流 图

43 循环示例 第 4 周期 Instruction status Executi Write Instruction j k iteration Issue comple Result BusyAddress 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 Reservation Stations S1 S2 RS forrs for k TimeName BusyOp Vj Vk Qj Qk Code: 0Add1No LD F0 0 R1 0Add2No MUL F4 F0 F2 0Add3No SD F4 0 R1 0Mult1Yes MULTD R(F2) Load1 SUB R1 R1 #8 0Mult2No BNEZR1 Loop Register result status Clock R1 F0 F2 F4 F6 F8 F10 F12... F Qi Load1 Mult1 北京大学计算机科学技术系 注意 : 发送 SUB 指令

44 循环示例 第 5 周期 Instruction status Executi Write Instruction j k iteration Issue comple Result BusyAddress 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 Reservation Stations S1 S2 RS forrs for k TimeName BusyOp Vj Vk Qj Qk Code: 0Add1No LD F0 0 R1 0Add2No MUL F4 F0 F2 0Add3No SD F4 0 R1 0Mult1Yes MULTD R(F2) Load1 SUB R1 R1 #8 0Mult2No BNEZR1 Loop Register result status Clock R1 F0 F2 F4 F6 F8 F10 F12... F Qi Load1 Mult1 注意 : 处理 BNEZ 指令

45 循环示例 第 6 周期 Instruction status Executi Write Instruction j k iteration Issue comple Result BusyAddress 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 Reservation Stations S1 S2 RS forrs for k TimeName BusyOp Vj Vk Qj Qk Code: 0Add1No LD F0 0 R1 0Add2No MUL F4 F0 F2 0Add3No SD F4 0 R1 0Mult1Yes MULTD R(F2) Load1 SUB R1 R1 #8 0Mult2No BNEZR1 Loop Register result status Clock R1 F0 F2 F4 F6 F8 F10 F12... F Qi Load2 Mult1 注意 : F0 一直看不到 Load1 的结果 北京大学计算机科学技术系

46 循环示例 第 7 周期 Instruction status 北京大学计算机科学技术系 Executi Write Instruction j k iteration Issue comple Result BusyAddress 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 Reservation Stations S1 S2 RS forrs for k TimeName BusyOp Vj Vk Qj Qk Code: 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 Register result status Clock R1 F0 F2 F4 F6 F8 F10 F12... F Qi Load2 Mult2 Note: MULT2 has no registers names in RS

47 Instruction status 北京大学计算机科学技术系 循环示例 第 8 周期 Executi Write Instruction j k iteration Issue comple Result BusyAddress 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 Reservation Stations S1 S2 RS forrs for k TimeName BusyOp Vj Vk Qj Qk Code: 0Add1No LD F0 0 R1 0Add2No MUL F4 F0 F2 0Add3No SD F4 0 R1 0Mult1Yes MULTD R(F2) Load1 SUB R1 R1 #8 0Mult2Yes MULTD R(F2) Load2 BNEZR1 Loop Register result status Clock R1 F0 F2 F4 F6 F8 F10 F12... F Qi Load2 Mult2

48 Instruction status 北京大学计算机科学技术系 循环示例 第 9 周期 Executi Write Instruction j k iteration Issue comple Result BusyAddress LD F0 0 R 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 Reservation Stations S1 S2 RS forrs for k TimeName BusyOp Vj Vk Qj Qk Code: 0Add1No LD F0 0 R1 0Add2No MUL F4 F0 F2 0Add3No SD F4 0 R1 0Mult1Yes MULTD R(F2) Load1 SUB R1 R1 #8 0Mult2Yes MULTD R(F2) Load2 BNEZR1 Loop Register result status Clock R1 F0 F2 F4 F6 F8 F10F12... F Qi Load2 Mult2 Load1 完成, 注意等待其结果的指令! 注意 : 发送 SUB 指令

49 Instruction status 北京大学计算机科学技术系 循环示例 第 10 周期 Executi Write Instruction j k iteration Issue comple Result BusyAddress LD F0 0 R Load1 No MULF4 F0 F2 1 2 Load2 Yes 72 SD F4 0 R1 1 3 Load3 No Qi LD F0 0 R Store1Yes 80 Mult1 MUL F4 F0 F2 2 7 Store2Yes 72 Mult2 SD F4 0 R1 2 8 Store3No Reservation Stations S1 S2 RS forrs for k TimeName BusyOp Vj Vk Qj Qk Code: 0Add1No LD F0 0 R1 0Add2No MULT F4 F0 F2 0Add3No SD F4 0 R1 4Mult1Yes MULTD M(80)R(F2) SUBI R1 R1 #8 0Mult2Yes MULTD R(F2) Load2 BNEZ R1 Loop Register result status Clock R1 F0 F2 F4 F6 F8 F10 F12... F Qi Load2 Mult2 Load2 Load1 完成, 注意等待其结果的指令

50 循环示例 第 11 周期 Instruction status 北京大学计算机科学技术系 Executi Write Instruction j k iteration Issue comple Result BusyAddress LD F0 0 R Load1 No MULF4 F0 F2 1 2 Load2 No SD F4 0 R1 1 3 Load3 Yes 64 Qi LD F0 0 R Store1Yes 80 Mult1 MUL F4 F0 F2 2 7 Store2Yes 72 Mult2 SD F4 0 R1 2 8 Store3No Reservation Stations S1 S2 RS forrs for k TimeName BusyOp Vj Vk Qj Qk Code: 0Add1No LD F0 0 R1 0Add2No MULT F4 F0 F2 0Add3No SD F4 0 R1 3Mult1Yes MULTD M(80)R(F2) SUBI R1 R1 #8 4Mult2Yes MULTD M(72)R(F2) BNEZ R1 Loop Register result status Clock R1 F0 F2 F4 F6 F8 F10 F12... F Qi Load3 Mult2

51 循环示例 第 12 周期 Instruction status Executi Write Instruction j k iteration Issue comple Result BusyAddress LD F0 0 R Load1 No MUL F4 F0 F2 1 2 Load2 No SD F4 0 R1 1 3 Load3 Yes 64 Qi LD F0 0 R Store1Yes 80 Mult1 MUL F4 F0 F2 2 7 Store2 Yes 72 Mult2 SD F4 0 R1 2 8 Store3No Reservation Stations S1 S2 RS forrs for k TimeName BusyOp Vj Vk Qj Qk Code: 0Add1No LD F0 0 R1 0Add2No MULT F4 F0 F2 北京大学计算机科学技术系 为什么不能发送第三次迭代的乘法? 0Add3No SD F4 0 R1 2Mult1Yes MULTD M(80)R(F2) SUBI R1 R1 #8 3Mult2Yes MULTD M(72)R(F2) BNEZ R1 Loop Register result status Clock R1 F0 F2 F4 F6 F8 F10 F12... F Qi Load3 Mult2

52 Instruction status 北京大学计算机科学技术系 循环示例 第 13 周期 Executi Write Instruction j k iteration Issue comple Result BusyAddress LD F0 0 R Load1 No MULF4 F0 F2 1 2 Load2 No SD F4 0 R1 1 3 Load3 Yes 64 Qi LD F0 0 R Store1 Yes 80 Mult1 MUL F4 F0 F2 2 7 Store2 Yes 72 Mult2 SD F4 0 R1 2 8 Store3 No Reservation Stations S1 S2 RS forrs for k TimeName BusyOp Vj Vk Qj Qk Code: 0Add1No LD F0 0 R1 0Add2No MULT F4 F0 F2 0Add3No SD F4 0 R1 1Mult1Yes MULTD M(80)R(F2) SUBI R1 R1 #8 2Mult2Yes MULTD M(72)R(F2) BNEZ R1 Loop Register result status Clock R1 F0 F2 F4 F6 F8 F10 F12... F Qi Load3 Mult2

53 循环示例 第 14 周期 Instruction status 北京大学计算机科学技术系 Executi Write Instruction j k iteration Issue comple Result BusyAddress LD F0 0 R Load1 No MUL F4 F0 F Load2 No SD F4 0 R1 1 3 Load3Yes 64 Qi LD F0 0 R Store1Yes 80 Mult1 MUL F4 F0 F2 2 7 Store2 Yes 72 Mult2 SD F4 0 R1 2 8 Store3No Reservation Stations S1 S2 RS forrs for k TimeName BusyOp Vj Vk Qj Qk Code: 0Add1No LD F0 0 R1 0Add2No MULT F4 F0 F2 0Add3No SD F4 0 R1 0Mult1Yes MULTD M(80)R(F2) SUBI R1 R1 #8 1Mult2Yes MULTD M(72)R(F2) BNEZ R1 Loop Register result status Clock R1 F0 F2 F4 F6 F8 F10 F12... F Qi Load3 Mult2 Mult1 完成

54 Instruction status 北京大学计算机科学技术系 循环示例 第 15 周期 Executi Write Instruction j k iteration Issue comple Result BusyAddress LD F0 0 R Load1 No MUL F4 F0 F Load2 No SD F4 0 R1 1 3 Load3Yes 64 Qi LD F0 0 R Store1Yes 80 M(80)*R MUL F4 F0 F Store2 Yes 72 Mult2 SD F4 0 R1 2 8 Store3No Reservation Stations S1 S2 RS forrs for k TimeName BusyOp Vj Vk Qj Qk Code: 0Add1No LD F0 0 R1 0Add2No MULT F4 F0 F2 0Add3No SD F4 0 R1 0Mult1No SUBI R1 R1 #8 0Mult2Yes MULTD M(72)R(F2) BNEZ R1 Loop Register result status Clock R1 F0 F2 F4 F6 F8 F10 F12... F Qi Load3 Mult2 Mult2 完成

55 Instruction status 北京大学计算机科学技术系 循环示例 第 16 周期 Executi Write Instruction j k iteration Issue comple Result BusyAddress LD F0 0 R Load1 No MUL F4 F0 F Load2 No SD F4 0 R1 1 3 Load3 Yes 64 Qi LD F0 0 R Store1Yes 80 M(80)*R MUL F4 F0 F Store2 Yes 72 M(72)*R SD F4 0 R1 2 8 Store3No Reservation Stations S1 S2 RS forrs for k TimeName BusyOp Vj Vk Qj Qk Code: 0Add1No LD F0 0 R1 0Add2No MULT F4 F0 F2 0Add3No SD F4 0 R1 0 Mult1 Yes MULTD R(F2) Load3 SUBI R1 R1 #8 0Mult2No BNEZ R1 Loop Register result status Clock R1 F0 F2 F4 F6 F8 F10 F12... F Qi Load3 Mult1

56 Instruction status 北京大学计算机科学技术系 循环示例 第 17 周期 Executi Write Instruction j k iteration Issue comple Result BusyAddress LD F0 0 R Load1 No MUL F4 F0 F Load2 No SD F4 0 R1 1 3 Load3 Yes 64 Qi LD F0 0 R Store1Yes 80 M(80)*R MUL F4 F0 F Store2 Yes 72 M(72)*R SD F4 0 R1 2 8 Store3Yes 64 Mult1 Reservation Stations S1 S2 RS forrs for k TimeName BusyOp Vj Vk Qj Qk Code: 0Add1No LD F0 0 R1 0Add2No MULT F4 F0 F2 0Add3No SD F4 0 R1 0 Mult1 Yes MULTD R(F2) Load3 SUBI R1 R1 #8 0Mult2No BNEZ R1 Loop Register result status Clock R1 F0 F2 F4 F6 F8 F10 F12... F Qi Load3 Mult1

57 Instruction status 北京大学计算机科学技术系 循环示例 第 18 周期 Executi Write Instruction j k iteration Issue comple Result BusyAddress LD F0 0 R Load1 No MUL F4 F0 F Load2 No SD F4 0 R Load3 Yes 64 Qi LD F0 0 R Store1Yes 80 M(80)*R MUL F4 F0 F Store2 Yes 72 M(72)*R SD F4 0 R1 2 8 Store3Yes 64 Mult1 Reservation Stations S1 S2 RS forrs for k TimeName BusyOp Vj Vk Qj Qk Code: 0Add1No LD F0 0 R1 0Add2No MULT F4 F0 F2 0Add3No SD F4 0 R1 0 Mult1 Yes MULTD R(F2) Load3 SUBI R1 R1 #8 0Mult2No BNEZ R1 Loop Register result status Clock R1 F0 F2 F4 F6 F8 F10 F12... F Qi Load3 Mult1

58 Instruction status 北京大学计算机科学技术系 循环示例 第 19 周期 Executi Write Instruction j k iteration Issue comple Result BusyAddress LD F0 0 R Load1 No MULF4 F0 F Load2 No SD F4 0 R Load3 Yes 64 Qi LD F0 0 R Store1No MUL F4 F0 F Store2Yes 72 M(72)*R SD F4 0 R1 2 8 Store3Yes 64 Mult1 Reservation Stations S1 S2 RS forrs for k TimeName BusyOp Vj Vk Qj Qk Code: 0Add1No LD F0 0 R1 0Add2No MULT F4 F0 F2 0Add3No SD F4 0 R1 0 Mult1 Yes MULTD R(F2) Load3 SUBI R1 R1 #8 0Mult2No BNEZ R1 Loop Register result status Clock R1 F0 F2 F4 F6 F8 F10 F12... F Qi Load3 Mult1

59 循环示例 第 20 周期 Instruction status 北京大学计算机科学技术系 Executi Write Instruction j k iteration Issue comple Result BusyAddress LD F0 0 R Load1 No MUL F4 F0 F Load2 No SD F4 0 R Load3 Yes 64 Qi LD F0 0 R Store1No MUL F4 F0 F Store2 Yes 72 M(72)*R SD F4 0 R Store3Yes 64 Mult1 Reservation Stations S1 S2 RS forrs for k TimeName BusyOp Vj Vk Qj Qk Code: 0Add1No LD F0 0 R1 0Add2No MULT F4 F0 F2 0Add3No SD F4 0 R1 0 Mult1 Yes MULTD R(F2) Load3 SUBI R1 R1 #8 0Mult2No BNEZ R1 Loop Register result status Clock R1 F0 F2 F4 F6 F8 F10 F12... F Qi Load3 Mult1

60 循环示例 第 21 周期 Instruction status 北京大学计算机科学技术系 Executi Write Instruction j k iteration Issue comple Result BusyAddress LD F0 0 R Load1 No MULF4 F0 F Load2 No SD F4 0 R Load3 Yes 64 Qi LD F0 0 R Store1No MUL F4 F0 F Store2No SD F4 0 R Store3Yes 64 Mult1 Reservation Stations S1 S2 RS forrs for k TimeName BusyOp Vj Vk Qj Qk Code: 0Add1No LD F0 0 R1 0Add2No MULT F4 F0 F2 0Add3No SD F4 0 R1 0 Mult1 Yes MULTD R(F2) Load3 SUBI R1 R1 #8 0Mult2No BNEZ R1 Loop Register result status Clock R1 F0 F2 F4 F6 F8 F10 F12... F Qi Load3 Mult1

61 Tomasulo 算法小结 保留站 : 换名到巨大的寄存器空间 + 缓存源操作数 防止寄存器成为性能瓶颈 防止记分板中的 WAR WAW 冒险 具有硬件动态完成循环展开的功能 不局限在基本块内 ( 整数部件可以先行, 跨越基本块 ) 对于降低 cache 失效开销有利 对后续机型的影响 : 动态调度寄存器换名 Load/store 别名分析 360/91 的后续包括 :Pentium III PowerPC 604 MIPS R10000 HP-PA 8000 Alpha 等等

62 如何实现精确意外 / 中断处理? 记分板和 Tomasulo 算法都可实现 : 按序发送 乱序执行 乱序完成 如果中断或意外被称为 精确当且仅当对于单条指令 : 所有该指令之前的指令都已经提交其状态 所有后续指令 ( 包括产生中断的指令 ) 没有改变任何机器状态 需要一定措施将指令执行的次序与指令发射流进行再同步 对于按序完成的机制, 最容易实现 北京大学计算机科学技术系

63 精确中断与推测式之间的关系 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 北京大学计算机科学技术系

64 硬件对精确中断的支持 重排序缓冲器 (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

65 ROB 中硬件实现的复杂性 Dest Reg Result Exceptions? Valid Program Counter FP Op Queue Compar network Reorder Buffer FP Regs Reorder Table Res Stations FP Adder Res Stations FP Adder 如何找到寄存器对应的最新内容? 需要相联比较网络可以使用 未来文件 或使用寄存器结果状态缓冲器来跟踪哪个特定重排序缓冲器将接受具体数值 需要 ROB 具有寄存器堆那么多的端口

66 FP Op Queue 具有重排序缓冲器的 Tomasulo 算法 Reorder Buffer F0 F0 LD LD F0,10(R2) Done? N ROB7 ROB6 ROB5 ROB4 ROB3 ROB2 ROB1 Newest Oldest Dest Registers Dest To Memory from Memory FP FP adders adders Reservation Stations FP FP multipliers Dest 1 10+R2 10+R2

67 FP Op Queue 具有重排序缓冲器的 Tomasulo 算法 Reorder Buffer F10 F10 F0 F0 ADDD ADDD F10,F4,F0 LD LD F0,10(R2) Done? N N N N ROB7 ROB6 ROB5 ROB4 ROB3 ROB2 ROB1 Newest Oldest Registers Dest 2 ADDD ADDD R(F4),ROB1 FP FP adders adders Dest Reservation Stations FP FP multipliers To Memory from Memory Dest 1 10+R2 10+R2

68 FP Op Queue 具有重排序缓冲器的 Tomasulo 算法 Reorder Buffer F2 F2 F10 F10 F0 F0 DIVD DIVD F2,F10,F6 ADDD ADDD F10,F4,F0 LD LD F0,10(R2) Done? N N N N N N ROB7 ROB6 ROB5 ROB4 ROB3 ROB2 ROB1 Newest Oldest Registers Dest 2 ADDD ADDD R(F4),ROB1 FP FP adders adders Reservation Stations Dest 3 DIVD DIVD ROB2,R(F6) FP FP multipliers To Memory from Memory Dest 1 10+R2 10+R2

69 FP Op Queue 具有重排序缓冲器的 Tomasulo 算法 Reorder Buffer F0 F0 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 F0 F0 LD LD F0,10(R2) Done? N N N N N N ROB7 ROB6 ROB5 ROB4 ROB3 ROB2 ROB1 Newest Oldest Dest 2 ADDD ADDD R(F4),ROB1 6 ADDD ADDD ROB5, ROB5, R(F6) R(F6) FP FP adders adders Registers Reservation Stations Dest 3 DIVD DIVD ROB2,R(F6) FP FP multipliers To Memory from Memory Dest 1 10+R2 10+R2 5 0+R3 0+R3

70 FP Op Queue 具有重排序缓冲器的 Tomasulo 算法 Reorder Buffer ROB5 ROB5 ST ST 0(R3),F4 F0 F0 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 F0 F0 LD LD F0,10(R2) Done? N N N N N N N ROB7 ROB6 ROB5 ROB4 ROB3 ROB2 ROB1 Newest Oldest Dest 2 ADDD ADDD R(F4),ROB1 6 ADDD ADDD ROB5, ROB5, R(F6) R(F6) FP FP adders adders Registers Reservation Stations Dest 3 DIVD DIVD ROB2,R(F6) FP FP multipliers To Memory from Memory Dest 1 10+R2 10+R2 5 0+R3 0+R3

71 FP Op Queue 具有重排序缓冲器的 Tomasulo 算法 Reorder Buffer M[10] M[10] ST ST 0(R3),F4 F0 F0 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 F0 F0 LD LD F0,10(R2) Done? Y N Y N N N N ROB7 ROB6 ROB5 ROB4 ROB3 ROB2 ROB1 Newest Oldest Dest 2 ADDD ADDD R(F4),ROB1 6 ADDD ADDD M[10],R(F6) FP FP adders adders Registers Reservation Stations Dest 3 DIVD DIVD ROB2,R(F6) FP FP multipliers To Memory from Memory Dest 1 10+R2 10+R2

72 FP Op Queue 具有重排序缓冲器的 Tomasulo 算法 Reorder Buffer M[10] M[10] ST ST 0(R3),F4 F0 F0 <val2> 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 F0 F0 LD LD F0,10(R2) Done? Y Ex Y Ex N N N N ROB7 ROB6 ROB5 ROB4 ROB3 ROB2 ROB1 Newest Oldest Registers Dest 2 ADDD ADDD R(F4),ROB1 FP FP adders adders Reservation Stations Dest 3 DIVD DIVD ROB2,R(F6) FP FP multipliers To Memory from Memory Dest 1 10+R2 10+R2

73 FP Op Queue 具有重排序缓冲器的 Tomasulo 算法 Reorder Buffer What about memory hazards??? Dest 2 ADDD ADDD R(F4),ROB1 FP FP adders adders Registers Reservation Stations M[10] M[10] ST ST 0(R3),F4 F0 F0 <val2> 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 F0 F0 LD LD F0,10(R2) Dest 3 DIVD DIVD ROB2,R(F6) FP FP multipliers Done? Y Ex Y Ex N N N N To Memory from Memory Dest 1 10+R2 10+R2 ROB7 ROB6 ROB5 ROB4 ROB3 ROB2 ROB1 Newest Oldest

74 存储器别名 : 消除关于存储器的 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. 北京大学计算机科学技术系

75 硬件对存储器歧义的支持 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.

76 存储器歧义 FP Op Queue Done? ROB7 ROB6 Newest ROB5 Reorder Buffer F4 F F0 F <val <val 1> 1> LD LD F4, F4, 10(R3) ST ST 10(R3), F5 F5 LD LD F0,32(R2) ST ST 0(R3), F4 F4 N N N Y ROB4 ROB3 ROB2 ROB1 Oldest Dest Registers Dest To Memory from Memory FP FP adders adders Reservation Stations FP FP multipliers Dest 2 32+R2 32+R2 4 ROB3 ROB3

77 复习 : 相关和冒险 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/Speculatoin precise exceptions/speculation 北京大学计算机科学技术系

78 复习 :Tomasolu 算法的相关技术 积分板 Tomasolu Reorder 结构冒险发射, Stall 保留站 Buffer Store Queue Register Renaming RAW 冒险译码保留站 WAR 冒险 WB, Stall 保留站 / 换名 WAW 冒险发射, Stall 保留站 / 换名?? Memory 冒险? Store Buffer 精确例外 / 推测执行 非精确?

79 显式寄存器换名 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

80 显式寄存器换名的优点 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)

81 能够在记分板中使用显式寄存器换名策略 Registers FP FP Mult Mult FP FP Mult Mult FP FP Divide Divide FP FP Add Add Integer Functional Units Rename Table SCOREBOARD Memory

82 采用显式寄存器换名策略的记分板控制 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!

83 Scoreboard With Explicit Renaming Instruction status: Read Exec Write Instruction j k Issue Oper Comp Result LD F6 34+ R2 LD F2 45+ R3 MULTD F0 F2 F4 SUBD F8 F6 F2 DIVD F10 F0 F6 ADDD F6 F8 F2 Functional unit status: dest S1 S2 FU FU Fj? Fk? Time Name Busy Op Fi Fj Fk Qj Qk Rj Rk Int1 Int2 Mult1 Add Divide No No No No No Register Rename and Result Clock F0 F2 F4 F6 F8 F10 F12... F30 FU P0 P2 P4 P6 P8 P10 P12 P30 Initialized Rename Table

84 Instruction status: 北京大学计算机科学技术系 Renamed Scoreboard 1 Read Exec Write Instruction j k Issue Oper Comp Result 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 Functional unit status: dest S1 S2 FU FU Fj? Fk? Time Name Busy Op Fi Fj Fk Qj Qk Rj Rk Int1 Yes Load P32 R2 Yes Int2 No Mult1 No Add No Divide No Register Rename and Result Clock F0 F2 F4 F6 F8 F10 F12... F30 1 FU P0 P2 P4 P32 P8 P10 P12 P30 Each instruction allocates free register Similar to single-assignment compiler transformation

85 Renamed Scoreboard 2 Instruction status: Read Exec Write Instruction j k Issue Oper Comp Result 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 Functional unit status: dest S1 S2 FU FU Fj? Fk? Time Name Busy Op Fi Fj Fk Qj Qk Rj Rk Int1 Yes Load P32 R2 Yes Int2 Yes Load P34 R3 Yes Mult1 No Add No Divide No Register Rename and Result Clock F0 F2 F4 F6 F8 F10 F12... F30 2 FU P0 P34 P4 P32 P8 P10 P12 P30

86 Renamed Scoreboard 3 Instruction status: Read Exec Write Instruction j k Issue Oper Comp Result 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 Functional unit status: dest S1 S2 FU FU Fj? Fk? Time Name Busy Op Fi Fj Fk Qj Qk Rj Rk Int1 Yes Load P32 R2 Yes Int2 Yes Load P34 R3 Yes Mult1 Yes Multd P36 P34 P4 Int2 No Yes Add No Divide No Register Rename and Result Clock F0 F2 F4 F6 F8 F10 F12... F30 3 FU P36 P34 P4 P32 P8 P10 P12 P30

87 Renamed Scoreboard 4 Instruction status: Read Exec Write Instruction j k Issue Oper Comp Result LD F6 34+ R LD F2 45+ R MULTD F0 F2 F4 3 SUBD F8 F6 F2 4 DIVD F10 F0 F6 ADDD F6 F8 F2 Functional unit status: dest S1 S2 FU FU Fj? Fk? Time Name Busy Op Fi Fj Fk Qj Qk Rj Rk Int1 No Int2 Yes Load P34 R3 Yes Mult1 Yes Multd P36 P34 P4 Int2 No Yes Add Yes Sub P38 P32 P34 Int2 Yes No Divide No Register Rename and Result Clock F0 F2 F4 F6 F8 F10 F12... F30 4 FU P36 P34 P4 P32 P38 P10 P12 P30

88 Renamed Scoreboard 5 Instruction status: Read Exec Write Instruction j k Issue Oper Comp Result LD F6 34+ R LD F2 45+ R MULTD F0 F2 F4 3 SUBD F8 F6 F2 4 DIVD F10 F0 F6 5 ADDD F6 F8 F2 Functional unit status: dest S1 S2 FU FU Fj? Fk? Time Name Busy Op Fi Fj Fk Qj Qk Rj Rk Int1 No Int2 No 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 Register Rename and Result Clock F0 F2 F4 F6 F8 F10 F12... F30 5 FU P36 P34 P4 P32 P38 P40 P12 P30

89 Renamed Scoreboard 6 Instruction status: Read Exec Write Instruction j k Issue Oper Comp Result LD F6 34+ R 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 Functional unit status: dest S1 S2 FU FU Fj? Fk? Time Name Busy Op Fi Fj Fk Qj Qk Rj Rk Int1 No Int2 No 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 Register Rename and Result Clock F0 F2 F4 F6 F8 F10 F12... F30 6 FU P36 P34 P4 P32 P38 P40 P12 P30

90 Renamed Scoreboard 7 Instruction status: Read Exec Write Instruction j k Issue Oper Comp Result LD F6 34+ R 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 Functional unit status: dest S1 S2 FU FU Fj? Fk? Time Name Busy Op Fi Fj Fk Qj Qk Rj Rk Int1 No Int2 No 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 Register Rename and Result Clock F0 F2 F4 F6 F8 F10 F12... F30 7 FU P36 P34 P4 P32 P38 P40 P12 P30

91 Renamed Scoreboard 8 Instruction status: Read Exec Write Instruction j k Issue Oper Comp Result LD F6 34+ R LD F2 45+ R MULTD F0 F2 F4 3 6 SUBD F8 F6 F DIVD F10 F0 F6 5 ADDD F6 F8 F2 Functional unit status: dest S1 S2 FU FU Fj? Fk? Time Name Busy Op Fi Fj Fk Qj Qk Rj Rk Int1 No Int2 No 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 Register Rename and Result Clock F0 F2 F4 F6 F8 F10 F12... F30 8 FU P36 P34 P4 P32 P38 P40 P12 P30

92 Renamed Scoreboard 9 Instruction status: Read Exec Write Instruction j k Issue Oper Comp Result LD F6 34+ R LD F2 45+ R MULTD F0 F2 F4 3 6 SUBD F8 F6 F DIVD F10 F0 F6 5 ADDD F6 F8 F2 Functional unit status: dest S1 S2 FU FU Fj? Fk? Time Name Busy Op Fi Fj Fk Qj Qk Rj Rk Int1 No Int2 No 7 Mult1 Yes Multd P36 P34 P4 Yes Yes Add No Divide Yes Divd P40 P36 P32 Mult1 No Yes Register Rename and Result Clock F0 F2 F4 F6 F8 F10 F12... F30 9 FU P36 P34 P4 P32 P38 P40 P12 P30

93 Instruction status: 北京大学计算机科学技术系 Renamed Scoreboard 10 Read Exec Write Instruction j k Issue Oper Comp Result LD F6 34+ R LD F2 45+ R MULTD F0 F2 F4 3 6 SUBD F8 F6 F DIVD F10 F0 F6 5 ADDD F6 F8 F2 10 Functional unit status: dest S1 S2 FU FU Fj? Fk? Time Name Busy Op Fi Fj Fk Qj Qk Rj Rk Int1 No Int2 No 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 Register Rename and Result Clock F0 F2 F4 F6 F8 F10 F12... F30 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

94 Renamed Scoreboard 11 Instruction status: Read Exec Write Instruction j k Issue Oper Comp Result LD F6 34+ R LD F2 45+ R MULTD F0 F2 F4 3 6 SUBD F8 F6 F DIVD F10 F0 F6 5 ADDD F6 F8 F Functional unit status: dest S1 S2 FU FU Fj? Fk? Time Name Busy Op Fi Fj Fk Qj Qk Rj Rk Int1 No Int2 No 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 Register Rename and Result Clock F0 F2 F4 F6 F8 F10 F12... F30 11 FU P36 P34 P4 P42 P38 P40 P12 P30

95 Renamed Scoreboard 12 Instruction status: Read Exec Write Instruction j k Issue Oper Comp Result LD F6 34+ R LD F2 45+ R MULTD F0 F2 F4 3 6 SUBD F8 F6 F DIVD F10 F0 F6 5 ADDD F6 F8 F Functional unit status: dest S1 S2 FU FU Fj? Fk? Time Name Busy Op Fi Fj Fk Qj Qk Rj Rk Int1 No Int2 No 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 Register Rename and Result Clock F0 F2 F4 F6 F8 F10 F12... F30 12 FU P36 P34 P4 P42 P38 P40 P12 P30

96 Renamed Scoreboard 13 Instruction status: Read Exec Write Instruction j k Issue Oper Comp Result LD F6 34+ R LD F2 45+ R MULTD F0 F2 F4 3 6 SUBD F8 F6 F DIVD F10 F0 F6 5 ADDD F6 F8 F Functional unit status: dest S1 S2 FU FU Fj? Fk? Time Name Busy Op Fi Fj Fk Qj Qk Rj Rk Int1 No Int2 No 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 Register Rename and Result Clock F0 F2 F4 F6 F8 F10 F12... F30 13 FU P36 P34 P4 P42 P38 P40 P12 P30

97 Renamed Scoreboard 14 Instruction status: Read Exec Write Instruction j k Issue Oper Comp Result LD F6 34+ R LD F2 45+ R MULTD F0 F2 F4 3 6 SUBD F8 F6 F DIVD F10 F0 F6 5 ADDD F6 F8 F Functional unit status: dest S1 S2 FU FU Fj? Fk? Time Name Busy Op Fi Fj Fk Qj Qk Rj Rk Int1 No Int2 No 2 Mult1 Yes Multd P36 P34 P4 Yes Yes Add No Divide Yes Divd P40 P36 P32 Mult1 No Yes Register Rename and Result Clock F0 F2 F4 F6 F8 F10 F12... F30 14 FU P36 P34 P4 P42 P38 P40 P12 P30

98 Renamed Scoreboard 15 Instruction status: Read Exec Write Instruction j k Issue Oper Comp Result LD F6 34+ R LD F2 45+ R MULTD F0 F2 F4 3 6 SUBD F8 F6 F DIVD F10 F0 F6 5 ADDD F6 F8 F Functional unit status: dest S1 S2 FU FU Fj? Fk? Time Name Busy Op Fi Fj Fk Qj Qk Rj Rk Int1 No Int2 No 1 Mult1 Yes Multd P36 P34 P4 Yes Yes Add No Divide Yes Divd P40 P36 P32 Mult1 No Yes Register Rename and Result Clock F0 F2 F4 F6 F8 F10 F12... F30 15 FU P36 P34 P4 P42 P38 P40 P12 P30

99 Renamed Scoreboard 16 Instruction status: Read Exec Write Instruction j k Issue Oper Comp Result LD F6 34+ R LD F2 45+ R MULTD F0 F2 F SUBD F8 F6 F DIVD F10 F0 F6 5 ADDD F6 F8 F Functional unit status: dest S1 S2 FU FU Fj? Fk? Time Name Busy Op Fi Fj Fk Qj Qk Rj Rk Int1 No Int2 No 0 Mult1 Yes Multd P36 P34 P4 Yes Yes Add No Divide Yes Divd P40 P36 P32 Mult1 No Yes Register Rename and Result Clock F0 F2 F4 F6 F8 F10 F12... F30 16 FU P36 P34 P4 P42 P38 P40 P12 P30

100 Renamed Scoreboard 17 Instruction status: Read Exec Write Instruction j k Issue Oper Comp Result LD F6 34+ R LD F2 45+ R MULTD F0 F2 F SUBD F8 F6 F DIVD F10 F0 F6 5 ADDD F6 F8 F Functional unit status: dest S1 S2 FU FU Fj? Fk? Time Name Busy Op Fi Fj Fk Qj Qk Rj Rk Int1 No Int2 No Mult1 No Add No Divide Yes Divd P40 P36 P32 Mult1 Yes Yes Register Rename and Result Clock F0 F2 F4 F6 F8 F10 F12... F30 17 FU P36 P34 P4 P42 P38 P40 P12 P30

101 Renamed Scoreboard 18 Instruction status: Read Exec Write Instruction j k Issue Oper Comp Result LD F6 34+ R LD F2 45+ R MULTD F0 F2 F SUBD F8 F6 F DIVD F10 F0 F ADDD F6 F8 F Functional unit status: dest S1 S2 FU FU Fj? Fk? Time Name Busy Op Fi Fj Fk Qj Qk Rj Rk Int1 No Int2 No Mult1 No Add No 40 Divide Yes Divd P40 P36 P32 Mult1 Yes Yes Register Rename and Result Clock F0 F2 F4 F6 F8 F10 F12... F30 18 FU P36 P34 P4 P42 P38 P40 P12 P30

102 显式寄存器换名 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? 北京大学计算机科学技术系

103 显式寄存器换名 (R10000 Style) P0 P0 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 Current Map Table Done? Newest P32 P32P34 P34 P36 P36 P38 P38 P60 P60 P62 P62 Freelist Oldest Physical register file larger than ISA register file On issue, each instruction that modifies a register is allocated new physical register from freelist 北京大学计算机科学技术系

104 显式寄存器换名 (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 Current Map Table Done? Newest P34 P34P36 P36 P38 P38 P40 P40 P60 P60 P62 P62 Freelist F0 F0 P0 P0 LD LD P32,10(R2) N Oldest 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

105 显式寄存器换名 (R10000 Style) 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 Done? Newest P36 P36P38 P38 P40 P40 P42 P42 P60 P60 P62 P62 Freelist F10 F10P10 F0 F0 P0 P0 ADDD ADDD P34,P4,P32 LD LD P32,10(R2) N N N N Oldest

106 显式寄存器换名 (R10000 Style) 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 Current Map Table Done? Newest P38 P38P40 P40 P44 P44 P48 P48 P60 P60 P62 P62 Freelist F2 F2 P2 P2 F10 F10P10 F0 F0 P0 P0 BNE BNE P36,< > DIVD DIVD P36,P34,P6 ADDD ADDD P34,P4,P32 LD LD P32,10(R2) N N N N Oldest 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

107 显式寄存器换名 (R10000Style) 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 P42 P42P44 P44 P48 P48 P50 P50 P0 P0 Freelist P10 P F0 F0 P32 P32 F4 F4 P4 P F2 F2 P2 P2 F10 F10P10 F0 F0 P0 P0 ST ST 0(R3),P40 ADDD ADDD P40,P38,P6 LD LD P38,0(R3) BNE BNE P36,< > DIVD DIVD P36,P34,P6 ADDD ADDD P34,P4,P32 LD LD P32,10(R2) Done? Y Y Y N N y y Newest Oldest 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