1、高等计算机系统结构,指令级并行处理,（第二讲）,2011年3月7日,程 旭,复习: 三种数据冒险,对于执行如下类型的指令序列： rk (ri) op (rj),数据冒险示例,I1 DIVDf6, f6,f4I2 LDf2,45(r3)I3 MULTDf0,f2,f4I4 DIVDf8,f6,f2I5SUBDf10,f0,f6I6 ADDDf6,f8,f2,先写后读冒险（RAW Hazards）,先读后写冒险（WAR Hazards）,写写冒险（WAW Hazards）,dest,src1,src2,复杂指令流水线,ID,ALU,Mem,Fadd,Fmul,Fdiv,Issue,GPRsFPRs
2、,为了追求更高性能，流水线变得更加复杂，这是因为: 流水化浮点部件的长时延 多功能和存储部件 具有可变访问时间的存储系统 精确中断,复杂按序指令流水线,延迟回写（Delay writeback）以确保所有操作到W级都具有相同的时延写端口不可被复用（每个周期只有一条指令进入、一条指令流出)指令按序提交，简化了精确中断的实现。,Commit Point,如何避免由于不断增加的回写时延，而不要导致单周期整数操作变慢?,旁路（Bypassing）,复杂指令流水线,ID,ALU,Mem,Fadd,Fmul,Fdiv,Issue,GPRsFPRs,如何解决写冒险，而不需要均分所有流水级，并不要旁路电路？,
3、何时可以安全地发射一条指令?,假设有一个统一的数据结构跟踪记录在所有功能部件中的所有指令状态在发射级分发（dispatch）一条指令之前，需要完成如下检查： 所需功能部件是否可用? 输入数据是否可用? RAW? 写目的操作数是否安全? WAR? WAW? 是否在WB级会出现结构冒险?,硬件策略：指令并行,为什么需要硬件在运行时支持?在编译时有些相关情况不能真正判定简化编译处理针对某一机器产生的代码可以在另一机器上有效运行核心思路：允许暂停之后的指令被处理DIVDF0,F2,F4ADDDF10,F0,F8SUBDF12,F8,F14允许乱序(out-of-order)执行 = 乱序完成在1963
4、年的CDC 6600机器中，ID段检测结构冒险和记分板（Scoreboard）数据核心思路： 寄存器换名DIVDF0,F2,F4 DIVDF0,F2,F4 ADDDF10,F0,F8 ADDDF10,F0,F8 SUBDF0,F8,F14 SUBDF100,F8,F14 MULDF6,F10,F0 MULDF6,F10,F100消除WAR和WAW冒险,超标量处理器的内部部件,I-cache,D-cache,BusInter-faceUnit,BranchUnit,Instruction Fetch Unit,Reorder Buffer,InstructionIssue Unit,Retire
5、Unit,Load/ StoreUnit,IntegerUnit(s),Floating-PointUnit(s),RenameRegisters,General PurposeRegisters,Floating- PointRegisters,BTAC,BHT,MMU,MMU,32 (64),DataBus,32 (64),AddressBus,ControlBus,Instruction Buffer,Instruction Decode andRegister Rename Unit,超标量流水线,按序将指令递交到乱序执行的内核!,取指,译码和换名,发射,执行,执行,执行,执行,退离和
6、回写,指令窗口,支持按序发射指令的记分板技术Scoreboard for In-order Issues,BusyFU# : a bit-vector to indicate FUs availability. (FU = Int, Add, Mult, Div)These bits are hardwired to FUs.WPreg# : a bit-vector to record the registers for whichwrites are pending. These bits are set to true by the Issue stage and set to fals
7、e by the WB stageIssue checks the instruction (opcode dest src1 src2) against the scoreboard (Busy & WP) to dispatchFU available? RAW?WAR?WAW?,BusyFU#WPsrc1 or WPsrc2cannot ariseWPdest,硬件策略：指令并行（续一）,乱序执行 分解 ID段：1.Issuedecode instructions, check for structural hazards2.Read operandswait until no data
8、 hazards, then read operands只要指令同时满足上述两个条件，记分板就允许该指令执行，而无需等待前面的指令完成CDC 6600: 按序发射乱序执行乱序提交（commit） ( 也就是完成completion),CDC 6600logic gates,结构简图,记分板体系结构,Functional Units,Registers,Memory,SCOREBOARD,记分板的含义,乱序完成 = WAR, WAW冒险?对WAR的解决方案排队等待操作以及它们操作数的拷贝只在读操作段才读取寄存器对WAW的解决方案，必须检测冒险：暂停等待到其他指令完成在执行阶段可能有多个指令 =
9、设置多个执行部件或者流水化执行部件记分板跟踪相关、状态或操作记分板用四个流水段代替ID、EX、WB三段,记分板控制的四级,1.Issuedecode 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 function
10、al 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 operandswait until no data hazards, then read operands (ID2) A source operand is available if no ea
11、rlier 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 execut
12、ion. The scoreboard resolves RAW hazards dynamically in this step, and instructions may be sent into execution out of order.,记分板控制的四级（续一）,3.Executionoperate on operands (EX) The functional unit begins execution upon receiving operands. When the result is ready, it notifies the scoreboard that it has
13、 completed execution. 4.Write resultfinish 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: DIVDF0,F2,F4 ADDDF10,F0,F8 SUBDF8,F8,F14 CDC 660
14、0 scoreboard would stall SUBD until ADDD reads operands,记分板的三个主要组成部分,1.Instruction statuswhich of 4 steps the instruction is in2.Functional unit statusIndicates the state of the functional unit (FU). 9 fields for each functional unitBusyIndicates whether the unit is busy or notOpOperation to perform
15、 in the unit (e.g., + or )FiDestination registerFj, FkSource-register numbersQj, QkFunctional units producing source registers Fj, FkRj, RkFlags indicating when Fj, Fk are ready3.Register result statusIndicates which functional unit will write each register, if one exists. Blank when no pending inst
16、ructions will write that register,记分板流水线控制的细节,记分板示例,ADD:2 cyclesMult:10 cyclesDivd:40 cycles,记分板示例第一个周期,记分板示例第二个周期,Issue 2nd LD?,记分板示例第三个周期,Issue MULT?,记分板示例第四个周期,记分板示例第五个周期,记分板示例第六个周期,ADD:2 cyclesMult:10 cyclesDivd:40 cycles,记分板示例第七个周期,Read multiply operands?,记分板示例第8a个周期(前半个周期),记分板示例第8b个周期(后半个周期),记
17、分板示例第九个周期,Read operands for MULT & SUBD? Issue ADDD?,ADD:2 cyclesMult:10 cyclesDivd:40 cycles,记分板示例第十个周期,ADD:2 cyclesMult:10 cyclesDivd:40 cycles,记分板示例第十一个周期,ADD:2 cyclesMult:10 cyclesDivd:40 cycles,记分板示例第十二个周期,Read operands for DIVD?,记分板示例第十三个周期,记分板示例第十四个周期,记分板示例第十五个周期,记分板示例第十六个周期,记分板示例第十七个周期,Write
18、 result of ADDD?,记分板示例第十八个周期,记分板示例第十九个周期,记分板示例第二十个周期,记分板示例第二十一个周期,记分板示例第二十二个周期,ADD:2 cyclesMult:10 cyclesDivd:40 cycles,记分板示例第六十一个周期,记分板示例第六十二个周期,CDC 6600 的记分板,来自编译的加速比1.7；手编代码的加速比2.5，但是由于存储速度慢（没有Cache）限制了加速比的提高 6600记分板的局限性：没有前递硬件指令调度局限于基本块内(指令窗口小)功能部件少（结构冒险），特别是integer/load store部件存在结构冒险，就暂停发射指令等待到WAR冒险解决防止WAW冒险,本讲小结,软件或硬件的指令级并行 (ILP)循环级并行最容易判定软件并行性取决于程序，如果硬件不能支持就出现冒险软件相关性/编译器复杂性决定编译中是否能展开循环存储器相关是最难判定的硬件开采ILP在编译时有些相关情况不能真正判定针对某一机器产生的代码可以在另一机器上有效运行记分板的核心思想: 允许暂停之后的指令提前处理(译码 = 发射指令 & 读取操作数)允许乱序执行 = 乱序完成ID段检测所有的结构冒险,
