周学海 xhzhou@ustc.edu.cn 0551-63601556, 63492149 中国科学技术大学 2018/9/21 计算机体系结构 周学海 xhzhou@ustc.edu.cn 0551-63601556, 63492149 中国科学技术大学

第5章 指令级并行 指令集并行的基本概念及挑战 软件方法挖掘指令集并行 硬件方法挖掘指令集并行 跨越基本块的指令集并行 基于硬件的推测执行 基本块内的指令集并行 硬件方法挖掘指令集并行 Scoreboard Tomasulo 跨越基本块的指令集并行 基于硬件的推测执行 以多发射和静态调度来挖掘指令集并行 以动态调度、多发射和推测执行来挖掘指令集并行 2018/9/21 计算机体系结构 2

并行及并行体系结构 应用程序中的并行: Data-Level Parallelism (DLP) 2018/9/21 并行及并行体系结构 应用程序中的并行: Data-Level Parallelism (DLP) Task-Level Parallelism (TLP) 软硬件挖掘应用程序的DLP或TLP的方式 Instruction-Level Parallelism (ILP) Vector architectures/Graphic Processor Units (GPUs) Thread-Level Parallelism Request-Level Parallelism 2018/9/21 计算机体系结构 3 Chapter 2 — Instructions: Language of the Computer 3

Review: 基本流水线 流水线提高的是指令带宽（吞吐率），而不是单 条指令的执行速度 相关限制了流水线性能的发挥 结构相关：需要更多的硬件资源 数据相关：需要定向，编译器调度 控制相关：尽早检测条件，计算目标地址，延迟转移， 预测 增加流水线的级数会增加相关产生的可能性 异常，浮点运算使得流水线控制更加复杂 编译器可降低数据相关和控制相关的开销 Load 延迟槽 Branch 延迟槽 Branch预测 2018/9/21 计算机体系结构 4

5.1 指令级并行的基本概念及挑战 ILP: 无关的指令重叠执行 流水线的平均CPI Pipeline CPI = Ideal Pipeline CPI + Struct Stalls + RAW Stalls + WAR Stalls + WAW Stalls + Control Stalls 本章研究：减少停顿（stalls)数的方法和技术 基本途径 软件方法： Gcc: 17%控制类指令，5 instructions + 1 branch； 在基本块上，得到更多的并行性 挖掘循环级并行 硬件方法 动态调度方法 以DLX（MIPS）的浮点数操作为例 2018/9/21 计算机体系结构 5

采用的基本技术 2018/9/21 计算机体系结构 6

本章遵循的指令延时 产生结果的指令 使用结果的指令 所需延时 FP ALU op Another FP ALU op 3 产生结果的指令 使用结果的指令 所需延时 FP ALU op Another FP ALU op 3 FP ALU op Store double 2 Load double FP ALU op 1 Load double Store double 0 Integer op Integer op 0 (当使用结果的指令为BRANCH指令时除外) 2018/9/21 计算机体系结构 7

5.2 基本块内的指令级并行 基本块的定义： 循环级并行 直线型代码，无分支；单入口；程序由分支语句连接 基本块构成 for (i = 1; i <= 1000; i++) x(i) = x(i) + s; • 计算x(i)时没有数据相关；可以并行产生1000个数据； •问题：在生成代码时会有Branch指令－控制相关 •预测比较容易，但我们必须有预测方案 向量处理机模型 load vectors x and y (up to some machine dependent max) then do result-vec = xvec + yvec in a single instruction 2018/9/21 计算机体系结构 8

简单循环及其对应的汇编程序 x(i) = x(i) + s; for (i=1; i<=1000; i++) Loop： LD F0,0(R1) ;F0=vector element ADDD F4,F0,F2 ;add scalar from F2 SD 0(R1),F4 ;store result SUBI R1,R1,8 ;decrement pointer 8B (DW) BNEZ R1,Loop ;branch R1!=zero NOP ;delayed branch slot 2018/9/21 计算机体系结构 9

FP 循环中的Stalls 2 stall 3 ADDD F4,F0,F2 ;add scalar in F2 4 stall 1 Loop: LD F0,0(R1) ;F0=vector element 2 stall 3 ADDD F4,F0,F2 ;add scalar in F2 4 stall 5 stall 6 SD 0(R1),F4 ;store result 7 SUBI R1,R1,8 ;decrement pointer 8B (DW) 8 stall ； 9 BNEZ R1,Loop ;branch R1!=zero 10 stall ;delayed branch slot 产生结果的指令 使用结果的指令 所需的延时 FP ALU op Another FP ALU op 3 FP ALU op Store double 2 Load double FP ALU op 1 Load double Store double 0 Integer op Integer op 0 10 clocks: 是否可以通过调整代码顺序使stalls减到最小 2018/9/21 计算机体系结构 11

FP 循环中的最少Stalls数 1 Loop: LD F0,0(R1) 2 SUBI R1,R1,8 3 ADDD F4,F0,F2 5 BNEZ R1,Loop ;delayed branch 6 SD 8(R1),F4 ;altered when move past SUBI 3 clocks doing work, 3 overhead (stall, branch, sub) Swap BNEZ and SD by changing address of SD 6 clocks: 通过循环展开4次是否可以提高性能? 2018/9/21 计算机体系结构 12

循环展开4次(straightforward way) 1 Loop: LD F0,0(R1) stall 2 ADDD F4,F0,F2 stall stall 3 SD 0(R1),F4 ;drop SUBI & BNEZ 4 LD F6,-8(R1) stall 5 ADDD F8,F6,F2 stall stall 6 SD -8(R1),F8 ;drop SUBI & BNEZ 7 LD F10,-16(R1) stall 8 ADDD F12,F10,F2 stall stall 9 SD -16(R1),F12 ;drop SUBI & BNEZ 10 LD F14,-24(R1) stall 11 ADDD F16,F14,F2 stall stall 12 SD -24(R1),F16 13 SUBI R1,R1,#32 stall ;alter to 4*8 14 BNEZ R1,LOOP 15 NOP 15 + 4 x (1+2) + 1 = 28 cycles, or 7 per iteration Assumes R1 is multiple of 4 Rewrite loop to minimize stalls? 2018/9/21 计算机体系结构 13

Stalls数最小的循环展开 代码移动后 SD移动到SUBI后，注意偏移量 的修改 Loads移动到SD前，注意偏移量 的修改 1 Loop: LD F0,0(R1) 2 LD F6,-8(R1) 3 LD F10,-16(R1) 4 LD F14,-24(R1) 5 ADDD F4,F0,F2 6 ADDD F8,F6,F2 7 ADDD F12,F10,F2 8 ADDD F16,F14,F2 9 SD 0(R1),F4 10 SD -8(R1),F8 11 SUBI R1,R1,#32 12 SD 16(R1),F12 13 BNEZ R1,LOOP 14 SD 8(R1),F16 ; 8-32 = -24 14 clock cycles, or 3.5 per iteration 代码移动后 SD移动到SUBI后，注意偏移量 的修改 Loads移动到SD前，注意偏移量 的修改 2018/9/21 计算机体系结构 14

循环展开示例小结 循环展开对循环间无关的程序是有效降低stalls的 手段(对循环级并行）. 指令调度，必须保证程序运行的结果不变 注意循环展开中的Load和Store,不同次循环的Load 和Store 是相互独立的。需要分析对存储器的引用， 保证他们没有引用同一地址. 不同次的循环，使用不同的寄存器 删除不必要的测试和分支后，需调整循环步长等控 制循环的代码. 移动SD到SUBI和BNEZ后，需要调整SD中的偏移 2009-11-16 2018/9/21 计算机体系结构 15

从编译器角度看代码移动（1/4) 编译器分析程序的相关性依赖于给定的流水线 编译器进行指令调度来消除相关 (True) 数据相关（Data dependencies） 对于指令i和j，如果Instruction j使用指令i产生的结 果 , 或Instruction j 与instruction k相关, 并且 instruction k 与instruction i有数据相关. 如果相关, 不能并行执行 对于寄存器比较容易确定(fixed names) 但对memory的引用，比较难确定: 100(R4) = 20(R6)? 在不同次的循环中，20(R6) = 20(R6)? 2018/9/21 计算机体系结构 16

下列程序哪里有数据相关? 1 Loop: LD F0,0(R1) 2 ADDD F4,F0,F2 3 SUBI R1,R1,8 4 BNEZ R1,Loop ;delayed branch 5 SD 8(R1),F4 ;altered when move past SUBI 3 clocks doing work, 3 overhead (stall, branch, sub) 2018/9/21 计算机体系结构 17

从编译器角度看代码移动(2/4) 另一种相关称为名相关（ name dependence）: 两条指令使用同名参数(register or memory location) 但不交 换数据 反相关（Antidependence） (WAR if a hazard for HW) Instruction j 所写的寄存器或存储单元，与 instruction i 所读的寄存 器或存储单元相同，注instruction i 是先执行 输出相关(Output dependence) (WAW if a hazard for HW) Instruction i 和instruction j 对同一寄存器或存储单元进行写操作， 必须保证两条指令的写顺序 2018/9/21 计算机体系结构 18

下列是否有名相关? 如何消除名相关? 1 Loop: LD F0,0(R1) 2 ADDD F4,F0,F2 3 SD 0(R1),F4 ;drop SUBI & BNEZ 4 LD F0,-8(R1) 5 ADDD F4,F0,F2 6 SD -8(R1),F4 ;drop SUBI & BNEZ 7 LD F0,-16(R1) 8 ADDD F4,F0,F2 9 SD -16(R1),F4 ;drop SUBI & BNEZ 10 LD F0,-24(R1) 11 ADDD F4,F0,F2 12 SD -24(R1),F4 13 SUBI R1,R1,#32 ;alter to 4*8 14 BNEZ R1,LOOP 15 NOP 如何消除名相关? LD F0 to output to next LD F0 ADD F0 input to LD F0 2018/9/21 计算机体系结构 19

从编译器角度看代码移动（3/4) 访问存储单元时，很难判断名相关 100(R4) = 20(R6)? 不同次的循环，20(R6) = 20(R6)? 我们给出的示例要求编译器知道假设R1不变， 因此: 0(R1) ≠ -8(R1) ≠ -16(R1) ≠ -24(R1) 因此loads和stores之间相互无关可以移动 2018/9/21 计算机体系结构 21

从编译器角度看代码移动（4/4) 最后一种相关称为控制相关( control dependence) Example 处理控制相关的原则： if p1 {S1;}; if p2 {S2;}; S1 依赖于P1的测试结果，S2依赖于P2的测试。 处理控制相关的原则： 受分支指令控制的指令，不能移到控制指令之前，以免该指令的执行不在分支指令的控制范围. 不受分支指令控制的指令，不能移到控制指令之后，以免该指令的执行受分支指令的控制. 减少控制相关可以提高指令的并行性 2018/9/21 计算机体系结构 22

下列程序段的控制相关 11 LD F0,0(R1) 1 Loop: LD F0,0(R1) 12 ADDD F4,F0,F2 13 SD 0(R1),F4 14 SUBI R1,R1,8 15 BEQZ R1,exit .... 1 Loop: LD F0,0(R1) 2 ADDD F4,F0,F2 3 SD 0(R1),F4 4 SUBI R1,R1,8 5 BEQZ R1,exit 6 LD F0,0(R1) 7 ADDD F4,F0,F2 8 SD 0(R1),F4 9 SUBI R1,R1,8 10 BEQZ R1,exit Everything after branch to next branch 2018/9/21 计算机体系结构 23

循环间相关（1/4） Example: 下列程序段存在哪些数据相关? (A,B,C 指向不同的存储区且不存在覆盖区) for (i=1; i<=100; i=i+1) { A[i+1] = A[i] + C[i]; /* S1 */ B[i+1] = B[i] + A[i+1]; /* S2 */ } 1. S2使用由S1在同一循环计算出的 A[i+1]. 2. S1 使用由S1在前一次循环中计算的值；S2也使用由S2在前 一次循环中计算的值. 这种存在于循环间的相关，我们称为 “loop-carried dependence”这表示循环间存在相关，不能并行 执行，它与我们前面的例子中循环间无关是有区别的 2018/9/21 计算机体系结构 24

无回路的循环间相关（2/4)- Example:A,B,C,D distinct & nonoverlapping for (i=1; i<=100; i=i+1) { A[i] = A[i] + B[i]; /* S1 */ B[i+1] = C[i] + D[i];} /* S2 */ Non-Circular Loop-Carried Dependence 1. S1和S2没有相关，S1和S2互换不会影响程序的正 确性 2. 在第一次循环中，S1依赖于前一次循环的B[1]. 3. S1依赖上一次循环的S2，但S2不依赖S1 2018/9/21 计算机体系结构 25

循环间相关（3/4）-循环变换 A[1] = A[1] + B[1]; OLD: for (i=1; i<=100; i=i+1) { A[i] = A[i] + B[i]; /* S1 */ B[i+1] = C[i] + D[i];} /* S2 */ A[1] = A[1] + B[1]; for (i=1; i<=99; i=i+1) { B[i+1] = C[i] + D[i]; A[i+1] = A[i+1] + B[i+1]; } B[101] = C[100] + D[100]; NEW: 2013-03-27 2018/9/21 计算机体系结构 26

循环间相关（4/4）-Dependence Distance 通常循环间相关呈现为递推关系 for (i=1; i<N; i++) A[i] = A[i-1] + B[i]; 相关的距离可能大于1 for (i=4; i<N; i++) A[i] = A[i-4] + B[i]; 可以通过循环展开增加循环内的并行性 for (i=4; i<N; i=i+4) { A[i] = A[i-4] + B[i]; A[i+1] = A[i-3] + B[i+1]; A[i+2] = A[i-2] + B[i+2]; A[i+3] = A[i-1] + B[i+3]; } 2018/9/21 计算机体系结构 27

04/17-Review 虚拟存储器 指令级并行(ILP) 4Q TLB 流水线的平均CPI 提高指令级并行的方法 Pipeline CPI = Ideal Pipeline CPI + Struct Stalls + RAW Stalls + WAR Stalls + WAW Stalls + Control Stalls +…… 提高指令级并行的方法 软件方法：指令流调度，循环展开，软件流水线，trace scheduling 硬件方法 软件方法：指令流调度-循环展开 指令调度，必须保证程序运行的结果不变 偏移量的修改 寄存器的重命名 循环步长的调整 2013-04-02 2018/9/21 计算机体系结构 28

5.3 硬件方案: 指令级并行 为什么要使用硬件调度方案? 基本思想: 允许 stall后的指令继续向前流动 在编译时无法确定的相关，可以通过硬件调度来优化 编译器简单 代码在不同组织结构的机器上，同样可以有效的运行 基本思想: 允许 stall后的指令继续向前流动 DIVD F0,F2,F4 ADDD F10,F0,F8 SUBD F12,F8,F14 允许乱序执行（out-of-order execution） => out-of-order completion 2018/9/21 计算机体系结构 29

硬件方案之一: 记分牌 记分牌的基本概念示意图 2018/9/21 计算机体系结构 30

记分牌技术要点（1/2) Out-of-order execution 将ID 段分为: 起源于1963年推出的CDC6600 Issue—译码，检测结构相关 Read operands—等待到无数据相关时，读操作数 起源于1963年推出的CDC6600 4 FPU 5 Memory Reference 7 IU 集中相关检查，互锁机制解决相关 CDC 6600: 顺序发射，乱序执行，乱序完成，CDC6600流水 线没有采用定向技术，只实现非精确中断 Load /store结构 采用这种技术的微处理器企业 MIPS，HP， IBM Sun 公司的UltraSparc DEC Alpha 2018/9/21 计算机体系结构 31

记分牌技术要点(2/2) Out-of-order completion => WAR, WAW hazards? 对操作排队 仅在读操作数阶段读寄存器 对WAW而言, 检测到相关后，停止发射前一条指令， 直到前一条指令完成 要提高效率，需要有多条指令进入执行阶段=>必须 有多个执行部件或执行部件是流水化的 记分牌保存相关操作和状态 记分牌用四段代替ID, EX, WB 三段 2018/9/21 计算机体系结构 32

带有记分牌控制的DLX 2018/9/21 计算机体系结构 33

记分牌控制的四阶段（1/2) 1.Issue—指令译码，检测结构相关 Read operands—没有数据相关时，读操作数 如果当前指令所使用的功能部件空闲，并且没有其他活 动的指令使用相同的目的寄存器（WAW), 记分牌发射该 指令到功能部件，并更新记分牌内部数据，如果有结构 相关或WAW相关，则该指令的发射暂停，并且也不发射 后继指令，直到相关解除. Read operands—没有数据相关时，读操作数 如果先前已发射的正在运行的指令不对当前指令的源操作 数寄存器进行写操作，或者一个正在工作的功能部件已 经完成了对该寄存器的写操作，则该操作数有效。操作 数有效时，记分牌控制功能部件读操作数，准备执行。 记分牌在这一步动态地解决了RAW相关，指令可能会乱 序执行。 2018/9/21 计算机体系结构 34

记分牌控制的四阶段（2/2） 3.Execution—取到操作数后执行 (EX) 接收到操作数后，功能部件开始执行. 当计算出结果后， 它通知记分牌，可以结束该条指令的执行. 4.Write result—finish execution (WB) 一旦记分牌得到功能部件执行完毕的信息后，记分牌检测 WAR相关，如果没有WAR相关，就写结果，如果有WAR 相关，则暂停该条指令。 Example: DIVD F0,F2,F4 ADDD F10,F0,F8 SUBD F8,F8,F14 CDC 6600 scoreboard 将暂停 SUBD 直到ADDD 读取操作数 后，才进入WR段处理。 2018/9/21 计算机体系结构 35

记分牌的结构 2.Functional unit status—记录功能部件(FU)的状态。用9个域记 录每个功能部件的9个参量： 1. Instruction status—记录正在执行的各条指令处于四步中的哪一步 2.Functional unit status—记录功能部件(FU)的状态。用9个域记 录每个功能部件的9个参量： Busy—指示该部件是否空闲 Op—该部件所完成的操作 Fi—其目的寄存器编号 Fj, Fk—源寄存器编号 Qj, Qk—产生源操作数Fj, Fk的功能部件 Rj, Rk—标识源操作数Fj, Fk是否就绪的标志 3.Register result status—如果存在功能部件对某一寄存器进行 写操作，指示具体是哪个功能部件对该寄存器进行写操作。 如果没有指令对该寄存器进行写操作，则该域 为Blank What you might have thought 1. 4 stages of instruction executino 2.Status of FU: Normal things to keep track of (RAW & structura for busyl): Fi from instruction format of the mahine (Fi is dest) Add unit can Add or Sub Rj, Rk - status of registers (Yes means ready) Qj,Qk - If a no in Rj, Rk, means waiting for a FU to write result; Qj, Qk means wihch FU waiting for it 3.Status of register result (WAW &WAR)s: which FU is going to write into registers Scoreboard on 6600 = size of FU 6.7, 6.8, 6.9, 6.12, 6.13, 6.16, 6.17 FU latencies: Add 2, Mult 10, Div 40 clocks 2018/9/21 计算机体系结构 36

记分牌流水线控制 Read operands Execution complete Instruction status Write result Issue Bookkeeping Rj No; Rk No f(if Qj(f)=FU then Rj(f) Yes); f(if Qk(f)=FU then Rk(f) Yes); Result(Fi(FU)) 0; Busy(FU) No 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 and Rk Functional unit done Wait until f((Fj( f )≠Fi(FU) or Rj( f )=No) & (Fk( f ) ≠Fi(FU) or Rk( f )=No)) Not busy (FU) and not result(D) 1.Issue - if no structural haards AND non wAW (no Funtional Unit is going to write this destination register; 1 per clock cycle 2. Read -(RAW) if no instructions is going to write a source register of this instruction (alternatively, no write signal this clock cycle) +> gein exection of the instruction; many read ports, so can read many times 3. Execution Complete; multiple during clock cyle 4. Write result - (WAR) If no instructiion is watiing to read the destination register; assume multiple wriite ports; wait for clock cycle to write and tehn read the results; assume can oerlap issue & write show clock cyclesneed 20 or so Latency: minimum is 4 through 4 stages * 2018/9/21 计算机体系结构 37

Scoreboard Example 2018/9/21 计算机体系结构 38

Scoreboard Example: Cycle 1 2018/9/21 计算机体系结构 39

Scoreboard Example: Cycle 2 Issue 2nd LD? 2018/9/21 计算机体系结构 40

Scoreboard Example: Cycle 3 Issue MULT? 2018/9/21 计算机体系结构 41

Scoreboard Example: Cycle 4 2018/9/21 计算机体系结构 42

Scoreboard Example: Cycle 5 2018/9/21 计算机体系结构 43

Scoreboard Example: Cycle 6 2018/9/21 计算机体系结构 44

Scoreboard Example: Cycle 7 Read multiply operands? 2018/9/21 计算机体系结构 45

Scoreboard Example: Cycle 8a (First half of clock cycle) 2018/9/21 计算机体系结构 46

Scoreboard Example: Cycle 8b (Second half of clock cycle) 2018/9/21 计算机体系结构 47

Scoreboard Example: Cycle 9 Note Remaining Read operands for MULT & SUB? Issue ADDD? 2018/9/21 计算机体系结构 48

Scoreboard Example: Cycle 10 2018/9/21 计算机体系结构 49

Scoreboard Example: Cycle 11 2018/9/21 计算机体系结构 50

Scoreboard Example: Cycle 12 Read operands for DIVD? 2018/9/21 计算机体系结构 51

Scoreboard Example: Cycle 13 2018/9/21 计算机体系结构 52

Scoreboard Example: Cycle 14 2018/9/21 计算机体系结构 53

Scoreboard Example: Cycle 15 2018/9/21 计算机体系结构 54

Scoreboard Example: Cycle 16 2018/9/21 计算机体系结构 55

Scoreboard Example: Cycle 17 WAR Hazard! Why not write result of ADD??? 2018/9/21 计算机体系结构 56

Scoreboard Example: Cycle 18 2018/9/21 计算机体系结构 57

Scoreboard Example: Cycle 19 2018/9/21 计算机体系结构 58

Scoreboard Example: Cycle 20 2018/9/21 计算机体系结构 59

Scoreboard Example: Cycle 21 WAR Hazard is now gone... 2018/9/21 计算机体系结构 60

Scoreboard Example: Cycle 22 2018/9/21 计算机体系结构 61

Continue……. 2018/9/21 计算机体系结构 62

Scoreboard Example: Cycle 61 2018/9/21 计算机体系结构 63

Scoreboard Example: Cycle 62 2018/9/21 计算机体系结构 64

Review: Scoreboard Example: Cycle 62 In-order issue; out-of-order execute & commit 2018/9/21 计算机体系结构 65

04/22-Review 硬件方法挖掘ILP 记分牌的主要思想是：允许stall后的指令继续进行处理 编译阶段无法确定的相关性，可以在程序执行时，用硬件方法判定 这种方法还可以使得程序代码在其他机器上有效地执行 记分牌的主要思想是：允许stall后的指令继续进行处理 可以out-of-order execution => out-of-order completion 发射前检测结构相关和WAW相关 读操作数前检测RAW相关 写结果前处理WAR相关 上一讲 1节课 上课，1节课 习题课 2018/9/21 计算机体系结构 66

CDC 6600 Scoreboard 编译器优化，加速比可达到1.7，手工优化加 速比可达到 2.5 ，其存储系统较慢 (no cache) 限制了性能的发挥 6600 scoreboard的缺陷: 没有定向数据通路 指令窗口较小，仅局限于基本块内的调度 功能部件数较少，容易产生结构相关，特别是其 Load store操作也是用IU部件完成的 结构冲突时不能发射 WAR相关是通过等待解决的 WAW相关时，不会进入IS阶段 2018/9/21 计算机体系结构 67

ILP小结 Tomasulo Algorithm：….. 可通过软件或硬件来挖掘指令级并行潜力 循环级并行是最容易判断的 程序内在的相关性限制了用软件方法挖掘程序的并行性 编译器数据相关性分析结果，确定了是否可以循环展开 当对存储器单元引用时，数据相关分析很困难 硬件方法挖掘ILP 编译阶段无法确定的相关性，可以在程序执行时，用硬件方法判定 这种方法还可以使得程序代码在其他机器上有效地执行 记分牌的主要思想是：允许stall后的指令继续进行处理 可以out-of-order execution => out-of-order completion 发射前检测结构相关和WAW相关 写结果前处理WAR相关 Tomasulo Algorithm：….. 2018/9/21 计算机体系结构 68

动态调度方案之二：Tomasulo Algorithm 该算法首次在 IBM 360/91上使用（ CDC6600推出三 年后） 目标: 在没有专用编译器的情况下，提高系统性能 IBM 360 & CDC 6600 ISA的差别 IBM360只有 2位寄存器描述符 vs. CDC 6600寄存器描述符 3位 IBM360 4个FP 寄存器 vs. CDC 6600 8个 IBM 360 有memory-register 操作 为什么研究? Alpha 21264, HP 8000, MIPS 10000, Pentium II, PowerPC 604，… 2018/9/21 计算机体系结构 69

Tomasulo Algorithm vs. Scoreboard FU 缓存称为 “reservation stations”; 保存待用操作数 指令中的寄存器在RS中用寄存器值或指向RS的指针代替。称 为 register renaming ; 避免 WAR, WAW hazards RS多于寄存器，因此可以做更多编译器无法做的优化 传给FU的结果，从RS来而不是从寄存器来，FU的计算结果通 过Common Data Bus 以广播方式发向所有的功能部件。 Load和Store部件也看作带有RS的功能部件 可以跨越分支，允许FP操作队列中FP操作不仅仅局限于基本块 2018/9/21 计算机体系结构 70

Tomasulo Organization FP Registers From Mem FP Op Queue Load Buffers Load1 Load2 Load3 Load4 Load5 Load6 Store Buffers Resolve RAW memory conflict? (address in memory buffers) Integer unit executes in parallel Add1 Add2 Add3 Mult1 Mult2 Reservation Stations To Mem FP adders FP multipliers Common Data Bus (CDB) 2018/9/21 计算机体系结构 71

Tomasulo Organization (cont.) 2018/9/21 计算机体系结构 72

Reservation Station 结构 Op: 部件所进行的操作 Vj, Vk: 源操作数的值。Store 缓冲区有Vk域，用于存放要写入存储器的值 A： 存放存储器地址。开始存立即数，计算出有效地址后，存放有效 地址 Qj, Qk: 产生源操作数的RS 注：没有记分牌中的准备就绪标志， Qj, Qk=0 => ready Store 缓存区只有Qk表示产生结果的RS Busy: 标识RS或FU是否空闲 Register result status—如果存在对寄存器的写操作，指示对该寄存 器进行写操作的部件. Qi: 保留站的编号 What you might have thought 1. 4 stages of instruction execution 2. Status of FU: Normal things to keep track of (RAW & structura for busyl): Fi from instruction format of the mahine (Fi is dest) Add unit can Add or Sub Rj, Rk - status of registers (Yes means ready) Qj,Qk - If a no in Rj, Rk, means waiting for a FU to write result; Qj, Qk means wihch FU waiting for it 3.Status of register result (WAW &WAR)s: which FU is going to write into registers Scoreboard on 6600 = size of FU 6.7, 6.8, 6.9, 6.12, 6.13, 6.16, 6.17 FU latencies: Add 2, Mult 10, Div 40 clocks 2018/9/21 计算机体系结构 73

Tomasulo 算法的三阶段 通常的数据总线: data + destination (“go to” bus) 1. Issue—从FP操作队列中取指令 如果RS空闲(no structural hazard), 则控制发射指令和操作数 (renames registers). 消除WAR，WAW相关 2. Execution—operate on operands (EX) 当两操作数就绪后，就可以执行 如果没有准备好，则监测Common Data Bus 以获取结果。通 过推迟指令执行避免RAW相关 3. Write result—finish execution (WB) 将结果通过Common Data Bus传给所有等待该结果的部件; 表示RS可用 通常的数据总线: data + destination (“go to” bus) Common data bus: data + source (“come from” bus) 64 bits 数据线 + 4位功能部件源地址（ FU source address） 产生结果的部件如果与RS中等待的部件匹配，就进行写操作 广播方式传送 2018/9/21 计算机体系结构 74

Tomasulo 算法流水线控制 rs, rt : 源寄存器名；rd:目的寄存器名 RS: 保留站数据结构；r:保留站编号 RegisterStat：寄存器状态表 Reg： 寄存器堆 Issue FP Operation: Wait until : Station r empty Action or bookkeeping: if(RegisterStat[rs].Qi0) {RS[r].Qj  RegisterStat[rs].Qi} else {RS[r].Vj Reg[rs]; RS[r].Qj 0 } if(RegisterStat[rt].Qi0) {RS[r].Qk  RegisterStat[rt].Qi} else {RS[r].Vk Reg[rt]; RS[r].Qk0 } RS[r].Busy  yes; RegisterStat[rd].Qi = r; Load or Store: Wait until: Buffer r empty RS[r].A imm; RS[r].Busy  yes; Load only: RegisterStat[rt].Qi = r; Store only: 2018/9/21 计算机体系结构 75 75

wait until: (RS[r].Qj=0) and (RS[r].Qk=0) Action or bookkeeping: 注意：Load操作在EXE阶段分两步 2、Execute FP Operation wait until: (RS[r].Qj=0) and (RS[r].Qk=0) Action or bookkeeping: computer result: Operands are in Vj and Vk Load-store step1 wait until: RS[r].Qj =0 & r is head of load-store queue RS[r].A  RS[r].Vj + RS[r].A; Load step2 wait until: Load Step1 complete Action or bookkeeping: Read from Mem[RS[r].A] 2018/9/21 计算机体系结构 76

Wait until: Execution complete at r & CDB available 3、Write result FP Operation or Load Wait until: Execution complete at r & CDB available Action or bookkeeping x (if (RegisterStat[x].Qi=r) {Regs[x]  result; RegisterStat[x].Qi  0})  x (if(RS[x].Qj =r) {RS[x].Vj result; RS[x].Qj 0});  x (if(RS[x].Qk =r) {RS[x].Vk result; RS[x].Qk 0}); RS[r].Busy  no; Store wait until: Execution complete at r & RS[r].Qk = 0 Mem[RS[r].A]  RS[r].Vk; 2018/9/21 计算机体系结构 77

Tomasulo Example 2018/9/21 计算机体系结构 78

Tomasulo Example Cycle 1 2018/9/21 计算机体系结构 79

Tomasulo Example Cycle 2 Note: Unlike 6600, can have multiple loads outstanding 2018/9/21 计算机体系结构 80

Tomasulo Example Cycle 3 Note: registers names are removed (“renamed”) in Reservation Stations; MULT issued vs. scoreboard Load1 completing; what is waiting for Load1? 2018/9/21 计算机体系结构 81

Tomasulo Example Cycle 4 Load2 completing; what is waiting for Load1? 2018/9/21 计算机体系结构 82

Tomasulo Example Cycle 5 2018/9/21 计算机体系结构 83

Tomasulo Example Cycle 6 Issue ADDD here vs. scoreboard? 2018/9/21 计算机体系结构 84

Tomasulo Example Cycle 7 Add1 completing; what is waiting for it? 2018/9/21 计算机体系结构 85

Tomasulo Example Cycle 8 2018/9/21 计算机体系结构 86

Tomasulo Example Cycle 9 2018/9/21 计算机体系结构 87

Tomasulo Example Cycle 10 Add2 completing; what is waiting for it? 2018/9/21 计算机体系结构 88

Tomasulo Example Cycle 11 Write result of ADDD here vs. scoreboard? All quick instructions complete in this cycle! 2018/9/21 计算机体系结构 89

Tomasulo Example Cycle 12 2018/9/21 计算机体系结构 90

Tomasulo Example Cycle 13 2018/9/21 计算机体系结构 91

Tomasulo Example Cycle 14 2018/9/21 计算机体系结构 92

Tomasulo Example Cycle 15 2018/9/21 计算机体系结构 93

Tomasulo Example Cycle 16 2018/9/21 计算机体系结构 94

Faster than light computation (skip a couple of cycles) 2018/9/21 计算机体系结构 95

Tomasulo Example Cycle 55 2018/9/21 计算机体系结构 96

Tomasulo Example Cycle 56 Mult2 is completing; what is waiting for it? 2018/9/21 计算机体系结构 97

Tomasulo Example Cycle 57 Once again: In-order issue, out-of-order execution and completion. 2018/9/21 计算机体系结构 98

Compare to Scoreboard Cycle 62 结构冲突 没有定向技术 2018/9/21 计算机体系结构 99

Tomasulo v. Scoreboard (IBM 360/91 v. CDC 6600) 流水化的功能部件 多个功能部件 流水化的功能部件 多个功能部件 (6 load, 3 store, 3 +, 2 x/÷) (1 load/store, 1 + , 2 x, 1 ÷) 指令窗口大小: ~ 14 instructions ~ 5 instructions 有结构冲突时不发射 相同 WAR: 用寄存器重命名避免 stall 来避免 WAW:用寄存器重命名避免 停止发射 从FU广播结果 写寄存器方式 Control: RS 集中式scoreboard 2018/9/21 计算机体系结构 100

review Tomasulo Algorithm 三阶段 1. Issue—从FP操作队列中取指令 如果RS空闲(no structural hazard), 则控制发射指令和操作数 (renames registers). 2. Execution—operate on operands (EX) 当两操作数就绪后，就可以执行 如果没有准备好，则监测Common Data Bus 以获取结果 3. Write result—finish execution (WB) 将结果通过Common Data Bus传给所有等待该结果的部件; 表示RS可用 通常的数据总线: data + destination (“go to” bus) Common data bus: data + source (“come from” bus) 64 bits 数据线 + 4位功能部件源地址（ FU source address） 产生结果的部件如果与RS中等待的部件匹配，就进行写操作 广播方式传送 2018/9/21 计算机体系结构 101

Tomasulo 缺陷 复杂 delays of 360/91, MIPS 10000, IBM 620? 要求高速CDB 性能受限于Common Data Bus 2018/9/21 计算机体系结构 102

Tomasulo Loop Example Loop: LD F0 0(R1) MULTD F4 F0 F2 SD F4 0(R1) SUBI R1 R1 #8 BNEZ R1 Loop 设Multiply执行阶段4 clocks 第一次load 需8 clocks (cache miss), 第2次以后假 设命中(hit) 为清楚起见，下面我们也列出SUBI, BNEZ的时钟 周期 2018/9/21 计算机体系结构 103

Loop Example 2018/9/21 计算机体系结构 104

Loop Example Cycle 1 2018/9/21 计算机体系结构 105

Loop Example Cycle 2 2018/9/21 计算机体系结构 106

Loop Example Cycle 3 Implicit renaming sets up “DataFlow” graph 2018/9/21 计算机体系结构 107

What does this mean physically? FP Registers From Mem FP Op Queue F0: Load 1 Load Buffers F4: Mult1 Load1 Load2 Load3 Load4 Load5 Load6 addr: 80 Store Buffers Addr: 80 Mult1 Resolve RAW memory conflict? (address in memory buffers) Integer unit executes in parallel Add1 Add2 Add3 Mult1 Mult2 mul R(F2) Load1 Reservation Stations To Mem FP adders FP multipliers Common Data Bus (CDB) 2018/9/21 计算机体系结构 108

Loop Example Cycle 4 Dispatching SUBI Instruction 2018/9/21 计算机体系结构 109

Loop Example Cycle 5 And, BNEZ instruction 2018/9/21 计算机体系结构 110

Loop Example Cycle 6 Notice that F0 never sees Load from location 80 2018/9/21 计算机体系结构 111

Loop Example Cycle 7 Register file completely detached from iteration 1 2018/9/21 计算机体系结构 112

Loop Example Cycle 8 First and Second iteration completely overlapped 2018/9/21 计算机体系结构 113

What does this mean physically? FP Registers From Mem FP Op Queue F0: Load2 Load Buffers F4: Mult2 Load1 Load2 Load3 Load4 Load5 Load6 addr: 80 addr: 72 Store Buffers Addr: 80 Mult1 Resolve RAW memory conflict? (address in memory buffers) Integer unit executes in parallel Addr: 72 Mult2 Add1 Add2 Add3 Mult1 Mult2 R(F2) Load1 mul R(F2) Load2 mul Reservation Stations To Mem FP adders FP multipliers Common Data Bus (CDB) 2018/9/21 计算机体系结构 114

Loop Example Cycle 9 Load1 completing: who is waiting? Note: Dispatching SUBI 2018/9/21 计算机体系结构 115

Loop Example Cycle 10 Load2 completing: who is waiting? Note: Dispatching BNEZ 2018/9/21 计算机体系结构 116

Loop Example Cycle 11 Next load in sequence 2018/9/21 计算机体系结构 117

Loop Example Cycle 12 Why not issue third multiply? 结构冲突，Mult只有两个保留站 2018/9/21 计算机体系结构 118

Loop Example Cycle 13 2018/9/21 计算机体系结构 119

Loop Example Cycle 14 Mult1 completing. Who is waiting? 2018/9/21 计算机体系结构 120

Loop Example Cycle 15 Mult2 completing. Who is waiting? 2018/9/21 计算机体系结构 121

Loop Example Cycle 16 2018/9/21 计算机体系结构 122

Loop Example Cycle 17 2018/9/21 计算机体系结构 123

Loop Example Cycle 18 2018/9/21 计算机体系结构 124

Loop Example Cycle 19 2018/9/21 计算机体系结构 125

Loop Example Cycle 20 2018/9/21 计算机体系结构 126

04/29-Review-基本Tomasulo Tomasulo三阶段 Issue - Execution – WriteResult 基本数据结构 Instruction Status Reservation Station Register Result Status 2018/9/21 计算机体系结构

为何Tomasulo可以循环覆盖执行？ 寄存器重命名技术 关键: 整数部件必须先行，以便能发射多个循 环中的操作 不同的循环使用不同的物理寄存器 (dynamic loop unrolling). 将代码中的静态寄存器名修改为动态寄存器指针 “pointers” 有效地增加了寄存器文件的大小 关键: 整数部件必须先行，以便能发射多个循 环中的操作 2018/9/21 计算机体系结构 128

Summary#1/2 Reservations stations: 寄存器重命名，缓冲源操作数 不限于基本块(IU先行，解决控制相关) 避免寄存器成为瓶颈 避免了Scoreboard中无法解决的 WAR, WAW hazards 允许硬件做循环展开 不限于基本块(IU先行，解决控制相关) 贡献 Dynamic scheduling Register renaming Load/store disambiguation 360/91 后 Pentium II; PowerPC 604; MIPS R10000; HP- PA 8000; Alpha 21264使用这种技术 2018/9/21 计算机体系结构 129

Summary #2/2 动态硬件方案可以用硬件进行循环展开 但如何处理精确中断? 如何处理分支? Out-of-order execution  out-of-order completion! 如何处理分支? 我们可以用硬件做循环展开必须可以解决分支指令问题 2018/9/21 计算机体系结构 130

为什么顺序发射? 顺序发射使我们可以进行程序的数据流分析 每一周期发射多条指令也使用该原则将会正确地工作: 我们可以知道某条指令的结果会流向哪些指令 如果我们乱序发射，可能会混淆RAW和WAR相关 每一周期发射多条指令也使用该原则将会正确地工作: 需要多端口的 “rename table” ,以同时对一组指令所用的寄存器重命名 需要在单周期内发射到多个RS中. 寄存器文件需要有2x 个读端口和x个写端口. 2018/9/21 计算机体系结构 131

关于异常处理??? 乱序完成加大了实现精确中断的难度 需要“rollback” 寄存器文件到原来的状态: 在前面指令还没有完成时，寄存器文件中可能会有后面指令的运行 结果. 如果这些前面的指令执行时有中断产生，怎么办？ 例如：DIVD F10, F0, F2 SUBD F4, F6, F8 ADDD F12, F14, F16 需要“rollback” 寄存器文件到原来的状态: 精确中断的含义是其返回地址为： 该地址之前的所有指令都已完成 其后的指令还都没有完成 实现精确中断的技术：顺序完成（或提交） 即提交指令完成的顺序必须与指令发射的顺序相同 2018/9/21 计算机体系结构 132

进行循环重叠执行需要尽快解决分支问题! 在循环展开的例子中，我们假设整数部件可以快速 解决分支问题，以便进行循环重叠执行! Loop: LD F0 0 R1 MULTD F4 F0 F2 SD F4 0 R1 SUBI R1 R1 #8 BNEZ R1 Loop 如果分支依赖于multd,怎么办?? 需要能预测分支方向 如果分支成功，我们就可以重叠执行循环 对于superscalar机器这一问题更加突出 2018/9/21 计算机体系结构 133

控制相关的动态解决技术 控制相关：由条件转移或程序中断引起的相关，也 称全局相关。控制相关对流水线的吞吐率和效率影 响相对于数据相关要大得多 条件指令在一般程序中所占的比例相当大 中断虽然在程序中所占的比例不大，但中断发生在程序 中的哪一条指令，发生在一条指令执行过程中的哪一个 功能段都是不确定的 处理好条件转移和中断引起的控制相关是很重要的。 关键问题： 要确保流水线能够正常工作 减少因断流引起的吞吐率和效率的下降 2018/9/21 计算机体系结构 134

分支对性能的影响 假设在一条有K段的流水线中，在最后一段才能确 定目标地址 当分支方向预测错误时，不仅流水线中有多个功能 段要浪费，更严重的是可能造成程序执行结果发生 错误，因此当程序沿着错误方向运行后，作废这些 程序时，一定不能破坏通用寄存器和主存储器的内 容。 i-1 i i+1 i+2 i+k-3 p+1 p+2 p+k-3 i+k-2 p+k-2 Output 2018/9/21 计算机体系结构 135

条件转移指令对流水线性能的影响 假设对于一条有K段的流水线，由于条件分支的影 响，在最坏情况下，每次条件转移将造成k-1个时钟 周期的断流。假设条件分支在一般程序中所占的比 例为p, 条件成功的概率为q。试分析分支对流水线 的影响。 结论：条件转移指令对流水线的影响很大，必须采 取相关措施来减少这种影响。 预测可以是静态预测“Static” (at compile time) 或动 态预测 “Dynamic” (at runtime) 例：一个循环供循环10次，它将分支成功9次，1次不成功。 动态分支预测 vs. 静态分支预测，哪个好？ 2018/9/21 计算机体系结构 136

Dynamic Branch Prediction 动态分支预测：预测分支的方向在程序运行时刻动态确定 需解决的关键问题是： 如何记录转移历史信息 如何根据所记录的转移历史信息，预测转移的方向 主要方法 基于BPB(Branch Prediction Buffer)或BHT(Branch History Table)的方法 1-bit BHT和2-bit BHT Correlating Branch Predictors Tournament Predictors: Adaptively Combining Local and Global Predictors High Performance Instruction Delivery BTB Integrated Instruction Fetch Units Return Address Predictors Performance = ƒ(accuracy, cost of misprediction) Misprediction  Flush Reorder Buffer 2018/9/21 计算机体系结构 137

1-bit BHT Branch History Table: 分支指令的PC的低位索引 1-bit BHT 该表记录上一次转移是否成功 不做地址检查 问题: 在一个循环中, 1-bit BHT 将导致2次分支 预测错误(avg is 9 iteratios before exit): 最后一次循环, 前面都是预测成功，而这次需要退 出循环 首次循环，由于前面预测为失败，而这次实际上 为成功 2018/9/21 计算机体系结构 138

2-bit BHT 解决办法: 2位记录分支历史 Blue: stop, not taken Green: go, taken T Predict Taken Predict Not Taken NT 2018/9/21 计算机体系结构 139

2018/9/21 计算机体系结构 140

2018/9/21 计算机体系结构 141

BHT Accuracy 分支预测错误的原因: BHT表的大小问题 预测错误 由于使用PC的低位查找BHT表，可能得到错误的分 支历史记录 4096 项的表分支预测错误的比例为1% (nasa7, tomcatv) to 18% (eqntott), spice at 9% and gcc at 12% 再增加项数，对提高预测准确率几乎没有效果 (in Alpha 21164) 2018/9/21 计算机体系结构 142

Correlating Branch Predicator 翻译为DLX SUBI R3,R1,#2 BNEZ R3,L1 ; branch b1 (aa!=2) ADDI R1,R0,R0 ;aa=0 L1: SUBI R3,R2,#2 BNEZ R3,L2 ;branch b2(bb!=2) ADDI R2,R0,R0 ; bb=0 L2: SUBI R3,R1,R2 ;R3=aa-bb BEQZ R3,L3 ;branch b3 (aa==bb) 例如： if (aa==2) aa=0; if (bb==2) bb=0; if (aa!=bb) { Branch Predictors that use the behavior of other branches to make a prediction are called correlating predictors or two-level predictors. 2018/9/21 计算机体系结构 143

Correlating Branches 观察结果：b3 与分支b2 和b1相关。如果b1和b2都分支失败， 则b3一定成功。 Correlating predictors 或 两级预测器：分支预测器根据其他 分支的行为来进行预测。 工作原理：根据一个简单的例子我们来看其基本原理 if (d==0)d=1; if (d==1) d=0; 翻译为DLX BNEZ R1,L1 ;branch b1(d!=0) ADDI R1,R0,#1 ;d==0, so d=1 L1: ADDI R3,R1,#-1 BNEZ R3,L2 ;branch b2(d!=1) ... L2: 2018/9/21 计算机体系结构 144

两级预测器基本工作原理 假设d的初始值序列为0，1，2 b1 如果分支失败，b2一定也 分支失败。 前面的两位标准的预测方案就 没法利用这一点，而两级预测 方案就可以。 翻译为DLX BNEZ R1,L1 ;branch b1(d!=0) ADDI R1,R0,#1 ;d==0, so d=1 L1: ADDI R3,R1,#-1 BNEZ R3,L2 ;branch b2(d!=1) 2018/9/21 计算机体系结构 145

用1-bit预测器，初始设置为预测失败，T表示预测成功， NT表示预测失败。 结论：这样的序列每次预测都错，预测错误率100％ 假设d的初始值在2和0之间切换。 用1-bit预测器，初始设置为预测失败，T表示预测成功， NT表示预测失败。 结论：这样的序列每次预测都错，预测错误率100％ BNEZ R1,L1 ;branch b1(d!=0) ADDI R1,R0,#1 ;d==0, so d=1 L1: ADDI R3,R1,#-1 BNEZ R3,L2 ;branch b2(d!=1) 2018/9/21 计算机体系结构 146

Correlating Branches 基本思想：用1位作为correlation位。即每个分支都有两个相互独立 的预测位：一个预测位假设最近一次执行的分支失败时的预测位， 另一个预测位是假设最近一次执行的分支成功时的预测位。 最近一次执行的分支与要预测的分支可能不是同一条指令 记为 （1，1）前一位表示最近一次分支失败时的预测位，后一位表 示最近一次分支成功时的预测位 2018/9/21 计算机体系结构 147

Correlating 预测器的预测和执行情况 显然只有在第一次d=2时，预测错误，其他都预测正确 记为（1，1）预测器，即根据最近一次分支的行为来选 择一对1-bit预测器中的一个。 更一般的表示为（m, n)，即根据最近的m个分支，从2m 个分支预测器中选择预测器，每个预测器的位数为n BNEZ R1,L1 ;branch b1(d!=0) ADDI R1,R0,#1 ;d==0, so d=1 L1: ADDI R3,R1,#-1 BNEZ R3,L2 ;branch b2(d!=1) 2018/9/21 计算机体系结构 148

2-bits per branch local predictors (01 = not taken then taken) Correlating Branches Branch address (4 bits) 2-bits per branch local predictors Prediction 2-bit recent global branch history (01 = not taken then taken) (2,2) predictor: 2-bit global, 2-bit local 2018/9/21 计算机体系结构 149

2018/9/21 计算机体系结构 150

Accuracy of Different Schemes 4096 Entries 2-bit BHT Unlimited Entries 2-bit BHT 1024 Entries (2,2) BHT 0% 18% Frequency of Mispredictions 2018/9/21 计算机体系结构 151

Branch Prediction Basic 2-bit predictor: 关联预测器(n,2): The University of Adelaide, School of Computer Science 9/21/2018 Branch Prediction Basic 2-bit predictor: 关联预测器(n,2): 每个分支有多个 2-bit 预测器 根据最近n次分支的执行情况从2n中选择预测器 两级局部预测器(Local predictor): 每个分支有多个2-bit 预测器 根据该分支的最近n次分支的执行情况从2n中选择预测器 竞赛预测器(Tournament predictor): 结合关联预测器和两级局部预测器 2018/9/21 计算机体系结构 152 Chapter 2 — Instructions: Language of the Computer 152

竞赛预测器 全局预测器：使用最后n个分支跳转情况进行索引，即全局预测器入口数 ：2n每个入口是一个标准的2位预测器 Local History Eg.（1024*10) Global Prediction Local Prediction Eg.(1024*2) Choice Prediction Global History PC 全局预测器：使用最后n个分支跳转情况进行索引，即全局预测器入口数 ：2n每个入口是一个标准的2位预测器 局部预测器：设计为两层，一个局部历史记录,使用指令地址的低m位进行 索引，每个入口k位，分别对应这个入口最近的k次分支，即最近k次分支 的 跳转情况，从局部历史记录选择出的入口对一个2K的入口表进行索引， 这些入口由2位计数器构成，以提供本地预测。 选择器：使用分支局部地址的低m位分支局部地址索引，每个索引得到一 个两位计数器，用来选择使用局部预测器还是使用全局预测器的预测结果 。在设计时默认使用局部预测器，当两个预测器都正确或都不正确时，不 改变计数器；当全局预测器正确而局部预测器预测错误时，计数器加1， 否则减1。 2018/9/21 计算机体系结构

选择器状态转移图 2018/9/21 计算机体系结构 1/0 0/1 0/0, 1/0, 1/1 0/0, 1/1 0/0, 0/1, 1/1 1/0 2018/9/21 计算机体系结构

Branch predictor performance The University of Adelaide, School of Computer Science 9/21/2018 Branch Prediction Performance Branch predictor performance 2018/9/21 计算机体系结构 155 Chapter 2 — Instructions: Language of the Computer 155

Simple dynamic prediction: Branch Target Buffer (BTB) 必须检测分支指令的地址是否匹配，以免用错误的分支地址 从表中得到预测地址 分支方向确定后，更新预测的PC Branch PC Predicted PC =? PC of instruction FETCH Extra prediction state bits Yes: instruction is branch and use predicted PC as next PC No: branch not predicted, proceed normally (Next PC = PC+4) 2018/9/21 计算机体系结构 156

2018/9/21 计算机体系结构 157

2018/9/21 计算机体系结构 158

05/06-review 分支预测对提高性能是非常重要的 基于BHT表的预测器: Basic 2-bit predictor: Correlating predictor: Multiple 2-bit predictors for each branch One for each possible combination of outcomes of preceding n branches Local predictor: One for each possible combination of outcomes for the last n occurrences of this branch Tournament predictor: Combine correlating predictor with local predictor 基于BTB的分支预测器

硬件支持精确中断 需要硬件缓存没有提交的指令结 果: reorder buffer （ROB） 3 个域: 指令类型,目的地址, 值 Reorder buffer 可以作为操作数源 => 就像有更多的寄存器（与RS类 似） 当指令执行阶段完成后，用ROB的 编号代替RS中的值 增加指令提交阶段 ROB提供执行完成阶段和提交阶段 的操作数 一旦操作数提交，结果就写入寄 存器 这样，在预测失败时，容易恢复 推断执行的指令，或发生异常时， 容易恢复状态 Reorder Buffer FP Op Queue FP Adder Res Stations FP Regs 2018/9/21 计算机体系结构 160

支持推断执行的 Tomasulo 算法的四阶段 1. Issue—get instruction from FP Op Queue 如果RS和ROB有空闲单元就发射指令。如果寄存器或ROB中源操作数 可用，就将其发送到RS，目的地址的ROB编号也发送给RS 2. Execution—operate on operands (EX) 当操作数就绪后，开始执行。如果没有就绪，监测CDB，检查RAW相 关 3. Write result—finish execution (WB) 将运算结果通过CDB传送给所有等待结果的FU以及ROB单元，标识RS 可用 4. Commit—update register with reorder result 按ROB表中顺序，如果结果已有，就更新寄存器（或存储器），并将 该指令从ROB表中删除 预测失败或有中断时，刷新ROB P191 Figure 3.14 (英文版), P141 Figure 3-9 (中文版) 2018/9/21 计算机体系结构 161

LD F6, 34(R2) LD F2, 45(R3) MULT F0, F2, F4 SUBD F8, F6, F2 DIVD F10, F0, F6 ADDD F6, F8, F2 2018/9/21 计算机体系结构 162

2018/9/21 计算机体系结构 163

2018/9/21 计算机体系结构 164

2018/9/21 计算机体系结构 165

2018/9/21 计算机体系结构 166

2018/9/21 计算机体系结构 167

2018/9/21 计算机体系结构 168

2018/9/21 计算机体系结构 169

2018/9/21 计算机体系结构 170

2018/9/21 计算机体系结构 171

2018/9/21 计算机体系结构 172

2018/9/21 计算机体系结构 173

2018/9/21 计算机体系结构 174

2018/9/21 计算机体系结构 175

2018/9/21 计算机体系结构 176

2018/9/21 计算机体系结构 177

2018/9/21 计算机体系结构 178

2018/9/21 计算机体系结构 179

2018/9/21 计算机体系结构 180

2018/9/21 计算机体系结构 181

2018/9/21 计算机体系结构 182

消除存储器的二义性 : 处理对存储器引用的RAW相关 Question: 给定一个指令序列，store，load 这两个操 作是否有关？ 即下列代码是否有相关问题? Eg: st 0(R2),R5 ld R6,0(R3) 我们是否可以较早启动ld? Store的地址可能会延迟很长时间才能得到. 我们也许想在同一个周期开始这两个操作的执行. 两种方法: No Speculation: 不进行load操作，直到我们确信地址 0(R2)  0(R3) Speculation: 我们可以假设他们相关还是不相关 (called “dependence speculation”) ，如果推测错误通过ROB来修正 2018/9/21 计算机体系结构 183

Nonspeculative Memory Disambiguation 2018/9/21 计算机体系结构

Load Ordering. Store Ordering Load queue: 以程序序存储load指令 Address generation: 生成存储器访问有效地址 Store queue: 以程序序存储store指令 Store buffer: 以程序序保留store操作（有效地址，值），一直到其成为最早的store操作，才实际更新存储器 2018/9/21 计算机体系结构

Partial Ordering 2018/9/21 计算机体系结构 Load/store queue: 长度为16的队列，存储load/store指令，直到其操作数准备好。 Indetermination matrix: 16x16 矩阵（half)，每行每列代表一个队列中的存储器操作。当有存储器操作进入队列时，对应列置位。当存储器指令计算有效地址时，对应列复位。计算有效地址的条件之一，该操作对应行为全0 2018/9/21 计算机体系结构

Dependency matrix: 16x16 矩阵，每行每列对应load/store队列的存储器操作。Load操 作如果依赖于前面的store，则将该load操作的行中对应该store的列置位。Store操作更 新存储器时，将复位该store操作对应的列。只有当load操作对应的行全0时，方可执行 load操作 Address generation: 计算存储器操作的有效地址 Address queue:保存访问cache的loads/store操作的地址。如果是load操作，除了保存地 址，还需要比较所有在该load操作之前的store的地址，如果匹配，则对dependency matrix对应位置位。 2018/9/21 计算机体系结构

Speculative Memory Disambiguation Load/Store Queue: 保存存储器操作的队列,直到可以计算有效地址 Load Queue: 该队列以程序序存储load操作的存储器物理地址。该队列有32项 Store Queue: 存储store操作的存储器物理地址以及要存储的值。该对列32项 Wait Table: 具有1024 项，每项1位的表，由存储器指令虚拟地址索引. 当我们检测到一个load操作超越了与它相关的store操作时，该 load对应项置1，取指部件读取该信息，将不会再提前发射出去。该表每隔16384周期复位一次，否则该表可能所有项均为1 2018/9/21 计算机体系结构

Memory Disambiguation: Done? FP Op Queue ROB7 ROB6 ROB5 ROB4 ROB3 ROB2 ROB1 Newest Reorder Buffer -- LD F4, 10(R3) N F2 ST 10(R3), F5 N F0 LD F0,32(R2) N Oldest -- <val 1> ST 0(R3), F4 Y Resolve RAW memory conflict? (address in memory buffers) Integer unit executes in parallel Registers To Memory Dest Dest from Memory Dest Reservation Stations 2 32+R2 4 ROB3 FP adders FP multipliers 2018/9/21 计算机体系结构 189

Tomasulo+ROB summary 实际系统的实现非常相似 不足之处： PentiumIII, PowerPC, 等 Too many value copy operations Register File →RS→ROB→Register File Too many muxes/busses (CDB) Values are from everywhere to everywhere else! Reservation Stations mix values(data) and tags (control) Slow down max clock frequency

Upper Limit to ILP: Ideal Machine FP: 75 - 150 Integer: 18 - 60 IPC 2018/9/21 计算机体系结构 191

More Realistic HW: Branch Impact FP: 15 - 45 Change from Infinite window to examine to 2000 and maximum issue of 64 instructions per clock cycle Integer: 6 - 12 IPC Perfect Pick Cor. or BHT BHT (512) Profile No prediction 2018/9/21 计算机体系结构 192

More Realistic HW: Register Impact (rename regs) FP: 11 - 45 Change 2000 instr window, 64 instr issue, 8K 2 level Prediction Integer: 5 - 15 IPC Infinite 256 128 64 32 None 2018/9/21 计算机体系结构 193

More Realistic HW: Alias Impact Change 2000 instr window, 64 instr issue, 8K 2 level Prediction, 256 renaming registers FP: 4 - 45 (Fortran, no heap) Integer: 4 - 9 IPC Perfect Global/Stack perf; heap conflicts Inspec. Assem. None 2018/9/21 计算机体系结构 194

Realistic HW for ‘9X: Window Impact Perfect disambiguation (HW), 1K Selective Prediction, 16 entry return, 64 registers, issue as many as window FP: 8 - 45 IPC Integer: 6 - 12 Infinite 256 128 64 32 16 8 4 2018/9/21 计算机体系结构 195

小结#1/2 Reservations stations: 寄存器重命名，缓冲源操作数 贡献 避免寄存器成为瓶颈 避免了Scoreboard中无法解决的 WAR, WAW hazards 允许硬件做循环展开 不限于基本块(IU先行，解决控制相关) 贡献 Dynamic scheduling Register renaming Load/store disambiguation 360/91 后 Pentium II; PowerPC 604; MIPS R10000; HP- PA 8000; Alpha 21264使用这种技术 2018/9/21 计算机体系结构 196

小结 #2/2 动态调度方案可以用硬件动态完成循环展开 Reorder Buffer: 分支预测对提高性能是非常重要的 通过重命名机制来消除WAR和 WAW 相关 Reorder Buffer: 提供了撤销指令运行的机制 指令以发射序存放在ROB中 指令顺序提交 分支预测对提高性能是非常重要的 推断执行是利用了ROB撤销指令执行的机制 Superscalar 和VLIW: CPI < 1 (IPC > 1) 2018/9/21 计算机体系结构 197

05/08-Review Reorder Buffer: 分支预测对提高性能是非常重要的 Memory Disambiguation 提供了撤销指令运行的机制 指令以发射序存放在ROB中 指令顺序提交 分支预测对提高性能是非常重要的 推断执行: 在控制相关还没有解决的情况下，就开始执行 推断执行是利用了ROB撤销指令执行的机制 Memory Disambiguation Nonspeculative Memory Disambiguation Speculative Memory Disambiguation Superscalar 和VLIW: CPI < 1 (IPC > 1) 2018/9/21 计算机体系结构 198

如何使CPI < 1 (1/2) 前面所述的各种技术主要通过减少数据相关 和控制相关，使得CPI = 1 ( CPI接近1） 两种基本方法 Superscalar: 每个时钟周期所发射的指令数不定（1 －8条） 由编译器或硬件完成调度 IBM PowerPC, Sun UltraSparc, DEC Alpha, HP 8000 该方法对目前通用计算是最成功的方法 新的概念 Instructions Per Clock (IPC) vs. CPI 2018/9/21 计算机体系结构 199

如何使 CPI < 1？ (2/2) (Very) Long Instruction Words (V)LIW: 每个时钟周期流出的指令数（操作）固定 (4-16) 由编译器调度，实际上由多个单操作指令构成一个 超长指令 目前比较成功的应用于DSP，多媒体应用 1999/2000 HP和Intel达成协议共同研究VLIW Intel Architecture-64 (Merced/A-64) 64-bit address Style: “Explicitly Parallel Instruction Computer (EPIC)” 2018/9/21 计算机体系结构 200

用于多发射处理器的五种主要方法 2018/9/21 计算机体系结构 201

Superscalar DLX 原来1 cycle load 延时在Superscalar中扩展为3条指令 Superscalar DLX: 每个时钟周期发射2条指令，1 条FP指令和一条其他 指令 – 每个时钟周期取64位; 左边为Int , 右边为FP – 只有第一条指令发射了，才能发射第二条 – 需要更多的寄存器端口，因为如果两条指令中第一条指令是对FP 的load操作（通过整数部件完成），另一条指令为浮点操作指令， 则都会有对浮点寄存器文件的操作 原来1 cycle load 延时在Superscalar中扩展为3条指令 Type Pipe Stages Int. instruction IF ID EX MEM WB Fp. Instruction Int. Instruction 2018/9/21 计算机体系结构 202

Review: 具有最小stalls数的循环展开优化 1 Loop: LD F0,0(R1) 2 LD F6,-8(R1) 3 LD F10,-16(R1) 4 LD F14,-24(R1) 5 ADDD F4,F0,F2 6 ADDD F8,F6,F2 7 ADDD F12,F10,F2 8 ADDD F16,F14,F2 9 SD 0(R1),F4 10 SD -8(R1),F8 11 SUBI R1,R1,#32 12 SD 16(R1),F12 13 BNEZ R1,LOOP 14 SD 8(R1),F16 ; 8-32 = -24 14 clock cycles, or 3.5 per iteration LD to ADDD: 1 Cycle ADDD to SD: 2 Cycles 2018/9/21 计算机体系结构 203

采用Superscalar技术的循环展开 Integer instruction FP instruction Clock cycle Loop: LD F0,0(R1) 1 LD F6,-8(R1) 2 LD F10,-16(R1) ADDD F4,F0,F2 3 LD F14,-24(R1) ADDD F8,F6,F2 4 LD F18,-32(R1) ADDD F12,F10,F2 5 SD 0(R1),F4 ADDD F16,F14,F2 6 SD -8(R1),F8 ADDD F20,F18,F2 7 SD -16(R1),F12 8 SD -24(R1),F16 9 SUBI R1,R1,#40 10 BNEZ R1,LOOP 11 SD ＋8(R1),F20 12 循环展开5次以消除延时 (+1 due to SS) 12 clocks, or 2.4 clocks per iteration (1.5X) 2018/9/21 计算机体系结构 204

多发射的问题 如果Integer和FP操作很容易区分组合，那么对这类程序在下列条件满足的 情况下理想CPI= 0.5 : 没有任何相关 如果在同一时刻发射的指令越多，译码和发射就越困难 即使是同一时刻发射2条 =>需检查2个操作码，6个寄存器描述符 ，检 查是发射1条还是2条指令。 VLIW 指令字较长可以容纳较多的操作 根据定义,VLIW中的所有操作是由编译时刻组合的，并且是相互无关 的，也就是说：可以并行执行 例如 2 个整数操作，2个浮点操作，2个存储器引用，1个分支指令 每一个操作用16 到 24 位 表示 => 共7*16 ＝ 112 bits 到 7*24 ＝ 168 bits wide 需要用编译技术调度来解决分支问题 2018/9/21 计算机体系结构 205

基于VLIW的循环展开 Unrolled 7 times to avoid delays Memory Memory FP FP Int. op/ Clock reference 1 reference 2 operation 1 op. 2 branch LD F0,0(R1) LD F6,-8(R1) 1 LD F10,-16(R1) LD F14,-24(R1) 2 LD F18,-32(R1) LD F22,-40(R1) ADDD F4,F0,F2 ADDD F8,F6,F2 3 LD F26,-48(R1) ADDD F12,F10,F2 ADDD F16,F14,F2 4 ADDD F20,F18,F2 ADDD F24,F22,F2 5 SD 0(R1),F4 SD -8(R1),F8 ADDD F28,F26,F2 6 SD -16(R1),F12 SD -24(R1),F16 SUBI R1,R1,#48 7 SD 16(R1),F20 SD 8(R1),F24 8 SD -0(R1),F28 BNEZ R1,LOOP 9 Unrolled 7 times to avoid delays 7 results in 9 clocks, or 1.3 clocks per iteration (1.8X) Average: 2.5 ops per clock, 50% efficiency 注: 在VLIW中，一条超长指令有更多的读写寄存器操作(15 vs. 6 in SS) 2018/9/21 计算机体系结构 206

Trace Scheduling 消除分支的一种策略 两步： 由编译器撤销预测错误造成的后果（恢复寄存器的 原值) Trace Selection 搜索可能最长的直线型代码（由一组基本块构成）（通过静态 预测或profile技术）(trace) Trace Compaction 将trace中的指令拼装为若干条VLIW 指令 需要一些保存环境的代码，以防预测错误 由编译器撤销预测错误造成的后果（恢复寄存器的 原值) 2018/9/21 计算机体系结构 207

HW推断执行(Tomasulo) vs. SW (VLIW) 推断执行 SW 推断执行比HW设计简单的多 2018/9/21 计算机体系结构 208

Superscalar vs. VLIW 译码、发射指令的硬件设计简单 代码量较小 更多的寄存器，一般使用多个寄存器 文件而不是多端口寄存器文件 代码量较小 二进制兼容性好 2018/9/21 计算机体系结构 209

Superscalar 的动态调度（1/2） 静态调度的缺陷： 有相关就停止发射 基于原来Superscalar的代码生成器所生成的代 码可能在新的Superscalar上运行效率较差，代 码与superscalar的结构有关 2018/9/21 计算机体系结构 210

Superscalar 的动态调度（2/2） 用Tomasulo如何发射两条指令并保持指令序 假设有1 浮点操作，1个整数操作 Tomasulo控制器一个控制整型操作的发射，一个控制浮点型操作的 发射 如果每个周期发射两条不同的指令，比较容易保持指令序 （整型类操作序，浮点类操作序） 现在只有FP的Loads操作可能会引起整型操作发射和浮点操 作发射的相关 存储器引用问题： 将load的保留站组织成队列方式，操作数必须按指令序读取 Load操作时检测Store队列中Store的地址以防止RAW冲突 Store操作时检测Load队列的地址，以防止WAR相关 Store操作按指令序进行，防止WAW相关 2018/9/21 计算机体系结构 211

Example Consider the execution of the following loop, which increments each element of an integer array, on a two-issue processor, once without speculation and once with speculation: Loop: LD R2,0(R1) ; R2=array element DADDIU R2,R2,#1 ; increment R2 SD R2,0(R1) ;store result DADDIU R1,R1,#8 ;increment pointer BNE R2,R3,LOOP ;branch if not last element Assume that there are separate integer functional units for effective address calculation, for ALU operations, and for branch condition evaluation. Create a table for the first three iterations of this loop for both processors. Assume that up to two instructions of any type can commit per clock. 2018/9/21 计算机体系结构 212

Performance of Dynamic SS 2018/9/21 计算机体系结构 213

2018/9/21 计算机体系结构 214

多发射处理器受到的限制（1/2） 程序内在的ILP的限制 如果每5条指令中有1条相关指令 : 如何保持5-路 VLIW 并行? 部件的操作延时：许多操作需要调度，使部件延 时加大 多指令流出的处理器需要大量的硬件资源 需要多个功能部件来使得多个操作并行(Easy) 需要更大的指令访问带宽(Easy) 需要增加寄存器文件的端口数（以及通信带宽） (Hard) 增加存储器的端口数（带宽） (Harder) 2018/9/21 计算机体系结构 215

多发射处理器受到的限制（2/2） 一些由Superscalar或VLIW的实现带来的特殊问题 VLIW 代码量问题: 循环展开 + VLIW中无用的区域 VLIW 互锁 => 1 个相关导致所有指令停顿 VLIW 的二进制兼容问题 2018/9/21 计算机体系结构 216

ILP受到的限制 大量研究结果的相互矛盾 Benchmarks (vectorized Fortran FP vs. integer C programs) HW方式好 软件（Compiler）方式好 通过增加HW成本使用现有各种机制到底能提 高多少ILP? 我们是否要设计新的HW/SW机制来提高性能? 2018/9/21 计算机体系结构 217

Summary 推断执行: Superscalar and VLIW: CPI < 1 (IPC > 1) 基于硬件的推断执行 在控制相关还没有实际解决的情况下，就开始执行 乱序执行，顺序确认(reorder buffer) Superscalar and VLIW: CPI < 1 (IPC > 1) Dynamic issue vs. Static issue 同一时刻发射更多的指令 => 导致更大的冲突开销 基于硬件的推断执行 动态分支预测 推断执行 动态调度 2018/9/21 计算机体系结构 218

Multithreading 背景：从单线程程序挖掘指令集并行越来越困难 许多工作任务可以使用线程级并行来完成 线程级并行来源于多道程序设计 线程级并行的基础是多线程应用，即一个任务可以用多 个线程并行来加速 多线程应用可以用线程级并行来提高单个处理器的 利用率 针对单个处理器：多个线程以重叠方式共享单个处理器 的功能单元 2018/9/21 计算机体系结构 219 219

Pipeline Hazards 如何处理相关? 使用interlock机制(slow) F D X M W t0 t1 t2 t3 t4 t5 t6 t7 t8 t9 t10 t11 t12 t13 t14 LW r1, 0(r2) LW r5, 12(r1) ADDI r5, r5, #12 SW 12(r1), r5 Each instruction may depend on the next 如何处理相关? 使用interlock机制(slow) 或定向路径 (needs hardware, doesn’t help all hazards) 2018/9/21 计算机体系结构 220 220

Multithreading 如何保证流水线中指令间无数据依赖关系？ 一种办法：在相同的流水线中交叉执行来自不同线程的指令 F D X M W t0 t1 t2 t3 t4 t5 t6 t7 t8 T1: LW r1, 0(r2) T2: ADD r7, r1, r4 T3: XORI r5, r4, #12 T4: SW 0(r7), r5 T1: LW r5, 12(r1) t9 Interleave 4 threads, T1-T4, on non-bypassed 5-stage pipe Prior instruction in a thread always completes write-back before next instruction in same thread reads register file 2018/9/21 计算机体系结构 221 221

A conventional processor compared with a multithreaded processor. 2018/9/21 计算机体系结构

CDC 6600 Peripheral Processors (Cray, 1964) 第一个支持多线程模式的硬件系统 10 个“virtual” I/O 处理器 流水线控制采用固定交叉方式 流水线周期为100ns(每段100ns) 每个虚拟处理器每隔1000ns执行一条 指令 累加器型ISA有利于保存处理器状态 Was objective was to cope with long I/O latencies? 2018/9/21 计算机体系结构 223 223

Simple Multithreaded Pipeline X PC 1 PC 1 GPR1 I$ IR GPR1 PC 1 GPR1 GPR1 PC 1 D$ Y +1 2 2 Thread select 必须传递线程选择信号以保证各流水段读写的正确性 从软件（包括OS）的角度看 好像存在多个CPU（虽然针对每个 线程，CPU似乎运行的慢一些 2018/9/21 计算机体系结构 224 224

Multithreading Costs 每个线程需要拥有自己的用户态信息（user state) ： 包括PC、GPRs 需要自己的系统态信息（system state） 虚拟存储的页表基地址寄存器（Virtual-memory page- table-base register） 异常处理寄存器（Exception-handling registers） 其他开销: 需要处理由于线程竞争导致的Cache/TLB冲突 或 需要更 大的cache/TLB 容量 更多的OS调度开销 2018/9/21 计算机体系结构 225 225

Thread Scheduling Policies 固定交叉模式 (CDC 6600 PPUs, 1964) 针对N个线程，每个线程每隔N个周期执行一条指令 如果流水线的某一时隙(slot)其对应线程未就绪，插入 pipeline bubble 软件控制的交叉模式 (TI ASC PPUs, 1971) OS 为N个线程分配流水线的S个pipeline slots 硬件针对S个slots采用固定交叉模式执行相应的线程 硬件控制的线程调度 (HEP, 1982) 硬件跟踪哪些线程处于ready状态 根据优先级方案选择线程执行 Software-controlled interleave, S > N. Wheel with the threads in each slot. If thread is ready to go It goes, else NOP, I.e., pipeline bubble. 2018/9/21 计算机体系结构 226 226

Superscalar Machine Efficiency Issue width Time Instruction issue Completely idle cycle (vertical waste) Partially filled cycle, i.e., IPC < 4 (horizontal waste) Focus is switching to function unit efficiency (as a measure of throughput). 2018/9/21 计算机体系结构 227 227

Chip Multiprocessing (CMP) Issue width Time 分成两个处理器后的效果？ reduces horizontal waste, leaves some vertical waste, and puts upper limit on peak throughput of each thread. 2018/9/21 计算机体系结构 228 228

Vertical(Coarse-Grain) Multithreading Issue width Instruction issue Second thread interleaved cycle-by-cycle Time Partially filled cycle, i.e., IPC < 4 (horizontal waste) 如果基于细粒度的时钟周期交叉运行模式，结果怎样？ removes vertical waste, but leaves some horizontal waste 2018/9/21 计算机体系结构 229 229

Fine-Grain Multithreading Issue width Fine-Grained Instruction issue Time 2018/9/21 计算机体系结构

Ideal Superscalar Multithreading [Tullsen, Eggers, Levy, UW, 1995] Issue width Time 采用多线程交叉模式使用多个issue slots Simultaneous Multithreading (SMT) 2018/9/21 计算机体系结构 231 231

Simultaneous Multithreading (SMT) for OoO Superscalars “vertical”多线程：即某一时段每条流水线上运 行一个线程 SMT 使用OoOSuperscalar细粒度控制技术在相同 时钟周期运行多个线程的指令，以更好的利用系 统资源 2018/9/21 计算机体系结构 232 232

For most apps, most execution units lie idle in an OoO superscalar For an 8-way superscalar. From: Tullsen, Eggers, and Levy, “Simultaneous Multithreading: Maximizing On-chip Parallelism”, ISCA 1995. 2018/9/21 计算机体系结构 233 233

增加多上下文切换以及取指引擎可以从多个线程取指令， 并可同时发射 O-o-O Simultaneous Multithreading [Tullsen, Eggers, Emer, Levy, Stamm, Lo, DEC/UW, 1996] 增加多上下文切换以及取指引擎可以从多个线程取指令， 并可同时发射 使用OoO superscalar处理器的发射宽度，从发射队列中 选择指令发射，这些指令可来源于多个线程 OoO 指令窗口已经具备从多个线程调度指令的绝大多 数电路 任何单线程程序可以充分使用整个系统资源 2018/9/21 计算机体系结构 234 234

SMT adaptation to parallelism type For regions with high thread level parallelism (TLP) entire machine width is shared by all threads For regions with low thread level parallelism (TLP) entire machine width is available for instruction level parallelism (ILP) Issue width Time Issue width Time Amdahl’s law… 2018/9/21 计算机体系结构 235 235

Denelcor HEP (Burton Smith, 1982) 第一个在主处理器中使用硬件多线程技术的商用机器 120 threads per processor 10 MHz clock rate Up to 8 processors precursor to Tera MTA (Multithreaded Architecture) Would be nice to add a slide on the implementation… HEP（Heterogeneous Element Processor） 2018/9/21 计算机体系结构 236 236

Tera MTA (1990-) Up to 256 processors Up to 128 active threads per processor Processors and memory modules populate a sparse 3D torus interconnection fabric Flat, shared main memory No data cache Sustains one main memory access per cycle per processor GaAs logic in prototype, 1KW/processor @ 260MHz Second version CMOS, MTA-2, 50W/processor New version, XMT, fits into AMD Opteron socket, runs at 500MHz 2018/9/21 计算机体系结构 237 237

MTA Pipeline Every cycle, one VLIW instruction from one active thread is launched into pipeline Instruction pipeline is 21 cycles long Memory operations incur ~150 cycles of latency Issue Pool Inst Fetch W M A C W Write Pool Memory Pool W Retry Pool Assuming a single thread issues one instruction every 21 cycles, and clock rate is 260 MHz… What is single-thread performance? Effective single-thread issue rate is 260/21 = 12.4 MIPS Memory unit is busy, or sync operation failed retry. Just goes around the memory pipeline. Interconnection Network Memory pipeline 2018/9/21 计算机体系结构 238 238

Coarse-Grain Multithreading Tera MTA 适用于大规模数据集并且数据本地性较低 的应用 没有数据Cache 需要大量的并行线程以隐藏存储器访问延迟 其他数据本地性较好的应用 如果Cache命中，流水线上的停顿较少 仅需要添加较少的线程来隐藏偶尔Cache失效导致的延迟 Cache失效时，将该线程换出 当某一线程的执行存在长延迟操作时，选择另一线 程执行，并切换线程上下文 Tera --- 256 mem-ops/cycle * 150 cycles/mem-op = 38K instructions-in-flight… Tera not very successful, 2 machines sold. Changed their name back to Cray! 2018/9/21 计算机体系结构 239 239

MIT Alewife (1990) Modified SPARC chips Up to four threads per node register windows hold different thread contexts Up to four threads per node Thread switch on local cache miss 2018/9/21 计算机体系结构 240 240

IBM PowerPC RS64-IV (2000) Commercial coarse-grain multithreading CPU Based on PowerPC with quad-issue in-order five-stage pipeline Each physical CPU supports two virtual CPUs On L2 cache miss, pipeline is flushed and execution switches to second thread short pipeline minimizes flush penalty (4 cycles), small compared to memory access latency flush pipeline to simplify exception handling 2018/9/21 计算机体系结构 241 241

Oracle/Sun Niagara processors Target is datacenters running web servers and databases, with many concurrent requests Provide multiple simple cores each with multiple hardware threads, reduced energy/operation though much lower single thread performance Niagara-1 [2004], 8 cores, 4 threads/core Niagara-2 [2007], 8 cores, 8 threads/core Niagara-3 [2009], 16 cores, 8 threads/core T4 [2011], 8 cores, 8 threads/core T5 [2012], 16 cores, 8 threads/core 2018/9/21 计算机体系结构 242

Oracle/Sun Niagara-3, “Rainbow Falls” 2009 2018/9/21 计算机体系结构 243

IBM Power 4 Single-threaded predecessor to Power 5. 8 execution units in out-of-order engine, each may issue an instruction each cycle. 2018/9/21 计算机体系结构 244 244

Power 4 Power 5 2 fetch (PC), 2 initial decodes 2 commits (architected register sets) Power 5 2 fetch (PC), 2 initial decodes 2018/9/21 计算机体系结构 245 245

Power 5 data flow ... Why only 2 threads? With 4, one of the shared resources (physical registers, cache, memory bandwidth) would be prone to bottleneck 2018/9/21 计算机体系结构 246 246

Changes in Power 5 to support SMT Increased associativity of L1 instruction cache and the instruction address translation buffers Added per-thread load and store queues Increased size of the L2 (1.92 vs. 1.44 MB) and L3 caches Added separate instruction prefetch and buffering per thread Increased the number of virtual registers from 152 to 240 Increased the size of several issue queues The Power5 core is about 24% larger than the Power4 core because of the addition of SMT support 2018/9/21 计算机体系结构 247 247

Pentium-4 Hyperthreading (2002) First commercial SMT design (2-way SMT) Hyperthreading == SMT Logical processors share nearly all resources of the physical processor Caches, execution units, branch predictors Die area overhead of hyperthreading ~ 5% When one logical processor is stalled, the other can make progress No logical processor can use all entries in queues when two threads are active Processor running only one active software thread runs at approximately same speed with or without hyperthreading Hyperthreading dropped on OoO P6 based followons to Pentium-4 (Pentium-M, Core Duo, Core 2 Duo), until revived with Nehalem generation machines in 2008. Intel Atom (in-order x86 core) has two-way vertical multithreading Load-store buffer in L1 cache doesn’t behave like that, and hence 15% slowdown. 2018/9/21 计算机体系结构 248 248

Initial Performance of SMT Pentium 4 Extreme SMT yields 1.01 speedup for SPECint_rate benchmark and 1.07 for SPECfp_rate Pentium 4 is dual threaded SMT SPECRate requires that each SPEC benchmark be run against a vendor-selected number of copies of the same benchmark Running on Pentium 4 each of 26 SPEC benchmarks paired with every other (262 runs) speed-ups from 0.90 to 1.58; average was 1.20 Power 5, 8-processor server 1.23 faster for SPECint_rate with SMT, 1.16 faster for SPECfp_rate Power 5 running 2 copies of each app speedup between 0.89 and 1.41 Most gained some Fl.Pt. apps had most cache conflicts and least gains 2018/9/21 计算机体系结构 249 249

Summary: Multithreaded Categories Simultaneous Multithreading Superscalar Fine-Grained Coarse-Grained Multiprocessing Time (processor cycle) Thread 1 Thread 3 Thread 5 Thread 2 Thread 4 Idle slot 2018/9/21 计算机体系结构 250 250

Acknowledgements These slides contain material developed and copyright by: John Kubiatowicz (UCB) Krste Asanovic (UCB) David Patterson (UCB) Chenxi Zhang (Tongji) UCB material derived from course CS152、CS252 2018/9/21 计算机体系结构 251 251