计算机体系结构 week6 浙江大学 石教英 陈天洲(主讲)

1、u第第 6 6 周周 第第 1 1 节课节课 u授课教师：授课教师： 陈天洲陈天洲 u课件下载课件下载 http:/ 非流水线实现的非流水线实现的DLX u一条指令一条指令5个时钟周期个时钟周期 u一个流水级一个流水级 花一个时钟周期花一个时钟周期 u每个时钟周期启动一条指令每个时钟周期启动一条指令 关键：同一时钟周期里，不同指令不会使用同一数据通路关键：同一时钟周期里，不同指令不会使用同一数据通路 资源资源 uIM 与与DM不能用单一不能用单一memory IM：指令：指令Cache DM：数据：数据Cache 存储器带宽要提高存储器带宽要提高5倍倍 2次次 /5个时钟周期个时钟周期 2次次

2、/1个时钟周期个时钟周期 u ID的读的读Reg 与与WB的写的写Reg 2个个Reg读读 + 1个个Reg写写 / 时钟周期时钟周期 2个读口，一个写口个读口，一个写口 Reg 读读 = Reg写写 数据竞争数据竞争 uPC 非流水：非流水： IF读读PC，MEM写写PC 流水：流水： IF完成完成 PC+4 PC 前面的前面的Branch指令可能要写指令可能要写PC u流水线锁存器（在两级之间传递值和控制信号）流水线锁存器（在两级之间传递值和控制信号） 某一值在后续流水级中要用到，就必须送入某一值在后续流水级中要用到，就必须送入Latch 如：如：IF/ID中有中有IR ID中要译码中要译

3、码 MEM/WB中有中有IR ALU（IR16.20） 或或Load（ IR11.15）的目的域段的目的域段 ID/EX中有中有IR uALU： PC增值增值 1个个Adder 算术逻辑部件算术逻辑部件 ALU不访存不访存 有效地址计算有效地址计算 访存指令不做访存指令不做ALU操作操作 1个个 ALU u控制信号（控制信号（ MUX） 1. EX级的级的MUX： 由指令类型控制由指令类型控制 是：是： NPC ALU 是是Branch？ 否：否：IR6.10 ALU 是：是： IR11.15 ALU 是是R-R ALU指令？指令？ 否：立即数否：立即数/位移量位移量 ALU 2. IF级的级

4、的MUX： 由由Cond判断控制判断控制 3. WB级的级的MUX： 由指令类型控制（由指令类型控制（ Load/ALU) 4. ALU级的级的MUX：由指令类型控制由指令类型控制 ALU R-R（ IR11.15 ） ALU R-I （ IR16.20 ） 五级流水线的每一级的具体操作五级流水线的每一级的具体操作 ( P136) 提高吞吐率，但不减少单条指令的执行时间提高吞吐率，但不减少单条指令的执行时间 程序执行快，总时间减少程序执行快，总时间减少 理想理想Speedup = 流水级数流水级数 流水级数的限制：流水级数的限制： u 流水线延时流水线延时 u流水线开销（流水周期流水线开销（流

5、水周期 latch开销开销+时钟上升沿和时钟上升沿和 下降沿）下降沿） u流水级间的不平衡性流水级间的不平衡性 t = maxti latch： 对时钟上升延敏感、对时钟上升延敏感、latch延时是常数、可在延时是常数、可在latch中中 实现二级逻辑实现二级逻辑 unpipeline: CC=10ns, ALU(40%)、Branch(20%) 4CC Load/Store (40%) 5CC pipeline CC = (10+1) = 11ns 问：用流水线，执行速度提高几倍？问：用流水线，执行速度提高几倍？ 单条指令执行时间单条指令执行时间 = CC 平均平均CPI = 10 （60%

6、 4 + 40% 5）= 44ns 平均指令执行时间平均指令执行时间 CCpipeline = 11ns Speedup = 44 /11 = 4 已知已知CPI=1。设各流水级的执行时间分别为：。设各流水级的执行时间分别为： IF：10ns；ID：8ns；ALU：10ns；MEM：10ns WB：7ns 平均指令执行时间平均指令执行时间 = 10+8+10+10+7 = 45ns 流水线时平均指令执行时间流水线时平均指令执行时间 = 11ns Speedup = 45/11 = 4.1 一、流水线竞争种类一、流水线竞争种类 u结构竞争：资源冲突（不支持某些指令组合）结构竞争：资源冲突（不支持

7、某些指令组合） u数据竞争：后续指令的执行依赖于前面指令的数据竞争：后续指令的执行依赖于前面指令的 执行结果执行结果 u控制竞争：因转移或修改控制竞争：因转移或修改PC引起的竞争引起的竞争 流水线停顿流水线停顿(stall)：若若 i 指令引起竞争，在指令引起竞争，在 i 指指 令之前进入流水线的指令继续执行，而在令之前进入流水线的指令继续执行，而在 i指指 令之后进入流水线或尚未进入流水线的指令停令之后进入流水线或尚未进入流水线的指令停 下来等待竞争消除下来等待竞争消除 平均指令执行时间平均指令执行时间unpipeline Speedup = - 平均指令执行时间平均指令执行时间pipeli

8、ne CPIun *CCun = - CPIp * CCp CPI pipeline = CPI ideal + 流水线流水线stall周期周期 = 1 + 流水线流水线stall周期周期 CPIun CPIun Speedup = - = - CPIp 1+流水线流水线stall周期周期 最简单情况：最简单情况： 所有指令的执行周期数相等，均为所有指令的执行周期数相等，均为 流水级数流水级数 CPIun = 流水级流水级 流水级流水级 Speedup = - 1+流水线流水线stall周期周期 1 CCun Speedup = - * - 1+流水线流水线stall周期周期 CCp 若流水线

9、各级完成时间均衡，且无其他开销，则若流水线各级完成时间均衡，且无其他开销，则 CCun - = 流水级流水级 CCp 流水级流水级 Speedup = - 1+流水线流水线stall周期周期 如果流水线因资源冲突不能支持某些指令组如果流水线因资源冲突不能支持某些指令组 合的重叠执行，则称之为结构竞争。合的重叠执行，则称之为结构竞争。 u原因原因 u功能部件非完全流水功能部件非完全流水 u硬件资源数量不足硬件资源数量不足 结构竞争例结构竞争例 结构竞争解决办法结构竞争解决办法 已知已知CPIideal = 1，数据访存占，数据访存占40%， CRhazard = 1.05 CRideal 平均指

10、令执行时间平均指令执行时间 = IC* CPIhazard * CChazard = IC*（1+0.4*1）*CCideal/1.05 = 1.3 *IC*CCideal CPI ideal CPI hazard 设计有设计有hazard机器的原因：机器的原因： u降低成本降低成本 u降低部件延时降低部件延时 非流水不见延时非流水不见延时 不完全流水部件不完全流水部件 14% （2）最坏情况：分布最不均匀）最坏情况：分布最不均匀 因结构竞争造成因结构竞争造成CPI增加：增加：14%*5 = 0.7 （3）实测结果：用流水线实现仅使执行时间减）实测结果：用流水线实现仅使执行时间减 少少3% u

11、浮点乘法使用频度低浮点乘法使用频度低 u因数据竞争引起的因数据竞争引起的Stall避免了结构竞争避免了结构竞争 一、原因一、原因 流水实现时的读写顺序流水实现时的读写顺序 非流水时的读写顺序非流水时的读写顺序 例例 ADD R1, R2, R3 SUB R4, R5, R1 AND R6, R1, R7 OR R8, R1, R9 XOR R10, R1, R11 指令流水执行状态图指令流水执行状态图 147/146 u插入插入Stall -极大地降低流水线的效率极大地降低流水线的效率 u寄存器读写小技巧：前半周期：写；后半周期：读寄存器读写小技巧：前半周期：写；后半周期：读 u旁路技术旁路技

12、术（forwarding, bypassing, short-circuiting) 注意：注意：ADD结果在结果在EX级之后就有了（级之后就有了（CC3) SUB真正需要真正需要R1的值是在的值是在EX级级(CC4) forwarding: EX/MEM中中ALU的结果反馈给的结果反馈给ALU的输入端的输入端 若硬件检测到前面指令的目的若硬件检测到前面指令的目的Reg是当前是当前ALU指指 令的源令的源Reg，则把旁路，则把旁路 结果作为结果作为ALU的输入。的输入。 一般一般forwarding 通路：通路： 功能部件功能部件 i 的的结果输出口的的结果输出口 需要该结果的功需要该结果的功

13、 能部件能部件 j 的入口的入口 提供数据提供数据 需要数据需要数据 ALU/MEM ALU MEM/WB DM =0检测电路检测电路 例例 引入引入forwarding消除竞争带来的消除竞争带来的stall 指令间有依赖关系，且间距较近，重叠执行引起操作数指令间有依赖关系，且间距较近，重叠执行引起操作数 访问顺序发生变化访问顺序发生变化 u 寄存器操作数相关寄存器操作数相关 u 存储器操作数存储器操作数 u先写后读竞争先写后读竞争(RAW)： 指令指令 i 写写Rx，指令，指令 j= i+n 读读Rx u写写竞争（写写竞争（WW）：）： 指令指令 i 写写Rx，指令，指令 j= i+n 写写

14、Rx u先读后写竞争先读后写竞争(WAR)： 指令指令 i 读读Rx，指令，指令 j= i+n 写写Rx （152 / 150） LW R1,0（R2） IFIDEXMEM 1 MEM 2 WB ADD R1,R2,R3 IFIDEXWB 写写数据竞争写写数据竞争 SW R1,0（R2）IFIDEXM E M 1 M E M 2 WB ADD R2,R3,R4 IFIDEXWB 先读后写数据竞争先读后写数据竞争 例例 LW R1，0（R2） SUB R4，R1，R5 AND R6，R1，R7 OR R8，R1，R9 指令流水执行状态图指令流水执行状态图 内锁电路：检测竞争，并暂停流水线直到竞争

15、消除内锁电路：检测竞争，并暂停流水线直到竞争消除 插入插入Stall消除消除Load引起的竞争引起的竞争 LW R1,0 （R1） IFIDEXM E M WB SUB R4,R1,R5 IFIDEXM E M WB AND R6,R1,R7 IFIDEXM E M WB OR R8,R1,R9 IFIDEXM E M WB LW R1,0 （R1） IFIDEXM E M WB SUB R4,R1,R5 IFIDstallEXM E M WB AND R6,R1,R7 IFstallIDEXM E M WB OR R8,R1,R9 stallIFIDEXM E M WB Load指令的使用频

16、度是指令的使用频度是30%，且，且Load后面的指令有后面的指令有50 运行时间是执行依赖于运行时间是执行依赖于Load的指令。若竞争产生一个的指令。若竞争产生一个 时钟周期的延时（只需插入一个时钟周期的延时（只需插入一个Stall），理想机器），理想机器 （CPI=1）比有）比有Stall的机器快多少（不考虑其他的机器快多少（不考虑其他Stall） ？ 实际实际CPI = 70% *1 + 30% * （50%*1 + 50%*2） =0.7 + 0.45 = 1.15 理想机器快理想机器快15%。 避免在一条避免在一条LW指令之后立即出现一条使用指令之后立即出现一条使用LW指令指令 目的目

17、的Reg的指令的指令 Load Rx， Data OP ， ，Rx 基本模块：除第一条或最后一条指令外，不含基本模块：除第一条或最后一条指令外，不含 转入或转出该段代码的指令序列转入或转出该段代码的指令序列 画出依赖图画出依赖图 重排指令使重排指令使Stall最少最少 LW R1,B IFIDEXM E M WB LW R2,C IFIDEXM E M WB ADD R3,R1,R2 IFIDstallEXM E M WB SW A,R3 IFstallIDEXM E M WB 图图4-22 A=B+C的代码序列的代码序列 LW Rb， b LW Rc， c ADD Ra，Rb，Rc SW a

18、， Ra LW Re， e LW Rf， f SUB Rd，Re，Rf SW d， Rd 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 图 编译调度的作用 54% 42% 65% 31% 14% 25% 0% 10% 20% 30% 40% 50% 60% 70% GCCSpiceTex UnsanduiedScheduied 指令发射（指令发射（ issue）：让指令从）：让指令从ID级进入级进入EX级级 u在在ID级检测是否有数据竞争，若存在竞争，或在级检测是否有数据竞争，若存

19、在竞争，或在 发射前就暂停该指令进入发射前就暂停该指令进入EX级，或确定用哪条级，或确定用哪条 forwarding path,发出响应控制信号。发出响应控制信号。 (158,154) u插入插入Stall：ID/EX寄存器置寄存器置0 IF/ID锁存器内容回送锁存器内容回送IF/ID u如何确定如何确定forwarding path -组合逻辑组合逻辑(160,155) 图图 输入口为输入口为ALUin的的forwarding path (161,156) 表4-2 Load引起数据竞争的几种情况 操作数相关性操作数相关性代码序列举例代码序列举例处理方式处理方式 操作数不相关。 LW R1,

20、45（R2） ADD R5,R6,R7 SUB R8,R6,R7 OR R9,R6,R7 无竞争。后序三条指令不立即 使用R1操作数。 操作数相关。需插入 Stall。 LW R1,45（R2） ADD R5,R1,R7 SUB R8,R6,R7 OR R9,R6,R7 比较检测R1操作数和ADD指 令相关,插入Stall延时ADD指 令进入EX级。 操作数相关。需旁路机 构。 LW R1,45（R2） ADD R5,R6,R7 SUB R8,R1,R7 OR R9,R6,R7 比较检测LW指令的操作数R1 和SUB指令相关,旁路机构及时 将LW指令的操作结果直接送 至ALU的输入端,供SUB

21、进入 EX级使用。 操作数相关。可用指令 调度避免。 LW R1,45（R2） ADD R5,R6,R7 SUB R8,R6,R7 OR R9,R1,R7 无需任何相应。OR指令读R1 操作数在ID级的后半拍,LW写 结果在WB级的前半拍。 ID/EX级流水寄存 器的代码段 （ID/EX.IR0.5） IF/ID级流水寄存器 的代码段 （IF/ID.IR0.5） 相应流水寄存器操 作数段匹配传输 Loadr-r ALU操作ID/EX.IR11.15=ID/ EX.IR6.10 Loadr-r ALU操作ID/EX.IR11.15=ID/ EX.IR11.15 LoadLoad,store,ALU立即 数或转移 ID/EX.IR11.15=ID/ EX.IR6.10 控制竞争造成的性能损失比数据竞争大控制竞争造