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

第三章 流水线技术 3.1流水线的基本概念 3.2 DLX(MIPS）基本流水线 3.3 流水线的相关 3.4 异常处理 3.6 MIPS R4000流水线 中国科学技术大学

Review:性能评测 平均CPI? 每类指令的使用频度 Type CPIi for type Frequency CPIi x freqIi Arith/Logic 4 40% 1.6 Load 5 30% 1.5 Store 4 10% 0.4 branch 3 20% 0.6 Average CPI: 4.1 中国科学技术大学

是否可以使 CPI < 4.1? 在一条指令执行过程中下图有许多空闲部件 可以让指令重叠执行?? Ideal Memory MemWr WrAdr Din RAdr 32 Dout MemWr ALU ALUOp Control IRWr Instruction Reg Reg File Ra Rw busW Rb 5 busA busB RegWr Rs Rt Mux 1 Rd PCWr ALUSelA RegDst PC MemtoReg Extend ExtOp 2 3 4 16 Imm << 2 ALUSelB Zero PCWrCond PCSrc IorD Mem Data Reg ALU Out B A 中国科学技术大学

3.1 流水线的基本概念 洗衣为例 Ann, Brian, Cathy, Dave 每人进行洗衣的动作： wash, dry, and fold washer需要 30 minutes Dryer 需要 40 minutes “Folder” 需要 20 minutes A B C D 中国科学技术大学

Sequential Laundry 6 PM 7 8 9 10 11 Midnight 30 40 20 30 40 20 30 40 Time 30 40 20 30 40 20 30 40 20 30 40 20 T a s k O r d e A B C D 顺序完成这些任务需要 6 小时 如果采用流水作业, 需要多长时间? 中国科学技术大学

流水线作业: 尽可能让任务重叠进行 6 PM 7 8 9 10 11 Midnight 30 40 20 A B C D Time 30 40 20 T a s k O r d e A B C D 流水作业完成四人的洗衣任务只需要 3.5 hours 中国科学技术大学

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

3.2 DLX (MIPS)的基本流水线 指令流水线：CPU执行大量的指令，指令吞吐率非常重要 DLX 的指令格式 所有指令相同长度 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可以对存储器操作 中国科学技术大学

DLX(MIPS)数据通路一种简单实现 4 Instruction Fetch Instr. Decode Reg. Fetch Execute Addr. Calc Memory Access Write Back Next PC MUX 4 Adder Next SEQ PC Zero? RS1 Reg File Address MUX Memory RS2 ALU Inst Memory Data L M D RD MUX MUX Sign Extend Imm WB Data 中国科学技术大学

基本操作(Step 1 & 2) Step 1 - IF IR <-- Mem[PC] --------- fetch the next instruction from memory NPC <-- PC + 4 ---------- compute the new PC Step 2 - ID - instruction decode and register fetch step A <-- Regs[IR6..10] B <-- Regs[IR11..15] 可能读取的寄存器值没有用，但没有关系，译码后如果无用，以后操作就不用 Imm  ((IR16)16 ## IR16-31 中国科学技术大学

基本操作－Step 3, 执行阶段 根据译码的结果，有四种情况 Memory Reference ALUOutput <-- A + (IR16)16 ## IR16..31--------- effective address SMD <-- B ---------- data to be written if it is a STORE -- SMD (store mem data) = MDR Register - Register ALU instruction ALUOutput <-- A op B Register - Immediate ALU instruction ALUOutput <-- A op ((IR16)16 ## IR16..31)) Branch/Jump ALUOutput <-- NPC + (IR16)16 ## IR16..31 cond <-- A op 0 --- for conditional branches A’s value is the condition base (= for BEQZ) 在简单的 Load-Store机器中，不存在即需要计算存储器地址，指令地址，又要进行ALU运算的指令，因此可以将计算有效地址与执行合二为一，在一个流水段中进行。 中国科学技术大学

Step 4 & Step5 Step 4 MEM - memory access/branch completion memory reference LMD <--- Mem[ALUOutput] ------- if it’s a load; LMD (load memory data) = MDR 或 Mem[ALUOutput] <-- SMD branch if (cond) then PC <-- ALUOutput else PC <-- NPC for Jumps the condition is always true Step 5 WB - write back Reg - Reg ALU Regs[IR16..20] <-- ALUOutput Reg - Immed ALU Regs[IR11..15] <-- ALUOutput Load Regs[IR11..15] <-- LMD 中国科学技术大学

这种结构是否可行 模型是正确的，但没有优化 还有其他选择 指令和数据存储器是否可以分开 采用一个长周期还是5个短周期实现 中国科学技术大学

单周期和多周期控制 多周期控制可实现指令重叠执行 中国科学技术大学

DLX(MIPS)的基本流水线 假设流水线周期为每步所花费的时间 中国科学技术大学

为什么用流水线? 假设执行100条指令 单周期机器 多周期机器 理想流水线机器 45 ns/cycle x 1 CPI x 100 inst = 4500 ns 多周期机器 10 ns/cycle x 4.6 CPI (due to inst mix) x 100 inst = 4600 ns 理想流水线机器 10 ns/cycle x (1 CPI x 100 inst + 4 cycle drain) = 1040 ns 中国科学技术大学

为什么用流水线(cont.)?－资源利用率高 Time (clock cycles) ALU Im Reg Dm I n s t r. O r d e Inst 0 ALU Im Reg Dm Inst 1 ALU Im Reg Dm Inst 2 Inst 3 ALU Im Reg Dm Inst 4 ALU Im Reg Dm 中国科学技术大学

流水线正常工作的基本条件 各段间需要使用寄存器文件保存当前段传送到下一段的数据和控制信息 存储器带宽是非流水的5倍 中国科学技术大学

新的 DLX (MIPS)数据通路 中国科学技术大学

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

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

新的DLX (MIPS)数据通路 中国科学技术大学

在新的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; 中国科学技术大学

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） 中国科学技术大学

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 中国科学技术大学

简化的 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 中国科学技术大学

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

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

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

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

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

中国科学技术大学

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

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

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

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

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

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

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

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

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

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

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

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

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

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

中国科学技术大学

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

-Review：流水线性能分析 吞吐率、加速比、效率之间的关系 流水线技术应用的难度何在? ：相关问题 中国科学技术大学

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

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

单个存储器引起的结构相关 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) 中国科学技术大学

消除结构相关 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 中国科学技术大学

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

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

例如： 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 中国科学技术大学

数据相关问题 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 中国科学技术大学

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

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 中国科学技术大学

编译器编写者称之为“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 中国科学技术大学

采用定向技术避免数据相关 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 中国科学技术大学

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

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

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

定向源为Load操作的比较判定 2013-03-20 中国科学技术大学

采用定向技术仍然存在相关 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 中国科学技术大学

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 中国科学技术大学

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

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

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

定向源为Load操作的比较判定 2013-03-20 中国科学技术大学

采用软件方法避免数据相关 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 中国科学技术大学

流水线相关检测部件能检测到的相关情况 中国科学技术大学

03/25-Review：流水线性能分析 吞吐率、加速比、效率之间的关系 流水线技术应用的难度何在? ：相关问题 中国科学技术大学

03/25-Review- 相关的处理 结构相关 数据相关 控制相关 概念：由于争用资源而引起的 解决办法 概念：两条指令访问相同的数据而引起的 解决办法： 硬件：定向技术（forwarding) 软件：指令级调度 控制相关 概念：由于控制类指令引起的 解决办法 ？？？ 中国科学技术大学

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

回顾DLX (MIPS)数据通路 中国科学技术大学

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

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

新的DLX (MIPS)数据通路 中国科学技术大学

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

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

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

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

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

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

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

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

分支取消机制示意 分 支 失 败 分支指令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 预测分支成功的情况下，分支取消机制的执行情况 中国科学技术大学

评估减少分支策略的效果 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 3 1.42 3.5 1.0 Predict taken 1 1.14 4.4 1.26 Predict not taken 1 1.09 4.5 1.29 Delayed branch 0.5 1.07 4.6 1.31 1.14 = 1 + 1*14%*100% 1.09 = 1+1*14%*65% 1.07 = 1+ 0.5*14% Conditional & Unconditional = 14%, 65% change PC 中国科学技术大学

-Review（续） 控制相关 异常 概念： 减少性能损失的基本方法 冻结或排空流水线 预测分支成功 预测分支失败 延迟转移 异常的分类 精确中断和非精确中断 中国科学技术大学

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

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

异常的分类 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 中国科学技术大学

例如 中国科学技术大学

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

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

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

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

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

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

扩展的DLX(MIPS)流水线 中国科学技术大学

Latency & Repeat Interval 定义为完成某一操作所需的cycle数 定义为使用当前指令所产生结果的指令与当前指令间的最小间隔周期数 循环间隔（Repeat/Initiation interval） 发射相同类型的操作所需的间隔周期数 对于EX部件流水化的新的DLX(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 中国科学技术大学

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

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

03/27-Review 多周期操作处理基本模型 控制相关 异常 概念： 减少性能损失的基本方法-转移地址，条件码 静态处理： 冻结或排空流水线 预测分支成功 预测分支失败 延迟转移 异常 异常的分类 精确中断和非精确中断 多周期操作处理基本模型 EX段若干个cycles Latency & repeat interval 中国科学技术大学

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

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

关于数据相关 中国科学技术大学

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

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

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

第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使用这种方法 中国科学技术大学

DLX(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 中国科学技术大学

平均每条指令的stall数 The total number of stalls per instruction ranges from 0.65 for su2cor to 1.21 for doduc, with an average of 0.87. 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. 中国科学技术大学

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

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

在使用定向技术的情况下，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 中国科学技术大学

图示 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 中国科学技术大学

MIPS R4000 浮点数操作 3个功能部件组成：FP Adder, FP Multiplier, FP Divider FP操作需要2（negate）-112个（square root）cycles 8 kinds of stages in 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 中国科学技术大学

MIPS FP 流水段 FP Instr 1 2 3 4 5 6 7 8 … 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 … A R 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 中国科学技术大学

双精度浮点操作指令延迟、启动间隔和流水段的使用情况 中国科学技术大学

注： Multiply Issue U M M -> U E+M M 中国科学技术大学

注：Multiply 的 第 2 拍的M -〉 E+M 中国科学技术大学

中国科学技术大学

中国科学技术大学

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

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

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

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 中国科学技术大学

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

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

review 流水线性能分析 吞吐率、加速比、效率之间的关系 流水线技术应用的难度何在? ：相关问题 中国科学技术大学

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

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的表达式。 中国科学技术大学

Review- 相关的处理 结构相关 数据相关 概念：由于争用资源而引起的 解决办法 概念：由于存在实际的通信，而引起的 解决办法： 硬件：定向技术（forwarding) 软件: 指令级调度 中国科学技术大学

Review （续） 控制相关 异常 概念： 减少性能损失的基本方法-转移地址，条件码 静态处理： 冻结或排空流水线 预测分支成功 预测分支失败 延迟转移 异常 异常的分类 精确中断和非精确中断 中国科学技术大学

控制相关 分支需要解决两个问题 译码在ID段，此时取进来的指令可能是错误的指令 分支目标地址（转移成功意谓着PC值不是 PC+4） CC是否有效，这两点在DLX(MIPS)中都在流水线的靠后段中确定 译码在ID段，此时取进来的指令可能是错误的指令 对于简单的DLX(MIPS)流水线 - 3 cycle branch penalty 有效地址在EX段才能确定 条件是否为真在MEM段 因此有3个stall 流水线的时空图 中国科学技术大学