没有幻灯片标题

高等计算机系统结构 Tomasulo 算法 ( 第三讲 ) 程旭 2013 年 3 月 25 日

上一讲小结 软件或硬件的指令级并行 (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 Functional Units 记分板体系结构 FP Mult FP Mult FP Divide FP Add Integer SCOREBOARD Memory

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

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

记分板的三个主要组成部分 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

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

思考 如何使处理器更快 更有效?

从算法到程序 算法 C 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 '?'; } }

C 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 '?'; } } 处理器 控制 数据通路 存储器 输入 输出

静态程序流图到动态处理流图

计算机系统中的七种序列 提交序列 : 指令退离处理器 完成序列 : 指令操作完成 执行序列 : 指令开始执行 发送序列 : 指令发送到执行部件 译码序列 : 指令开始译码 取指序列 : 处理器访问存储器中的指令 存储序列 : 程序在存储器中的存放地址

按序发射的局限性 : 示例 latency 1 LD F2, 34(R2) 1 1 2 2 LD F4, 45(R3) long 3 MULTD F6, F4, F2 3 4 SUBD F8, F2, F2 1 5 DIVD F4, F2, F8 4 4 5 3 6 ADDD F10, F6, F4 1 6 按序 (In-order): 1 (2,1)...... 2 3 4 4 3 5... 5 6 6 按序发射阻止了指令 4 的分发 (dispatched) ( 下划线表明指令回写结果的周期 )

乱序发射 (Out-of-Order Issue) ALU Mem IF ID Issue WB Fadd Fmul 发射级的缓冲器中具有多个等待发射的指令 当上述缓冲器中有空位且该指令不会导致 WAR 和 WAW 冒险, 译码后就可将该指令加入到缓冲器中 缓冲器中任何满足 RAW 冒险要求的指令就可以被发射 ( 目前, 还是要求每个周期最多只能分发一条指令 ) 在 WB 级, 可能会多条指令同时抵达

按序发射的局限性 : 示例 latency 1 LD F2, 34(R2) 1 1 2 2 LD F4, 45(R3) long 3 MULTD F6, F4, F2 3 4 3 4 SUBD F8, F2, F2 1 5 DIVD F4, F2, F8 4 5 6 ADDD F10, F6, F4 1 6 In-order: 1 (2,1)...... 2 3 4 4 3 5... 5 6 6 Out-of-order: 1 (2,1) 4 4.... 2 3.. 3 5... 5 6 6 乱序执行并没有任何显著改进!

在流水线能够有多少指令? 一种指令系统体系结构中的哪些特征限制了流水线中的指令数? 寄存器数量 程序的哪些特征限制了流水线中的指令数? Control transfers 简单地单一应用乱序分发技术并不能为性能的改进提供显著支撑!

突破 ISA 中程序可用寄存器数目限制 浮点流水线通常由于寄存器数目少的原因不能满负荷运行 IBM 360 机器只有 4 个浮点寄存器 在保持 ISA 兼容的前提下, 能否通过微体系结构使用比 ISA 中指定寄存器更多的寄存器, 来突破上述限制? 1967 年,IBM 的 Robert Tomasulo 提出了一种通过程序执行时动态寄存器换名 (register renaming) 的独创解决方案

Little s Law Throughput (T) = Number in Flight (N) / Latency (L) Issue Execution WB 示例 : 4 floating point registers 8 cycles per floating point operation maximum of ½ issue per cycle!

指令级并行与换名技术 latency 1 LD F2, 34(R2) 1 1 2 2 LD F4, 45(R3) long 3 MULTD F6, F4, F2 3 4 SUBD F8, F2, F2 1 4 X 3 5 DIVD F4, F2, F8 4 5 6 ADDD F10, F6, F4 1 6 In-order: 1 (2,1)...... 2 3 4 4 3 5... 5 6 6 Out-of-order: 1 (2,1) 4 4 5... 2 (3,5) 3 6 6 任何反相关都可以通过换名来消除 ( 换名技术 额外的存储 ) 硬件能实现吗? 如何用硬件实现?

寄存器换名技术 ALU Mem 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

另一个动态算法 : 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 Memory FP Add Res. Station Tomasulo 的结构图 Operation Bus 3 2 1 Adders FP Op Queue From Instruction Unit 1 2 1 Reservation Station Multers FP Registers 3 2 1 To Memory FP Mul Res. Station Store Buffer Common Data Bus(CDB)

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 处于忙状态 Register result status 指明哪个功能部件将写到哪个寄存器 (Qi); 如果没有将写入寄存器的未决指令, 该域为空

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 SUBDF8 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: 0 Add1 No 0 Add2 No ADD: 0 Add3 No Mult: 0 Mult1 No 0 Mult2 No Divd: Register result status 2 cycles 2 cycles 10 cycles 40 cycles Clock F0 F2 F4 F6 F8 F10 F12... F30 0 FU

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 0 Add1 No 0 Add2 No Add3 No 0 Mult1 No 0 Mult2 No Register result status Clock F0 F2 F4 F6 F8 F10 F12... F30 1 FU Load1

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 0 Load3 No SUBDF8 F6 F2 DIVDF10 F0 F6 ADD F6 F8 F2 Reservation Stations S1 S2 RS for j RS for k TimeNameBusyOp Vj Vk Qj Qk 0 Add1 No 0 Add2 No Add3 No 0 Mult1 No 0 Mult2 No Register result status Clock F0 F2 F4 F6 F8 F10 F12... F30 2 FU Load2 Load1 注意 : 与 CDC6600 不同, 可以有多个 loads 被发射 ; 记分板能否改进?

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

Tomasulo 示例第 4 周期 Instruction status Execution Write Instruction j k Issue complete Result Busy Address LD F6 34+ R2 1 3 4 0 Load1 No LD F2 45+ R3 2 4 0 Load2 Yes 45+R3 MUL F0 F2 F4 3 0 Load3 No SUBDF8 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 0 Mult1 Yes MULTD R(F4) Load2 0 Mult2 No Register result status Clock F0 F2 F4 F6 F8 F10 F12... F30 4 FU Mult1 Load2 M(34+R2) Add1 Load2 将完成 ; 哪些指令在等待 Load2?

Instruction status Tomasulo 示例第 5 周期 Execution Write Instruction j k Issue complete Result Busy Address LD F6 34+ R2 1 3 4 Load1 No LD F2 45+ R3 2 4 5 Load2 No MUL F0 F2 F4 3 Load3 No SUBDF8 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) 0 Mult2 Yes 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

Instruction status Tomasulo 示例第 6 周期 Execution Write Instruction j k Issue complete Result Busy Address LD F6 34+ R2 1 3 4 Load1 No LD F2 45+ R3 2 4 5 Load2 No MUL F0 F2 F4 3 Load3 No SUBDF8 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 1 Add1 Yes SUBDM(34+R2) M(45+R3) 0 Add2 Yes ADDD M(45+R3) Add1 Add3 No 9 Mult1 Yes MULT M(45+R3) R(F4) 0 Mult2 Yes 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

Instruction status Tomasulo 示例第 7 周期 Execution Write Instruction j k Issue complete Result Busy Address LD F6 34+ R2 1 3 4 Load1 No LD F2 45+ R3 2 4 5 Load2 No MUL F0 F2 F4 3 Load3 No SUBDF8 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 0 Add1 Yes SUBDM(34+R2) M(45+R3) 0 Add2 Yes ADDD M(45+R3) Add1 Add3 No 8 Mult1 Yes MULT M(45+R3) R(F4) 0 Mult2 Yes 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?

Instruction status Tomasulo 示例第 8 周期 Execution Write Instruction j k Issue complete Result Busy Address LD F6 34+ R2 1 3 4 Load1 No LD F2 45+ R3 2 4 5 Load2 No MUL F0 F2 F4 3 Load3 No SUBDF8 F6 F2 4 7 8 DIVDF10 F0 F6 5 ADD F6 F8 F2 6 Reservation Stations S1 S2 RS for j RS for k TimeNameBusyOp Vj Vk Qj Qk 0 Add1 No 2 Add2 Yes ADDDM()-M() M(45+R3) Add3 No 7 Mult1 Yes MULTM(45+R3) R(F4) 0 Mult2 Yes 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

Tomasulo 示例第 9 周期 Instruction j k Issue complete Result Busy Address LD F6 34+ R2 1 3 4 Load1 No LD F2 45+ R3 2 4 5 Load2 No MUL F0 F2 F4 3 Load3 No SUBDF8 F6 F2 4 7 8 DIVDF10 F0 F6 5 ADD F6 F8 F2 6 Reservation Stations S1 S2 RS for j RS for k TimeNameBusyOp Vj Vk Qj Qk 0 Add1 No 1 Add2 Yes ADDDM()-M() M(45+R3) Add3 No 6 Mult1 Yes MULTM(45+R3) R(F4) 0 Mult2 Yes 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 Button 6

Instruction status Tomasulo 示例第 10 周期 Execution Write Instruction j k Issue complete Result Busy Address LD F6 34+ R2 1 3 4 Load1 No LD F2 45+ R3 2 4 5 Load2 No MUL F0 F2 F4 3 Load3 No SUBDF8 F6 F2 4 7 8 DIVDF10 F0 F6 5 ADD F6 F8 F2 6 10 Reservation Stations S1 S2 RS for j RS for k TimeNameBusyOp Vj Vk Qj Qk 0 Add1 No 0 Add2 Yes ADDDM()-M() M(45+R3) Add3 No 5 Mult1 Yes MULTM(45+R3) R(F4) 0 Mult2 Yes 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?

Instruction status Tomasulo 示例第 11 周期 Execution Write Instruction j k Issue complete Result Busy Address LD F6 34+ R2 1 3 4 Load1 No LD F2 45+ R3 2 4 5 Load2 No MUL F0 F2 F4 3 Load3 No SUBDF8 F6 F2 4 7 8 DIVDF10 F0 F6 5 ADD F6 F8 F2 6 10 11 Reservation Stations S1 S2 RS for j RS for k TimeNameBusyOp Vj Vk Qj Qk 0 Add1 No 0 Add2 No Add3 No 4 Mult1 Yes MULTM(45+R3) R(F4) 0 Mult2 Yes 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 在该周期写结果

Instruction status Tomasulo 示例第 12 周期 Execution Write Instruction j k Issue complete Result Busy Address LD F6 34+ R2 1 3 4 Load1 No LD F2 45+ R3 2 4 5 Load2 No MUL F0 F2 F4 3 Load3 No SUBDF8 F6 F2 4 6 7 DIVDF10 F0 F6 5 ADD F6 F8 F2 6 10 11 Reservation Stations S1 S2 RS for j RS for k TimeNameBusyOp Vj Vk Qj Qk 0 Add1 No 0 Add2 No Add3 No 3 Mult1 Yes MULTM(45+R3) R(F4) 0 Mult2 Yes 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 注意 : 所有短周期指令都已经完成

Instruction status Tomasulo 示例第 13 周期 Execution Write Instruction j k Issue complete Result Busy Address LD F6 34+ R2 1 3 4 Load1 No LD F2 45+ R3 2 4 5 Load2 No MUL F0 F2 F4 3 Load3 No SUBDF8 F6 F2 4 7 8 DIVDF10 F0 F6 5 ADD F6 F8 F2 6 10 11 Reservation Stations S1 S2 RS for j RS for k TimeNameBusyOp Vj Vk Qj Qk 0 Add1 No 0 Add2 No Add3 No 2 Mult1 Yes MULTM(45+R3) R(F4) 0 Mult2 Yes 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

Instruction status Tomasulo 示例第 14 周期 Execution Write Instruction j k Issue complete Result Busy Address LD F6 34+ R2 1 3 4 Load1 No LD F2 45+ R3 2 4 5 Load2 No MUL F0 F2 F4 3 Load3 No SUBDF8 F6 F2 4 7 8 DIVDF10 F0 F6 5 ADD F6 F8 F2 6 10 11 Reservation Stations S1 S2 RS for j RS for k TimeNameBusyOp Vj Vk Qj Qk 0 Add1 No 0 Add2 No Add3 No 1 Mult1 Yes MULTM(45+R3) R(F4) 0 Mult2 Yes 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

Instruction status Tomasulo 示例第 15 周期 Execution Write Instruction j k Issue complete Result Busy Address LD F6 34+ R2 1 3 4 Load1 No LD F2 45+ R3 2 4 5 Load2 No MUL F0 F2 F4 3 15 Load3 No SUBDF8 F6 F2 4 7 8 DIVDF10 F0 F6 5 ADD F6 F8 F2 6 10 11 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 0 Mult1 Yes MULT M(45+R3) R(F4) 0 Mult2 Yes 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?

Instruction status Tomasulo 示例第 16 周期 Execution Write Instruction j k Issue complete Result Busy Address LD F6 34+ R2 1 3 4 Load1 No LD F2 45+ R3 2 4 5 Load2 No MUL F0 F2 F4 3 15 16 Load3 No SUBDF8 F6 F2 4 7 8 DIVDF10 F0 F6 5 ADD F6 F8 F2 6 10 11 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 0 Mult1 No 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 注意 : 只有除法指令没有完成

Instruction status Tomasulo 示例第 55 周期 Execution Write Instruction j k Issue complete Result Busy Address LD F6 34+ R2 1 3 4 Load1 No LD F2 45+ R3 2 4 5 Load2 No MUL F0 F2 F4 3 15 16 Load3 No SUBDF8 F6 F2 4 7 8 DIVDF10 F0 F6 5 ADD F6 F8 F2 6 10 11 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 0 Mult1 No 1 Mult2 Yes 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

Instruction status Tomasulo 示例第 56 周期 Execution Write Instruction j k Issue complete Result Busy Address LD F6 34+ R2 1 3 4 Load1 No LD F2 45+ R3 2 4 5 Load2 No MUL F0 F2 F4 3 15 16 Load3 No SUBDF8 F6 F2 4 7 8 DIVDF10 F0 F6 5 56 ADD F6 F8 F2 6 10 11 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 0 Mult1 No 0 Mult2 Yes 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 完成

Instruction status Tomasulo 示例第 57 周期 Execution Write Instruction j k Issue complete Result Busy Address LD F6 34+ R2 1 3 4 Load1 No LD F2 45+ R3 2 4 5 Load2 No MUL F0 F2 F4 3 15 16 Load3 No SUBDF8 F6 F2 4 7 8 DIVDF10 F0 F6 5 56 57 ADD F6 F8 F2 6 10 11 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 0 Mult1 No 0 Mult2 No 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 乱序执行 乱序完成

与记分板的第 62 周期相比 Instruction status Read Execu Write Instruction j k IssueoperancompleResult LD F6 34+ R2 1 2 3 4 LD F2 45+ R3 5 6 7 8 MUL F0 F2 F4 6 9 19 20 SUBDF8 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 Register result status Clock F0 F2 F4 F6 F8 F10 F12... F30 62 FU CDC6600 的记分板为什么需要更长的时间?

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 10000 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 的周期数 实际上, 整数指令先行

Instruction status 循环示例 第 0 周期 Executi Write Instruction j k iteration Issue completresult 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: 0 Add1 No LD F0 0 R1 0 Add2 No MUL F4 F0 F2 0 Add3 No SD F4 0 R1 0 Mult1 No SUBIR1 R1 #8 0 Mult2 No BNEZR1 Loop Register result status Clock R1 F0 F2 F4 F6 F8 F10 F12... F30 0 80 Qi

Instruction status 循环示例 第 1 周期 Executi Write Instruction j k iteration Issue completresult 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 0 Mult1 No SUBIR1 R1 #8 0 Mult2 No BNEZR1 Loop Register result status Clock R1 F0 F2 F4 F6 F8 F10 F12... F30 1 80 Qi Load1

Instruction status 循环示例 第 2 周期 Executi Write Instruction j k iteration Issue completresult BusyAddress LD F0 0 R1 1 1 Load1 Yes 80 MUL F4 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: 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 SUBIR1 R1 #8 0 Mult2 No BNEZR1 Loop Register result status Clock R1 F0 F2 F4 F6 F8 F10 F12... F30 2 80 Qi Load1 Mult1

Instruction status 循环示例 第 3 周期 Executi Write Instruction j k iteration Issue completresult BusyAddress LD F0 0 R1 1 1 Load1 Yes 80 MUL F4 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 0 Mult1 Yes MULTD R(F2) Load1 SUBIR1 R1 #8 0 Mult2 No BNEZR1 Loop Register result status Clock R1 F0 F2 F4 F6 F8 F10 F12... F30 3 80 Qi Load1 Mult1 注意 : 隐含的换名功能动态建立起 数据流 图

循环示例 第 4 周期 Instruction status Executi Write Instruction j k iteration Issue completresult BusyAddress LD F0 0 R1 1 1 Load1 Yes 80 MUL F4 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 0 Mult1 Yes MULTD R(F2) Load1 SUBIR1 R1 #8 0 Mult2 No BNEZR1 Loop Register result status Clock R1 F0 F2 F4 F6 F8 F10 F12... F30 4 72 Qi Load1 Mult1 注意 : 发送 SUB 指令

Instruction status 循环示例 第 5 周期 Executi Write Instruction j k iteration Issue completresult BusyAddress LD F0 0 R1 1 1 Load1 Yes 80 MUL F4 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 0 Mult1 Yes MULTD R(F2) Load1 SUBIR1 R1 #8 0 Mult2 No BNEZR1 Loop Register result status Clock R1 F0 F2 F4 F6 F8 F10 F12... F30 5 72 Qi Load1 Mult1 注意 : 处理 BNEZ 指令

循环示例 第 6 周期 Instruction status Executi Write Instruction j k iteration Issue completresult 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 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 0 Mult1 Yes MULTD R(F2) Load1 SUBIR1 R1 #8 0 Mult2 No BNEZR1 Loop Register result status Clock R1 F0 F2 F4 F6 F8 F10 F12... F30 6 72 Qi Load2 Mult1 注意 : F0 一直看不到 Load1 的结果

循环示例 第 7 周期 Instruction status Executi Write Instruction j k iteration Issue completresult 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 Store1 Yes 80 Mult1 MUL F4 F0 F2 2 7 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 0 Mult1 Yes MULTD R(F2) Load1 SUBIR1 R1 #8 0 Mult2 Yes MULTD R(F2) Load2 BNEZR1 Loop Register result status Clock R1 F0 F2 F4 F6 F8 F10 F12... F30 7 72 Qi Load2 Mult2 Note: MULT2 has no registers names in RS

Instruction status 循环示例 第 8 周期 Executi Write Instruction j k iteration Issue completresult 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 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: 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 SUBIR1 R1 #8 0 Mult2 Yes MULTD R(F2) Load2 BNEZR1 Loop Register result status Clock R1 F0 F2 F4 F6 F8 F10 F12... F30 8 72 Qi Load2 Mult2

Instruction status 循环示例 第 9 周期 Executi Write Instruction j k iteration Issue completresult BusyAddress 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 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: 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 SUBIR1 R1 #8 0 Mult2 Yes MULTD R(F2) Load2 BNEZR1 Loop Register result status Clock R1 F0 F2 F4 F6 F8 F10F12... F30 9 64 Qi Load2 Mult2 Load1 完成, 注意等待其结果的指令! 注意 : 发送 SUB 指令

Instruction status 循环示例 第 10 周期 Executi Write Instruction j k iteration Issue completresult BusyAddress LD F0 0 R1 1 1 9 10 Load1 No MUL F4 F0 F2 1 2 Load2 Yes 72 SD F4 0 R1 1 3 Load3 No Qi LD F0 0 R1 2 6 10 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: 0 Add1 No LD F0 0 R1 0 Add2 No MULTDF4 F0 F2 0 Add3 No SD F4 0 R1 4 Mult1 Yes MULTD M(80)R(F2) SUBI R1 R1 #8 0 Mult2 Yes MULTD R(F2) Load2 BNEZ R1 Loop Register result status Clock R1 F0 F2 F4 F6 F8 F10 F12... F30 10 64 Qi Load2 Mult2 Load2 Load1 完成, 注意等待其结果的指令

循环示例 第 11 周期 Instruction status Executi Write Instruction j k iteration Issue completresult BusyAddress 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 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: 0 Add1 No LD F0 0 R1 0 Add2 No MULTDF4 F0 F2 0 Add3 No SD F4 0 R1 3 Mult1 Yes MULTD M(80)R(F2) SUBI R1 R1 #8 4 Mult2 Yes MULTD M(72)R(F2) BNEZ R1 Loop Register result status Clock R1 F0 F2 F4 F6 F8 F10 F12... F30 11 64 Qi Load3 Mult2

循环示例 第 12 周期 Instruction status Executi Write Instruction j k iteration Issue completresult BusyAddress 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 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: 0 Add1 No LD F0 0 R1 0 Add2 No 为什么不能发送第三次迭代的乘法? MULTDF4 F0 F2 0 Add3 No SD F4 0 R1 2 Mult1 Yes MULTD M(80)R(F2) SUBI R1 R1 #8 3 Mult2 Yes MULTD M(72)R(F2) BNEZ R1 Loop Register result status Clock R1 F0 F2 F4 F6 F8 F10 F12... F30 12 64 Qi Load3 Mult2

Instruction status 循环示例 第 13 周期 Executi Write Instruction j k iteration Issue completresult BusyAddress 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 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: 0 Add1 No LD F0 0 R1 0 Add2 No MULTDF4 F0 F2 0 Add3 No SD F4 0 R1 1 Mult1 Yes MULTD M(80)R(F2) SUBI R1 R1 #8 2 Mult2 Yes MULTD M(72)R(F2) BNEZ R1 Loop Register result status Clock R1 F0 F2 F4 F6 F8 F10 F12... F30 13 64 Qi Load3 Mult2

循环示例 第 14 周期 Instruction status Executi Write Instruction j k iteration Issue completresult BusyAddress 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 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 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 MULTDF4 F0 F2 0 Add3 No SD F4 0 R1 0 Mult1 Yes MULTD M(80)R(F2) SUBI R1 R1 #8 1 Mult2 Yes MULTD M(72)R(F2) BNEZ R1 Loop Register result status Clock R1 F0 F2 F4 F6 F8 F10 F12... F30 14 64 Qi Load3 Mult2 Mult1 完成

Instruction status 循环示例 第 15 周期 Executi Write Instruction j k iteration Issue completresult BusyAddress 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 Store1 Yes 80 M(80)*R MUL F4 F0 F2 2 7 15 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: 0 Add1 No LD F0 0 R1 0 Add2 No MULTDF4 F0 F2 0 Add3 No SD F4 0 R1 0 Mult1 No SUBI R1 R1 #8 0 Mult2 Yes MULTD M(72)R(F2) BNEZ R1 Loop Register result status Clock R1 F0 F2 F4 F6 F8 F10 F12... F30 15 64 Qi Load3 Mult2 Mult2 完成

Instruction status 循环示例 第 16 周期 Executi Write Instruction j k iteration Issue completresult BusyAddress 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 Store1 Yes 80 M(80)*R MUL F4 F0 F2 2 7 15 16 Store2 Yes 72 M(72)*R SD F4 0 R1 2 8 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 MULTDF4 F0 F2 0 Add3 No SD F4 0 R1 0 Mult1 Yes MULTD R(F2) Load3 SUBI R1 R1 #8 0 Mult2 No BNEZ R1 Loop Register result status Clock R1 F0 F2 F4 F6 F8 F10 F12... F30 16 64 Qi Load3 Mult1

Instruction status 循环示例 第 17 周期 Executi Write Instruction j k iteration Issue completresult BusyAddress 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 Store1 Yes 80 M(80)*R MUL F4 F0 F2 2 7 15 16 Store2 Yes 72 M(72)*R SD F4 0 R1 2 8 Store3 Yes 64 Mult1 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 MULTDF4 F0 F2 0 Add3 No SD F4 0 R1 0 Mult1 Yes MULTD R(F2) Load3 SUBI R1 R1 #8 0 Mult2 No BNEZ R1 Loop Register result status Clock R1 F0 F2 F4 F6 F8 F10 F12... F30 17 64 Qi Load3 Mult1

Instruction status 循环示例 第 18 周期 Executi Write Instruction j k iteration Issue completresult BusyAddress 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 Store1 Yes 80 M(80)*R MUL F4 F0 F2 2 7 15 16 Store2 Yes 72 M(72)*R SD F4 0 R1 2 8 Store3 Yes 64 Mult1 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 MULTDF4 F0 F2 0 Add3 No SD F4 0 R1 0 Mult1 Yes MULTD R(F2) Load3 SUBI R1 R1 #8 0 Mult2 No BNEZ R1 Loop Register result status Clock R1 F0 F2 F4 F6 F8 F10 F12... F30 18 56 Qi Load3 Mult1

Instruction status 循环示例 第 19 周期 Executi Write Instruction j k iteration Issue completresult BusyAddress 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 Store1 No MUL F4 F0 F2 2 7 15 16 Store2 Yes 72 M(72)*R SD F4 0 R1 2 8 Store3 Yes 64 Mult1 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 MULTDF4 F0 F2 0 Add3 No SD F4 0 R1 0 Mult1 Yes MULTD R(F2) Load3 SUBI R1 R1 #8 0 Mult2 No BNEZ R1 Loop Register result status Clock R1 F0 F2 F4 F6 F8 F10 F12... F30 19 56 Qi Load3 Mult1

循环示例 第 20 周期 Instruction status Executi Write Instruction j k iteration Issue completresult BusyAddress 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 Store1 No MUL F4 F0 F2 2 7 15 16 Store2 Yes 72 M(72)*R SD F4 0 R1 2 8 20 Store3 Yes 64 Mult1 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 MULTDF4 F0 F2 0 Add3 No SD F4 0 R1 0 Mult1 Yes MULTD R(F2) Load3 SUBI R1 R1 #8 0 Mult2 No BNEZ R1 Loop Register result status Clock R1 F0 F2 F4 F6 F8 F10 F12... F30 20 56 Qi Load3 Mult1

循环示例 第 21 周期 Instruction status Executi Write Instruction j k iteration Issue completresult BusyAddress 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 Store1 No MUL F4 F0 F2 2 7 15 16 Store2 No SD F4 0 R1 2 8 20 21 Store3 Yes 64 Mult1 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 MULTDF4 F0 F2 0 Add3 No SD F4 0 R1 0 Mult1 Yes MULTD R(F2) Load3 SUBI R1 R1 #8 0 Mult2 No BNEZ R1 Loop Register result status Clock R1 F0 F2 F4 F6 F8 F10 F12... F30 21 56 Qi Load3 Mult1

寄存器换名技术 ALU Mem 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

数据流 (Dataflow) 执行 Ins# use exec op p1 src1 p2 src2 ptr 2 next to deallocate t 1 t 2... prt 1 next available Reorder buffer 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) t n

换名 & 乱序发射 : 示例 v1 Renaming table F1 F2 F3 F4 F5 F6 F7 F8 p data v1 t1 t2 t5 t3 v4 t4 Reorder buffer Ins# use exec op p1 src1 p2 src2 1 1 0 10 LD 2 10 01 LD 3 1 0 MUL 10 v2 t2 1 v1 4 1 0 10 SUB 1 v1 1 v1 5 1 0 DIV 1 v1 01 t4 v4 t 1 t 2 t 3 t 4 t 5.. 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 When are names in sources replaced by data? Whenever an FU produces data When can a name be reused? Whenever an instruction completes

数据驱动 (Data-Driven) 执行 Renaming table & reg file Reorder buffer Ins# use exec op p1 src1 p2 src2 t 1 t2.. t n Replacing the tag by its value is an expensive operation 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 Ins# use exec op p1 src1 p2 src2 ptr 2 next to deallocate t 1 t 2... prt 1 next available 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 n

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

有效性 (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

精确中断 (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 1 2 2 3 1 4 3 5 5 4 6 6 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

支持精确中断的 ROB 扩展 Inst# use exec op p1 src1 p2 src2 pd dest data cause ptr 2 next to commit ptr 1 next available 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) 回卷和换名 Rollback and Renaming Reorder buffer Ins# use exec op p1 src1 p2 src2 pd dest data t 1 t 2.. t n Load Unit 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 FU FU FU Store Unit Commit < t, result >

换名表 (Renaming Table) Rename Table r 1 t v r 2 tag valid bit Register File Reorder buffer Ins# use exec op p1 src1 p2 src2 pd dest data t 1 t 2.. t n Load Unit FU FU FU 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

转移开销 (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

转移之间的平均指令运行长度 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 Functional Units 能够在记分板中使用显式寄存器换名策略 FP Mult FP Mult FP Divide FP Add Integer Rename Table SCOREBOARD Memory

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

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

Instruction status: Renamed Scoreboard 2 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

Instruction status: Renamed Scoreboard 3 Read Exec Write Instruction j k Issue Oper Comp Result 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 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

Instruction status: Renamed Scoreboard 4 Read Exec Write Instruction j k Issue Oper Comp Result LD F6 34+ R2 1 2 3 4 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 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

Instruction status: Renamed Scoreboard 5 Read Exec Write Instruction j k Issue Oper Comp Result LD F6 34+ R2 1 2 3 4 LD F2 45+ R3 2 3 4 5 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

Instruction status: Renamed Scoreboard 6 Read Exec Write Instruction j k Issue Oper Comp Result LD F6 34+ R2 1 2 3 4 LD F2 45+ R3 2 3 4 5 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 2 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 6 FU P36 P34 P4 P32 P38 P40 P12 P30

Instruction status: Renamed Scoreboard 7 Read Exec Write Instruction j k Issue Oper Comp Result LD F6 34+ R2 1 2 3 4 LD F2 45+ R3 2 3 4 5 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 1 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 7 FU P36 P34 P4 P32 P38 P40 P12 P30

Instruction status: Renamed Scoreboard 8 Read Exec Write Instruction j k Issue Oper Comp Result LD F6 34+ R2 1 2 3 4 LD F2 45+ R3 2 3 4 5 MULTD F0 F2 F4 3 6 SUBD F8 F6 F2 4 6 8 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 0 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 8 FU P36 P34 P4 P32 P38 P40 P12 P30

Instruction status: Renamed Scoreboard 9 Read Exec Write Instruction j k Issue Oper Comp Result LD F6 34+ R2 1 2 3 4 LD F2 45+ R3 2 3 4 5 MULTD F0 F2 F4 3 6 SUBD F8 F6 F2 4 6 8 9 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

Instruction status: Renamed Scoreboard 10 Read Exec Write Instruction j k Issue Oper Comp Result LD F6 34+ R2 1 2 3 4 LD F2 45+ R3 2 3 4 5 MULTD F0 F2 F4 3 6 SUBD F8 F6 F2 4 6 8 9 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

Instruction status: Renamed Scoreboard 11 Read Exec Write Instruction j k Issue Oper Comp Result LD F6 34+ R2 1 2 3 4 LD F2 45+ R3 2 3 4 5 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 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

Instruction status: Renamed Scoreboard 12 Read Exec Write Instruction j k Issue Oper Comp Result LD F6 34+ R2 1 2 3 4 LD F2 45+ R3 2 3 4 5 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 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

Instruction status: Renamed Scoreboard 13 Read Exec Write Instruction j k Issue Oper Comp Result LD F6 34+ R2 1 2 3 4 LD F2 45+ R3 2 3 4 5 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 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

Instruction status: Renamed Scoreboard 14 Read Exec Write Instruction j k Issue Oper Comp Result LD F6 34+ R2 1 2 3 4 LD F2 45+ R3 2 3 4 5 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 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

Instruction status: Renamed Scoreboard 15 Read Exec Write Instruction j k Issue Oper Comp Result LD F6 34+ R2 1 2 3 4 LD F2 45+ R3 2 3 4 5 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 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

Instruction status: Renamed Scoreboard 16 Read Exec Write Instruction j k Issue Oper Comp Result LD F6 34+ R2 1 2 3 4 LD F2 45+ R3 2 3 4 5 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 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

Instruction status: Renamed Scoreboard 17 Read Exec Write Instruction j k Issue Oper Comp Result LD F6 34+ R2 1 2 3 4 LD F2 45+ R3 2 3 4 5 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 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

Instruction status: Renamed Scoreboard 18 Read Exec Write Instruction j k Issue Oper Comp Result LD F6 34+ R2 1 2 3 4 LD F2 45+ R3 2 3 4 5 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 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

小结 动态硬件策略能够在硬件层面动态展开循环 (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? 精确例外 / 推测执行 非精确?