高等计算机系统结构 指令级并行处理 ( 第二讲 ) 程旭 2010 年 3 月 29 日 复习 : 三种数据冒险 对于执行如下类型的指令序列 : r k (r i ) op (r j ) 真数据相关 (True Data-dependence) r 3 (r 1 ) op (r 2 ) Read-after-Write r 5 (r 3 ) op (r 4 ) (RAW) hazard 反相关 (Anti-dependence) r 3 (r 1 ) op (r 2 ) Write-after-Read r 1 (r 4 ) op (r 5 ) (WAR) hazard 输出相关 (Output-dependence) r 3 (r 1 ) op (r 2 ) Write-after-Write r 3 (r 6 ) op (r 7 ) (WAW) hazard 数据冒险示例 dest src1 src2 I 1 DIVD f6, f6, f4 I 2 LD f2, 45(r3) I 3 MULTD f0, f2, f4 复杂指令流水线 IF ID Issue WB Fadd GPR s FPR s ALU Fmul Mem I 4 DIVD f8, f6, f2 I 5 SUBD f10, f0, f6 I 6 ADDD f6, f8, f2 先写后读冒险 (RAW Hazards) 先读后写冒险 (WAR Hazards) 写写冒险 (WAW Hazards) Fdiv 为了追求更高性能, 流水线变得更加复杂, 这是因为 : 流水化浮点部件的长时延 多功能和存储部件 具有可变访问时间的存储系统 精确中断
复杂按序指令流水线 复杂指令流水线 PC Inst. Data Mem D Decode GPRs X1 + X2 Mem X3 W ALU Mem g 延迟回写 (Delay writeback) 以确保所有操作到 W 级都具有相同的时延 = 写端口不可被复用 ( 每个周期只有一条指令进入 一条指令流出 ) = 指令按序提交, 简化了精确中断的实现 FPRs X1 X2 Fadd X3 X2 Fmul X3 W Commit Point IF ID Issue WB GPR s FPR s Fadd Fmul 如何避免由于不断增加的回写时延, 而不要导致单周期整数操作变慢? 旁路 (Bypassing) FDiv X2 Unpipelined divider X3 如何解决写冒险, 而不需要均分所有流水级, 并不要旁路电路? Fdiv 何时可以安全地发射一条指令? 假设有一个统一的数据结构跟踪记录在所有功能部件中的所有指令状态 在发射级分发 (dispatch) 一条指令之前, 需要完成如下检查 : 所需功能部件是否可用? 输入数据是否可用? RAW? 写目的操作数是否安全? WAR? WAW? 是否在 WB 级会出现结构冒险? 硬件策略 : 指令并行 g 为什么需要硬件在运行时支持? = 在编译时有些相关情况不能真正判定 = 简化编译处理 = 针对某一机器产生的代码可以在另一机器上有效运行 g g 核心思路 : 允许暂停之后的指令被处理 DIVD ADDD F0,F2,F4 F10,F0,F8 SUBD F12,F8,F14 = 允许乱序 (out-of-order) 执行 => 乱序完成 = 在 1963 年的 CDC 6600 机器中,ID 段检测结构冒险和记分板 (Scoreboard) 数据 核心思路 : 寄存器换名 DIVD F0,F2,F4 DIVD F0,F2,F4 ADDD F10,F0,F8 ADDD F10,F0,F8 SUBD F0,F8,F14 SUBD F100,F8,F14 MULD F6,F10,F0 MULD F6,F10,F100 = 消除 WAR 和 WAW 冒险
Branch Unit Load/ Store Unit MMU 超标量处理器的内部部件 Instruction Issue Unit Floating- Point Unit(s) Floating- Point Registers I-cache BHT D-cache BTAC Instruction Fetch Unit Instruction Decode and Register Rename Unit Integer Unit(s) General Purpose Registers MMU Instruction Buffer Reorder Buffer Retire Unit Rename Registers Bus Interface Unit 32 (64) Data Bus 32 (64) Address Bus Control Bus 取指 译码和换名 超标量流水线 指令窗口 发射 执行执行执行执行 g 按序将指令递交到乱序执行的内核! 退离和回写 支持按序发射指令的记分板技术 Scoreboard for In-order Issues Busy[FU#] : a bit-vector to indicate FU s availability. (FU = Int, Add, Mult, Div) These bits are hardwired to FU's. WP[reg#] : a bit-vector to record the registers for which writes are pending. These bits are set to true by the Issue stage and set to false by the WB stage Issue checks the instruction (opcode dest src1 src2) against the scoreboard (Busy & WP) to dispatch FU available? RAW? WAR? WAW? Busy[FU#] WP[src1] or WP[src2] cannot arise WP[dest] 硬件策略 : 指令并行 ( 续一 ) g 乱序执行分解 ID 段 : 1. Issue decode instructions, check for structural hazards 2. Read operands wait until no data hazards, then read operands g 只要指令同时满足上述两个条件, 记分板就允许该指令执行, 而无需等待前面的指令完成 g CDC 6600: = 按序发射 = 乱序执行 = 乱序提交 (commit) ( 也就是完成 [completion])
CDC 6600 logic gates C D C 6 6 0 0 结构简图 记分板体系结构 记分板的含义 g 乱序完成 => WAR, WAW 冒险? Registers FP Mult FP Mult FP Divide FP Add Integer Functional Units g 对 WAR 的解决方案 = 排队等待操作以及它们操作数的拷贝 = 只在读操作段才读取寄存器 g 对 WAW 的解决方案, 必须检测冒险 : 暂停等待到其他指令完成 g 在执行阶段可能有多个指令 => 设置多个执行部件或者流水化执行部件 g 记分板跟踪相关 状态或操作 g 记分板用四个流水段代替 ID EX WB 三段 SCOREBOARD Memory
记分板控制的四级 1. Issue decode instructions & check for structural hazards (ID1) If a functional unit for the instruction is free and no other active instruction has the same destination register (WAW), the scoreboard issues the instruction to the functional unit and updates its internal data structure. If a structural or WAW hazard exists, then the instruction issue stalls, and no further instructions will issue until these hazards are cleared. 2. Read operands wait until no data hazards, then read operands (ID2) A source operand is available if no earlier issued active instruction is going to write it, or if the register containing the operand is being written by a currently active functional unit. When the source operands are available, the scoreboard tells the functional unit to proceed to read the operands from the registers and begin execution. The scoreboard resolves RAW hazards dynamically in this step, and instructions may be sent into execution out of order. 记分板控制的四级 ( 续一 ) 3. Execution operate on operands (EX) The functional unit begins execution upon receiving operands. When the result is ready, it notifies the scoreboard that it has completed execution. 4. Write result finish execution (WB) Once the scoreboard is aware that the functional unit has completed execution, the scoreboard checks for WAR hazards. If none, it writes results. If WAR, then it stalls the instruction. Example: DIVD ADDD SUBD F0,F2,F4 F10,F0,F8 F8,F8,F14 CDC 6600 scoreboard would stall SUBD until ADDD reads operands 记分板的三个主要组成部分 1. Instruction status which of 4 steps the instruction is in 记分板流水线控制的细节 2. Functional unit status Indicates the state of the functional unit (FU). 9 fields for each functional unit Busy Indicates whether the unit is busy or not Op Operation to perform in the unit (e.g., + or ) Fi Destination register Fj, Fk Source-register numbers Qj, Qk Functional units producing source registers Fj, Fk Instruction status Issue Read operands Execution complete Wait until Not busy (FU) and not result(d) Rj and Rk Functional unit done Bookkeeping Busy(FU) yes; Op(FU) op; Fi(FU) `D ; Fj(FU) `S1 ; Fk(FU) `S2 ; Qj Result( S1 ); Qk Result(`S2 ); Rj not Qj; Rk not Qk; Result( D ) FU; Rj No; Rk No Rj, Rk Flags indicating when Fj, Fk are ready 3. Indicates which functional unit will write each register, if one exists. Blank when no pending instructions will write that register Write result f((fj( f ) Fi(FU) or Rj( f)=no) & (Fk( f ) Fi(FU) or Rk( f )=No)) f(if Qj(f)=FU then Rj(f) Yes); f(if Qk(f)=FU then Rj(f) Yes); Result(Fi(FU)) 0; Busy(FU) No
记分板示例 Instruction j k Issue operands complete Result ADD: 2 cycles LD MULTD F0 F6 F2 34+ R2 F4 LD SUBDF8 F2 F6 45+ R3 F2 Mult: 10 cycles Divd: 40 cycles Time Name Busy Op Fi Fj Fk Qj Qk Rj Rk FU 记分板示例第一个周期 Instruction j k Issue operands complete Result LD F6 34+ R2 1 LD F2 45+ R3 MULTD F0 F2 F4 SUBDF8 F6 F2 Integer Yes Load F6 R2 Yes 1 FU Integer 记分板示例第二个周期 LD F6 34+ R2 1 2 LD F2 45+ R3 Issue 2nd LD? MULTD F0 F2 F4 SUBDF8 F6 F2 Integer Yes Load F6 R2 Yes 2 FU Integer 记分板示例第三个周期 LD F6 34+ R2 1 2 3 LD F2 45+ R3 MULTD F0 F2 F4 SUBDF8 F6 F2 Integer Yes Load F6 R2 No 3 FU Integer Issue MULT?
记分板示例第四个周期 LD F2 45+ R3 MULTD F0 F2 F4 SUBDF8 F6 F2 4 FU 记分板示例第五个周期 LD F2 45+ R3 5 MULTD F0 F2 F4 SUBDF8 F6 F2 Integer Yes Load F2 R3 Yes 5 FU Integer 记分板示例第六个周期 LD F2 45+ R3 5 6 MULTD F0 F2 F4 6 ADD: 2 cycles Mult: 10 cycles SUBDF8 F6 F2 Divd: 40 cycles Integer Yes Load F2 R3 Yes Mult1 Yes Mult F0 F2 F4 Yes 6 FU Mult1Integer 记分板示例第七个周期 LD F2 45+ R3 5 6 7 MULTD F0 F2 F4 6 SUBDF8 F6 F2 7 Integer Yes Load F2 R3 No Mult1 Yes Mult F0 F2 F4 Yes Add Yes Sub F8 F6 F2 IntegerYes No 7 FU Mult1Integer Add Read multiply operands?
记分板示例第 8a 个周期 ( 前半个周期 ) LD F2 45+ R3 5 6 7 MULTD F0 F2 F4 6 SUBDF8 F6 F2 7 Integer Yes Load F2 R3 No Mult1 Yes Mult F0 F2 F4 Yes Add Yes Sub F8 F6 F2 IntegerYes No 8 FU Mult1Integer Add Divide 记分板示例第 8b 个周期 ( 后半个周期 ) MULTD F0 F2 F4 6 SUBDF8 F6 F2 7 Mult1 Yes Mult F0 F2 F4 Yes Yes Add Yes Sub F8 F6 F2 Yes Yes 8 FU Mult1 Add Divide 记分板示例第九个周期 ADD: 2 cycles Mult: 10 cycles SUBDF8 F6 F2 7 9 Divd: 40 cycles 10 Mult1 Yes Mult F0 F2 F4 Yes Yes 2Add Yes Sub F8 F6 F2 Yes Yes 9 FU Mult1 Add Divide Read operands for MULT & SUBD? Issue ADDD? 记分板示例第十个周期 ADD: 2 cycles Mult: 10 cycles SUBDF8 F6 F2 7 9 Divd: 40 cycles 9Mult1 Yes Mult F0 F2 F4 No No 1Add Yes Sub F8 F6 F2 No No 10 FU Mult1 Add Divide
记分板示例第十一个周期 ADD: 2 cycles Mult: 10 cycles SUBDF8 F6 F2 7 9 11 Divd: 40 cycles 8Mult1 Yes Mult F0 F2 F4 No No 0Add Yes Sub F8 F6 F2 No No 11 FU Mult1 Add Divide 记分板示例第十二个周期 7Mult1 Yes Mult F0 F2 F4 No No 12 FU Mult1 Divide Read operands for DIVD? 记分板示例第十三个周期 13 6Mult1 Yes Mult F0 F2 F4 No No Add Yes Add F6 F8 F2 Yes Yes 13 FU Mult1 Add Divide 记分板示例第十四个周期 13 14 5Mult1 Yes Mult F0 F2 F4 No No 2Add Yes Add F6 F8 F2 Yes Yes 14 FU Mult1 Add Divide
记分板示例第十五个周期 13 14 4Mult1 Yes Mult F0 F2 F4 No No 1Add Yes Add F6 F8 F2 No No 15 FU Mult1 Add Divide 记分板示例第十六个周期 13 14 16 3Mult1 Yes Mult F0 F2 F4 No No 0Add Yes Add F6 F8 F2 No No 16 FU Mult1 Add Divide 记分板示例第十七个周期 13 14 16 WAR Hazard! 2Mult1 Yes Mult F0 F2 F4 No No Add Yes Add F6 F8 F2 No No 17 FU Mult1 Add Divide Write result of ADDD? 记分板示例第十八个周期 13 14 16 1Mult1 Yes Mult F0 F2 F4 No No Add Yes Add F6 F8 F2 No No 18 FU Mult1 Add Divide
记分板示例第十九个周期 19 13 14 16 0Mult1 Yes Mult F0 F2 F4 No No Add Yes Add F6 F8 F2 No No 19 FU Mult1 Add Divide 记分板示例第二十个周期 19 20 13 14 16 Add Yes Add F6 F8 F2 No No Divide Yes Div F10 F0 F6 Yes Yes 20 FU Add Divide 记分板示例第二十一个周期 19 20 21 13 14 16 Add Yes Add F6 F8 F2 No No Divide Yes Div F10 F0 F6 Yes Yes 21 FU Add Divide 记分板示例第二十二个周期 19 20 21 ADD: 2 cycles Mult: 10 cycles Divd: 40 cycles 13 14 16 22 40 Divide Yes Div F10 F0 F6 No No 22 FU Divide
记分板示例第六十一个周期 19 20 21 61 13 14 16 22 0Divide Yes Div F10 F0 F6 No No 61 FU Divide 记分板示例第六十二个周期 Instruction status Read Execution Write Instruction j k Issueoperands complete Result MULTD F0 F2 F4 6 9 19 20 21 61 62 13 14 16 22 Integer No Mult1 No Mult2 No Add No 0Divide No 62 FU CDC 6600 的记分板 g 来自编译的加速比 1.7; 手编代码的加速比 2.5, 但是由于存储速度慢 ( 没有 Cache) 限制了加速比的提高 g 6600 记分板的局限性 : = 没有前递硬件 = 指令调度局限于基本块内 ( 指令窗口小 ) = 功能部件少 ( 结构冒险 ), 特别是 integer/load store 部件 = 存在结构冒险, 就暂停发射指令 = 等待到 WAR 冒险解决 = 防止 WAW 冒险 本讲小结 g 软件或硬件的指令级并行 (ILP) g 循环级并行最容易判定 g 软件并行性取决于程序, 如果硬件不能支持就出现冒险 g 软件相关性 / 编译器复杂性决定编译中是否能展开循环 = 存储器相关是最难判定的 g 硬件开采 ILP = 在编译时有些相关情况不能真正判定 = 针对某一机器产生的代码可以在另一机器上有效运行 g 记分板的核心思想 : 允许暂停之后的指令提前处理 ( 译码 => 发射指令 & 读取操作数 ) = 允许乱序执行 => 乱序完成 =ID 段检测所有的结构冒险