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

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

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

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

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

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

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

6 典型的 RISC 5段流水线 Memory EXecute Decode Fetch Registers ALU B A Data Cache PC Instruction Cache Store Imm Inst. Register Writeback This version designed for regfiles/memories with synchronous reads and writes.

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

8 Recap：流水线技术要点 流水线技术要点 流水线正常工作的基本条件 多个任务重叠（并发/并行）执行，但使用不同的资源
流水线技术提高整个系统的吞吐率，不能缩短单个任务的执行时间 其潜在的加速比＝流水线的级数 影响流水线性能的因素 流水线中的瓶颈——最慢的那一段 流水段所需时间不均衡将降低加速比 流水线存在装入时间和排空时间，使得加速比降低 由于存在相关(hazards)问题，会导致流水线停顿 Hazards 问题：流水线的执行可能会导致对资源的访问冲突，或破坏对资源的访问顺序 流水线正常工作的基本条件 增加寄存器文件保存当前段传送到下一段的数据和控制信息 需要更高的存储器带宽 4/19/2019

9 指令流时序 时序图展示： 每个时钟周期指令所使用的流水段情况 指令流在采用5段流水线执行模式的执行情况 4/19/2019

10 单周期、多周期、流水线控制性能比较 假设5段指令执行流水线 某一程序段假设： 比较三种执行模式的性能
20% load, 10% store, 40% ALU, and 30% branch 比较三种执行模式的性能 4/19/2019

11 流水线的相关（Hazards) 结构相关：流水线中一条指令可能需要另一条指令使用的资源
数据和控制相关：一条指令可能依赖于先前的指令生成的内容 数据相关：依赖先前指令产生的结果（数据）值 控制相关：依赖关系是如何确定下一条指令地址 (branches, exceptions) 处理相关的一般方法是插入bubble，导致CPI>1 (单发射理想CPI） CS252 S05

12 Pipeline CPI Examples Time Inst 1 Inst 2 Inst 3 Inst 1 Inst 2 Inst 3
Measure from when first instruction finishes to when last instruction in sequence finishes. 3 instructions finish in 3 cycles CPI = 3/3 =1 Inst 1 Inst 2 Inst 3 Inst 1 Inst 2 Inst 3 Bubble 3 instructions finish in 4 cycles CPI = 4/3 = 1.33 Inst 1 Inst 2 Inst 3 Bubble 1 Bubble 2 3 instructions finish in 5cycles CPI = 5/3 = 1.67

13 消减结构相关 当两条指令同时需要相同的硬件资源时，就会发生结构相关（冲突） 经典的 RISC 5-段整型数流水线通过设计可以没有结构相关
方法1：通过将新指令延迟到前一条指令执行完（释放资源后）执行 方法2：增加新的资源 E.g., 如果两条指令同时需要操作存储器，可以通过增加到两个存储器操作端口来避免结构冲突 经典的 RISC 5-段整型数流水线通过设计可以没有结构相关 很多RISC实现在多周期操作时存在结构相关 例如多周期操作的multipliers, dividers, floating-point units等，由于没有多个寄存器文件写端口 导致 结构冲突

14 三种基本的数据相关 写后读相关(Read After Write (RAW)) 读后写相关（Write After Read (WAR)
由于实际的数据交换需求而引起的 读后写相关（Write After Read (WAR) 编译器编写者称之为“anti-dependence”（反相关），是由于重复使用寄存器名“x1”引起的. 写后写相关（Write After Write (WAW)） 编译器编写者称之为“output dependence” ，也是由于重复使用寄存器名 “x1”引起的. 在后面的复杂的流水线中我们将会看到 WAR 和WAW 相关 4/19/2019

15 03/18-review 基本流水线回顾 微程序控制的单总线互连的处理器设计 重要概念： 理解微程序控制器的优劣势
数据通路、数据通路上的基本操作--寄存器传输 控制部件：控制信号、控制点 控制存储器 用微程序控制宏指令(macroinstruction)运行的基本过程 理解微程序控制器的优劣势 基本流水线回顾 4/19/2019

16 03/18-Review lecture 流水线技术要点 流水线正常工作的基本条件 多个任务重叠（并发/并行）执行，但使用不同的资源
流水线技术提高整个系统的吞吐率，不能缩短单个任务的执行时间 其潜在的加速比＝流水线的级数 影响流水线性能的因素 流水线中的瓶颈——最慢的那一段 流水段所需时间不均衡将降低加速比 流水线存在装入时间和排空时间，使得加速比降低 由于存在相关(hazards)问题，会导致流水线停顿 Hazards 问题：流水线的执行可能会导致对资源的访问冲突，或破坏对资源的访问顺序 流水线正常工作的基本条件 增加寄存器文件保存当前段传送到下一段的数据和控制信息 需要更高的存储器带宽 4/19/2019

17 三种基本的数据相关 写后读相关(Read After Write (RAW)) 读后写相关（Write After Read (WAR)
由于实际的数据交换需求而引起的 读后写相关（Write After Read (WAR) 编译器编写者称之为“anti-dependence”（反相关），是由于重复使用寄存器名“x1”引起的. 写后写相关（Write After Write (WAW)） 编译器编写者称之为“output dependence” ，也是由于重复使用寄存器名 “x1”引起的. 在后面的复杂的流水线中我们将会看到 WAR 和WAW 相关 4/19/2019

18 消减数据相关的三种策略 连锁机制（Interlock） 设置旁路定向路径（Bypass or Forwarding)
在issue阶段保持当前相关指令，等待相关解除 设置旁路定向路径（Bypass or Forwarding) 只要结果可用，通过旁路尽快传递数据 投机（Speculate） 猜测一个值继续，如果猜测错了再更正

19 Interlocking Versus Bypassing
add x1, x3, x5 sub x2, x1, x4 F D F X D F M X bubble D F Instruction interlocked in decode stage W M X bubble F D add x1, x3, x5 W M D X bubble W X M sub x2, x1, x4 F D X M W add x1, x3, x5 sub x2, x1, x4 Bypass around ALU with no bubbles

20 Example Bypass Path Fetch Decode EXecute Memory Writeback Imm Store
Data Cache Instruction Cache Inst. Register PC Registers B ALU A

21 Fully Bypassed Data Path
Fetch Decode EXecute Memory Writeback Imm Store Data Cache Instruction Cache Inst. Register PC Registers B ALU A F D X M W [ Assumes data written to registers in a W cycle is readable in parallel D cycle (dotted line). Extra write data register and bypass paths required if this is not possible. ] F D X M W F D X M W F D X M W

22 针对数据相关的值猜测执行 不等待产生结果的指令产生值，直接猜测一个值继续 这种技术，仅在某些情况下可以使用: 分支预测 堆栈指针更新
存储器地址消除歧义（Memory address disambiguation） CS252 S05

23 采用软件方法避免数据相关 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 4/19/2019

24 Control Hazards 如何计算下一条指令地址（next PC） 无条件直接转移 基于基址寄存器的无条件转移 条件转移 其他指令
Opcode, PC, and offset 基于基址寄存器的无条件转移 Opcode, Register value, and offset 条件转移 Opcode, Register (for condition), PC and offset 其他指令 Opcode and PC ( and have to know it’s not one of above ) CS252 S05

25 Control flow information in pipeline
Fetch Decode EXecute Memory Writeback Branch condition, Jump register value known Opcode, offset known PC known Imm Store Data Cache Instruction Cache Inst. Register PC Registers B ALU A

26 RISC-V Unconditional PC-Relative Jumps
PCJumpSel FKill PC_decode [ Kill bit turns instruction into a bubble ] Add +4 Imm Kill PC_fetch Instruction Cache Inst. Register Registers B ALU A Decode EXecute Fetch

27 Pipelining for Unconditional PC-Relative Jumps
j target ;等同于 jal x0,offset ; pc +=sext(offset) F D F target: add x1, x2, x3 X D F bubble M W X D

28 Branch Delay Slots 早期的RISC机器的延迟槽技术—改变ISA语义，在分支/跳转后的延迟槽中指令总是在控制流发生变化之前执行: 0x100 j target 0x104 add x1, x2, x3 // Executed before target … 0x205 target: xori x1, x1, 7 软件必须用有用的工作填充延迟槽（delay slots），或者用显式的NOP指令填充延迟槽 j target F D F target: xori x1, x1, 7 X D F add x1, x2, x3 M W X D

29 较好的分支预测技术减少了采用延迟槽技术的动力
Post-1990 RISC ISAs 取消了延迟槽 性能问题 当延迟槽中填充了NOPs指令后，增加了I-cache的失效率 即使延迟槽中只有一个NOP，I-cache失效导致机器等待 使先进的微体系架构复杂化 例如4发射30段流水线 较好的分支预测技术减少了采用延迟槽技术的动力

30 RISC-V Conditional Branches
PCSel DKill FKill Cond? PC_execute PC_decode Add Add +4 Kill Kill Inst. PC_fetch Instruction Cache Inst. Register Registers B ALU A Decode EXecute Fetch

31 Pipelining for Conditional Branches
M W X D beq x1, x2, target F target: add x1, x2, x3 bubble

32 Pipelining for Jump Register
Register value obtained in execute stage F D F X D F bubble M W jr x1 (等同于 jalr x0,0(x1); pc=0(x1) X M W D X M W F D X M W target: add x5, x6, x7

33 为什么在经典的五段流水线中 指令不能在每个周期都被分发(CPI>1)
采用全定向路径可能代价太高而无法实现 通常提供经常使用的定向路径 一些不经常使用的定向路径可能会增加时钟周期的长度，从而抵消降低CPI的好处 Load操作有两个时钟周期的延迟 Load指令后的指令不能马上使用Load的结果 MIPS-I ISA 定义了延迟槽, 软件可见的流水线冲突 (由编译器调度无关的指令或插入NOP指令避免冲突），MIPS-II中取消了延迟槽语义（硬件上增加流水线interlocks机制) MIPS:“Microprocessor without Interlocked Pipeline Stages” Jumps/Conditional branches 可能会导致流水线断流（bubbles) 如果没有延迟槽，则stall后续的指令 带有软件可见的延迟槽有可能需要执行大量的由编译器插入的NOP指令 NOP指令降低了CPI，但是增加了程序中执行的指令条数 CS252 S05

34 陷阱和中断 术语说明 异常（Exception）:由程序执行过程中引起的异常内部事件
E.g., page fault, arithmetic underflow 陷阱（Trap）:因异常情况而被迫将控制权移交给监控程序 Not all exceptions cause traps (c.f. IEEE 754 floating-point standard) 中断（Interrupt）:运行程序之外的外部事件，导致控制权转移到监控程序 陷阱和中断通常由同样的流水线机制处理

35 异常处理的发展历史 第一个带有陷阱（traps）的系统是Univac-I （1951年）
算术运算溢出有两种选择 1.在地址0处触发一个两条指令的修复例程的执行 或者 2.根据程序员的选择，使计算机停止 在后来的Univac 1103, 1955, 增加了外部中断机制 用于实时采集风洞数据 第一个带有I/O 中断的系统是DYSEAC（1954） 带有两个程序计数器，并且I/O信号引起这两个PC间的切换 它也是第一个带有DMA (direct memory access by I/O device)的系统 同时，也是第一台移动计算机 (两台半挂牵引车, 12 tons + 8 tons) CS252 S05

36 DYSEAC, first mobile computer!
Carried in two tractor trailers, 12 tons + 8 tons Built for US Army Signal Corps [Courtesy Mark Smotherman] CS252 S05

37 异步中断 I/O设备通过发出中断请求信号来请求处理 当处理器决定响应该中断时
停止当前指令(Ii)的执行 , 执行完当前指令前面的指令（执行完 Ii-1） (精确中断） 将li指令的PC值保存到专门寄存器(EPC)中 关中断并将控制转移到以监控模式运行的指定的中断处理程序 CS252 S05

38 Interrupts: 改变正常的控制流 Ii-1 HI1 interrupt handler program Ii HI2 Ii+1
HIn 需要由另一个（系统）程序处理的外部或内部事件。从程序的角度来看，事件通常是意外的或罕见的。 CS252 S05

39 Interrupt Handler 允许嵌套中断时，在开中断之前需要保存EPC  需要读取记录中断原因的状态寄存器
需要执行指令将EPC 存入 GPRs 至少在保存EPC之前，需要一种方法来暂时屏蔽进一步的中断 需要读取记录中断原因的状态寄存器 使用专门的间接跳转指令ERET (return-from-environment) 返回 开中断 将处理器恢复到用户模式 恢复硬件状态和控制状态 CS252 S05

40 Synchronous Trap 同步陷阱是由特定指令执行的异常引起的 通常，该指令无法完成，需要在处理异常之后重新启动
需要撤消一个或多个部分执行的指令的效果 在系统调用(陷阱)的情况下，该指令被认为已经完成 一种特殊的跳转指令，涉及到切换到特权模式的操作 CS252 S05

41 Exception Handling 5-Stage Pipeline
PC Inst. Mem D Decode E M Data Mem W + Illegal Opcode Overflow Data address Exceptions PC address Exception Asynchronous Interrupts 如何处理不同流水段的多个并发异常? 如何以及在哪里处理外部异步中断? CS252 S05

42 Exception Handling 5-Stage Pipeline
Commit Point PC D E M W Inst. Mem Decode Data Mem + Kill D Stage Kill F Stage Kill E Stage Select Handler PC Kill Writeback Illegal Opcode Overflow Data address Exceptions PC address Exception Exc D Exc E Exc M Cause PC D PC E PC M EPC Asynchronous Interrupts CS252 S05

43 Exception Handling 5-Stage Pipeline
在流水线中将异常标志保留到提交阶段 针对某一给定的指令，早期流水阶段中的异常覆盖该指令的后续异常 在提交阶段并入异步中断请求 (覆盖其他中断) 如果提交时检测到异常: 更新异常原因及EPC寄存器 终止所有流水段, 将异常处理程序的地址送入PC寄存器，以跳转到处理程序中执行 CS252 S05

44 异常的推测 预测机制 检查预测机制 恢复执行机制 定向路径机制允许后续的指令使用没有提交的指令结果
异常总是比较少的，所以简单地预测为没有异常 通常是大概率事件 检查预测机制 在指令执行的最后阶段进行异常检测 采用专门的硬件用于检测各种类型的异常 恢复执行机制 仅在提交阶段改变机器状态，因此可以在发生异常后丢弃部分执行的指令 刷新流水线后启动异常处理程序 定向路径机制允许后续的指令使用没有提交的指令结果 CS252 S05

45 流水线的性能分析 基本度量参数：吞吐率，加速比，效率 吞吐率：在单位时间内流水线所完成的任务数量或输 出结果的数量。 n：任务数
Tk：处理完成n个任务所用的时间 4/19/2019

46 流水线的性能分析 基本度量参数：吞吐率，加速比，效率 吞吐率：在单位时间内流水线所完成的任务数量或输出结果的数量。 n：任务数
Tk：处理完成n个任务所用的时间 4/19/2019

47 流水线技术提高系统的任务吞吐率 1. 各段时间均相等的流水线 各段时间均相等的流水线时空图 4/19/2019

48 吞吐率 流水线完成n个连续任务所需要的总时间（假设一条k段线性流水线） Tk＝kΔt＋(n-1)Δt＝(k＋n-1)Δt 流水线的实际吞吐率
最大吞吐率: 流水线在连续流动达到稳定状态后所得到的吞吐率。 S4 1 2 3 4 5 .. n-1 n S3 S2 S1 4/19/2019

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

50 流水线中的瓶颈——最慢的段 2. 各段时间不完全相等的流水线 各段时间不等的流水线及其时空图 流水线中这种时间最长的段称为流水线的瓶颈段
一条4段的流水线 S1，S3，S4各段的时间：Δt S2的时间：3Δt （瓶颈段） 流水线中这种时间最长的段称为流水线的瓶颈段 4/19/2019

51 各段时间不等的流水线的实际吞吐率： （ Δti为第i段的时间，共有k个段 ） 流水线的最大吞吐率为 4/19/2019

52 例如：一条4段的流水线中，S1，S2，S4各段的时间都是Δt，唯有S3的时间是3Δt。
最大吞吐率为 4/19/2019

53 解决流水线瓶颈问题的常用方法 改进后的流水线的吞吐率 ： 细分瓶颈段 例如：对前面的4段流水线
把瓶颈段S3细分为3个子流水线段：S3a，S3b，S3c 改进后的流水线的吞吐率 ： 4/19/2019

54 重复设置瓶颈段 缺点：控制逻辑比较复杂，所需的硬件增加了。 例如：对前面的4段流水线 重复设置瓶颈段S3：S3a，S3b，S3c
4/19/2019

55 重复设置瓶颈段后的时空图 4/19/2019

56 加速比 加速比：完成同样一批任务，不使用流水线所用的时间与使用流水线所用的时间之比。
假设：不使用流水线（即顺序执行）所用的间为Ts，使用流水线后所用的时间为Tk，则该流水线的加速比为 4/19/2019

57 1. 流水线各段时间相等（都是Δt） k段流水线完成n个连续任务所需要的时间为 Tk = (k＋n-1)Δt 顺序执行n个任务所需要的时间
Ts= nkΔt 流水线的实际加速比为 最大加速比 当n>>k时，S ≈ k 思考：流水线的段数愈多愈好？ 4/19/2019

58 流水线的各段时间不完全相等时 一条k段流水线完成n个连续任务的实际加速比为 4/19/2019

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

60 整条流水线的效率为 可以写成 最高效率为 当n>>k时，E≈1。 4/19/2019

61 流水线的效率是流水线的实际加速比S与它的最大加速比k的比值。
当流水线各段时间相等时，流水线的效率与吞吐率成正比。 E=TP△t 流水线的效率是流水线的实际加速比S与它的最大加速比k的比值。 当E=1时，S=k，实际加速比达到最大。 4/19/2019

62 从时空图上看，效率就是n个任务占用的时空面积和k个段总的时空面积之比。
当各段时间不相等时 4/19/2019

63 Summary 实际吞吐率：假设k段，完成n个任务，单位时间所实际完成的任务数。 加速比: k段流水线的速度与等功能的非流水线的速度之比。
效率：流水线的设备利用率。 4/19/2019

64 4/19/2019

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

66 For simple RISC pipeline, CPI = 1:
流水线的加速比计算 For simple RISC pipeline, CPI = 1: 4/19/2019

67 结构相关对性能的影响 例如: 如果每条指令平均访存1.3 次，而每个时钟周期只能访存一次，那么
在其他资源100％利用的前提下，平均 CPI  1.3 4/19/2019

68 例如： 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 4/19/2019

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

70 03/20-Review 相关的种类 相关会影响流水线性能 结构相关: 由于争用资源而引起的 数据相关：两条指令访问相同的数据而引起的
解决办法: 等待 增加（或拆分）资源 数据相关：两条指令访问相同的数据而引起的 类型： RAW WAR， WAW 解决办法： 硬件：定向技术（forwarding) 软件：指令级调度 控制相关：由于控制类指令引起的 减少性能损失的基本方法：冻结或排空流水线延迟转移 陷阱与中断 4/19/2019

71 解决控制相关的方法 #1: Stall 直到分支方向确定 #2: 预测分支失败 #3: 预测分支成功 #4: 延迟转移技术 直接执行后继指令
如果分支实际情况为分支成功，则撤销流水线中的指令对流水线状态的更新 要保证：分支结果出来之前不会改变处理机的状态，以便一旦猜错时，处理机能够回退到原先的状态。 #3: 预测分支成功 前提：先知道分支目标地址，后知道分支是否成功 #4: 延迟转移技术 4/19/2019

72 评估减少分支策略的效果 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 4/19/2019

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

74 对MIPS的扩充 四个功能部件 Integer 部件处理：Loads, Store, Integer ALU操作和Branch
FP/Integer 乘法部件：处理浮点数和整数乘法 FP加法器：处理FP加，减和类型转换 FP/Integer除法部件：处理浮点数和整数除法 这些功能部件未流水化 4/19/2019

75 扩展的MIPS流水线 4/19/2019

76 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 4/19/2019

77 将部分执行部件流水化后的MIPS流水线 4/19/2019

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

79 新的结构相关 纵向检查指令所使用的资源 第10个cycle，三条指令同时进入MEM，但由于MULTD和ADDD在MEM段没有实际动作，这种情况没有关系 第11个cycle，三条指令同时进入WB段，存在结构相关 4/19/2019

80 解决方法 Option 1 Option 2 在ID段跟踪写端口的使用情况，以便能暂停该指令的发射 一旦发现冲突，暂停当前指令的发射
在进入MEM或WB段时，暂停冲突的指令，让有较长延时的指令先做. 这里假设较长延时的指令，可能会更容易引起其他RAW相关，从而导致更多的stalls 4/19/2019

81 关于数据相关 S.D 多延迟一个cycle，以消解与ADD.D的冲突 4/19/2019

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

83 精确中断与长流水线 例如 ADDF 和SUBF都在DIVF前完成 如果DIVF导致异常，会如何？ Ideas??? 非精确中断
DIVF F0,F2,F4 ADDF F10,F10,F8 SUBF F12,F12,F14 ADDF 和SUBF都在DIVF前完成 如果DIVF导致异常，会如何？ 非精确中断 Ideas??? 4/19/2019

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

85 MIPS中的异常 IF page fault, misaligned address, memory protection violation ID undefined or illegal opcode EX arithmetic exception MEM WB none 4/19/2019

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

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

88 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 4/19/2019

89 平均每条指令的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. 4/19/2019

90 MIPS R4000 实际的 64-bit 机器 主频100MHz ~200MHz
较深的流水线（级数较多）(有时也称为 superpipelining) 4/19/2019

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

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

93 ALU输入端的定向源 4/19/2019

94 图示 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 4/19/2019

95 -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的浮点数操作 4/19/2019

96 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 4/19/2019

97 4/19/2019

98 双精度浮点数操作延迟及初始化间隔 浮点指令 延 迟 初始化 间隔 使用的流水段 加、减 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 4/19/2019

99 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 4/19/2019

100 4/19/2019

101 4/19/2019

102 4/19/2019

103 4/19/2019

104 R4000性能（1） 4/19/2019

105 R4000 性能（2） FP result stall because of FP RAW Hazards for an FP operand 4/19/2019

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

107 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 4/19/2019

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

109 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的表达式。 4/19/2019

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

111 在新的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; 4/19/2019

112 MEM Load or store instruction Branch instruction ALU 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） 4/19/2019

113 WB ALU instruction For load only
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 4/19/2019

114 简化的 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 4/19/2019