计算机组织与系统结构 流水技术引论 Itroductio to Pipeliig ( 第十四讲 ) 程旭 29.5 rach Jump st 单周期处理器 busw Wr 5 5 Istructio Fetch Uit Rd imm6 Istr<5:> Rs 5 Rw Ra Rb -bit isters 6 <3:26> Istructio<3:> op <6:2> <2:25> bus Exteder <:5> Rd Imm6 bus ExtOp <:5> <5:> MUX fuc Src op ctr Mai Cotrol Cotrol 3 3 I st Src : Wr WrE dr ory MUX to 该单周期处理器的缺陷 时钟周期时间长 : 对于装入指令, 周期时间必须足够长 : 的 Clock -to-q + 指令存储器访问时间 + 寄存器堆访问时间 + 延迟 ( 地址计算 ) + 数据存储器访问时间 + 寄存器对建立时间 + 时钟纽斜 对于所有其他指令, 周期时间都比所需的要长很多! 多周期实现概述 单周期处理器的问题根源 : 对于最慢的指令, 周期时间必须足够长 解决方案 : 将指令处理分为更小的步骤 每个周期执行一步 ( 而不是整个指令 ) - 周期时间 : 执行最长步所需的时间 - 使所有的步骤尽量具有相同的长度 这个多周期处理器的本质所在 多周期处理器的优点 : 周期时间非常短 不同的指令需要不同的周期数来完成 - 装入需要 5 个周期 - 跳转仅仅需要 3 个周期 允许每条指令多次使用同一个功能部件
多周期处理器 在每条指令的执行过程中, 可以多次使用同一功能部件 Wr WrCod Src rwr Ior Wr Wr st Wr Sel Target Rdr Ideal ory Wrdr i out Istructio Imm Rs Rd 5 5 Exted 6 Exted ExtOp Ra Rb bus Rw busw bus << 2 to 4 2 3 Sel Cotrol Cotrol Op Out 微程序设计 精心设计的状态图易于用微序列器实现 简单地递增和转移场位 数据通路控制场位 控制设计可以简化为微程序设计 微程序设计是一个基本概念 通过建造一个非常简单地处理器, 并对指令进行解释执行, 来实现指令系统 特别适用于非常复杂的指令, 以及寄存器传输比较少的情况 微程序设计对 RISC 产生的灵感 意外事件和中断 如果简单指令能够以很高的时钟频率执行 如果人们有能力编写产生微指令的编译器 如果绝大多数程序仅仅使用简单指令和简单的寻址方式 如果微码保存在 RM 中, 而非 ROM 中, 那么就易于排错 如果用于控制存储器的同一存储器还可被用为宏指令的 cache 那么, 为什么不用微程序和可直接产生机器最低级语言的编译器来跨越指令解释器呢? 意外处理是控制部分的难点 需要找到可以保存 并激活操作系统功能的方便地方来放置检测意外事件 转移到状态或微指令 当以后我们学习支持存储访问出现页面失效的流水化 CPU 时, 由于指令不能完成, 并且恰好要在产生意外事件的指令处重启程序, 这使得控制的设计难上加难!
对控制描述进行修改 <= MEM[] <= + 4 未定义指令 教学目标 : 已经掌握的内容 R-type S <= fu <= S overflow ORi S <= op ZX R[rt] <= S <= R[rs] <= R[rt] LW S <= + M <= MEM[S] R[rt] <= M SW other S <= + MEM[S] <= EQ S <= - Equal <= + E <= - 4 <= exp_addr cause <= (RI) ~Equal 计算机的五个基本部件处理器控制数据通路 存储器 输入 输出 E <= - 4 <= exp_addr cause <= 2 (Ovf) 来自数据通路的其他条件 本讲主题 : 流水技术 流水技术的思想非常自然! 洗衣房 张三 李四 王五 赵六每人有一包衣服需要洗涤 烘干 熨整 洗衣机需要 3 分钟 烘干机需要 3 分钟 熨斗需要 3 分钟 洗衣工需要 3 分钟将衣物放到抽屉里 C 任务次序 串行洗衣店 6 PM 7 8 9 2 2 M C 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 工作时间 串行洗衣店需要 8 个小时完成 4 个工作量 如果他们了解流水技术, 那么需要多长时间完成上述工作呢?
流水化的洗衣店 : 尽可能早地开始工作 任务次序 2 2 M 6 PM 7 8 9 C 3 3 3 3 3 3 3 工作时间 任务顺序 流水技术性质 6 PM 7 8 9 时间 3 3 3 3 3 3 3 C 流水技术无助于减少单个任务的处理延迟 (latecy), 但有助于提高整体工作负载的吞吐率 多个不同任务同时操作, 使用不同资源 潜在加速比 = 流水线级数 流水线的速率受限于最慢的流水段 流水段的执行时间如果不均衡, 那么加速比就会降低 流水化洗衣店需要 3.5 个小时完成 4 个工作量 开始填充流水线的时间和最后排放流水线的时间降低加速比 相关将导致流水线暂停 装入操作的五级 Ifetch: 取指 从指令存储器中取出指令 /ec: 取操作数和译码 取寄存器和指令译码 : 执行 计算存储器的地址 : 存储器访问 从数据存储器中读取数据 Wr: 写回 将数据写回到寄存器堆 Cycle Cycle 2 Cycle 3 Cycle 4 Cycle 5 Load Ifetch /ec Wr 指令执行次序 指令执行次序 流水技术 通过增加指令吞吐率来改进性能 Lw $, ($) Lw $2, 2($) Lw $3, 3($) Lw $, ($) Lw $2, 2($) Lw $3, 3($) TE TE 2 4 6 8 2 4 6 8 取指 access 取指 2s 8s 取指 8s access 取指 8s 2 4 6 8 2 4 6 8 取指 2s access 取指 access 取指 2s 2s 2s access 2s 2s 流水线加速比等于流水线的级数?
基本思路 流水线的图形化表示 取指译码 / 取操作数执行存储器访问回写 P C +4 ddress Istrucito Istructio ory Ra Rb bus Rw busw bus Sig Exted Shift left 2 将数据通路实际划分成流水段, 需要增加什么? add result result ddress Read ory Wr 执行某段代码需要多少周期? 在某一周期, 正在做什么? 该表示有助于加强对数据通路的理解 常规流水化执行的表示 时间 IFetch cd W IFetch cd W IFetch cd W IFetch cd W IFetch cd W 程序流 IFetch cd W 单周期 多周期与流水线 Cycle Cycle 2 单周期实现 : Load Store Waste Cycle Cycle 2 Cycle 3 Cycle 4 Cycle 5 Cycle 6 Cycle 7 Cycle 8 Cycle 9 Cycle 多周期实现 : Load Store R-type Ifetch Wr Ifetch Ifetch 流水线实现 : Load Ifetch Wr Store Ifetch Wr R-type Ifetch Wr
为什么需要流水线? 假设我们需要执行 条指令 为什么需要流水线? 因为需要提高资源利用率 时间 ( 时钟周期 ) 单周期机器 45 s/cycle x CPI x ist = 45 s 多周期机器 s/cycle x 4.6 CPI (due to ist mix) x ist = 46 s 理想的流水化机器 s/cycle x ( CPI x ist + 4 cycle drai) = 4 s 指令执行次序 Ist Ist Ist 2 Ist 3 Ist 4 Im Im Im m Im m Im m m m 流水技术会产生哪些问题? 流水线冒险 (Pipelie Hazards) 结构冒险 (structural hazards): 试图同时以两种不同的方式使用同一资源 - 例如, 组合式洗衣机 / 烘干机可能产生结构冒险或者熨整工工作时偷看电视 数据冒险 (data hazards): 在产生数据之前, 就试图使用它们 - 例如, 一包衣物在洗衣机中, 另一包衣物在干衣机中, 那么就不能对这些衣物进行熨整 - 流水线中的一条指令等待使用上一条指令的结果 控制冒险 (cotrol hazards): 在判定转移条件之前, 就试图决策转移方向 - 例如, 在洗一件非常脏的衣物之前, 需要判定加多少洗衣粉 ; - 转移指令 流水技术会产生哪些问题 ( 续 )? 等待总是可以解决冒险问题 流水线控制必须检测冒险 采取必要措施 ( 或延迟等待 ) 来解决冒险
指令次序 单存储器是一种结构冒险 Load Istr Istr 2 时间 ( 时钟周期 ) 结构冒险限制性能 示例 : 如果每条指令平均访问.3 次存储器, 而每个周期只能完成一次存储器访问, 那么 平均 CPI.3 否则, 资源的利用率 > % Istr 3 Istr 4 此例中, 检测非常容易! 读 写 解决方案一 : 暂停解决单存储器结构冒险 时间 ( 时钟周期 ) 解决方案二 : 资源复置解决存储器结构冒险 分离指令 Cache (Im) 和数据 Cache (m) 时间 ( 时钟周期 ) 指 Load 指 Load M 令 Istr 令 Istr M 次序 Istr 2 次序 Istr 2 M Istr 3(stall) bubble Istr 3 M Istr 4 Istr 4 M 读 写 读 写
指 令 次 序 控制冒险的解决策略 暂停 (Stall): 等待直到决策明朗 通过增设硬件在读取寄存器的周期就对转移方向进行判定, 从而可以在第二流水段完成转移方向的判定 dd eq Load 时间 ( 时钟周期 ) 影响 : 每条转移指令需要两个时钟周期完成 => 速度慢 控制冒险的解决策略 预测 : 猜测某一转移方向, 如果猜测错误, 就用备份恢复 猜测转移不发生 指 令 次 序 dd eq Load 时间 ( 时钟周期 ) 效果 : 如果猜测正确, 每条指令一个时钟周期完成, 如果猜错每条转移指令两个周期 ( 正确率 5%) 较复杂的硬件预测 : 一条指令的历史 (( 正确率 9%) 控制冒险的解决策略 重新定义转移指令的行为 延迟转移 : 转移行为在下一条指令之后发生 时间 ( 时钟周期 ) 关于 r 的数据冒险 立即向后相关就可能出现冒险 时间 ( 时钟周期 ) IF I/RF EX MEM W add r,r2,r3 M 指 dd 指 sub r4,r,r3 M 令 次 序 eq Misc Load 影响 : 如果能够将有效指令调度到延迟槽中, 每条转移指令的完成将不占用时钟周期 ( 5% 的可能 ) 令次序 ad r6,r,r7 or r8,r,r9 xor r,r,r M M
数据冒险解决策略 从某流水段向其他流水段前递 (forward) 结果 前递或旁路 (forward or bypass): 装入指令 立即向后相关就可能出现冒险 时间 ( 时钟周期 ) IF I/RF EX MEM W 时间 ( 时钟周期 ) IF I/RF EX MEM W 指 令 次 add r,r2,r3 sub r4,r,r3 ad r6,r,r7 M M M 指令次序 lw r,(r2) sub r4,r,r3 m M 序 or r8,r,r9 xor r,r,r M 不能通过前递技术解决 必须延迟 / 暂停与装入指令相关的指令 如果适当定义读 / 写次序, 就可能正常工作 设计一个流水化的处理器 教科书上的流水化的数据通路 回顾我们设计的数据通路和控制图 将资源和状态联系起来 保证处理流程没有冲突, 或考虑出解决方案 在适当的流水段发出正确的控制信号
多周期数据通路中介绍的基本流水化的处理器 如果每周期, 开始一条新指令的处理, 会发生什么情况? Valid 控制和数据通路 [], [], +4; +4; R[rs]; R[rs]; R[rt] R[rt] Next Istructio Fetch. ex Ex mem S ccess M wb W. Equal S + + S; S; Next S or or ZX ZX R[rt] R[rt] S Istructio ory S + + M [S] [S] M S + + [S] [S] Equal S ccess If If cod cod +; +; M. Equal 流水化装入指令 Clock st lw Cycle Cycle 2 Cycle 3 Cycle 4 Cycle 5 Cycle 6 Cycle 7 Ifetch /ec Wr 2d lw Ifetch /ec Wr 3rd lw Ifetch /ec Wr 流水线数据通路中的五个独立功能部件是 : 取指段 (Ifetch) 的指令存储器 寄存器 / 译码段 (/ec ) 的寄存器堆的读端口 (bus 和 bus) 执行段 () 的 存储器段 () 段的数据存储器 回写段 (Wr) 的寄存器堆的写端口 (busw) R 型指令的四段 Cycle Cycle 2 Cycle 3 Cycle 4 R-type Ifetch /ec Wr Ifetch: 取指 从指令存储器中读取指令 /ec: 取寄存器和指令译码 : 对两个寄存器操作数执行 操作 Wr: 将 的输出回写到寄存器堆
流水化 R 型指令和装入指令 Cycle Cycle 2 Cycle 3 Cycle 4 Cycle 5 Cycle 6 Cycle 7 Cycle 8 Cycle 9 Clock R-type Ifetch /ec Wr 冒险! 出现问题! R-type Ifetch /ec Wr Load Ifetch /ec Wr R-type Ifetch /ec Wr 重要发现 每个功能部件只能被每条指令使用一次 每个功能部件必须被所有指令在相同的流水段使用 : 装入指令在它的第五级使用寄存器堆的写端口 Load Ifetch /ec Wr R-type Ifetch /ec Wr R 型指令在它的第四级使用寄存器堆的写端口 产生了流水线冲突或者结构冒险 : R-type Ifetch /ec Wr 两条指令都试图同时回写寄存器堆! 寄存器堆只有一个写入端口 有两种方法解决流水线冒险 第一种解决方案 : 在流水线中插入空泡 Cycle Cycle 2 Cycle 3 Cycle 4 Cycle 5 Cycle 6 Cycle 7 Cycle 8 Cycle 9 Clock Ifetch /ec Wr Load Ifetch /ec Wr R-type Ifetch /ec Wr R-type Ifetch /ec bubble Wr R-type Ifetch /ec Wr Ifetch /ec 在流水线中插入空泡从而避免了在同一周期出现两次写入操作 控制逻辑变得更加复杂 失去了取指和发送的机会 第二种解决方案 : 将 R 型指令的回写延迟一个周期 将 R 型指令的写寄存器操作延迟一个周期 : 现在,R 型指令也在第五段才使用寄存器堆的写端口 存储器段是一个空段 : 无所事事 2 3 4 5 R-type Ifetch /ec Wr Cycle Cycle 2 Cycle 3 Cycle 4 Cycle 5 Cycle 6 Cycle 7 Cycle 8 Cycle 9 Clock R-type Ifetch /ec Wr R-type Ifetch /ec Wr Load Ifetch /ec Wr R-type Ifetch /ec Wr 在第六周期没有任何指令启动! R-type Ifetch /ec Wr
流水化的数据通路 取指段 Locatio : lw $, x($2) $ [($2) + x] Ifetch /ec Wr Ifetch /ec Wr Wr ExtOp Op rach Wr ExtOp Op rach IUit I +4 IF/I ister +4 Imm6 Rs Rd Ra Rb R Rw i I/Ex ister +4 Imm6 bus bus Uit Ex/ ister R o W i /Wr ister IUit I +4 IF/I: lw $, ($2) +4 Imm6 Rs Rd Ra Rb R Rw i I/Ex ister +4 Imm6 bus bus Uit Ex/ ister R o W i /Wr ister st Src Wr to st Src Wr to 指令部件探秘 Locatio : lw $, x($2) 译码 / 寄存器访问段 Locatio : lw $, x($2) $ [($2) + x] Ifetch 注意这里! /ec Ifetch /ec Wr Wr ExtOp Op rach = 4 +4 ddress Istructio ory Istructio dder IF/I: lw $, ($2) IUit I +4 IF/I ister +4 Imm6 Rs Rd Ra Rb R Rw i I/Ex:. 2 & x st +4 Imm6 bus bus Uit Src Ex/ ister Wr R o W i /Wr ister to
装入指令的地址计算段 Locatio : lw $, x($2) $ [($2) + x] 执行部件探秘 Ifetch /ec Wr Op=dd IUit I +4 IF/I ister Wr +4 Imm6 Rs Ra Rd Rb R Rw i I/Ex ister ExtOp +4 Imm6 bus bus Uit Ex/ ister rach R o W i /Wr ister I/Ex ister +4 bus bus imm6 6 Exteder << 2 Target 3 Cotrol out ctr Ex/: Load 抯 ory ddress st= Src= Wr to ExtOp= Src= 3 Op=dd 装入指令的存储器访问段 Locatio : lw $, x($2) $ [($2) + x] 装入指令的回写段 Locatio : lw $, x($2) $ [($2) + x] Ifetch /ec Wr Ifetch /ec Wr Wr ExtOp Op rach= Wr= ExtOp Op rach IUit I +4 IF/I ister +4 Imm6 Rs Rd Ra Rb R Rw i I/Ex ister +4 Imm6 bus bus Uit Ex/ ister R o W i /Wr: Load s IUit I +4 IF/I ister +4 Imm6 Rs Rd Ra Rb R Rw i I/Ex ister +4 Imm6 bus bus Uit Ex/ ister R o W i /Wr ister st Src Wr= to st Src Wr to=
修改控制和数据通路 [], [], +4; +4; 存储指令的四段 Cycle Cycle 2 Cycle 3 Cycle 4 R[rs]; R[rs]; R[rt] R[rt] Store Ifetch /ec Wr S + + M S S or or ZX ZX M S S + + M [S] [S] S + + [S] [S] If If cod cod +; +; Ifetch: 取指 从指令存储器中读取指令 M; M; Next R[rt] R[rt] M Istructio ory M Equal S ccess M. Equal /ec: 取寄存器和指令译码 : 计算存储访问的地址 : 将数据写入到数据存储器 eq 指令的三段 Cycle Cycle 2 Cycle 3 Cycle 4 控制图 [], [], +4; +4; Store Ifetch /ec Wr R[rs]; R[rs]; R[rt] R[rt] Ifetch: 取指 从指令存储器中读取指令 S + + M S S or or ZX ZX M S S + + M [S] [S] S + + [S] [S] If If cod cod +; +; /ec: 取寄存器和指令译码 : 比较两个寄存器操作数 择取正确的转移目标地址 锁存到 M; M; Next R[rt] R[rt] M Istructio ory M Equal S ccess M. Equal
数据通路 + 数据固定控制 Ist. fu rt op rs rs ecode rt v rw wb me ex im v rw wb me S ccess v rw wb M W. 指令流水示例 lw r, r2(35) 4 addi r2, r2, 3 2 sub r3, r4, r5 24 beq r6, r7, 3 ori r8, r9, 7 34 add r, r, r2 Next ad r3, r4, 5 地址以八进制表示 开始 : 从地址 取指 Fetch4 并 ecode Ist. rs ecode rt im W Ist. lw r, r2(35) ecode 2 rt im W Next S ccess M. lw lw r, r, r2(35) r2(35) 4 4 addi addi r2, r2, r2, r2, 3 2 2 sub sub r3, r3, r4, r4, r5 r5 24 24 beq beq r6, r6, r7, r7, 3 3 ori ori r8, r8, r9, r9, 7 7 34 34 add add r, r, r, r, r2 r2 Next S 4 ccess M. lw lw r, r, r2(35) r2(35) 4 4 addi addi r2, r2, r2, r2, 3 2 2 sub sub r3, r3, r4, r4, r5 r5 24 24 beq beq r6, r6, r7, r7, 3 3 ori ori r8, r8, r9, r9, 7 7 34 34 add add r, r, r, r, r2 r2 ad ad r3, r3, r4, r4, 5 5 ad ad r3, r3, r4, r4, 5 5
Fetch2 并 ecode 4 并 Fetch24 并 ecode2 并 4 并 Ist. addi r2, r2, 3 ecode 2 rt lw r 35 r2 Next S 2 ccess M W. lw lw r, r, r2(35) r2(35) 4 4 addi addi r2, r2, r2, r2, 3 2 2 sub sub r3, r3, r4, r4, r5 r5 24 24 beq beq r6, r6, r7, r7, 3 3 ori ori r8, r8, r9, r9, 7 7 34 34 add add r, r, r, r, r2 r2 Ist. sub r3, r4, r5 ecode 4 5 addi r2 3 r2 Next 24 r2+35 lw r ccess M W. lw lw r, r, r2(35) r2(35) 4 4 addi addi r2, r2, r2, r2, 3 2 2 sub sub r3, r3, r4, r4, r5 r5 24 24 beq beq r6, r6, r7, r7, 3 3 ori ori r8, r8, r9, r9, 7 7 34 34 add add r, r, r, r, r2 r2 ad ad r3, r3, r4, r4, 5 5 ad ad r3, r3, r4, r4, 5 5 Fetch3 并 ecode24 并 2 并 4 并 W Fetch34 并 ecode3 并 24 并 2 并 W4 Ist. beq r6, r7 ecode 6 7 sub r3 r4 r5 Next addi r2 R2+3 3 ccess lw r M[r2+35] W. lw lw r, r, r2(35) r2(35) 4 4 addi addi r2, r2, r2, r2, 3 2 2 sub sub r3, r3, r4, r4, r5 r5 24 24 beq beq r6, r6, r7, r7, 3 3 ori ori r8, r8, r9, r9, 7 7 34 34 add add r, r, r, r, r2 r2 Ist. ori r8, r9 7 ecode 9 xx beq r6 r7 Next sub r3 r4-r5 34 ccess addi r2 r2+3 W. r=m[r2+35] lw lw r, r, r2(35) r2(35) 4 4 addi addi r2, r2, r2, r2, 3 2 2 sub sub r3, r3, r4, r4, r5 r5 24 24 beq beq r6, r6, r7, r7, 3 3 ori ori r8, r8, r9, r9, 7 7 34 34 add add r, r, r, r, r2 r2 ad ad r3, r3, r4, r4, 5 5 ad ad r3, r3, r4, r4, 5 5
Fetch 并 ecode34 并 3 并 24 并 W2 Fetch4 并 ecode 并 34 并 3 并 W24 Ist. add r, r, r2 ecode 2 ori r8 7 r9 X Next XXX beq ccess sub r3 R4-r5 W. r=m[r2+35] r2 = r2+3 lw lw r, r, r2(35) r2(35) 4 4 addi addi r2, r2, r2, r2, 3 2 2 sub sub r3, r3, r4, r4, r5 r5 24 24 beq beq r6, r6, r7, r7, 3 3 ori ori r8, r8, r9, r9, 7 7 34 34 add add r, r, r, r, r2 r2 Ist. ad r3, r4, r5 ecode 4 5 add r xx r r2 Next ori r8 r9 7 4 ccess beq xxx W. r=m[r2+35] r2 = r2+3 r3 = r4-r5 lw lw r, r, r2(35) r2(35) 4 4 addi addi r2, r2, r2, r2, 3 2 2 sub sub r3, r3, r4, r4, r5 r5 24 24 beq beq r6, r6, r7, r7, 3 3 ori ori r8, r8, r9, r9, 7 7 34 34 add add r, r, r, r, r2 r2 ad ad r3, r3, r4, r4, 5 5 ad ad r3, r3, r4, r4, 5 5 Fetch 并 ecode4 并 并 34 并 W3 Ist. ecode ad r3 xx r4 r5 Next add r R+r2 ccess ori r8 r9 7 W. r=m[r2+35] r2 = r2+3 r3 = r4-r5 lw lw r, r, r2(35) r2(35) 4 4 addi addi r2, r2, r2, r2, 3 2 2 sub sub r3, r3, r4, r4, r5 r5 24 24 beq beq r6, r6, r7, r7, 3 3 ori ori r8, r8, r9, r9, 7 7 34 34 add add r, r, r, r, r2 r2 Fetch4 并 cd 并 4 并 并 W34 Ist. ecode Next ad r3 r4 & R5 4 ccess add r R+r2 W. NO W NO Ovflow r=m[r2+35] r2 = r2+3 r3 = r4-r5 r8 = r9 7 lw lw r, r, r2(35) r2(35) 4 4 addi addi r2, r2, r2, r2, 3 2 2 sub sub r3, r3, r4, r4, r5 r5 24 24 beq beq r6, r6, r7, r7, 3 3 ori ori r8, r8, r9, r9, 7 7 34 34 add add r, r, r, r, r2 r2 Squash the extra istructio i the brach shadow! ad ad r3, r3, r4, r4, 5 5 Squash the extra istructio i the brach shadow! ad ad r3, r3, r4, r4, 5 5
总结 总结 哪些策略使得流水容易实现? 所有的指令长度相同 只有少量的指令格式 Ld/St 结构 我们将建造一条简单的流水线, 并考虑上述因素 我们将讨论现代微处理器, 并分析它的真正难点 : 意外事件处理 利用乱序执行等技术改进性能 哪些方面使得流水线难以实现? 结构冒险 : 假设我们只有一个存储器 控制冒险 : 需要考虑转移指令 数据冒险 : 一条指令依赖于上一条指令的结果