高等计算机系统结构 指令级并行处理 （第二讲） 程 旭 2011年3月7日

复习: 三种数据冒险 对于执行如下类型的指令序列： rk (ri) op (rj) 真数据相关（True Data-dependence) r3  (r1) op (r2) Read-after-Write r5  (r3) op (r4) (RAW) hazard 反相关（Anti-dependence） r3  (r1) op (r2) Write-after-Read r1  (r4) op (r5) (WAR) hazard 输出相关（Output-dependence） r3  (r1) op (r2) Write-after-Write r3  (r6) op (r7) (WAW) hazard

数据冒险示例 先写后读冒险（RAW Hazards） 先读后写冒险（WAR Hazards） 写写冒险（WAW Hazards） dest src1 src2 I1 DIVD f6, f6, f4 I2 LD f2, 45(r3) I3 MULTD f0, f2, f4 I4 DIVD f8, f6, f2 I5 SUBD f10, f0, f6 I6 ADDD f6, f8, f2 先写后读冒险（RAW Hazards） 先读后写冒险（WAR Hazards） 写写冒险（WAW Hazards）

复杂指令流水线 为了追求更高性能，流水线变得更加复杂，这是因为: ALU Mem IF WB ID Issue Fadd GPR’s FPR’s Fmul Fdiv 为了追求更高性能，流水线变得更加复杂，这是因为: 流水化浮点部件的长时延 多功能和存储部件 具有可变访问时间的存储系统 精确中断

复杂按序指令流水线 延迟回写（Delay writeback） 以确保所有操作到W级都具有 相同的时延 旁路（Bypassing） PC Inst. Mem D Decode X1 X2 Data Mem W + GPRs Fadd X3 FPRs Fmul FDiv Unpipelined divider 延迟回写（Delay writeback） 以确保所有操作到W级都具有 相同的时延 写端口不可被复用（每个周期只有一条指令进入、一条指令流出) 指令按序提交，简化了精确中断的实现。 Commit Point 如何避免由于不断增加的回写时延，而不要导致单周期整数操作变慢? 旁路（Bypassing）

复杂指令流水线 ALU Mem IF WB ID Issue Fadd GPR’s FPR’s Fmul 如何解决写冒险，而不需要均分所有流水级，并不要旁路电路？ Fdiv

何时可以安全地发射一条指令? 假设有一个统一的数据结构跟踪记录在所有功能部件中的所有指令状态 在发射级分发（dispatch）一条指令之前，需要完成如下检查： 所需功能部件是否可用? 输入数据是否可用?  RAW? 写目的操作数是否安全? WAR? WAW? 是否在WB级会出现结构冒险?

硬件策略：指令并行 为什么需要硬件在运行时支持? 核心思路：允许暂停之后的指令被处理 在编译时有些相关情况不能真正判定 简化编译处理 针对某一机器产生的代码可以在另一机器上有效运行 核心思路：允许暂停之后的指令被处理 DIVD F0,F2,F4 ADDD 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冒险

超标量处理器的内部部件 I-cache MMU 32 (64) BHT BTAC Branch Unit Data Bus Instruction Fetch Unit Instruction Decode and Register Rename Unit 32 (64) Bus Inter- face Unit Instruction Buffer Instruction Issue Unit Address Bus Reorder Buffer Floating- Point Unit(s) Load/ Store Unit Integer Unit(s) Retire Unit Control Bus Floating- Point Registers General Purpose Registers Rename Registers MMU D-cache

超标量流水线 执行 译码 和 换名 退离 和 回写 执行 取指 指令窗口 发射 执行 执行 按序将指令递交到乱序执行的内核!

支持按序发射指令的记分板技术 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]

硬件策略：指令并行（续一） 乱序执行 分解 ID段： 只要指令同时满足上述两个条件，记分板就允许该指令 执行，而无需等待前面的指令完成 1. Issue—decode instructions, check for structural hazards 2. Read operands—wait until no data hazards, then read operands 只要指令同时满足上述两个条件，记分板就允许该指令 执行，而无需等待前面的指令完成 CDC 6600: 按序发射 乱序执行 乱序提交（commit） ( 也就是完成[completion])

CDC 6600 logic gates

ＣＤＣ　６６００　结构简图

记分板体系结构 Functional Units Registers SCOREBOARD Memory FP Mult FP Divide FP Add Integer Registers Functional Units SCOREBOARD Memory

记分板的含义 乱序完成 => WAR, WAW冒险? 对WAR的解决方案 对WAW的解决方案，必须检测冒险：暂停等待到其他指令完 成 排队等待操作以及它们操作数的拷贝 只在读操作段才读取寄存器 对WAW的解决方案，必须检测冒险：暂停等待到其他指令完 成 在执行阶段可能有多个指令 => 设置多个执行部件或者流水化 执行部件 记分板跟踪相关、状态或操作 记分板用四个流水段代替ID、EX、WB三段

记分板控制的四级 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 F0,F2,F4 ADDD F10,F0,F8 SUBD 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 Rj, Rk—Flags indicating when Fj, Fk are ready 3. Register result status—Indicates which functional unit will write each register, if one exists. Blank when no pending instructions will write that register What you might have thought 1. 4 stages of instruction executino 2.Status of FU: Normal things to keep track of (RAW & structura for busyl): Fi from instruction format of the mahine (Fi is dest) Add unit can Add or Sub Rj, Rk - status of registers (Yes means ready) Qj,Qk - If a no in Rj, Rk, means waiting for a FU to write result; Qj, Qk means wihch FU waiting for it 3.Status of register result (WAW &WAR)s: which FU is going to write into registers Scoreboard on 6600 = size of FU 6.7, 6.8, 6.9, 6.12, 6.13, 6.16, 6.17 FU latencies: Add 2, Mult 10, Div 40 clocks

记分板流水线控制的细节 Read operands Execution complete Instruction status Write result Issue Rj and Rk Functional unit done Wait until f((Fj( f )≠Fi(FU) or Rj( f )=No) & (Fk( f ) ≠Fi(FU) or Rk( f )=No)) Not busy (FU) and not result(D) Bookkeeping Rj No; Rk 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 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; 1.Issue - if no structural haards AND non wAW (no Funtional Unit is going to write this destination register; 1 per clock cycle 2. Read -(RAW) if no instructions is going to write a source register of this instruction (alternatively, no write signal this clock cycle) +> gein exection of the instruction; many read ports, so can read many times 3. Execution Complete; multiple during clock cyle 4. Write result - (WAR) If no instructiion is watiing to read the destination register; assume multiple wriite ports; wait for clock cycle to write and tehn read the results; assume can oerlap issue & write show clock cyclesneed 20 or so Latency: minimum is 4 through 4 stages

记分板示例 ADD: 2 cycles Mult: 10 cycles Divd: 40 cycles

记分板示例第一个周期

记分板示例第二个周期 Issue 2nd LD?

记分板示例第三个周期 Issue MULT?

记分板示例第四个周期

记分板示例第五个周期

记分板示例第六个周期 ADD: 2 cycles Mult: 10 cycles Divd: 40 cycles

记分板示例第七个周期 Read multiply operands?

记分板示例第8a个周期(前半个周期)

记分板示例第8b个周期(后半个周期)

记分板示例第九个周期 ADD: 2 cycles Mult: 10 cycles Divd: 40 cycles Read operands for MULT & SUBD? Issue ADDD?

记分板示例第十个周期 ADD: 2 cycles Mult: 10 cycles Divd: 40 cycles

记分板示例第十一个周期 ADD: 2 cycles Mult: 10 cycles Divd: 40 cycles

记分板示例第十二个周期 Read operands for DIVD?

记分板示例第十三个周期

记分板示例第十四个周期

记分板示例第十五个周期

记分板示例第十六个周期

记分板示例第十七个周期 WAR Hazard! Write result of ADDD?

记分板示例第十八个周期

记分板示例第十九个周期

记分板示例第二十个周期

记分板示例第二十一个周期

记分板示例第二十二个周期 ADD: 2 cycles Mult: 10 cycles Divd: 40 cycles

记分板示例第六十一个周期

记分板示例第六十二个周期

CDC 6600 的记分板 来自编译的加速比1.7；手编代码的加速比2.5，但是 由于存储速度慢（没有Cache）限制了加速比的提高 6600记分板的局限性： 没有前递硬件 指令调度局限于基本块内(指令窗口小) 功能部件少（结构冒险），特别是integer/load store部件 存在结构冒险，就暂停发射指令 等待到WAR冒险解决 防止WAW冒险

本讲小结 软件或硬件的指令级并行 (ILP) 循环级并行最容易判定 软件并行性取决于程序，如果硬件不能支持就出现冒险 软件相关性/编译器复杂性决定编译中是否能展开循环 存储器相关是最难判定的 硬件开采ILP 在编译时有些相关情况不能真正判定 针对某一机器产生的代码可以在另一机器上有效运行 记分板的核心思想: 允许暂停之后的指令提前处理(译码 => 发射指 令 & 读取操作数) 允许乱序执行 => 乱序完成 ID段检测所有的结构冒险