周学海 xhzhou@ustc.edu.cn 0551-63606864 中国科学技术大学 2018/11/16 计算机体系结构 周学海 xhzhou@ustc.edu.cn 0551-63606864 中国科学技术大学.

Presentation on theme: "周学海 xhzhou@ustc.edu.cn 0551-63606864 中国科学技术大学 2018/11/16 计算机体系结构 周学海 xhzhou@ustc.edu.cn 0551-63606864 中国科学技术大学."— Presentation transcript:

1 周学海 xhzhou@ustc.edu.cn 0551-63606864 中国科学技术大学
2018/11/16 计算机体系结构 周学海 中国科学技术大学

2 04/16-review 存储器组织 存储系统结构 参考文献
Davis, B. T. (2001). Modern dram architectures, University of Michigan: 221. Jacob, B. (2009). The Memory System, Morgan & Claypool. 2018/11/16 计算机体系结构

3 04/16-review 交叉存储器组织 (80ns) (40ns) 2018/11/16 计算机体系结构

4 04/16-review 虚拟存储 解决的问题： 4Q 替换规则：LRU 写策略：总是用写回法，因为访问硬盘速度很慢。
映象规则：由于失效开销很大，一般选择低失效率方法，即全相联映射 查找算法－用附加数据结构（VPN －> PPN） 固定页大小－用页表 可变长段 －段表 替换规则：LRU 写策略：总是用写回法，因为访问硬盘速度很慢。 2018/11/16 计算机体系结构

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

6 系统结构的Flynn分类 (1966) SISD: Single instruction stream, single data stream 单处理器模式 SIMD: Single instruction stream, multiple data streams 相同的指令作用在不同的数据 可用来挖掘数据级并行(Data Level Parallelism) 如：Vector processors, SIMD instructions, and Graphics processing units MISD: Multiple instruction streams, single data stream No commercial implementation MIMD: Multiple instruction streams, multiple data streams 通用性最强的一种结构，可用来挖掘线程级并行、数据级并行….. 组织方式可以是松耦合方式也可以是紧耦合方式 2018/11/16 计算机体系结构

7 Levels of Parallelism 请求级并行 进程级并行 线程级并行 数据级并行 指令级并行
多个任务可被分配到多个计算机上并行执行 进程级并行 进程可被调度到不同的处理器上并行执行 线程级并行 任务被组织成多个线程，多个线程共享一个进程的地址空间 每个线程有自己独立的程序计数器和寄存器文件 数据级并行 单线程（逻辑上）中并行处理多个数据 (SIMD/Vector execution) 一个程序计数器, 多个执行部件 指令级并行 针对单一指令流，多个执行部件并行执行不同的指令 2018/11/16 计算机体系结构

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

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

10 采用的基本技术 2018/11/16 计算机体系结构 10

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

12 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/11/16 计算机体系结构 12

13 简单循环及其对应的汇编程序 for (i=1; i<=1000; i++) x(i) = x(i) + s; 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/11/16 计算机体系结构 13

14 FP 循环中的相关 Loop: LD F0,0(R1) ;F0=vector element
ADDD F4,F0,F ;add scalar in F2 SD (R1),F ;store result SUBI R1,R1, ;decrement pointer 8B (DW) BNEZ R1,Loop ;branch R1!=zero NOP ;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 2018/11/16 计算机体系结构 14

15 FP 循环中的最少Stalls数 Swap BNEZ and SD by changing address of SD
1 Loop: LD F0,0(R1) 2 SUBI R1,R1,8 3 ADDD F4,F0,F2 stall 5 BNEZ R1,Loop ;delayed branch 6 SD 8(R1),F ;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/11/16 计算机体系结构 15

16 FP 循环中的Stalls 10 clocks: 是否可以通过调整代码顺序使stalls减到最小 2 stall
1 Loop: LD F0,0(R1) ;F0=vector element stall 3 ADDD F4,F0,F2 ;add scalar in F2 stall stall SD 0(R1),F4 ;store result SUBI R1,R1,8 ;decrement pointer 8B (DW) stall ； BNEZ R1,Loop ;branch R1!=zero 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/11/16 计算机体系结构 16

17 循环展开4次(straight forward 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 x (1+2) + 1 = 28 cycles, or 7 per iteration Assumes R1 is multiple of 4 Rewrite loop to minimize stalls? 2018/11/16 计算机体系结构 17

18 Stalls数最小的循环展开 代码移动后 14 clock cycles, or 3.5 per iteration
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/11/16 计算机体系结构 18

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

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

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

22 下列程序哪里有数据相关? 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/11/16 计算机体系结构 22

23 从编译器角度看代码移动(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/11/16 计算机体系结构 23

24 下列是否有名相关? 如何消除名相关? 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/11/16 计算机体系结构 24

25 下列是否存在名相关? 1 Loop:LD F0,0(R1) 2 ADDD F4,F0,F2
3 SD 0(R1),F4 ;drop SUBI & BNEZ 4 LD F6,-8(R1) 5 ADDD F8,F6,F2 6 SD -8(R1),F8 ;drop SUBI & BNEZ 7 LD F10,-16(R1) 8 ADDD F12,F10,F2 9 SD -16(R1),F12 ;drop SUBI & BNEZ 10 LD F14,-24(R1) 11 ADDD F16,F14,F2 12 SD -24(R1),F16 13 SUBI R1,R1,#32 ;alter to 4*8 14 BNEZ R1,LOOP 15 NOP 这种方法称为寄存器重命名（register renaming） 2018/11/16 计算机体系结构 25

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

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

28 下列程序段的控制相关 1 Loop: LD F0,0(R1) 11 LD F0,0(R1) 2 ADDD F4,F0,F2
SD (R1),F4 SUBI R1,R1,8 BEQZ R1,exit LD F0,0(R1) ADDD F4,F0,F2 SD (R1),F4 SUBI R1,R1,8 BEQZ R1,exit LD F0,0(R1) ADDD F4,F0,F2 SD (R1),F4 SUBI R1,R1,8 BEQZ R1,exit .... Everything after branch to next branch 2018/11/16 计算机体系结构 28

29 循环间相关（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/11/16 计算机体系结构 29

30 无回路的循环间相关（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/11/16 计算机体系结构 30

31 循环间相关（3/4）-循环变换 OLD: for (i=1; i<=100; i=i+1) { A[i] = A[i] + B[i]; /* S1 */ B[i+1] = C[i] + D[i];} /* S2 */ NEW: 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]; 2018/11/16 计算机体系结构 31

32 循环间相关（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/11/16 计算机体系结构 32

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

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

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

36 基本流水线 lw r1, 0(r2) sub r4,r1,r6 and r6,r3,r7 or r8,r4,r9
Time (clock cycles) or r8,r4,r9 I n s t r. O r d e lw r1, 0(r2) sub r4,r1,r6 and r6,r3,r7 Reg ALU DMem Ifetch Bubble DMem 中国科学技术大学

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

38 记分牌技术要点(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/11/16 计算机体系结构 38

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

40 带有记分牌控制的DLX 2018/11/16 计算机体系结构 40

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

42 记分牌控制的四阶段（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/11/16 计算机体系结构 42

43 记分牌的结构 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/11/16 计算机体系结构 43

44 记分牌流水线控制 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/11/16 计算机体系结构 44

45 Scoreboard Example 2018/11/16 计算机体系结构 45

46 Scoreboard Example: Cycle 1
2018/11/16 计算机体系结构 46

47 Scoreboard Example: Cycle 2
Issue 2nd LD? 2018/11/16 计算机体系结构 47

48 Scoreboard Example: Cycle 3
Issue MULT? 2018/11/16 计算机体系结构 48

49 Scoreboard Example: Cycle 4
2018/11/16 计算机体系结构 49

50 Scoreboard Example: Cycle 5
2018/11/16 计算机体系结构 50

51 Scoreboard Example: Cycle 6
2018/11/16 计算机体系结构 51

52 Scoreboard Example: Cycle 7
Read multiply operands? 2018/11/16 计算机体系结构 52

53 Scoreboard Example: Cycle 8a (First half of clock cycle)
2018/11/16 计算机体系结构 53

54 Scoreboard Example: Cycle 8b (Second half of clock cycle)
2018/11/16 计算机体系结构 54

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

56 Scoreboard Example: Cycle 10
2018/11/16 计算机体系结构 56

57 Scoreboard Example: Cycle 11
2018/11/16 计算机体系结构 57

58 Scoreboard Example: Cycle 12
Read operands for DIVD? 2018/11/16 计算机体系结构 58

59 Scoreboard Example: Cycle 13
2018/11/16 计算机体系结构 59

60 Scoreboard Example: Cycle 14
2018/11/16 计算机体系结构 60

61 Scoreboard Example: Cycle 15
2018/11/16 计算机体系结构 61

62 Scoreboard Example: Cycle 16
2018/11/16 计算机体系结构 62

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

64 Scoreboard Example: Cycle 18
2018/11/16 计算机体系结构 64

65 Scoreboard Example: Cycle 19
2018/11/16 计算机体系结构 65

66 Scoreboard Example: Cycle 20
2018/11/16 计算机体系结构 66

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

68 Scoreboard Example: Cycle 22
2018/11/16 计算机体系结构 68

69 Continue……. 2018/11/16 计算机体系结构 69

70 Scoreboard Example: Cycle 61
2018/11/16 计算机体系结构 70

71 Scoreboard Example: Cycle 62
2018/11/16 计算机体系结构 71

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

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

74 CDC 6600 Scoreboard CDC 6600 scoreboard的主要缺陷: 没有定向数据通路
指令窗口较小，仅局限于基本块内的调度 功能部件数较少，容易产生结构相关，特别是其 Load/store操作也是用IU部件完成的 结构冲突时不能发射 WAR相关是通过等待解决的 WAW相关时，不会进入IS阶段 2018/11/16 计算机体系结构 74

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

76 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/11/16 计算机体系结构 76

77 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/11/16 计算机体系结构 77

78 Tomasulo Organization (cont.)
2018/11/16 计算机体系结构 78

79 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/11/16 计算机体系结构 79

80 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/11/16 计算机体系结构 80

81 Tomasulo 算法流水线控制 Issue FP Operation: Wait until : Station r empty
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 if(RegisterStat[rs].Qi0) {RS[r].Qj  RegisterStat[rs].Qi} RS[r].A imm; RS[r].Busy  yes; Load only: RegisterStat[rt].Qi = r; Store only: 1st 操作数 2nd 操作数 基址寄存器 需写入的 数据寄存器 2018/11/16 计算机体系结构 81 81

82 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 Read from Mem[RS[r].A] 2018/11/16 计算机体系结构 82

83 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/11/16 计算机体系结构 83

84 Tomasulo Example 2018/11/16 计算机体系结构 84

85 Tomasulo Example Cycle 1
2018/11/16 计算机体系结构 85

86 Tomasulo Example Cycle 2
Note: Unlike 6600, can have multiple loads outstanding 2018/11/16 计算机体系结构 86

87 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/11/16 计算机体系结构 87

88 Tomasulo Example Cycle 4
Load2 completing; what is waiting for Load1? 2018/11/16 计算机体系结构 88

89 Tomasulo Example Cycle 5
2018/11/16 计算机体系结构 89

90 Tomasulo Example Cycle 6
Issue ADDD here vs. scoreboard? 2018/11/16 计算机体系结构 90

91 Tomasulo Example Cycle 7
Add1 completing; what is waiting for it? 2018/11/16 计算机体系结构 91

92 Tomasulo Example Cycle 8
2018/11/16 计算机体系结构 92

93 Tomasulo Example Cycle 9
2018/11/16 计算机体系结构 93

94 Tomasulo Example Cycle 10
Add2 completing; what is waiting for it? 2018/11/16 计算机体系结构 94

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

96 Tomasulo Example Cycle 12
2018/11/16 计算机体系结构 96

97 Tomasulo Example Cycle 13
2018/11/16 计算机体系结构 97

98 Tomasulo Example Cycle 14
2018/11/16 计算机体系结构 98

99 Tomasulo Example Cycle 15
2018/11/16 计算机体系结构 99

100 Tomasulo Example Cycle 16
2018/11/16 计算机体系结构 100

101 Faster than light computation (skip a couple of cycles)
2018/11/16 计算机体系结构 101

102 Tomasulo Example Cycle 55
2018/11/16 计算机体系结构 102

103 Tomasulo Example Cycle 56
Mult2 is completing; what is waiting for it? 2018/11/16 计算机体系结构 103

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

105 Compare to Scoreboard Cycle 62
结构冲突 没有定向技术 2018/11/16 计算机体系结构 105

106 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/11/16 计算机体系结构 106

107 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/11/16 计算机体系结构 107

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

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

110 Loop Example 2018/11/16 计算机体系结构 110

111 Loop Example Cycle 1 2018/11/16 计算机体系结构 111

112 Loop Example Cycle 2 2018/11/16 计算机体系结构 112

113 Loop Example Cycle 3 Implicit renaming sets up “DataFlow” graph
2018/11/16 计算机体系结构 113

114 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/11/16 计算机体系结构 114

115 Loop Example Cycle 4 Dispatching SUBI Instruction 2018/11/16 计算机体系结构
115

116 Loop Example Cycle 5 And, BNEZ instruction 2018/11/16 计算机体系结构 116

117 Loop Example Cycle 6 Notice that F0 never sees Load from location 80
2018/11/16 计算机体系结构 117

118 Loop Example Cycle 7 Register file completely detached from iteration 1 2018/11/16 计算机体系结构 118

119 Loop Example Cycle 8 First and Second iteration completely overlapped
2018/11/16 计算机体系结构 119

120 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/11/16 计算机体系结构 120

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

122 Loop Example Cycle 10 Load2 completing: who is waiting?
Note: Dispatching BNEZ 2018/11/16 计算机体系结构 122

123 Loop Example Cycle 11 Next load in sequence 2018/11/16 计算机体系结构 123

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

125 Loop Example Cycle 13 2018/11/16 计算机体系结构 125

126 Loop Example Cycle 14 Mult1 completing. Who is waiting? 2018/11/16
计算机体系结构 126

127 Loop Example Cycle 15 Mult2 completing. Who is waiting? 2018/11/16
计算机体系结构 127

128 Loop Example Cycle 16 2018/11/16 计算机体系结构 128

129 Loop Example Cycle 17 2018/11/16 计算机体系结构 129

130 Loop Example Cycle 18 2018/11/16 计算机体系结构 130

131 Loop Example Cycle 19 2018/11/16 计算机体系结构 131

132 Loop Example Cycle 20 2018/11/16 计算机体系结构 132

133 -Review-基本Tomasulo 基本数据结构 Tomasulo三阶段 Reservation Station
Issue Execution WriteResult 基本数据结构 Instruction Status Reservation Station Register Result Status 2018/11/16 计算机体系结构

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

135 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/11/16 计算机体系结构 135

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

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

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

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

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

141 分支对性能的影响 假设在一条有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/11/16 计算机体系结构 141

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

143 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/11/16 计算机体系结构 143

144 1-bit BHT Branch History Table: 问题: 在一个循环中, 1-bit BHT 将导致2次分支预 测错误
分支指令的PC的低位索引 该表记录上一次转移是否成功 不做地址检查 1-bit BHT 问题: 在一个循环中, 1-bit BHT 将导致2次分支预 测错误 假设一循环次数为10次的简单程序段 最后一次循环 前面为预测成功，最后一次需要退出循环 首次循环 前面为预测为失败，这次实际上为成功 2018/11/16 计算机体系结构 144

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

146 2018/11/16 计算机体系结构 146

147 2018/11/16 计算机体系结构 147

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

149 Correlating Branch Predicator
翻译为MIPS SUBI R3,R1,#2 BNEZ R3,L ; branch b1 (aa!=2) ADDI R1,R0,R0 ;aa=0 L1: SUBI R3,R2,#2 BNEZ R3,L ;branch b2(bb!=2) ADDI R2,R0,R0 ; bb=0 L2: SUBI R3,R1,R2 ;R3=aa-bb BEQZ R3,L ;branch b3 (aa==bb) 观察结果： b3 与分支b2 和b1相关。 如果b1和b2都分支失败，则b3一定成功。 例如： 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/11/16 计算机体系结构 149

150 Correlating Branches Correlating predictors 或 两级预测器： 工作原理：
分支预测器根据其他分支的行 为来进行预测。 工作原理： 根据一个简单的例子来看其基 本原理 翻译为DLX if (d==0)d=1; if (d==1) d=0; BNEZ R1,L ;branch b1(d!=0) ADDI R1,R0,#1 ;d==0, so d=1 L1: ADDI R3,R1,#-1 BNEZ R3,L ;branch b2(d!=1) ... L2: 2018/11/16 计算机体系结构 150

151 两级预测器基本工作原理 假设d的初始值序列为0，1，2 if (d==0)d=1; b1 如果分支失败，b2一定也 分支失败。
前面的两位标准的预测方案就 没法利用这一点，而两级预测 方案就可以。 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) 2018/11/16 计算机体系结构 151

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

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

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

155 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/11/16 计算机体系结构 155

156 2018/11/16 计算机体系结构 156

157 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/11/16 计算机体系结构 157

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

159 竞赛预测器 全局预测器 局部预测器：设计为两层。 选择器： Global Prediction
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/11/16 计算机体系结构

160 选择器状态转移图 选择局部预测器预测结果择 选择全局预测器预测结果择 1/0 0/1 0/0, 1/0, 1/1 0/0, 1/1
0/0, 0/1, 1/1 1/0 选择局部预测器预测结果择 选择全局预测器预测结果择 2018/11/16 计算机体系结构

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

162 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/11/16 计算机体系结构 162

163 2018/11/16 计算机体系结构 163

164 Prediction accuracy is 90% (for instructions in the buffer).
Determine the total branch penalty for a branch-target buffer assuming the penalty cycles for individual mispredictions from Figure Make the following assumptions about the prediction accuracy and hit rate: Prediction accuracy is 90% (for instructions in the buffer). Hit rate in the buffer is 90% (for branches predicted taken). 2018/11/16 计算机体系结构 164

165 -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的分支预测器

166 Instruction Fetch Unit
2018/11/16 计算机体系结构

167 预测器的基本结构及输入输出 预测器 --状态信息 根据outcomes来更新状态信息 使用FSM来完成决策
根据Branch History和PC来选择状态 由状态决定输出 预测器 --状态信息 --决策机制 outcomes Branch History PC NT or T 2018/11/16 计算机体系结构

168 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/11/16 计算机体系结构 168

169 Alpha 21264 Alpha 21264 竞赛预测器 1024 entries 1024 entries 4096 entries
2bits 3 bits 10 bits PC 12 bits Hash Hash 全局预测器 PC 2bits Selector Alpha 竞赛预测器 4096 entries NT or T 2018/11/16 计算机体系结构

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

171 支持推断执行的 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 (英文版), P141 Figure 3-9 (中文版) 2018/11/16 计算机体系结构 171

172 例如： LD F6, 34(R2) LD F2, 45(R3) MULT F0, F2, F4 SUBD F8, F6, F2
DIVD F10, F0, F6 ADDD F6, F8, F2 假设：执行阶段的周期数 LD：１cycles MULT: 9 cycles SUBD/ADDD: 2cycles DIVD: 40 cycles 2018/11/16 计算机体系结构 172

173 Issue 2018/11/16 计算机体系结构

174 Execute 2018/11/16 计算机体系结构

175 Write result & Commit 2018/11/16 计算机体系结构

176 2018/11/16 计算机体系结构 176

177 2018/11/16 计算机体系结构 177

178 2018/11/16 计算机体系结构 178

179 2018/11/16 计算机体系结构 179

180 2018/11/16 计算机体系结构 180

181 2018/11/16 计算机体系结构 181

182 2018/11/16 计算机体系结构 182

183 2018/11/16 计算机体系结构 183

184 2018/11/16 计算机体系结构 184

185 2018/11/16 计算机体系结构 185

186 2018/11/16 计算机体系结构 186

187 2018/11/16 计算机体系结构 187

188 2018/11/16 计算机体系结构 188

189 2018/11/16 计算机体系结构 189

190 2018/11/16 计算机体系结构 190

191 2018/11/16 计算机体系结构 191

192 2018/11/16 计算机体系结构 192

193 2018/11/16 计算机体系结构 193

194 2018/11/16 计算机体系结构 194

195 2018/11/16 计算机体系结构 195

196 -Review Reorder Buffer: 分支预测对提高性能是非常重要的 Memory Disambiguation
提供了撤销指令运行的机制 指令以发射序存放在ROB中 指令顺序提交 分支预测对提高性能是非常重要的 推断执行: 在控制相关还没有解决的情况下，开始执行 推断执行是利用了ROB撤销指令执行的机制 Memory Disambiguation Nonspeculative Memory Disambiguation Speculative Memory Disambiguation 2018/11/16 计算机体系结构 196

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

198 Nonspeculative Memory Disambiguation
非投机方式的基本原则：当前存储器指令之前的store指令计算存储器地址后， 才能执行当前的存储器操作 2018/11/16 计算机体系结构

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

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

201 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对应位置位。 Renaming stage 2018/11/16 计算机体系结构

202 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/11/16 计算机体系结构

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

204 Memory Disambiguation:
Done? FP Op Queue ROB7 ROB6 ROB5 ROB4 ROB3 ROB2 ROB1 Newest Reorder Buffer F4 LD F4, 10(R3) N -- 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/11/16 计算机体系结构 204

205 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

206 小结#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/11/16 计算机体系结构 206

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

208 如何使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/11/16 计算机体系结构 208

209 如何使 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/11/16 计算机体系结构 209

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

211 Superscalar DLX 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/11/16 计算机体系结构 211

212 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 = clock cycles, or 3.5 per iteration LD to ADDD: 1 Cycle ADDD to SD: 2 Cycles 2018/11/16 计算机体系结构 212

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

214 多发射的问题 如果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/11/16 计算机体系结构 214

215 Unrolled 7 times to avoid delays
基于VLIW的循环展开 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),F 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/11/16 计算机体系结构 215

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

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

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

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

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

221 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/11/16 计算机体系结构 221

222 Performance of Dynamic SS
2018/11/16 计算机体系结构 222

223 2018/11/16 计算机体系结构 223

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

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

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

227 -review 存储器访问的冲突消解 Superscalar and VLIW: CPI < 1 (IPC > 1)
非投机方式的冲突消解 Total Ordering Partial Ordering Load Ordering, Store Ordering 按照程序的逻辑序计算访存地址，乱序执行存储器操作。 投机方式的执行 Store Ordering 假设Load操作与之前未计算出有效地址的store操作无关。 Superscalar and VLIW: CPI < 1 (IPC > 1) Dynamic issue vs. Static issue 同一时刻发射更多的指令 => 导致更大的冲突开销 2018/11/16 计算机体系结构 227

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

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

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

231 Pipeline Hazards Each instruction may depend on the next 如何处理相关? F D X
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) 或定向路径 2018/11/16 计算机体系结构 231 231

232 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/11/16 计算机体系结构 232 232

233 A conventional processor compared with a multithreaded processor.
2018/11/16 计算机体系结构

234 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/11/16 计算机体系结构 234 234

235 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/11/16 计算机体系结构 235 235

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

237 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/11/16 计算机体系结构 237 237

238 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/11/16 计算机体系结构 238 238

239 Chip Multiprocessing (CMP)
Issue width Time 分成两个处理器后的效果？ 同一时钟周期无法执行不同线程的指令 提高了水平方向的利用率（reduces horizontal waste） 仍然存在垂直方向的浪费 2018/11/16 计算机体系结构 239 239

240 Vertical(Coarse-Grain) Multithreading
粗粒度多线程方式 当线程运行时存在较长时 间延时时切换到另一线程 例如：Cache失效时 等待同步结束 同一线程指令间的较短延 时不切换 如果基于粗粒度的时钟 周期交叉运行模式，结 果怎样？ 减少水平方向的浪费 仍然存在垂直方向的浪费 A Coarse-Grain Multithreaded architecture has the ability to switch between threads with only a short hardware context switch latency < 10 cycles 2018/11/16 计算机体系结构 240 240

241 Fine-Grain Multithreading
Issue width Fine-Grained 细粒度多线程 多个线程的指令交叉执行 如果基于细粒度的时钟周期交 叉运行模式，结果怎样？ 减少垂直方向的浪费 仍然存在水平方向的浪费 Instruction issue Time 2018/11/16 计算机体系结构

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

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

244 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/11/16 计算机体系结构 244 244

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

246 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/11/16 计算机体系结构 246 246

247 Performance 2018/11/16 计算机体系结构

248 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/11/16 计算机体系结构 248 248

249 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/11/16 计算机体系结构 249 249

250 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/11/16 计算机体系结构 250 250

251 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/11/16 计算机体系结构 251 251

252 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/11/16 计算机体系结构 252 252

253 Coarse-Grain Multithreading
Tera MTA 适用于大规模数据集并且数据本地性较低 的应用 没有数据Cache 需要大量的并行线程以隐藏存储器访问延迟 其他数据本地性较好的应用 如果Cache命中，流水线上的停顿较少 仅需要添加较少的线程来隐藏偶尔Cache失效导致的延迟 Cache失效时，将该线程换出 当某一线程的执行存在长延迟操作时，选择另一线 程执行，并切换线程上下文 Tera 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/11/16 计算机体系结构 253 253

254 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/11/16 计算机体系结构 254 254

255 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/11/16 计算机体系结构 255 255

256 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/11/16 计算机体系结构 256

257 Oracle/Sun Niagara-3, “Rainbow Falls” 2009
2018/11/16 计算机体系结构 257

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

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

260 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/11/16 计算机体系结构 260 260

261 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 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/11/16 计算机体系结构 261 261

262 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/11/16 计算机体系结构 262 262

263 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 and 1.41 Most gained some Fl.Pt. apps had most cache conflicts and least gains 2018/11/16 计算机体系结构 263 263

264 Upper Limit to ILP: Ideal Machine
FP: Integer: IPC 2018/11/16 计算机体系结构 264

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

266 More Realistic HW: Register Impact (rename regs)
FP: Change instr window, 64 instr issue, 8K 2 level Prediction Integer: IPC Infinite 256 128 64 32 None 2018/11/16 计算机体系结构 266

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

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