Quiz 3 假设各种分支占所有指令数的百分比如下表所示： 现有一5段流水线，每段延迟时间均为一个时钟周期，分支转移地址在第3个时钟周期结束时才能计算出来，条件分支的转移条件在第4个时钟周期才能确定。假设第一个流水段是取指阶段，第二个流水段是指令译码阶段，理想CPI值为1。试通过计算说明应该采用哪种控制相关处理策略（冻结技术、预测分支成功策略以及预测分支失败策略）性能最高？ 条件分支 20％ （其中60％是成功的） 跳转和调用 5％

第4章 指令级并行

Review: 基本流水线 流水线提高的是指令带宽（吞吐率），而不是单条指令的执行速度 相关限制了流水线性能的发挥 结构相关：需要更多的硬件资源 数据相关：需要定向，编译器调度 控制相关：尽早检测条件，计算目标地址，延迟转移，预测 增加流水线的级数会增加相关产生的可能性 异常，浮点运算使得流水线控制更加复杂 编译器可降低数据相关和控制相关的开销 Load 延迟槽 Branch 延迟槽 Branch预测 2006-10-24

指令级并行的概念 计算机系统的并行性，从执行程序的角度，分为： 从处理数据的角度，并行性等级分为： 提高并行的三种途径 指令内部并行：指令内部的微操作 指令级并行：并行执行两条或多条指令 任务级或过程级并行：并行执行两个或多个过程或任务 作业或程序级并行：在多个作业或程序间并行 从处理数据的角度，并行性等级分为： 字串位串 字串位并 字并位串 全并行 提高并行的三种途径 时间重叠 资源重复 资源共享

4.1 先进流水线技术和指令级并行 （Instruction Level Parallelism) ILP: 无关的指令重叠执行 流水线的平均CPI Pipeline CPI = Ideal Pipeline CPI + Struct Stalls + RAW Stalls + WAR Stalls + WAW Stalls + Control Stalls 本章研究 减少停顿（stalls)数的方法和技术 基本途径 软件方法（编译器优化） Gcc: 17%控制类指令 5 instructions + 1 branch 在基本块上，得到更多的并行性 挖掘循环级并行 硬件方法 动态调度方法 以DLX的浮点数操作为例

采用的基本技术

本章遵循的指令延时 产生结果的指令 使用结果的指令 所需延时 FP ALU op Another FP ALU op 3 产生结果的指令 使用结果的指令 所需延时 FP ALU op Another FP ALU op 3 FP ALU op Store double 2 Load double FP ALU op 1 Load double Store double 0 Integer op Integer op 0 (当使用结果的指令为BRANCH指令时除外)

基本块内的指令级并行 基本块的定义 循环级并行 向量处理机模型 直线型代码，无分支 单入口 整个程序是由分支语句连接基本块构成 for (i = 1; i <= 1000; i++) x(i) = x(i) + s; • 计算x(i)时没有相关 • 可以并行产生1000个数据 •这里没有相关是指没有数据相关 •问题是在生成代码时会有Branch指令－控制相关 •预测比较容易，但我们必须有预测方案 向量处理机模型 • load vectors x and y (up to some machine dependent max) • then do result-vec = xvec + yvec in a single instruction

简单循环及其对应的汇编程序 for (i=1; i<=1000; i++) x(i) = x(i) + s; Loop: LD F0,0(R1) ;F0=vector element ADDD F4,F0,F2 ;add scalar from F2 SD 0(R1),F4 ;store result SUBI R1,R1,8 ;decrement pointer 8B (DW) BNEZ R1,Loop ;branch R1!=zero NOP ;delayed branch slot

FP 循环中的相关 需要在哪里加stalls? Loop: LD F0,0(R1) ;F0=vector element ADDD F4,F0,F2 ;add scalar from F2 SD 0(R1),F4 ;store result SUBI R1,R1,8 ;decrement pointer 8B (DW) BNEZ R1,Loop ;branch R1!=zero NOP ;delayed branch slot 产生结果的指令 使用结果的指令 所需的延时 FP ALU op Another FP ALU op 3 FP ALU op Store double 2 Load double FP ALU op 1 Load double Store double 0 Integer op Integer op 0 需要在哪里加stalls?

FP 循环中的Stalls 10 clocks: 是否可以通过调整代码顺序使stalls减到最小 1 Loop: LD F0,0(R1) ;F0=vector element 2 stall 3 ADDD F4,F0,F2 ;add scalar in F2 4 stall 5 stall 6 SD 0(R1),F4 ;store result 7 SUBI R1,R1,8 ;decrement pointer 8B (DW) 8 stall ；书上有错 9 BNEZ R1,Loop ;branch R1!=zero 10 stall ;delayed branch slot 产生结果的指令 使用结果的指令 所需的延时 FP ALU op Another FP ALU op 3 FP ALU op Store double 2 Load double FP ALU op 1 Load double Store double 0 Integer op Integer op 0 10 clocks: 是否可以通过调整代码顺序使stalls减到最小

FP 循环中的最少Stalls数 Swap BNEZ and SD by changing address of SD 1 Loop: LD F0,0(R1) 书上P135 有错 2 SUBI R1,R1,8 3 ADDD F4,F0,F2 4 stall 5 BNEZ R1,Loop ;delayed branch 6 SD 8(R1),F4 ;altered when move past SUBI Swap BNEZ and SD by changing address of SD 产生结果的指令 使用结果的指令 所需的延时 FP ALU op Another FP ALU op 3 FP ALU op Store double 2 Load double FP ALU op 1 Load double Store double 0 Integer op Integer op 0 3 clocks doing work, 3 overhead (stall, branch, sub) 6 clocks: 通过循环展开4次是否可以提高性能?

循环展开4次(straightforward way) 1 Loop: LD F0,0(R1) stall 2 ADDD F4,F0,F2 stall stall 3 SD 0(R1),F4 ;drop SUBI & BNEZ 4 LD F6,-8(R1) stall 5 ADDD F8,F6,F2 stall stall 6 SD -8(R1),F8 ;drop SUBI & BNEZ 7 LD F10,-16(R1) stall 8 ADDD F12,F10,F2 stall stall 9 SD -16(R1),F12 ;drop SUBI & BNEZ 10 LD F14,-24(R1) stall 11 ADDD F16,F14,F2 stall stall 12 SD -24(R1),F16 13 SUBI R1,R1,#32 stall ;alter to 4*8 14 BNEZ R1,LOOP 15 NOP 15 + 4 x (1+2) + 1 = 28 cycles, or 7 per iteration Assumes R1 is multiple of 4 Rewrite loop to minimize stalls?

Stalls数最小的循环展开 代码移动后 14 clock cycles, or 3.5 per iteration 1 Loop: LD F0,0(R1) 2 LD F6,-8(R1) 3 LD F10,-16(R1) 4 LD F14,-24(R1) 5 ADDD F4,F0,F2 6 ADDD F8,F6,F2 7 ADDD F12,F10,F2 8 ADDD F16,F14,F2 9 SD 0(R1),F4 10 SD -8(R1),F8 11 SUBI R1,R1,#32 12 SD 16(R1),F12 13 BNEZ R1,LOOP 14 SD 8(R1),F16 ; 8-32 = -24 14 clock cycles, or 3.5 per iteration 注意第11，12行，P137有错 代码移动后 SD移动到SUBI后，注意偏移量的修改 Loads移动到SD前，注意偏移量的修改

循环展开示例小结 移动SD到SUBI和BNEZ后，需要调整 SD中的偏移 循环展开对循环间无关的程序是有效降低stalls的手段(对循环级并行）. 不同次的循环，使用不同的寄存器. 删除不必要的测试和分支后，需调整循环步长等控制循环的代码. 注意循环展开中的Load和Store,不同次循环的Load 和Store 是相互独立的。需要分析对存储器的引用，保证他们没有引用同一地址. 指令调度，必须保证程序运行的结果不变 2009-11-16

从编译器角度看代码移动（1/5) 编译器分析程序的相关性依赖于给定的流水线 编译器进行指令调度来消除相关 (True) 数据相关（Data dependencies）, 对于指令i和j，如果 Instruction j使用指令i产生的结果 , 或 Instruction j 与instruction k相关, 并且instruction k 与instruction i有数据相关. 如果相关, 不能并行执行 对于寄存器比较容易确定(fixed names) 但对memory的引用，比较难确定: 100(R4) = 20(R6)? 在不同次的循环中，20(R6) = 20(R6)?

下列程序哪里有数据相关? 1 Loop: LD F0,0(R1) 2 ADDD F4,F0,F2 3 SUBI R1,R1,8 4 BNEZ R1,Loop ;delayed branch 5 SD 8(R1),F4 ;altered when move past SUBI 3 clocks doing work, 3 overhead (stall, branch, sub)

从编译器角度看代码移动(2/5) 另一种相关称为名相关（ name dependence）: 两条指令使用同一个名子(register or memory location) 但不交换数据 反相关（Antidependence） (WAR if a hazard for HW) Instruction j 所写的寄存器或存储单元，与 instruction i 所读的寄存器或存储单元相同，注instruction i 是先执行 输出相关(Output dependence) (WAW if a hazard for HW) Instruction i 和instruction j 对同一寄存器或存储单元进行写操作，必须保证两条指令的写顺序

下列是否有名相关? 如何消除名相关? 1 Loop: LD F0,0(R1) 2 ADDD F4,F0,F2 3 SD 0(R1),F4 ;drop SUBI & BNEZ 4 LD F0,-8(R1) 5 ADDD F4,F0,F2 6 SD -8(R1),F4 ;drop SUBI & BNEZ 7 LD F0,-16(R1) 8 ADDD F4,F0,F2 9 SD -16(R1),F4 ;drop SUBI & BNEZ 10 LD F0,-24(R1) 11 ADDD F4,F0,F2 12 SD -24(R1),F4 13 SUBI R1,R1,#32 ;alter to 4*8 14 BNEZ R1,LOOP 15 NOP 如何消除名相关? LD F0 to output to next LD F0 ADD F0 input to LD F0

从编译器角度看代码移动（3/5) 访问存储单元时，很难判断名相关 100(R4) = 20(R6)? 不同次的循环，20(R6) = 20(R6)? 我们给出的示例要求编译器知道假设R1不变，因此: 0(R1) ≠ -8(R1) ≠ -16(R1) ≠ -24(R1) 因此loads和stores之间相互无关可以移动

从编译器角度看代码移动（4/5) 最后一种相关称为控制相关( control dependence) Example if p1 {S1;}; if p2 {S2;}; S1 依赖于P1的测试结果，S2依赖于P2的测试。

从编译器角度看代码移动（5/5) 处理控制相关的原则：: 减少控制相关可以提高指令的并行性 受分支指令控制的指令，不能移到控制指令之前，以免该指令的执行不在分支指令的控制范围. 不受分支指令控制的指令，不能移到控制指令之后，以免该指令的执行受分支指令的控制. 减少控制相关可以提高指令的并行性

下列程序段的控制相关 1 Loop: LD F0,0(R1) 2 ADDD F4,F0,F2 3 SD 0(R1),F4 4 SUBI R1,R1,8 5 BEQZ R1,exit 6 LD F0,0(R1) 7 ADDD F4,F0,F2 8 SD 0(R1),F4 9 SUBI R1,R1,8 10 BEQZ R1,exit 11 LD F0,0(R1) 12 ADDD F4,F0,F2 13 SD 0(R1),F4 14 SUBI R1,R1,8 15 BEQZ R1,exit .... Everything after branch to next branch

循环展开（1/3) Example: 下列程序段存在哪些数据相关? (A,B,C 指向不同的存储区且不存在覆盖区) for (i=1; i<=100; i=i+1) { A[i+1] = A[i] + C[i]; /* S1 */ B[i+1] = B[i] + A[i+1]; /* S2 */ } 1. S2使用由S1在同一循环计算出的 A[i+1]. 2. S1 使用由S1在前一次循环中计算的值，同样S2也使用由S2在前一次循环中计算的值. 这种存在于循环间的相关，我们称为 “loop-carried dependence” 这表示循环间存在相关，不能并行执行，它与我们前面的例子中循环间无关是有区别的

循环展开（2/3) Example:A,B,C,D distinct & nonoverlapping for (i=1; i<=100; i=i+1) { A[i] = A[i] + B[i]; /* S1 */ B[i+1] = C[i] + D[i];} /* S2 */ 1. S1和S2没有相关，S1和S2互换不会影响程序的正确性 2. 在第一次循环中，S1依赖于前一次循环的B[1].

循环展开（3/3) for (i=1; i<=100; i=i+1) { A[i] = A[i] + B[i]; /* S1 */ B[i+1] = C[i] + D[i];} /* S2 */ OLD: A[1] = A[1] + B[1]; for (i=1; i<=99; i=i+1) { B[i+1] = C[i] + D[i]; A[i+1] = A[i+1] + B[i+1]; } B[101] = C[100] + D[100]; NEW:

Review 指令级并行(ILP) 流水线的平均CPI Pipeline CPI = Ideal Pipeline CPI + Struct Stalls + RAW Stalls + WAR Stalls + WAW Stalls + Control Stalls 提高指令级并行的方法 软件方法：指令流调度，循环展开，软件流水线，trace scheduling 硬件方法 循环展开 指令调度，必须保证程序运行的结果不变 偏移量的修改 寄存器的重命名 循环步长的调整

4.2 硬件方案: 指令级并行 为什么要使用硬件调度方案? 基本思想: 允许 stall后的指令继续向前流动 在编译时无法确定的相关，可以通过硬件调度来优化 编译器简单 代码在不同组织结构的机器上，同样可以有效的运行 基本思想: 允许 stall后的指令继续向前流动 DIVD F0,F2,F4 ADDD F10,F0,F8 SUBD F12,F8,F14 允许乱序执行（out-of-order execution） => out-of-order completion

硬件方案之一: 记分牌 记分牌的基本概念示意图

记分牌技术要点（1/2) Out-of-order execution 将ID 段分为: 起源于1963年推出的CDC6600 Issue—译码，检测结构相关 Read operands—等待到无数据相关时，读操作数 起源于1963年推出的CDC6600 4 FPU 5 Memory Reference 7 IU 集中相关检查，互锁机制解决相关 CDC 6600: 顺序发射，乱序执行，乱序完成，CDC6600流水线没有采用定向技术，只实现非精确中断 Load /store结构 采用这种技术的微处理器企业 MIPS，HP， IBM Sun 公司的UltraSparc DEC Alpha

记分牌技术要点(2/2) Out-of-order completion => WAR, WAW hazards? 对操作排队 仅在读操作数阶段读寄存器 对WAW而言, 检测到相关后，停止发射前一条指令，直到前一条指令完成 要提高效率，需要有多条指令进入执行阶段=>必须有多个执行部件或执行部件是流水化的 记分牌保存相关操作和状态 记分牌用四段代替ID, EX, WB 三段

带有记分牌控制的DLX

记分牌控制的四阶段（1/2) 1. Issue—指令译码，检测结构相关 Read operands—没有数据相关时，读操作数 如果当前指令所使用的功能部件空闲，并且没有其他活动的指令使用相同的目的寄存器（WAW), 记分牌发射该指令到功能部件，并更新记分牌内部数据，如果有结构相关或WAW相关，则该指令的发射暂停，并且也不发射后继指令，直到相关解除. Read operands—没有数据相关时，读操作数 如果先前已发射的正在运行的指令不对当前指令的源操作数寄存器进行写操作，或者一个正在工作的功能部件已经完成了对该寄存器的写操作，则该操作数有效. 操作数有效时，记分牌控制功能部件读操作数，准备执行。 记分牌在这一步动态地解决了RAW相关，指令可能会乱序执行。

记分牌控制的四阶段（2/2） 3. Execution—取到操作数后执行 (EX) 接收到操作数后，功能部件开始执行. 当计算出结果后，它通知记分牌，可以结束该条指令的执行. 4. Write result—finish execution (WB) 一旦记分牌得到功能部件执行完毕的信息后，记分牌检测WAR相关，如果没有WAR相关，就写结果，如果有WAR 相关，则暂停该条指令。 Example: DIVD F0,F2,F4 ADDD F10,F0,F8 SUBD F8,F8,F14 CDC 6600 scoreboard 将暂停 SUBD 直到ADDD 读取操作数后，才进入WR段处理。

记分牌的结构 1. Instruction status—记录正在执行的各条指令处于四步中的哪一步 2. Functional unit status—记录功能部件(FU)的状态。用9个域记录每个功能部件的9个参量： Busy—指示该部件是否空闲 Op—该部件所完成的操作 Fi—其目的寄存器编号 Fj, Fk—源寄存器编号 Qj, Qk—产生源操作数Fj, Fk的功能部件 Rj, Rk—标识源操作数Fj, Fk是否就绪的标志 3. Register result status—如果存在功能部件对某一寄存器进行写操作，指示具体是哪个功能部件对该寄存器进行写操作。如果没有指令对该寄存器进行写操作，则该域 为Blank 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 Bookkeeping Rj No; Rk No f(if Qj(f)=FU then Rj(f) Yes); f(if Qk(f)=FU then Rk(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; 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) 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 *

Scoreboard Example

Scoreboard Example: Cycle 1

Scoreboard Example: Cycle 2 Issue 2nd LD?

Scoreboard Example: Cycle 3 Issue MULT?

Scoreboard Example: Cycle 4

Scoreboard Example: Cycle 5

Scoreboard Example: Cycle 6

Scoreboard Example: Cycle 7 Read multiply operands?

Scoreboard Example: Cycle 8a (First half of clock cycle)

Scoreboard Example: Cycle 8b (Second half of clock cycle)

Scoreboard Example: Cycle 9 Note Remaining Read operands for MULT & SUB? Issue ADDD?

Scoreboard Example: Cycle 10

Scoreboard Example: Cycle 11

Scoreboard Example: Cycle 12 Read operands for DIVD?

Scoreboard Example: Cycle 13

Scoreboard Example: Cycle 14

Scoreboard Example: Cycle 15

Scoreboard Example: Cycle 16

Scoreboard Example: Cycle 17 WAR Hazard! Why not write result of ADD???

Scoreboard Example: Cycle 18

Scoreboard Example: Cycle 19

Scoreboard Example: Cycle 20

Scoreboard Example: Cycle 21 WAR Hazard is now gone...

Scoreboard Example: Cycle 22

Continue…….

Scoreboard Example: Cycle 61

Scoreboard Example: Cycle 62

Review: Scoreboard Example: Cycle 62 In-order issue; out-of-order execute & commit

CDC 6600 Scoreboard 编译器优化，加速比可达到1.7，手工优化加速比可达到 2.5 ，其存储系统较慢 (no cache)限制了性能的发挥 6600 scoreboard的缺陷: 没有定向数据通路 指令窗口较小，仅局限于基本块内的调度 功能部件数较少，容易产生结构相关，特别是其Load store操作也是用IU部件完成的 结构冲突时不能发射 WAR相关是通过等待解决的 WAW相关时，不会进入IS阶段

ILP小结 可通过软件或硬件来挖掘指令级并行潜力 循环级并行是最容易判断的 程序内在的相关性限制了用软件方法挖掘程序的并行性 编译器的数据相关性分析结果，确定了是否可以进行循环展开 当对存储器单元引用时，数据相关分析很困难 硬件方法挖掘ILP 在编译阶段无法确定的相关性，可以在程序执行时，用硬件方法判定 这种方法还可以使得程序代码在其他机器上有效地执行 记分牌的主要思想是：允许stall后的指令继续进行处理 可以out-of-order execution => out-of-order completion ID 段检测结构相关和WAW相关