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

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

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

2 3.1流水线的基本概念 3.2 MIPS基本流水线 3.3 MIPS中多周期操作的处理 3.4 MIPS R4000流水线
第三章 流水线技术 3.1流水线的基本概念 3.2 MIPS基本流水线 3.3 MIPS中多周期操作的处理 3.4 MIPS R4000流水线 中国科学技术大学

3 流水线的基本概念 一个任务可以分解为k 个子任务 流水线执行模式是重叠执行模式 K个子任务在 K 个不同阶段（使用不同的资源）运行
每个子任务执行需要1个单位时间 整个任务的执行时间为 K倍单位时间 流水线执行模式是重叠执行模式 K个流水段并行执行K个不同任务 每个单位时间进入/离开流水线一个任务 中国科学技术大学

4 同步流水线 流水段之间采用时钟控制的寄存器文件（clocked registers) 时钟上升沿到达时… 流水段是组合逻辑电路
所有寄存器同时保存前一流水段的结果 流水段是组合逻辑电路 流水线设计中希望各段相对平衡 即所有段的延迟时间大致相等 时钟周期取决于延迟最长的流水段 中国科学技术大学

5 流水线的性能 设 = time delay in stage Si 时钟周期 = max( ) 为最长的流水段延迟
时钟频率 f = 1/ = 1/max( ) 流水线可以在k+n-1个时钟周期内完成n个任务 完成第一个任务需要 k个时钟周期 其他n-1个任务需要n-1个时钟周期完成 K-段流水线的理想加速比（相对于串行执行） 中国科学技术大学

6 简单的5段流水线 5个流水段，每段的延迟为1个cycle IF: 取值阶段 ID: 译码阶段 EX: 执行
选择地址：下一条指令地址、转移地址 ID: 译码阶段 确定控制信号 并从寄存器文件中读取寄存器值 EX: 执行 Load 、Store：计算有效地址 Branch：计算转移地址并确定转移方向 MEM: 存储器访问（仅Load和Store) WB: 结果写回 中国科学技术大学

7 流水线的可视化表示 多条指令执行多个时钟周期 指令按程序序从上到下排列 图中展示了每一时钟周期资源的使用情况 不同指令相邻阶段之间没有干扰
中国科学技术大学

8 03/19-review 编译技术与计算机体系结构设计 MIPS指令集 有利于编译器的ISA： 规整性、正交性、完整性
帮助编译器设计者了解各种代码序列的执行效率和代价，有助于编译器的优化 对于在编译时就已经可确定的量，提供能够将其变为常数的指令 寄存器分配是关键问题 寄存器数目多有利于编译器的设计与实现 提供至少16个通用寄存器和独立的浮点寄存器 保证所有的寻址方式可用于各种数据传送指令 最小指令集 MIPS指令集 2018/11/14 中国科学技术大学

9 03/19-review (MIPS) Use general purpose registers with a load-store architecture: YES Provide at least 16 general purpose registers plus separate floating-point registers: 31 GPR & 32 FPR Support basic addressing modes: displacement (with an address offset size of 12 to 16 bits), immediate (size 8 to 16 bits), and register deferred; : YES: 16 bits for immediate, displacement (disp=0 => register deferred) All addressing modes apply to all data transfer instructions : YES Use fixed instruction encoding if interested in performance and use variable instruction encoding if interested in code size : Fixed Support these data sizes and types: 8-bit, 16-bit, 32-bit integers and 32-bit and 64-bit IEEE 754 floating point numbers: YES Support these simple instructions, since they will dominate the number of instructions executed: load, store, add, subtract, move register-register, and, shift, compare equal, compare not equal, branch (with a PC-relative address at least 8-bits long), jump, call, and return: YES, 16b Aim for a minimalist instruction set: YES 2018/11/14 中国科学技术大学

10 03/19-review 流水线技术要点 流水线技术并不能提高单个任务的执行效率，它可以提高整个系统的吞吐率 流水线中的瓶颈——最慢的那一段
多个任务同时执行，但使用不同的资源 其潜在的加速比＝流水线的级数 流水段所需时间不均衡将降低加速比 流水线存在装入时间和排空时间，使得加速比降低 由于存在相关问题，会导致流水线停顿 中国科学技术大学

11 指令流时序 时序图展示： 每个时钟周期指令所使用的流水段情况 指令流在采用5段流水线执行模式的执行情况 中国科学技术大学

12 单周期、多周期、流水线控制性能比较 假设5段指令执行流水线 某一程序段假设： 比较三种执行模式的性能
20% load, 10% store, 40% ALU, and 30% branch 比较三种执行模式的性能 中国科学技术大学

13 流水线的性能分析 基本度量参数：吞吐率，加速比，效率 吞吐率：在单位时间内流水线所完成的任务数量或输 出结果的数量。 n：任务数
Tk：处理完成n个任务所用的时间 中国科学技术大学

14 流水线技术提高系统的任务吞吐率 1. 各段时间均相等的流水线 各段时间均相等的流水线时空图 中国科学技术大学

15 吞吐率 流水线完成n个连续任务所需要的总时间为 Tk＝kΔt＋(n-1)Δt＝(k＋n-1)Δt 流水线的实际吞吐率
最大吞吐率:流水线在连续流动达到稳定状态后所得到的吞吐率。 S4 1 2 3 4 5 .. n-1 n S3 S2 S1 中国科学技术大学

16 TP与Tpmax的关系 最大吞吐率与实际吞吐率的关系
流水线的实际吞吐率小于最大吞吐率，它除了与每个段的时间有关外，还与流水线的段数k以及输入到流水线中的任务数n等有关。 只有当n>>k时，才有TP≈TPmax。 中国科学技术大学

17 流水线中的瓶颈——最慢的段 2. 各段时间不完全相等的流水线 各段时间不等的流水线及其时空图 一条4段的流水线
S1，S3，S4各段的时间：Δt S2的时间：3Δt （瓶颈段） 流水线中这种时间最长的段称为流水线的瓶颈段。 中国科学技术大学

18 中国科学技术大学

19 各段时间不等的流水线的实际吞吐率： （ Δti为第i段的时间，共有k个段 ） 流水线的最大吞吐率为 中国科学技术大学

20 例如：一条4段的流水线中，S1，S2，S4各段的 时间都是Δt，唯有S3的时间是3Δt。
最大吞吐率为 中国科学技术大学

21 解决流水线瓶颈问题的常用方法 改进后的流水线的吞吐率 ： 细分瓶颈段 例如：对前面的4段流水线
把瓶颈段S3细分为3个子流水线段：S3a，S3b，S3c 改进后的流水线的吞吐率 ： 中国科学技术大学

22 缺点：控制逻辑比较复杂，所需的硬件增加了。 例如：对前面的4段流水线 重复设置瓶颈段S3：S3a，S3b，S3c
中国科学技术大学

23 重复设置瓶颈段后的时空图 中国科学技术大学

24 加速比 加速比：完成同样一批任务，不使用流水线所用的时间 与使用流水线所用的时间之比。
假设：不使用流水线（即顺序执行）所用的间为Ts，使用流水线后所用的时间为Tk，则该流水线的加速比为 中国科学技术大学

25 1. 流水线各段时间相等（都是△t） 一条k段流水线完成n个连续任务 所需要的时间为 Tk = (k＋n-1)Δt 顺序执行n个任务
所需要的时间： Ts= nk△t 流水线的实际加速比为 中国科学技术大学

26 最大加速比 当n>>k时，S ≈ k 思考：流水线的段数愈多愈好？ 中国科学技术大学

27 流水线的各段时间不完全相等时 一条k段流水线完成n个连续任务的实际加速比为 中国科学技术大学

28 效率 效率：流水线中的设备实际使用时间与整个运行时间 的比值，即流水线设备的利用率。 各段时间相等
由于流水线有通过时间和排空时间，所以在连续 完成n个任务的时间内，各段并不是满负荷地工作。 各段时间相等 各段的效率ei相同 中国科学技术大学

29 整条流水线的效率为 可以写成 最高效率为 当n>>k时，E≈1。 中国科学技术大学

30 当流水线各段时间相等时，流水线的效率与吞吐率成正比。 E=TP△t
流水线的效率是流水线的实际加速比S与它的最大加速 比k的比值。 当E=1时，S=k，实际加速比达到最大。 中国科学技术大学

31 从时空图上看，效率就是n个任务占用的时空面积和 k个段总的时空面积之比。
当各段时间不相等时 中国科学技术大学

32 实际吞吐率：假设k段，完成n个任务，单位时间所实际完成的任务数。 加速比: k段流水线的速度与等功能的非流水线的速度之比。
Summary 实际吞吐率：假设k段，完成n个任务，单位时间所实际完成的任务数。 加速比: k段流水线的速度与等功能的非流水线的速度之比。 效率：流水线的设备利用率。 中国科学技术大学

33 中国科学技术大学

34 -Review: Pipelining 指令流水线通过指令重叠减小 CPI 充分利用数据通路 如何有利于流水线技术的应用
当前指令执行时，启动下一条指令 其性能受限于花费时间最长的段 检测和消除相关 如何有利于流水线技术的应用 所有的指令都等长 只有很少的指令格式 只用Load/Store来进行存储器访问 中国科学技术大学

35 3.2 MIPS的基本流水线 指令流水线：CPU执行大量的指令，指令吞吐率非常重要 MIPS 的指令格式 所有指令相同长度
Op 5 31 16 15 11 10 6 rs rt immediate offset added to PC rd Register-Register (R-type) ADD R1, R2, R3 26 25 21 20 Register-Immediate (I-type) SUB R1, R2, #3 Jump / Call (J-type) JUMP end func (jump, jump and link, trap and return from exception) 6 所有指令相同长度 在指令格式中寄存器位于同一位置 只有Loads和Stores可以对存储器操作 中国科学技术大学

36 MIPS数据通路 中国科学技术大学

37 1 编译器与ISA 2 MIPS指令集 3 Pipeline (基本模型）由串行执行到重叠执行 中国科学技术大学

38 MIPS数据通路 中国科学技术大学

39 改进后流水线的分支操作 中国科学技术大学

40 3.2.1 流水线的相关 相关的基本概念 结构相关 数据相关 控制相关 中国科学技术大学

41 采用流水线技术带来的新问题 流水线相关 使用等待策略总是可以解决相关 结构相关：同一时间两种方式使用同一资源
例如 washer/dryer 合在一起， IM和ID合在一起 控制相关: 试图在条件未评估之前，就做决定 例如 branch instructions 数据相关：在数据未准备好之前，就需要使用数据 当前指令的执行需要上一条指令的结果 使用等待策略总是可以解决相关 流水线控制必须能检测相关，否则由软件设计来避免 采用相应操作解决相关 (or 等待) 中国科学技术大学

42 单个存储器引起的结构相关 Load Instr 1 Instr 2 Instr 3 Instr 4 Time (clock cycles)
ALU I n s t r. O r d e Load Mem Reg Mem Reg ALU Mem Reg Instr 1 ALU Mem Reg Instr 2 ALU Instr 3 Mem Reg Mem Reg ALU Mem Reg Instr 4 Detection is easy in this case! (right half highlight means read, left half write) 中国科学技术大学

43 消除结构相关 Load Instr 1 Instr 2 Stall Instr 3 Time (clock cycles) I n s t
Reg ALU DMem Ifetch Cycle 1 Cycle 2 Cycle 3 Cycle 4 Cycle 6 Cycle 7 Cycle 5 Bubble 中国科学技术大学

44 结构相关对性能的影响 例如: 如果每条指令平均访存1.3 次，而每个时钟周期只能访存一次，那么
在其他资源100％利用的前提下，平均 CPI  1.3 中国科学技术大学

45 For simple RISC pipeline, CPI = 1:
流水线的加速比计算 For simple RISC pipeline, CPI = 1: 中国科学技术大学

46 例如： Dual-port vs. Single-port
机器A: Dual ported memory (“Harvard Architecture”) 机器B: Single ported memory 存在结构相关的机器B的时钟频率是机器A的时钟频率的1.05倍 Ideal CPI = 1 在机器B中load指令会引起结构相关，所执行的指令中Loads指令占 40% Average instruction time = CPI * Clock cycle time 无结构相关的机器A： Average Instruction time = Clock cycle time 存在结构相关的机器B： Average Instruction time = (1+0.4*1) * clock cycle time /1.05 = 1.3 * clock cycle time 中国科学技术大学

47 数据相关问题 add r1,r2,r3 sub r4,r1,r3 and r6,r1,r7 or r8,r1,r9
Time (clock cycles) IF ID/RF EX MEM WB I n s t r. O r d e add r1,r2,r3 sub r4,r1,r3 and r6,r1,r7 or r8,r1,r9 xor r10,r1,r11 Reg ALU DMem Ifetch 中国科学技术大学

48 三种基本的数据相关 写后读相关(Read After Write (RAW)) InstrJ tries to read operand before InstrI writes it 由于实际的数据交换需求而引起的 I: add r1,r2,r3 J: sub r4,r1,r3 中国科学技术大学

49 I: sub r4,r1,r3 J: add r1,r2,r3 K: mul r6,r1,r7
读后写相关Write After Read (WAR) InstrJ writes operand before InstrI reads it 编译器编写者称之为“anti-dependence”（反相关），是由于重复使用寄存器名“r1”引起的. DLX(MIPS) 5 段基本流水线不会有此类相关因为: 所有的指令都是5段, 并且 读操作总是在第2段，而 写操作在第5段 I: sub r4,r1,r3 J: add r1,r2,r3 K: mul r6,r1,r7 中国科学技术大学

50 编译器编写者称之为“output dependence” ，也是由于重复使用寄存器名 “r1”引起的.
写后写相关（Write After Write (WAW)） InstrJ writes operand before InstrI writes it. 编译器编写者称之为“output dependence” ，也是由于重复使用寄存器名 “r1”引起的. 在DLX(MIPS) 5段基本流水线中，也不会发生。因为 所有指令都是5段，并且写操作都在第5段 在后面的复杂的流水线中我们将会看到 WAR 和WAW 相关 I: sub r1,r4,r3 J: add r1,r2,r3 K: mul r6,r1,r7 中国科学技术大学

51 03/21-Review：流水线性能分析 吞吐率、加速比、效率之间的关系 流水线技术应用的难度何在? ：相关问题 相关的类型：
流水线技术应用的难度何在? ：相关问题 相关的类型： 结构相关，控制相关，以及 数据相关（RAW, WAR, WAW） 中国科学技术大学

52 03/21-Review: MIPS的基本流水线 指令流水线：CPU执行大量的指令，指令吞吐率非常重要 MIPS 的ISA：RISC
中国科学技术大学

53 03/21-Review 相关的种类 相关会影响流水线性能 结构相关: 由于争用资源而引起的 控制相关：由于控制类指令引起的
解决办法: 等待 增加（或拆分）资源 控制相关：由于控制类指令引起的 减少性能损失的基本方法：冻结或排空流水线，预测分支成功；预测分支失败；延迟转移 数据相关：两条指令访问相同的数据而引起的 类型： RAW WAR， WAW 解决办法： 硬件：定向技术（forwarding) 软件：指令级调度 中国科学技术大学

54 采用定向技术避免数据相关 add r1,r2,r3 sub r4,r1,r3 and r6,r1,r7 or r8,r1,r9
Time (clock cycles) I n s t r. O r d e add r1,r2,r3 sub r4,r1,r3 and r6,r1,r7 or r8,r1,r9 xor r10,r1,r11 Reg ALU DMem Ifetch 中国科学技术大学

55 采用定向技术硬件所需做的修改 MEM/WR ID/EX EX/MEM Data Memory mux Registers NextPC
ALU mux Registers NextPC Immediate 中国科学技术大学

56 定向源为R-R ALU操作的定向比较判断 中国科学技术大学

57 定向源为ALU－imm操作的定向比较判断
中国科学技术大学

58 定向源为Load操作的比较判定 中国科学技术大学

59 采用定向技术仍然存在相关 lw r1, 0(r2) sub r4,r1,r6 and r6,r1,r7 or r8,r1,r9
Time (clock cycles) Reg ALU DMem Ifetch I n s t r. O r d e lw r1, 0(r2) sub r4,r1,r6 and r6,r1,r7 or r8,r1,r9 中国科学技术大学

60 lw r1, 0(r2) sub r4,r1,r6 and r6,r1,r7 or r8,r1,r9 Time (clock cycles)
Reg ALU DMem Ifetch Bubble DMem 中国科学技术大学

61 采用软件方法避免数据相关 Try producing fast code for a = b + c; d = e – f;
assuming a, b, c, d ,e, and f in memory. Slow code: LW Rb,b LW Rc,c ADD Ra,Rb,Rc SW a,Ra LW Re,e LW Rf,f SUB Rd,Re,Rf SW d,Rd Fast code: LW Rb,b LW Rc,c LW Re,e ADD Ra,Rb,Rc LW Rf,f SW a,Ra SUB Rd,Re,Rf SW d,Rd 中国科学技术大学

62 控制冲突 执行分支指令的结果有两种 分支需要解决两个问题 处理分支指令最简单的方法： 分支成功：PC值改变为分支转移的目标地址。
分支目标地址（转移成功意谓着PC值不是 PC+4） CC是否有效，这两点在MIPS中都在流水线的靠后段中确定 处理分支指令最简单的方法： “冻结”或者“排空”流水线 。 优点：简单。 中国科学技术大学

63 回顾MIPS初始数据通路 中国科学技术大学

64 简单处理分支指令：分支成功的情况 简单处理分支指令：分支失败的情况 分支指令 IF ID EX MEM WB 分支目标指令 stall
分支目标指令+1 分支目标指令+2 分支目标指令+3 简单处理分支指令：分支失败的情况 分支指令 IF ID EX MEM WB 分支后继指令 stall 分支后继指令+1 分支后继指令+2 分支后继指令+3 中国科学技术大学

65 减少分支延时的方法 硬件的方法 软件（通过编译器）的方法： 修改数据通路：使得目标地址和分支条件尽早确定，其中之一尽早确定是没有用的
判断是否为0可以在ID段确定 使用另一个加法器计算 可以在ID段计算BTA(分支目标地址)，即在ID段形成下一条指令地址，两种可能（BTA, PC+4)，选择哪一个取决于ID段确定的CC 必要时使用互锁机制来插入Stall• 设计合适的ISA e.g. BNEZ, BEQZ on MIPS 使得CC可以在ID段确定 软件（通过编译器）的方法： 调度一些指令放入分支的延迟槽中 预测的方法：统计分支成功和失败的情况，提高预测精度 中国科学技术大学

66 新的MIPS数据通路 中国科学技术大学

67 改进后流水线的分支操作 中国科学技术大学

68 四种可能的解决控制相关的方法 #1: Stall 直到分支方向确定 #2: 预测分支失败 #3: 预测分支成功
直接执行后继指令 如果分支实际情况为分支成功，则撤销流水线中的指令对流水线状态的更新 MIPS分支指令平均47%为分支失败 要保证：分支结果出来之前不会改变处理机的状态，以便一旦猜错时，处理机能够回退到原先的状态。 #3: 预测分支成功 前提：先知道分支目标地址，后知道分支是否 成功。 平均53% MIPS分支为分支成功 MIPS分支目标地址在ID段才能计算出目标地址 MIPS 还是有1个 cycle 的分支延迟 中国科学技术大学

69 延迟转移 #4: 延迟转移 主要思想： 从逻辑上“延长”分支指令的执行时间。把延迟分支看成是由原来的分支指令和若干个延迟槽构成，不管分支是否成功，都要按顺序执行延迟槽中的指令。 定义分支发生在一系列指令之后 branch instruction sequential successor1 sequential successor sequential successorn branch target if taken 5级流水只需要一个延迟槽就可以确定目标地址和确定条件 MIPS 使用这种方式 Branch delay of length n 中国科学技术大学

70 具有一个分支延迟槽的流水线的执行过程 分 支 失 败 分支指令i IF ID EX MEM WB 延迟槽指令 i+1 指令 i+2
成 功 分支指令i IF ID EX MEM WB 延迟槽指令 i+1 分支目标指令j 分支目标指令j+1 分支目标指令j+2 分支延迟槽中的指令“掩盖”了流水线原来必须插入的暂停周期。 中国科学技术大学

71 延迟转移 从何处选择指令来填充延迟槽？ 编译器可以有效的调度一个延迟槽 分支指令之前的指令：最好
从分支目标地址处取: 在分支成功可能性大时，这种策略较好 从分支失败处调度：仅在分支失败时 编译器可以有效的调度一个延迟槽 如果提供取消分支时， 编译器可以调度更多的指令填入延迟槽 中国科学技术大学

72 调度前和调度后的代码 中国科学技术大学

73 三种方法的要求及效果 调 度 策 略 对调度的要求 什么情况下起作用 从 前 调 度 被调度的指令必须与分支无关 任何情况
必须保证在分支失败时执行被调度 的指令不会导致错误。有可能需要 复制指令 分支成功时 (但由于复制指令，有 可能会增大程序空间) 从目标处调度 必须保证在分支成功时执行被调度 的指令不会导致错误 从失败处调度 分支失败时 中国科学技术大学

74 分支取消机制 分支延迟受到两个方面的限制： 进一步改进：分支取消机制 可以被放入延迟槽中的指令要满足一定的条件。
编译器预测分支转移方向的能力。 进一步改进：分支取消机制 当分支的实际执行方向和事先所预测的一样时执行分支延迟槽中的指令，否则就将分支延迟槽中的指令转化成一个空操作。 中国科学技术大学

75 分支取消机制示意 分 支 失 败 分支指令i IF ID EX MEM WB 延迟槽指令 i+1 idle 指令 i+2 指令 i+3
成 功 分支指令i IF ID EX MEM WB 延迟槽指令 i+1 分支目标指令j 分支目标指令j+1 分支目标指令j+2 预测分支成功的情况下，分支取消机制的执行情况 中国科学技术大学

76 评估减少分支策略的效果 1.14 = 1 + 1*14%*100% 1.09 = 1+1*14%*65% 1.07 = 1+ 0.5*14%
Scheduling Branch CPI speedup v. speedup v. scheme penalty unpipelined stall Stall pipeline Predict taken Predict not taken Delayed branch 1.14 = 1 + 1*14%*100% 1.09 = 1+1*14%*65% 1.07 = *14% Conditional & Unconditional = 14%, 65% change PC 中国科学技术大学

77 3.2.2 异常处理 流水线使得系统的吞吐率提高 问题:由于相关会影响系统性能的发挥 另一问题：异常 Why？ 采用何种策略取决于异常的类型
多级流水－》多周期指令 异常可以发生在任何地方 指令序与异常序可能不同 必须按指令序处理异常 采用何种策略取决于异常的类型 中国科学技术大学

78 异常的类型 I/O 设备请求 用户程序调用OS服务 断点 整数或浮点数运算溢出 缺页 非对齐存储器访问 存储器保护冲突 未定义的指令
硬件失效 – 例如： parity or ECC error 电源故障 中国科学技术大学

79 异常的分类 Synchronous vs. Asynchronous User requested vs. Coerced
synchronous caused by a particular instruction asynchronous - external devices and HW failures User requested vs. Coerced requested is predictable and can happen after the instruction User maskable vs. user non-maskable e.g. arithmetic overflow on some machines is user maskable Within vs. Between instructions within ==> synchronous, key is that completion is prevented some asynchronous are also within Resume vs. Terminate program implications for how much state must be preserved 中国科学技术大学

80 例如 中国科学技术大学

81 最困难的问题 异常发生在指令中(within)，并且要求恢复执行(resume) 要求==>流水线必须安全地 shut down
PC必须保存 如果重新开始的是一条分支指令，它需要重新执行，这意味着条件码状态必须没有改变 在MIPS中的处理步骤 强制trap指令在下一个IF段进入流水线 封锁引起故障的指令的所有写操作和流水线中后继指令的写操作 让所有前序指令执行完（如果能） 保存重新执行时的地址（PC） PC 或 PC + 1 调用OS处理异常 中国科学技术大学

82 异常处理后，缺省的恢复点是第一条延迟指令 不会有Branch指令 因此需要保存的PC值不止一个，根据具体情况进行恢复
考虑延迟转移时，假设有两个延迟槽的分支 I Branch Instr1 I+1 Delay instr1 I+2 Delay Instr2 I+3 inst I+4 inst 假设branch指令是好的 第1个延迟指令引起缺页中断 第2条指令封锁 异常处理后，缺省的恢复点是第一条延迟指令 不会有Branch指令 因此需要保存的PC值不止一个，根据具体情况进行恢复 中国科学技术大学

83 精确中断与非精确中断 精确中断 在有些机器上，浮点数异常 精确中断对整数流水线而言，不是太难实现
如果流水线可以控制使得引起异常的指令前序指令都执行完，故障后的指令可以重新执行，则称该流水线支持精确中断 按照指令的逻辑序处理异常 理想情况，引起故障的指令没有改变机器的状态 要正确的处理这类异常请求，必须保证故障指令不产生副作用 在有些机器上，浮点数异常 流水线段数多，在发现故障前，故障点后的指令就已经写了结果，在这种情况下，必须有办法处理。 很多高性能计算机，Alpha 21164，MIPS R10000等支持精确中断，但精确模式要慢10+倍，一般用在代码调试时，很多系统要求精确中断模式，如IEEE FP标准处理程序，虚拟存储器等。 精确中断对整数流水线而言，不是太难实现 指令执行的中途改变机器的状态 例如IA-32 的自动增量寻址模式 中国科学技术大学

84 MIPS中的异常 IF page fault, misaligned address, memory protection violation ID undefined or illegal opcode EX arithmetic exception MEM WB none 中国科学技术大学

85 3.3 MIPS中多周期操作的处理 问题 在1到2个cycles时间内完成的处理方法 现假设FP指令与整数指令采用相同的流水线，那么
在DLX(MIPS)中如何处理 在1到2个cycles时间内完成的处理方法 采用较慢的时钟源，或 在FP部件中延迟其EX段 现假设FP指令与整数指令采用相同的流水线，那么 EX 段需要循环多次来完成FP操作，循环次数取决于操作类型 有多个FP功能部件，如果发射出的指令导致结构或数据相关，需暂停 中国科学技术大学

86 对MIPS的扩充 四个功能部件 Integer 部件处理：Loads, Store, Integer ALU操作和Branch
FP/Integer 乘法部件：处理浮点数和整数乘法 FP加法器：处理FP加，减和类型转换 FP/Integer除法部件：处理浮点数和整数除法 这些功能部件未流水化 中国科学技术大学

87 扩展的MIPS流水线 中国科学技术大学

88 Latency & Repeat Interval
定义1：完成某一操作所需的cycle数 定义2：使用当前指令所产生结果的指令与当前指令间的最小间隔周期数 循环间隔（Repeat/Initiation interval） 发射相同类型的操作所需的间隔周期数 对于EX部件流水化的新的MIPS Function Unit Latency Repeat Interval Integer ALU 1 Data Memory (Integer and FP loads(1 less for store latency)) FP Add 3 FP multiply 6 FP Divide (also integer divide and FP sqrt) 24 25 中国科学技术大学

89 将部分执行部件流水化后的MIPS流水线 中国科学技术大学

90 新的相关和定向问题 结构冲突增多 在一个周期内可能有多个寄存器写操作 可能指令乱序完成（乱序到达WB段）有可能存在WAW
非流水的Divide部件，使得EX段增长24个cycles 在一个周期内可能有多个寄存器写操作 可能指令乱序完成（乱序到达WB段）有可能存在WAW 由于在ID段读，还不会有 WAR 相关 乱序完成导致异常处理复杂 由于指令的延迟加大导致RAW 相关的stall数增多 需要付出更多的代价来增加定向路径 中国科学技术大学

91 新的结构相关 纵向检查指令所使用的资源 第10个cycle，三条指令同时进入MEM，但由于MULTD和ADDD在MEM段没有实际动作，这种情况没有关系 第11个cycle，三条指令同时进入WB段，存在结构相关 中国科学技术大学

92 解决方法 Option 1 Option 2 在ID段跟踪写端口的使用情况，以便能暂停该指令的发射 一旦发现冲突，暂停当前指令的发射
在进入MEM或WB段时，暂停冲突的指令，让有较长延时的指令先做，因为较长延时的指令，可能会更容易引起其他RAW相关，从而导致更多的stalls 中国科学技术大学

93 关于数据相关 S.D 多延迟一个cycle，以消解与ADD.D的冲突 中国科学技术大学

94 新的冲突源 GPR与FPR间的数据传送造成的数据相关 如果在ID段进行相关检测，指令发射前须做如下检测：
MOVI2FP and MOVFP2I instructions 如果在ID段进行相关检测，指令发射前须做如下检测： 结构相关 循环间隔检测 确定寄存器写端口是否可用 RAW相关 列表所有待写的目的寄存器 不发射以待写寄存器做为源寄存器的指令，插入latency个stall WAW相关 仍然使用上述待写寄存器列表 不发射那些目的寄存器与待写寄存器列表中的指令有WAW冲突的指令，延迟1个cycle发射。 中国科学技术大学

95 精确中断与长流水线 例如 DIVF F0,F2,F4 ADDF F10,F10,F8 SUBF F12,F12,F14
ADDF 和SUBF都在DIVF前完成 如果DIVF导致异常，会如何？ 非精确中断 Ideas??? 中国科学技术大学

96 处理中断4种可能的办法 方法1：忽略这种问题，当非精确处理 方法2：缓存操作结果，直到早期发射的指令执行完。
原来的supercomputer的方法 但现代计算机对IEEE 浮点标准的异常处理，虚拟存储的异常处理要求必须是精确中断。 方法2：缓存操作结果，直到早期发射的指令执行完。 当指令运行时间较长时，Buffer区较大 Future file (Power PC620 MIPS R10000) 缓存执行结果，按指令序确认 history file (CYBER 180/990) 尽快确认 缓存区存放原来的操作数，如果异常发生，回卷到合适的状态 中国科学技术大学

97 第3 & 4种方法 以非精确方式处理，用软件来修正 暂停发射，直到确定先前的指令都可无异常的完成，再发射下面的指令。
为软件修正保存足够的状态 让软件仿真尚未执行完的指令的执行 例如 Instruction 1 – A 执行时间较长，引起中断的指令 Instruction 2, instruction 3, ….instruction n-1 未执行完的指令 Instruction n 已执行完的指令 由于第n条指令已执行完，希望中断返回后从第n+1条指令开始执行，如果我们保存所有的流水线的PC值，那么软件可以仿真Instruction1 到Instruction n-1 的执行 暂停发射，直到确定先前的指令都可无异常的完成，再发射下面的指令。 在EX段的前期确认（MIPS流水线在前三个周期中） MIPS R2K to R4K 以及Pentium使用这种方法 中国科学技术大学

98 MIPS流水线的性能 Except for the divide structural hazards, these data do not depend on the frequency of an operation, only on its latency and the number of cycles before the result is used. The number of stalls from RAW hazards roughly tracks the latency of the FP unit. For example, the average number of stalls per FP add, subtract, or convert is 1.7 cycles, or 56% of the latency (3 cycles). Likewise, the average number of stalls for multiplies and divides are 2.8 and 14.2, respectively, or 46% and 59% of the corresponding latency. Structural hazards for divides are rare, since the divide frequency is low. Stalls per FP operation for each major type of FP operation for the SPEC89 FP benchmarks 中国科学技术大学

99 平均每条指令的stall数 The total number of stalls per instruction ranges from 0.65 for su2cor to 1.21 for doduc, with an average of FP result stalls dominate in all cases, with an average of 0.71 stalls per instruction, or 82% of the stalled cycles. Compares generate an average of 0.1 stalls per instruction and are the second largest source. The divide structural hazard is only significant for doduc. The stalls occurring for the MIPS FP pipeline for five for the SPEC89 FP benchmarks. 中国科学技术大学

100 MIPS R4000 实际的 64-bit 机器 主频100MHz ~200MHz
较深的流水线（级数较多）(有时也称为 superpipelining) 指令集与DLX非常类似 中国科学技术大学

101 MIPS R4000的8 级整数流水线 IF–取指阶段前半部分；选择PC值，初始化指令cache的访问
IS–取指阶段后半部分，主要完成访问指令cache的操作 RF–指令译码，寄存器读取，相关检测以及指令cache命中检测 EX–执行，包括：计算有效地址，进行ALU操作，计算分支目标地址和检测分支条件 DF–取数据，访问数据cache的前半部分 DS–访问数据cache的后半部分 TC–tag 检测，确定数据cache是否命中 WB–Load操作和R-R操作的结果写回 中国科学技术大学

102 在使用定向技术的情况下，Load 延迟为2个cycles
需注意的问题 在使用定向技术的情况下，Load 延迟为2个cycles Load和与其相关的指令间必须有2条指令或两个bubbles 原因：load的结果在DS结束时可用 分支延迟3个cycles 分支与目标指令间需要3条指令或3个bubbles 原因：目标地址在EX段后才能知道 R4000的流水线中，到ALU输入端有四个定向源 EX/DF, DF/DS, DS/ TC, TC/WB 中国科学技术大学

103 图示 IF IS RF EX DF DS TC WB TWO Cycle Load Latency THREE Cycle
Branch Latency (conditions evaluated during EX phase) Delay slot plus two stalls Branch likely cancels delay slot if not taken 中国科学技术大学

104 -review 影响流水线性能 异常处理 支持浮点数操作的MIPS流水线 结构相关、数据相关 控制相关、异常 种类与分类 精确与非精确中断
Latency & Repeat Interval 问题：结构相关（增多）；数据相关、控制相关引起的stall增多；有新的冲突源产生；定向路径增多；异常处理复杂 MIPS R4000 8级流水线 存储器操作分阶段 – load延迟为2个cycles Branch操作在EX段确定分支方向- 3个cycles的延迟 多个定向源 ：EX/DF，DF/DS，DS/TC，TC/WB MIPS R4000的浮点数操作 中国科学技术大学

105 ALU输入端的定向源 中国科学技术大学

106 MIPS R4000 浮点数操作 3个功能部件组成：FP Adder, FP Multiplier, FP Divider
FP操作需要2（negate）-112个（square root）cycles 8 种类型的FP units: Stage Functional unit Description A FP adder Mantissa ADD stage D FP divider Divide pipeline stage E FP multiplier Exception test stage M FP multiplier First stage of multiplier N FP multiplier Second stage of multiplier R FP adder Rounding stage S FP adder Operand shift stage U Unpack FP numbers 中国科学技术大学

107 中国科学技术大学

108 双精度浮点数操作延迟及初始化间隔 浮点指令 延 迟 初始化 间隔 使用的流水段 加、减 4 3 U,S+A,A+R,R+S 乘 8
U,E+M,M,M,M,N,N+A,R 除 36 35 U,A,R,D28,D+A,D+R,D+A,D+R,A,R 求平方根 112 111 U,E,(A+R) 108,A,R 取反 2 1 U,S 求绝对值 浮点比较 U,A,R 中国科学技术大学

109 MIPS FP 流水段 Stages: M First stage of multiplier
FP Instr … Add, Subtract U S+A A+R R+S Multiply U E+M M M M N N+A R Divide U A R D28 … D+A，D+R, D+R, D+A, D+R, A, R Square root U E (A+R)108 … AR Negate U S Absolute value U S FP compare U A R Stages: M First stage of multiplier N Second stage of multiplier R Rounding stage S Operand shift stage U Unpack FP numbers A Mantissa ADD stage D Divide pipeline stage E Exception test stage 中国科学技术大学

110 中国科学技术大学

111 中国科学技术大学

112 中国科学技术大学

113 中国科学技术大学

114 R4000性能（1） 中国科学技术大学

115 R4000 性能（2） FP result stall because of FP RAW Hazards for an FP operand 中国科学技术大学

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

117 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、CS61C KFUPM material derived from course COE501、COE502 中国科学技术大学

118 Review 流水线技术并不能提高单个任务的执行效率，它可以提高整个系统的吞吐率 流水线性能分析：吞吐率、加速比、效率
多个任务同时执行，但使用不同的资源 流水线性能分析：吞吐率、加速比、效率 流水线中的瓶颈——最慢的那一段 其潜在的加速比＝流水线的级数 流水段所需时间不均衡将降低加速比 流水线存在装入时间和排空时间，使得加速比降低 由于存在相关问题，会导致流水线停顿 结构相关、数据相关和控制相关 中国科学技术大学

119 Quiz 流水线的成本（cost）可以用c+k*h估算，其中 c为所有功能段本身的总成本，h为段间锁存器成本，k为段数。流水线的性价比可以定义为 PCR = Throughput/(c+k*h), 其中Throughput = 1/t, t为t_{latch}+T/k, t_{latch}为锁存器的延迟时间， T为在非流水线的机器上采用顺序执行方式完成一个任务所花费的总时间。 试推导出使得PCR最大化的最优段数k_opt的表达式。 中国科学技术大学

120 -Review lecture 流水线技术要点 流水线正常工作的基本条件 多个任务重叠（并发/并行）执行，但使用不同的资源
流水线技术提高整个系统的吞吐率，不能缩短单个任务的执行时间 其潜在的加速比＝流水线的级数 影响流水线性能的因素 流水线中的瓶颈——最慢的那一段 流水段所需时间不均衡将降低加速比 流水线存在装入时间和排空时间，使得加速比降低 由于存在相关问题，会导致流水线停顿 流水线正常工作的基本条件 增加寄存器文件保存当前段传送到下一段的数据和控制信息 存储器带宽是非流水的n倍 中国科学技术大学

121 在新的Datapath下各段的操作 IF ID EX IF/ID.IR ←Mem[PC];
IF/ID.NPC,PC ←(if ((EX/MEM.opcode == branch) & EX/MEM.cond) {EX/MEM.ALUOutput} else {PC+4}); ID ID/EX.A ←Regs[IF/ID.IR[rs]]; ID/EX.B ← Regs[IF/ID.IR[rt]]; ID/EX.NPC←IF/ID.NPC; ID/EX.IR ← IF/ID.IR; ID/EX/Imm ← sign-extend(IF/ID.IR[immediate field]); EX ALU instruction EX/MEM.IR ← ID/EX.IR; EX/MEM.ALUOutput ← ID/EX.A func ID/EX.B; or EX/MEM.ALUOoutput ← ID/EX.A op ID/EX.Imm; 中国科学技术大学

122 MEM Load or store instruction EX/MEM.IR ← ID/EX.IR
EX/MEM.ALUOutput ← ID/EX.A + ID/EX.Imm EX/MEM.B ← ID/EX.B Branch instruction EX/MEM.ALUOutput ← ID/EX.NPC + (ID/EX.Imm << 2) EX/MEM.cond ← (ID/EX.A == 0)； MEM ALU Instruction MEM/WB.IR ←EX/MEM.IR MEM/WB.ALUOutput ←EX/MEM.ALUOutput; MEM/WB.IR ←EX/MEM.IR; MEM/WB.LMD ← Mem[EX/MEM.ALUOutput]; or Mem[EX/MEM.ALUOutput] ← EX/MEM.B; （store） 中国科学技术大学

123 WB ALU instruction Regs[MEM/WB.IR[rd]] ← MEM/WB.ALUOutput; or
Regs[MEM/WB.IR[rt]] ← MEM/WB.ALUOutput; For load only Regs[MEM/WB.IR[rt]] ← MEM/WB.LMD 中国科学技术大学

124 简化的 Pipelining Time (clock cycles) I n s t r. O r d e Cycle 1 Cycle 2
Reg ALU DMem Ifetch Cycle 1 Cycle 2 Cycle 3 Cycle 4 Cycle 6 Cycle 7 Cycle 5 I n s t r. O r d e 中国科学技术大学