The IPS Processor Implementation: Pipeline ILP Computer Organization & Design John Hennessy, David Patterson
内容提要 流水线技术原理 IPS 的五级流水线实现 流水线的 Hazard( 冲突 / 依赖 / 相关 ) 及其处理 结构冲突 : 哈佛结构 数据依赖 编译技术 : 插入 nop, 指令重排, 寄存器重命名 forwarding 技术 Interlock 技术 控制相关 编译技术 : 延迟分支 硬件优化 : 提前完成, 投机, 预测
Iron Law of Performance 处理器性能 : 程序的执行时间? 程序的指令数 : 源代码, 编译器,ISA CPI:ISA,uArch Frequency:uArch, 工艺 CISC or RISC? RISC 的指令数多, 但 CPI 少! CISC 顺序模型,RISC 并行模型
Laundry Example 4 袋衣服 :Wash(30), dry(40), and fold(20) Sequential Laundry 需要花费 6 小时 (4x(30+40+20)=360 分钟 ) Pipelined Laundry:Start work ASAP 需 30+4x40+20=210 分 (3.5 小时 ) 约束 : 设备独立, 作业时长相等,buffers?In-order?
流水线技术 Wash Dry 顺序执行 1 2 3 4 5 6 7 8 Non-pipelined 1 2 3 4 5 6 7 8 指令级并行 (ILP) 1 2 3 4 5 6 7 8 Pipelined 1 2 3 4 5 6 7 8 non-pipelined dish cleaning Time pipelined dish cleaning Time 流水过程由多个相互联系的子过程组成, 每个子过程称为流水线的 级 或 段 一条流水线的段数被称为流水线的深度, 或 流水深度 各个功能段所需时间尽量相等 否则, 消耗时间长的功能段将成为流水线的瓶颈, 会造成流水线的阻塞或断流 每个功能段所需的时间一般为一个机器周期 (cycle) llxx@ustc.edu.cn 5
指令流水线技术 将指令的处理过程分解为更细的几个阶段 取指 (FI): 从存储器取出一条指令并暂时存入指令部件的缓冲区 指令译码 (DI): 确定操作性质和操作数地址的形成 方式 计算操作数地址 (CO): 计算操作数的有效地址, 涉及到寄存器间址 间址 变址 基址 相对寻址等各种地址计算方式 取操作数 (FO): 从存储器中取操作数 ( 若操作数在寄存器中, 则无需此阶段 ) 执行指令 (EI): 执行指令所需的操作, 并将结果存于目的位置 ( 寄存器中 ) 写操作数 (WO): 将结果存入存储器 llxx@ustc.edu.cn 6
六级指令流水线时空图 (Gantt chart) llxx@ustc.edu.cn 7
流水线性能 CPI,IPC 流水线加速比 (speedup) 非流水线执行时间 speedup= = lim 流水线执行时间 n* k * t k * t ( n 1) * t n * k 从此开始, 每个周期流出一条指令,IPC 1 llxx@ustc.edu.cn 8
流水线分类 单功能流水线 : 只能完成一种功能的流水线, 如浮点加法流水线 多功能流水线 : 流水线的各段可以进行不同的连接, 从而使流水线在不同的时间完成不同的功能 静态流水线 : 在某一时间段内, 流水线的各段只能按同一种功能的连接方式工作, 即只有当输入是一串相同性质的操作时其性能才能得到发挥 动态流水线 : 在某一段时间内, 某些段正在实现某类操作 ( 定点乘 ), 其他段却在实现另一类操作 ( 浮点加 ) 线性流水线 : 流水线的各段串行连接, 没有反馈回路 非线性流水线 : 流水线中除了串行的通路, 还有反馈回来 顺序流水线 : 流水线的流出顺序与其流入顺序相同 乱序流水线 : 流水线的流出顺序与其流入顺序不同 llxx@ustc.edu.cn 9
适应流水线的 IPS ISA 五原则 指令字等长 适于取指和译码 指令格式简单 R-type I-type J-type op(6 bits) rs(5 bits) rt(5 bits) rd(5 bits) shamt(5 bits) funct(6 bits) op(6 bits) rs(5 bits) rt(5 bits) addr/immediate(16 bits) op(6 bits) rs(5 bits) rt(5 bits) addr(16 bits) op(6 bits) addr(26 bits) 源操作数位置固定, 因此可以在译码的同时取操作数 ( 读寄存器 ), 否则要增加一级流水线段 只有 load/store 访存 意味着可以在执行阶段计算访存地址, 然后在下一阶段访存 如果 R-type 指令也可访存, 则变为取指 译码 地址计算 访存 执行 写回等几个阶段 操作数在内存中要 字对齐 因此在取操作数时不需要访问存储器多次 每条指令最多只写一个结果, 且在流水线的最后一级进行写操作 2003.6.1 llxx@ustc.edu.cn 10
IPS 的 5 级流水线划分 基于单周期 or 多周期? 2003.6.1 llxx@ustc.edu.cn 11
指令数据通路划分 IF: Instruction fetch 0 u x 1 ID: Instruction decode/ register file read EX: Execute/ address calculation E: emory access WB: Write back Add 4 Add Add result Shift left 2 PC Address Instruction memory Instruction register 1 data 1 register 2 Registers data 2 Write register Write data 0 u x 1 Zero ALU ALU result Address Write data Data memory data 1 u x 0 16 Sign extend 32 2003.6.1 llxx@ustc.edu.cn 13
流水线的段寄存器 ux 0 1 IF/ID ID/EX EX/E E/WB Add 4 Add Add result Shift left 2 PC Address Instruction memory Ins truc tion register 1 data 1 register 2 Registers data 2 Write register Write data 0 ux 1 Zero ALU ALU result Address Write data Data memory data ux 1 0 16 Sign extend 32 2003.6.1 llxx@ustc.edu.cn 14
ultiple-clock-cycle Pipeline Diagram
Single-clock-cycle Diagram: CC5
load 指令的取指阶段 lw I n s tr u c tio n fe t c h lw $s1,100($s2) ux 0 1 IF/ID ID/EX EX/E E/WB Add 4 Shift left 2 Add result Add PC Address Instruction memory I nst ruction register 1 data 1 register 2 Registers data 2 Write register Write data 0 ux 1 Zero ALU ALU result Address Write data Data memory data ux 1 0 16 Sign extend 32 2003.6.1 llxx@ustc.edu.cn 17
load 指令的译码阶段 0 u x 1 lw I n s t r u c tio n d e c o d e lw $s1,100($s2) IF/ID ID/EX EX/E E/WB Add 4 Add Add result Shift left 2 PC Address Instruction memory Instruction register 1 data 1 register 2 Registers data 2 Write register Write data 0 u x 1 Zero ALU ALU result Address Write data Data memory data 1 u x 0 16 Sign extend 32 2003.6.1 llxx@ustc.edu.cn 18
load 指令的执行阶段 ux 0 1 lw Execution lw $s1,100($s2) IF/ID ID/EX EX/E E/WB Add 4 Add result Add Shift left 2 PC Address Instruction memory Instruction register 1 data 1 register 2 Registers data 2 Write register Write data 0 ux 1 Zero ALU ALU result Address Write data Data memory data ux 1 0 16 Sign extend 32 2003.6.1 llxx@ustc.edu.cn 19
load 指令的访存阶段 ux 0 I lw $s1,100($s2) lw e m o r y 1 l t i I i t i i i t r t F/ID i ID/EX i EX/E E/WB Add i 4 Add Add result Shft ef 2 PC Address nstruct on memory Ins r uc ton register 1 data 1 register 2 Regs ers data 2 Wrte register Wrte data 16 i i i Sgn extend r t t 32 l 0 ux 1 Ze o ALU ALU result Address Data memory Wrte data da a 1 ux 0 2003.6.1 llxx@ustc.edu.cn 20
load 的写回阶段 :bug ux 0 1 lw $s1,100($s2) W r it e lw b a c k IF/ID ID/EX EX/E E/WB Add 4 Add result Add Shift left 2 PC Address Instruction memory Instruction regster 1 da a 1 regster 2 Registe s da a 2 Write regster Write data 16 Sign extend 32 0 ux 1 Zero ALU ALU resut Address Data memory Write data data 1 ux 0 2003.6.1 llxx@ustc.edu.cn 21
流水线的改正版 ux 0 1 IF/ID ID/EX EX/E E/WB Add 4 Add Add result Shift left 2 PC Address Instruction memory Instruction register 1 data 1 register 2 Registers data 2 Write register Write data 16 Sign extend 32 0 ux 1 Zero ALU ALU result Address Write data Data memory data ux 1 0 2003.6.1 llxx@ustc.edu.cn 22
各类指令的完成时间 :CPI=? 0 u x 1 IF/ID ID/EX EX/E E/WB Add 4 Shift left 2 Add Add result PC Address Instruction memory Instruction register 1 data 1 register 2 Registers data 2 Write register Write data 0 ux 1 Zero ALU ALU result Address Write data Data memory data ux 1 0 16 Sign extend 32 2003.6.1 23
CPI = IPC = 1?
R-type 指令完成时间 : 结构冲突 R-type 指令能否 4 个周期完成, 节省 WB 段? 例 : 当前指令为 ld, 下一条指令为 R-type CC5? 2003.6.1 25
beq 指令完成时间? ux 0 分支目的以哪一条指令为基址? beq 能否在 EXE 完成? 1 IF/ID ID/EX EX/E E/WB Add 4 Shift left 2 Add result Add PC Address Instruction memory Instruction register 1 data 1 register 2 Registers data 2 Write register Write data 16 Sign extend 32 0 ux 1 Zero ALU ALU result Address Write data Data memory data ux 1 0
Jmp 的数据通路与完成时间? PC 0 u x 1 Address Write data emory emdata Instruction [31-26] Instruction [25 21] Instruction [20 16] Instruction [15 0] Instruction register Instruction [15 0] emory data register PCWriteCond PCWrite IorD Outputs em emwrite emtoreg IRWrite Instruction [25 0] Instruction [15 11] Control Op [5 0] 0 u x 1 0 u x 1 PCSource ALUOp ALUSrcB ALUSrcA RegWrite RegDst 16 register 1 register 2 Registers Write register Write data Sign extend data 1 data 2 32 Shift left 2 A B 4 0 u x 1 0 1 u 2 x 3 26 Shift 28 left 2 ALU control PC [31-28] Zero ALU ALU result Jump address [31-0] ALUOut 0 1 u x 2 Instruction [5 0]
E/WB =0? ADD 4 分支结果 U X 1 IR[rs] NPC NPC cond EX/E ID/EX IF/ID DLX 的流水段寄存器数据存储器通用寄存器组符号位扩展 ALU PC 16 32 存储器 U X 2 U X 3 U X 4 IR A B Imm IR[rs] IR[rt] E/WB.IR IR ALUo B IR LD ALUo IR 指令
流水线控制信号?
流水线控制信号? David. Harris,Digital Design and Computer Architecture,2012
流水线控制信号 所有控制信号名及其功能与非流水线版相同 取指 : 读 I, 写 PC( 每个周期写入一次, 不需控制信号 ) 译码 / 寄存器读 : 没有控制信号 执行 / 地址计算 :RegDst,ALUOp,ALUSrc 访存 :Branch,em,emWrite,PCSrc 写回 :emtoreg,regwrite 流水线段寄存器 : 每个周期写入一次, 不需要单独的写控制 需要将控制分配给不同的流水线段 2003.6.1 llxx@ustc.edu.cn 32
控制的传递 WB Instruction Control WB EX WB IF/ID ID/EX EX/E E/WB 需要控制缓存 : 类似 load 指令的目的寄存器号传递 2003.6.1 llxx@ustc.edu.cn 33
the control of the pipeline register PCSrc ux 0 1 Control ID/EX WB EX/E WB E/WB IF/ID EX WB Add PC Add 4 Add result Address Instruction memory Instruction Write data Reg gwrite register 1 data 1 register 2 Registers Write data 2 register Shift left 2 0 u x 1 ALUSrc Zero ALU ALU result Branch Write data emwrite Address Data memory data emtoreg 1 u x 0 Instruction [15 0] 16 Sign 32 extend 6 ALU control em Instruction [20 16] Instruction [15 11] 0 ALUOp ux 1 RegDst 2003.6.1 llxx@ustc.edu.cn 34
Pipelined processor with clock David. Harris,Digital Design and Computer Architecture,2012
流水线的 hazard 冒险 问题 ILP: 资源 confict, 数据 dependency, 控制 penalty 结构相关 : 当指令在重叠执行的过程中, 硬件资源满足不了指令重叠执行的要求, 发生资源冲突时将产生结构相关 数据相关 : 当一条指令需要用到前面指令的执行结果, 而这些指令均在流水线中重叠执行时, 就可能引起数据相关 控制相关 : 当流水线遇到分支指令和其他会改变 PC 值的指令时, 会发生控制相关 llxx@ustc.edu.cn 36
结构相关 C1 C2 C3 C4 C5 C6 C7 C8 LOAD ALU E REG E REG 指令 1 ALU E REG E REG 指令 2 ALU E REG E REG 指令 3 ALU E REG E REG 典型的结构相关由访存造成 llxx@ustc.edu.cn 37
流水线 stall( 停顿, 阻塞 ) C1 C2 C3 C4 C5 C6 C7 C8 LOAD ALU E REG E REG 指令 1 E REG ALU E REG 指令 2 E REG ALU E REG 指令 3 ALU E REG E REG 气泡 (bubble): 流水线停顿一个周期 llxx@ustc.edu.cn 38
访存冲突处理 :IF 段 Stall 检测? Stalling:freeze up and bubble down 冻结其前面的流水段 : 使之持续重复相同的操作 使功能部件暂停一个周期, 再重新发出控制 不改变 PC, 重新取指 向后面的流水段插入气泡 : 将其后流水段的控制清零 IF/ID 段寄存器清零 : 相当于发一条 nop 指令
访存结构冲突消除 : 哈佛结构 ux 0 1 IF/ID ID/EX EX/E E/WB Add 4 Shift left 2 Add result Add PC Address Instruction memory Ins truc tion register 1 data 1 register 2 Registers data 2 Write register Write data 0 ux 1 Zero ALU ALU result Address Write data Data memory data ux 1 0 16 Sign extend 32 llxx@ustc.edu.cn 40
R-type 指令完成时间 : 结构冲突 R-type 指令能否 4 个周期完成, 节省 WB 段? 例 : 当前指令为 ld, 下一条指令为 R-type CC5? 2003.6.1 41
数据相关 ( 哪个周期数据可用?) RF 先写 : 三有四无 llxx@ustc.edu.cn 42
数据相关分类 写后读相关 (RAW):j 的执行要用到 i 的计算结果,j 可能在 i 写入其计算结果之前就先行对保存该结果的寄存器进行读操作 读 快, 写 慢 写后写相关 (WAW):j 和 i 的目的操作数一样, 写入顺序错误, 在目标寄存器中留下的是 i 的值而不是 j 的值 后面的 写 快, 前面的 写 慢 读后写相关 (WAR):j 可能在 i 读取某个源寄存器的内容之前就先对该寄存器进行写操作, 导致 i 读出的是错误的数据 后面的 写 快, 前面的 读 慢 in-order, out-of-order? llxx@ustc.edu.cn 43
RAW 问题 Stalling Interlock: 硬件控制, 动态技术 freeze up and bubble down 编译技术 : 静态技术 插入 nop 指令 : 降低 I$ 命中率 故后期 IPS 还是采用了 Interlock 减少 stall 损失 Forwarding: 硬件控制, 动态技术 数据定向技术 : 数据前推 / 旁路 (Bypassing) 使关键路径加长, 不利于提升主频! 编译器 : 延迟槽 : 写指令与读指令之间的周期数 WB 与 ID 之间隔周期数 调度无关指令 : 兼容性问题 新旧版本 延迟槽 数可能不同 llxx@ustc.edu.cn 44
化解 RAW: 编译器 stall 指令调度 逻辑上 CC6数据安全可用
减少 RAW 损失 :Forwarding to EX 段 检测 ( 三有四无 ), 前推 46
Forwarding: 实现 EX 段旁路 ID/EX WB EX/E Control WB E/WB IF/ID EX WB PC Instruction memory Instruc ction Registers ux x ALU Data memory ux ux IF/ID.RegisterRs Rs IF/ID.RegisterRt Rt IF/ID.RegisterRt IF/ID.RegisterRd Rt Rd ux EX/E.RegisterRd Forwarding unit E/WB.RegisterRd 将 EX/E(ALU 计算结果 ) 和 E/WB(lw) 前推至 EX 段 (ALU 输入 ) 2003.6.1 llxx@ustc.edu.cn 47
RAW 的检测规则 : 实现 EX 段旁路 EX/E 前推 前一条依赖 E/WB 前推 第三条依赖 2003.6.1 llxx@ustc.edu.cn 48
Forwarding 的控制信号
流水线段寄存器中的 IR
求和累加 : 假依赖? 第三条依赖第一条, 有 第三条假依赖第一条 :
E copy 问题 IPS 中,mem-to-mem 拷贝频繁 mem copy 由 lw-sw 实现 需要 E/WB 前推到 E 段 如何实现 lw-sw 前推? 此时无需插入 bubble!
ultilevel Bypass: 需要多个段前推! 哪儿用就前推到哪儿关键路径被延长
forwarding 可消解的 RAW Time (in clock cycles) CC 1 CC 2 CC 3 CC 4 CC 5 CC 6 CC 7 CC 8 CC 9 Value of register $2 : 10 10 10 10 10/ 20 20 20 20 20 Value of EX/E : X X X 20 X X X X X Value of E/WB : X X X X 20 X X X X Program execution order (in instructions) sub $2, $1, $3 I Reg D Reg and $12, $2, $5 I Reg D Reg or $13, $6, $2 I Reg D Reg add $14, $2, $2 I Reg D Reg sw $15, 100($2) I Reg D Reg 2003.6.1 llxx@ustc.edu.cn 54
forwarding 无法解决的 RAW:backwards 2003.6.1 llxx@ustc.edu.cn 55
load-use-data hazard 编译器 : 指令重排序 硬件 stalling:interlock Forwarding:E/WB
指令重排序 : 编译 快 2 个 cycle? 不是所有指令顺序都能调整 ( 结合律 )!
Interlock:lw 指令 stalling! Interlock The hardware detect a data hazard and stall the pipeline until the hazard is cleared 检测数据依赖 : 在 ID 段执行! Stalling:freeze up and bubble down 冻结其前面的流水段 :IF 增加两个控制信号 :PCWrite 和 IF/IDWrite 阻止更新 PC 和 IF/ID 使之持续重复相同的操作 向其后的流水段插入气泡 :ID/EX 将其后的控制清零 使功能部件暂停一个周期, 再重新发出控制 可能需要连续插入多个 stall?
interlock freeze up interlock Hazard detection unit ID/EX.em ID/EX ld? bubble down IF/IDWrite IF/ID Control 0 ux WB EX EX/E WB E/WB WB PCW Write PC Instruction memory Instruction Registers ux ALU Data memory ux ux IF/ID.RegisterRs IF/ID.RegisterRt IF/ID.RegisterRt IF/ID.RegisterRd Rt Rd ux EX/E.RegisterRd ID/EX.RegisterRt Rs Rt Forwarding unit E/WB.RegisterRd 2003.6.1 llxx@ustc.edu.cn 59
分支相关 假设指令 3 是一条条件转移指令 必须待指令 2 的结果出现后 ( 第 7 个时间单元 ), 才能决定下一条指令是 4( 条件不满足,no taken) 还是指令 15( 条件满足,taken) 延迟槽 (delay slot) 排空 (flush): 将已进入流水线的指令清除 60
branch hazard P ro g ra m e x e c u tio n o rd e r (in in s tru c tio n s ) T im e (in c lo c k c y c le s ) C C 1 C C 2 C C 3 C C 4 C C 5 C C 6 C C 7 C C 8 C C 9 4 0 b e q $ 1, $ 3, 72 I R e g D R e g 4 4 a n d $ 1 2, $ 2, $ 5 I R e g D R e g 4 8 o r $ 1 3, $ 6, $ 2 I R e g D R e g 5 2 a d d $ 1 4, $ 2, $ 2 I R e g D R e g 7 2 lw $ 4, 5 0 ( $ 7 ) I R e g D R e g 2003.6.1 llxx@ustc.edu.cn 61
分支依赖的优化技术 投机执行 (Speculation): 静态 ( 固定 ) 预测 硬件 / 编译器 :Taken or not taken? COD 的 beq 为 非延迟分支 : 设 not taken, 需要 flush IF 减少分支延迟 :COD 的 beq 为 单周期分支 延迟分支 (delayed branch): 编译调度 按一定的模式向延迟槽 (delay slot) 填入某些指令 向前找? 向后找? 三种模式 分支发生 : 延迟槽指令执行完再转移! 难实现? 分支延迟小时才有效? 一般单延迟槽 IPS 用单延迟槽 + 投机,RISC-V 不用延迟槽 分支预测器 (Branch predictor): 动态预测 -Arch 少用分支指令 :AR/IPS 的条件执行指令 62
投机执行 大多数 RISC 微处理器一般都采用了静态转移预测 3 种 : 预测总是不会发生转移 这是最简单最经济的转移预测策略 在转移实际发生之前, 它预测指令执行 是顺序的 对于向后的转移预测转移会发生, 向前的转移预测转移不会发生 这种预测策略与循环的结构 (profile) 非常匹配 在循环中, 向后的转移用 于迭代, 向前的转移用于退出循环 由于迭代次数很多, 而退出只有一次, 因此这种预测对循环是非常准确的 预测转移总是发生 只要转移指令在实际中进行转移的百分比远高于没有发生转移的情况, 这种 转移预测策略可以很好的工作
COD branch: assume not taken + flush P ro g ra m e x e c u tio n o rd e r (in in s tru c tio n s ) T im e (in c lo c k c y c le s ) C C 1 C C 2 C C 3 C C 4 C C 5 C C 6 C C 7 C C 8 C C 9 4 0 b e q $ 1, $ 3, 72 I R e g D R e g 4 4 a n d $ 1 2, $ 2, $ 5 I R e g D R e g 4 8 o r $ 1 3, $ 6, $ 2 I R e g D R e g 5 2 a d d $ 1 4, $ 2, $ 2 I R e g D R e g 7 2 lw $ 4, 5 0 ( $ 7 ) I R e g D R e g 2003.6.1 llxx@ustc.edu.cn 64
Flush 语义 Clear UP and Bubble Down
分支发生 :flush+ 更新 PC?
分支发生 :flush 并更新 PC( 见 beq) flush: Clear up and Bubble down?
beq 指令的完成时间 PCSrc ux 0 1 Control ID/EX WB EX/E WB E/WB IF/ID EX WB Add PC Add 4 Add result Address Instruction memory Instruction Write data Reg gwrite register 1 data 1 register 2 Registers Write data 2 register Shift left 2 0 u x 1 ALUSrc Zero ALU ALU result Branch Write data emwrite Address Data memory data emtoreg 1 u x 0 Instruction [15 0] 16 Sign 32 extend 6 ALU control em Instruction [20 16] Instruction [15 11] 0 ALUOp ux 1 RegDst 2003.6.1 llxx@ustc.edu.cn 68
减小 beq 损失 : 单周期分支 将 beq 完成时间从 E 提前到 ID 在 ID 段增加一个加法器, 计算 npc 在 ID 段增加一个比较器, 判断分支条件 针对 简单条件判断 : 按位 xor, 再 or 不适于 复杂条件判断 : 如溢出等需要 ALU 分支发生时 : 只需 flush IF 段 增加 IF.Flush, 控制清空 IF/ID 的 IR npc? 由 controler 控制 IF.Flush( 见 COD4 图 4-65)? llxx: 好像应该由比较器控制吧? 更新 PC 仍然损失一个周期 : 一条指令
reducing the delay penalty & flush IF IF.Flush ux Hazard detection unit ID/EX WB EX/E Control 0 ux WB E/WB IF/ID EX WB 4 Shift left 2 ux PC Instruction memory Registers = ALU Data memory ux ux Sign extend ux Forwarding unit 图 4-65 llxx@ustc.edu.cn 70
Flush & Taken Clear or 取 lw 图 4-62 商榷?
单周期 beq 指令的数据依赖 例一 : add $4,$5,$6 beq $4,$2,40 例二 : lw $4,20($1) beq $4,$2,40 需要新的 interlock 和 forwarding?
beq 指令的性能 单周期分支 stall 对性能的影响, 例 SPECINT2006 中, 条件分支占 17% 设其他指令 CPI=1 单周期条件分支需 stall 一个周期, 因此平均 CPI=1.17,, 即性能下降 1.17 倍 原始版本的 CPI=?
编译器 : 延迟转移 分支延迟槽指令调度三种选择 : 无关指令,taken,not taken(?)
分支预测器 : 动态预测 动态转移预测基于实际运行时的转移历史 : 1 位转移预测缓冲器 将所有转移指令地址放入一个缓冲器, 并配置一个状 态位用于记录这条指令是否发生了转移 当取到一条新的转移指令时, 查看缓冲器是否有这条指令 如果这条指令不在缓冲器, 静 态地预测这条指令发生情况, 并在指令的状态输出已知时更新缓冲器 如果指令已在缓冲 器中, 根据以前状态预测这条指令 如果预测正确, 那是最好的 ; 否则, 更新缓冲器中的 状态位 2 位转移预测缓冲器 转移预测过程与 1 位时相同, 只是用两个状态位跟踪转移历史 只有当连续两次预测不成功时才修改转移预测的方向 用两位的目的是在特定条件下, 如嵌套循环退出时, 实现滞后作用 以硬件 ( 饱和计数器 (saturating counter)) 的复杂性和成本为代价, 动态 转移预测 ( 相对静态预测 ) 可以提高转移预测的精度
Branch Prediction State Diagram 2 位预测器 : 先预测 taken, 两次失败后预测 not taken
Branch Prediction 分支预测器
发挥分支预测器的效益 软硬协同 : 数据预排序, 提升分支预测的有效性
with full hazard handling
Hazard 问题小结 消除 hazard:stalling 硬件 :interlock(freeze up & bubble down) 编译 : 插入 nop 减少 stall 损失 结构 : 访存 哈佛结构,lw-R 延迟完成 无 stall RAW: 三有四无,forwarding( 检测, 前推 ), 指令调度 ID 段 EX 段 E 段 lw-r:backward 仍需 stalling 伪依赖 beq: 投机执行, 单周期, 延迟分支 ( 指令调度 ), 分支预测器 投机 / 预测失败 :flush clear up and bubble down? 仍需 stalling,raw 时需要 forwarding
Cache miss 的 stall(stall 多个周期?)
emory Delays:cache miss emory delays can also cause pipeline stalls A cache memory holds instructions and data from the main memory, but is faster to access With a cache, typical access time is one cycle But a cache miss requires accessing slower main memory with a much longer delay In pipeline, memory delay for one instruction causes subsequent instructions to be delayed
流水执行与机器指令的特征 寻址方式 : 避免造成 stall( 如 : 间接寻址 ) 适合流水线的三个特点 : 仅需访存一次就能得到操作数 只有 ld 和 st 指令访存 所采用的寻址方式没有副作用 适合者如 : 寄存器寻址 基址寻址 比较 : 变址寻址 相对寻址 寄存器间接寻址? 条件标志 1. Immediate addressing 2. Register addressing 3. Base addressing Register 4. PC-relative addressing 隐性依赖 : 不同指令序列造成最终的条件标志不同 op rs rt op rs rt op rs rt op rs rt PC Immediate rd... funct Address Address + + Registers Register emory Byte Halfword Word 编译器需指令重排以消解指令间的依赖, 但条件标志引起的依赖降低了指令重排 的可行性 能影响条件标志的指令越少越好 编译器可指定程序中哪些指令可以修改条件标志 如 AR 5. Pseudodirect addressing op Address PC emory Word emory Word Add r1,r2 Compare r3,r4 Branch=0 改成 : Compare r3,r4 Add r1,r2 Branch=0
关于 IPS 体系结构的说明 E 段 : 约 3/4 的指令在此段什么也不做 为所有指令分派这一步可保证两条指令不会同时访问数据 cache? load/store 必须数据对齐 延迟槽 分支延迟槽 : 分支指令的下一条指令 所有分支指令 延迟执行! Load 延迟槽 :ld 指令的下一条指令 寻址方式 在硬件层次上,IPS 仅提供 基址 + 偏移 一种寻址方式? 寄存器寻址? 在汇编程序中, 可以使用五种寻址方式 没有专门的栈支持? 仅提供最少的过程调用 (jal,jr) 支持和异常 / 中断支持 条件分支 : 使用寄存器中的值, 不使用条件标志
Single Cycle, ultiple Cycle, Pipeline 注意 : 多周期和流水线指令周期都不定长 2019/4/16 85
单周期实现 vs. 流水线性能 Program execution order Time (in instructions) lw $1, 100($0) Instruction fetch 2 4 6 8 10 12 14 16 18 Reg ALU Data access Reg lw $2, 200($0) 8 ns Instruction fetch Reg ALU Data access Reg lw $3, 300($0) Program execution Time order (in instructions) lw $1, 100($0) Instruction fetch 8 ns 2 4 6 8 10 12 14 Reg ALU Data access Reg Instruction fetch 8 ns... lw $2, 200($0) 2 ns Instruction fetch Reg ALU Data access Reg lw $3, 300($0) 2 ns Instruction fetch Reg ALU Data access Reg 2 ns 2 ns 2 ns 2 ns 2 ns llxx@ustc.edu.cn 86
单周期实现 vs. 流水线性能 (con t) 例 : 设 E=2ns,ALU 和加法器 =2ns, Reg=1ns, 其他部件没有延时 单周期 : 按执行时间最长的指令定时,8ns 执行 3 条指令所需的时间为 8ns 3=24ns 第 4 条指令与第 1 条指令之间的时间间隔 =8ns 3=24ns 流水线段, 按操作时间最长的阶段定义,2ns 执行 3 条指令所需的时间为 2ns 5+2ns+2ns=14ns 第 4 条指令与第 1 条指令之间的时间间隔 =2ns 3=6ns 性能提升 按照 3 条指令的总执行时间,2 倍 按照时间间隔,4 倍 注意, 不是 加速比, 加速比指非流水线实现与流水线实现比较 llxx@ustc.edu.cn 87
流水线中的多发技术 目的 : 在一个时钟周期 ( 机器周期?) 内流出多条指令 理想流水线 IPC=1, 能否使 IPC > 1 常见的多发技术 (multiple issue) 超标量技术 超长指令字技术 超流水线技术 (superpipeline) llxx@ustc.edu.cn 88
超标量技术 ( superscalar ) 在任一时刻取指并执行一条指令的简单的处理器被称为 简单标量处理器 超标量 : 指在每个时钟周期内可同时发射并执行多条指令 系统结构要求 : 处理机中配置多个功能部件和指令译码电路, 以及多个寄存器端口和总线, 以便能实现同时执行多个操作 编译器要求 : 决定哪几条相邻指令可并行执行 llxx@ustc.edu.cn 89
A Two-Way Superscalar Pipeline
IPS 多发射 : 两个通路不对称性 40000040 u x u x 4 ALU PC Instruction memory Registers u x Write data Data memory Sign extend Sign extend ALU Address u x 图 4-69 2003.6.1 llxx@ustc.edu.cn 91
Four-Deep Superpipeline
超长指令字技术 VLIW 把多条能并行操作的指令组合成一条具有多个操作码字段的超长指令 ( 指令字长可达几百位 ), 由这条超长指令控制 VLIW 机中多个独立工作的功能部件, 由每一个操作码字段控制一个功能部件, 相当于同时执行多条指令 超长指令字 (VLIW) 技术和超标量技术都是采用多条指令在多个处理部件中并行处理的体系结构, 在一个时钟周期内能流出多条指令 llxx@ustc.edu.cn 93
四种流水技术比较 llxx@ustc.edu.cn 94
HT 技术 coarse-grain multithreading,block ultithreading
RISC 技术的应用 按照设计技术的差异, 可将 RISC 产品分四类 : IB 公司的 801 小型计算机 采用紧藕合硬件技术和优化编译技术 Berkeley 的 RISC-I RISC-II:Patterson 柏克利分校分别于 1982 年和 1984 年研制的两种 32 位 RISC 微处理器 Stanford 的 IPS R2000 R3000 和 R4000 :Hennessy,1983 克雷公司的 CRAY-I CRAY-I 被认为是 RISC 技术的先驱 典型产品 IB 公司的 Power PC HP 的 PA 系列属 IB801 结构 ; IPS 公司的 Rx000 基本属斯坦福大学的 IPS 结构 ; R3000,32 位 ( 浮点协处理器 R3010);R4000,64 位 (8 级超流水线 ) Intel 公司的 i80860 属 CRAY-I 结构 Sun 公司的 SPARC 微处理器芯片 ( 基于 RISC-I 和 RISC-II) AR 公司的 AR 嵌入式微处理器 90 年代 Intel 抛弃了 x86 结构, 采用具有 RISC 特点的 Pentium 结构
IPS R4000: 多种 EX 部件
IB Power5 超标量 OOO 2003.6.1 llxx@ustc.edu.cn 98
Pentium4 处理器 外特性 : 一种传统的 CISC 处理器 具有数量众多但使用不方便的指令集 支持 8 16 32 位整数操作和 32 64 位浮点操作 只有 8 个可见的寄存器, 而且他们还各不相同 指令长度也长短不一 (1 字节到 17 字节 ) 内部实现 : 具有现代 精简高效 深度流水的 RISC 内核 2003.6.1 llxx@ustc.edu.cn 99
Pentium4 流水线微体系结构 ALU1 能够完成所有的算术和逻辑操作以及分支操作 ALU2 只能够完成加法 减法 移位和循环移位指令 第一个浮点单元能够完成移动和 SSE 指令 第二个浮点单元能完成浮点数运算 X 指令和 SSE 指令 2003.6.1 llxx@ustc.edu.cn 100
Summary ISA 的实现模式 单周期 : 指令周期 ( 定长 ) 由一个机器周期组成 多周期 : 指令周期 ( 变长 ) 由多个机器周期组成 每个功能部件分别参与不同机器周期的执行 ; 功能部件可以在不同周期中复用 ; 流水线中 : 指令周期 ( 变长 ) 由多个机器周期 ( 流水级 ) 组成, 每个功能部件仅完成各自指令的特定阶段的执行 ; 畅流 : 资源充分, 作业均衡, 各行其职 提升了吞吐率 ILP CPU 设计步骤 :ISA, 数据通路, 控制器, 时钟 流水线模式中指令周期定长? R-type 指令是否可以不要访存段? 是否会出现同一 cycle 流出两条指令? 2003.6.1 llxx@ustc.edu.cn 101
小结 单周期 = 一级流水线? 流水线中实现一个周期访存 ( 取指, 取数 ) 的前提条件是什么? 流水线执行第一条指令时,IF 在取指, 其他段在做什么? 各流水段的控制信号何时生成与释放? 寻址方式如何实现的? 哪些寻址方式适合流水线? 如果 R-type 指令也可访存, 则应如何设计流水线? IPS 能否采用 取指 译码 执行 三段流水线? 各段的 stall 原因与判断规则? 如何实现 stall? stall freeze bubble flush? IPS 的 I/O 操作? IPS 模拟器 SPI ARS
作业 思考 理想流水线加速比 =?IPC=? 为何单周期 多周期的控制信号不需要 buffer, 而 流水线的控制信号需要 buffer? 哪些情形可能造成流水线 stall, 有哪些解决方案? 影响流水线性能发挥的因素有哪些, 可以采用哪些手段减小这些因素的影响? 指令流水线中在哪个阶段会产生什么相关? 为何 IPS 只有 I-type 指令访存? 典型的流水线的多发射技术有哪些? 作业 :4.12,4.13,4.16,4.18 4.20.1,4.20.2,4.21.1
llxx@ustc.edu.cn 104/94