《流水线数据通路和控制逻辑第二讲流水线冒险处理ppt课件》由会员分享，可在线阅读，更多相关《流水线数据通路和控制逻辑第二讲流水线冒险处理ppt课件（114页珍藏版）》请在金锄头文库上搜索。
1、第一讲第一讲 流水线数据通路和控制逻辑流水线数据通路和控制逻辑第二讲第二讲 流水线冒险处理流水线冒险处理第三讲第三讲 高级流水线技术高级流水线技术Ch7: Instruction Pipeline指令流水线指令流水线1第一讲流水线数据通路和控制日常生活中的流水线处理例子：洗衣服单周期处理器模型和流水线性能比较什么样的指令集适合于流水线方式执行如何设计流水线数据通路以MIPS指令子集来说明详细设计取指令部件详细设计执行部件分析每条指令在流水线中的执行过程，遇到各种问题：资源冲突寄存器和存储器的信号竞争分支指令的延迟指令间数据相关如何设计流水线控制逻辑分析每条指令执行过程中的控制信号给出控制器设计
2、过程流水线冒险的概念主主 要要 内内 容容2复习：A SINGLE CYCLE PROCESSOR32ALUctrClkbusWRegWr3232busA32busB555Rw Ra Rb32 32-bitRegistersRsRtRtRdRegDstExtenderMuxMux3216imm16ALUSrcExtOpMuxMemtoRegClkData InWrEn32AdrDataMemory32MemWrALUZero010101InstructionFetch UnitClkInstructionJumpBranchImm16RdMainControlopALUControlfuncA
3、LUop3RegDstALUSrc:InstrZero33复习：MULTIPLE CYCLE PROCESSORMCP: 一个功能部件在一个指令周期中可以被使用多次。IdealMemoryWrAdrDinRAdr323232DoutMemWr32ALU3232ALUOpALUControlInstruction Reg32IRWr32Reg FileRaRwbusWRb5532busA32busBRegWrRsRtMux01RtRdPCWrALUSelAMux01RegDstMux0132PCMemtoRegExtendExtOpMux01320123416Imm32 2ALUSelBMux1
4、0Target32ZeroZeroPCWrCondPCSrcBrWr32IorD4复习：单周期中LW指令的定时ClkPCRs, Rt, Rd,Op, FuncClk-to-QALUctrInstruction Memory Access TimeOld ValueNew ValueRegWrOld ValueNew ValueDelay through Control LogicbusARegister File Access TimeOld ValueNew ValuebusBALU DelayOld ValueNew ValueOld ValueNew ValueNew ValueOld
5、ValueExtOpOld ValueNew ValueALUSrcOld ValueNew ValueAddressOld ValueNew ValuebusWOld ValueNewDelay through Extender & MuxData Memory Access TimeInstruction FetchInstr Decode /Reg. FetchAddressReg WrData MemoryRegister File Write Time1325一个日常生活中的例子洗衣服Laundry ExampleA, B, C, D四个人，每人都有一批衣服需要 wash, dry,
6、 foldWash阶段：30 minutesDry阶段：40 minutesFold阶段： 20 minutesABCDPipelining: Its Natural !如果让你来管理洗衣店，你会如何安排？如果让你来管理洗衣店，你会如何安排？6SEQUENTIAL LAUNDRY（串行方式）串行方式下， 4 批衣服需要花费6 小时（4x(30+40+20)=360分钟）N批衣服，需花费的时间为Nx(30+40+20) = 90N如果用流水线方式洗衣服，则花多少时间呢? ABCD3040 20 3040 20 3040 20 3040 206 PM7891011MidnightTaskOrder
7、Time7PIPELINED LAUNDRY: (START WORK ASAP)串行为6小时，N批则为90N分钟ABCD6 PM7891011MidnightTaskOrderTime3040404040 20流水线方式下，需流水线方式下，需30+4x40+20=210分分 (3.5小时小时)如果有如果有N批衣服呢？批衣服呢？30+Nx40+20分钟分钟假定每一步时间均衡，则假定每一步时间均衡，则比串行方式提高约比串行方式提高约3倍！倍！流水方式下，所用时间主要流水方式下，所用时间主要与最长阶段的时间有关！与最长阶段的时间有关！8复习：LOAD指令的5个阶段Ifetch (取指) : 取指令
8、并计算PC+4 (用到哪些部件？)Reg/Dec (取数和译码) : 取数同时译码(用到哪些部件？)Exec (执行) : 计算内存单元地址(用到哪些部件？)Mem (读存储器) : 从数据存储器中读(用到哪些部件？)Wr(写寄存器): 将数据写到寄存器中(用到哪些部件？)阶段阶段1阶段阶段2阶段阶段 3阶段阶段 4阶段阶段5IfetchReg/DecExecMemWr指令存储器、指令存储器、Adder寄存器堆读口、指令译码器寄存器堆读口、指令译码器扩展器、扩展器、ALU数据存储器数据存储器寄存器堆写口寄存器堆写口这里寄存器这里寄存器堆的读口和堆的读口和写口可看成写口可看成两个不同的两个不同的
9、部件。部件。指令的执行过程中，每个阶段使用不同的部件。指令的执行过程中，每个阶段使用不同的部件。是否和是否和“洗衣洗衣”过程类似？是否可以采用类似方式来执行指令呢？过程类似？是否可以采用类似方式来执行指令呢？9单周期指令模型与流水线性能假定以下每步操作所花时间为：取指：2ns寄存器读：1nsALU操作：2ns存储器读：2ns寄存器写：1ns单周期模型每条指令在一个时钟周期内完成时钟周期等于最长的lw指令的执行时间，即：8ns串行执行时，N条指令的执行时间为：8Nns流水线性能时钟周期等于最长阶段所花时间为：2ns每条lw指令的执行时间为： 2nsx5=10nsN条指令的执行时间为：(5+(N-
10、1)x2ns在N很大时约为2Nns，比串行方式提高约4 倍若各阶段操作均衡(例如，各阶段都是2ns，则串行需10Nns，流水线仍为2Nns)，提高倍数为5倍。Load指令执行时间总计为：指令执行时间总计为：8ns (假定控制单元、假定控制单元、PC访问、信号传访问、信号传递等没有延迟递等没有延迟)流水线方式下，单条指令执行时间不能缩短，但能大大提高指令吞吐率！流水线方式下，单条指令执行时间不能缩短，但能大大提高指令吞吐率！22222222222222210流水线指令集的设计具有什么特征的指令集有利于流水线执行呢？长度尽量一致，有利于简化取指令和指令译码操作MIPS指令32位，下址计算方便: P
11、C+4X86指令从1字节到17字节不等，使取指部件极其复杂格式少，且源寄存器位置相同，有利于在指令未知时就可取操作数MIPS指令的Rs和Rt位置一定，在指令译码时就可读Rs和Rt的值（若位置随指令不同而不同，则需先确定指令后才能取寄存器编号）load / Store指令才能访问存储器，有利于减少操作步骤，规整流水线lw/sw指令的地址计算和运算指令的执行步骤规整在同一个周期X86运算类指令操作数可为内存数据，需计算地址、访存、执行内存中”对齐”存放，有利于减少访存次数和流水线的规整总之，规整、简单和一致等特性有利于指令的流水线执行流水线执行方式能大大提高指令吞吐率，现代计算机都采用流水线执行方
12、式能大大提高指令吞吐率，现代计算机都采用流水线方式！流水线方式！11LOAD指令的流水线ClockCycle 1 Cycle 2Cycle 3 Cycle 4Cycle 5Cycle 6Cycle 7IfetchReg/DecExecMemWr1st lwIfetchReg/DecExecMemWr2nd lwIfetchReg/DecExecMemWr3rd lw每个周期最多有五个功能部件同时在工作每个周期最多有五个功能部件同时在工作后面指令在前面完成取指后马上开始后面指令在前面完成取指后马上开始每个每个load指令仍然需要五个周期完成指令仍然需要五个周期完成但是吞吐率但是吞吐率(throu
13、ghput)提高许多，理想情况下，有：提高许多，理想情况下，有：每个周期有一条指令进入流水线每个周期有一条指令进入流水线每个周期都有一条指令完成每个周期都有一条指令完成每条指令的有效周期每条指令的有效周期(CPI)为为1IfetchReg/DecExecMemWr4th lwIfetchReg/DecExecMemWr5th lwIfetchReg/DecExec12R-TYPE指令的4个阶段Ifetch: 取指令并计算PC+4Reg/Dec: 从寄存器取数，同时指令在译码器进行译码Exec: 在ALU中对操作数进行计算Wr: ALU计算的结果写到寄存器Cycle 1Cycle 2Cycle
14、3Cycle 4IfetchReg/DecExecWrR-type13含R-TYPE和LOAD 指令的流水线上述流水线有个问题: 两条指令试图同时写寄存器，因为Load在第5阶段用寄存器写口R-type在第4 阶段用寄存器写口把一个功能部件同时被多条指令使用的现象称为结构冒险(Struture Hazard)为了流水线能顺利工作，规定：每个功能部件每条指令只能用一次（如：写口不能用两次或以上）每个功能部件必须在相同的阶段被使用（如：写口总是在第五阶段被使用）IfetchReg/DecExecWrR-typeIfetchReg/DecExecWrR-typeClockCycle 1 Cycle
15、2Cycle 3 Cycle 4Cycle 5Cycle 6Cycle 7Cycle 8Cycle 9IfetchReg/DecExecWrR-typeIfetchReg/DecExecWrR-typeIfetchReg/DecExecMemWrLoadWe have a problem!或称为资源冲突！14解决方案: R-TYPE的WR操作延后一个周期执行加一个NOP阶段以延迟“写”操作:把“写”操作安排在第5阶段, 这样使R-Type的Mem阶段为空NOP这样使流水线中的每条指令都有相同多个阶段这样使流水线中的每条指令都有相同多个阶段!IfetchReg/DecExecWrR-type12
16、345MemClockCycle 1 Cycle 2Cycle 3 Cycle 4Cycle 5Cycle 6Cycle 7Cycle 8Cycle 9IfetchReg/DecWrR-typeIfetchReg/DecWrR-typeIfetchReg/DecExecMemWrLoadIfetchReg/DecWrR-typeIfetchReg/DecWrR-typeMemExecExecExecExecMemMemMemNOOP!15STORE指令的四个阶段Ifetch：取指令并计算PC+4Reg/Dec：从寄存器取数，同时指令在译码器进行译码Exec：16位立即数符号扩展后与寄存器值相加
17、，计算主存地址Mem：将寄存器读出的数据写到主存Cycle 1 Cycle 2Cycle 3 Cycle 4IfetchReg/DecExecMemStoreWrWr: 加一个空的写阶段，使流水线更规整！加一个空的写阶段，使流水线更规整！NOOP!16BEQ的四个阶段Ifetch: 取指令并计算PC+4Reg/Dec:从寄存器取数，同时指令在译码器进行译码Exec: 执行阶段ALU中比较两个寄存器的大小（做减法）Adder中计算转移地址Mem: 如果比较相等, 则：转移目标地址写到PCCycle 1 Cycle 2Cycle 3 Cycle 4IfetchReg/DecExecMemBeqWr
18、NOOP!Wr: 加一个空写阶段，使流水线更规整！加一个空写阶段，使流水线更规整！与多周期通路有什么不同？与多周期通路有什么不同？多周期通路中，在多周期通路中，在Reg/Dec阶段阶段投机投机进行了转移地址的进行了转移地址的计算！可以减少计算！可以减少Branch指指令的时钟数令的时钟数为什么流水线中不进行为什么流水线中不进行“投机投机”计算？计算？因为，流水线中所有指令的因为，流水线中所有指令的执行阶段一样多，执行阶段一样多，Branch指令无需节省时钟，因为有指令无需节省时钟，因为有比它更复杂的指令。比它更复杂的指令。按照上述方式，把所有指令都按照最复按照上述方式，把所有指令都按照最复杂的
19、杂的“load”指令所需的五个阶段来划指令所需的五个阶段来划分，不需要的阶段加一个分，不需要的阶段加一个“NOP”操作操作17A PIPELINED DATAPATH（五阶段流水线数据通路）IF/ID RegisterID/Ex RegisterEx/Mem RegisterMem/Wr RegisterPCDataMemWADiRADoIUnitAIRFileDiRaRbRwMemWrRegWrExtOpExecUnitbusAbusBImmALUOpALUSrcMux10MemtoReg10RegDstRtRdImmPC+4PC+4RsRtPC+4ZeroBranch10ClkIfetch
20、 (IF)Reg/Dec (ID)Exec (Ex)MemWrClock-to-Q delay下面看每条指令在流水线通路中的执行过程下面看每条指令在流水线通路中的执行过程Wr阶阶段没有段没有Data-Path吗吗？有！寄存器写口有！寄存器写口流水段寄存器的作用？流水段寄存器的作用？保存每个周期执行的结果保存每个周期执行的结果! !属于内部寄存器，对程序员透属于内部寄存器，对程序员透明，不需作为现场保存明，不需作为现场保存18取指令（IFETCH) 阶段开始时第10单元指令: lw $1, 0x100($2) 功能：$1 - Mem ($2) + 0x100IF/ID: ？ID/Ex Regis
21、terEx/Mem RegisterMem/Wr RegisterPC = 10DataMemWADiRADoIUnitAIRFileDiRaRbRwMemWrRegWrExtOpExecUnitbusAbusBImmALUOpALUSrcMux10MemtoReg10RegDstRtRdImmPC+4PC+4RsRtPC+4ZeroBranch10ClkIfetchReg/DecExecMemYou are here!有谁发现这里有一个假设有问题？有谁发现这里有一个假设有问题？MIPS指令的地址可能是指令的地址可能是10吗？吗？19取指令（IFETCH) 阶段结束后第10单元指令: lw $
22、1, 0x100($2) 功能：$1 Mem ($2) + 0x100IF/ID: lw $1, 100 ($2)ID/Ex RegisterEx/Mem RegisterMem/Wr RegisterPC = 14DataMemWADiRADoIUnitAIRFileDiRaRbRwMemWrRegWrExtOpExecUnitbusAbusBImmALUOpALUSrcMux10MemtoReg10RegDstRtRdImmPC+4PC+4RsRtPC+4ZeroBranch10ClkIfetchReg/DecExecMemYou are here!下一目标：设计下一目标：设计IUnit（
23、功能是啥？）（功能是啥？）20指令部件IUNIT的设计第10单元指令: : lw $1, 0x100($2) 随后的指令在14号单元中！IF/ID: lw $1, 100 ($2)PC = 1410AdderInstructionMemory“4”InstructionAddressClkIfetchYou are here!Reg/Dec开始从开始从14号号单元取指！单元取指！PC 新值（新值（14） 旧输出（旧输出（10）流水段寄存器用来存流水段寄存器用来存放各阶段的执行结果放各阶段的执行结果总是在下个时钟到来总是在下个时钟到来后的后的Clock-to-Q写入写入取指阶段有哪些控制信号？取
24、指阶段有哪些控制信号？不需控制信号，因为每条指令执行功能一样，是确定不需控制信号，因为每条指令执行功能一样，是确定的，无需根据指令的不同来控制执行不同的操作！的，无需根据指令的不同来控制执行不同的操作！指令部件功能指令部件功能Instr MemPCPC PC+4这里这里MUX的控制信的控制信号由其他号由其他阶段产生阶段产生！应把哪些信息存到流应把哪些信息存到流水段寄存器水段寄存器IF/ID中？中？应保存后面阶段用到的应保存后面阶段用到的指令和指令和PC+4的值！的值！指令在随后阶段被送出译码！指令在随后阶段被送出译码！PC+4用来计算转移目标地址用来计算转移目标地址21译码/取数（REG/DE
25、C）阶段第10单元指令: lw $1, 0x100($2) 功能：$1 Mem($2) + 0x100IF/ID:ID/Ex: Reg. 2 & 0x100Ex/Mem RegisterMem/Wr RegisterPC DataMemWADiRADoIUnitAIRFileDiRaRbRwMemWrRegWrExtOpExecUnitbusAbusBImmALUOpALUSrcMux10MemtoReg10RegDstRtRdImmPC+4PC+4RsRtPC+4ZeroBranch10ClkIfetchReg/DecExecMemYou are here!RegRs,RegRt,Rt,Rd
26、,Imm16,PC+4等被保存在等被保存在ID/EXE中中该阶段有哪些控制信号？该阶段有哪些控制信号？没有！因是所有指令的公共操作，故无控制信号没有！因是所有指令的公共操作，故无控制信号！RegWr是是Wr段段的信号的信号！指令还要存指令还要存ID/EX中吗？中吗？不要，只要不要，只要存相关信息存相关信息22LOAD指令的地址计算阶段第10单元指令: lw $1, 0x100($2) 功能：$1 Mem($2) + 0x100IF/ID:ID/Ex RegisterEx/Mem: Loads AddressMem/Wr RegisterPCDataMemWADiRADoIUnitAIRFile
27、DiRaRbRwMemWrRegWrExecUnitbusAbusBImmMux10MemtoReg10RtRdImmPC+4PC+4RsRtPC+4ZeroBranch10ClkIfetchReg/DecExecMemYou are here!ExtOp=？ALUOp=？ALUSrc=？RegDst=0指令已被译码，可确定执行部件的控制信号！指令已被译码，可确定执行部件的控制信号！下一目标：设计执行部件下一目标：设计执行部件(Exec Unit)连接到错误的目的地址，连接到错误的目的地址，指令执行错误指令执行错误！目的寄存器目的寄存器Rt不传不传递下去会怎样？递下去会怎样？23执行部件（EX
28、EC UNIT）的设计ID/Ex RegisterEx/Mem: Loads Memory AddressALUControlALUctr32busA32busBExtenderMux16immALUSrc=?ExtOp=?3ALUZero0132ALUout32Adder3ALUOp=? Tread比较洗衣流水线，指比较洗衣流水线，指令流水有什么不同？令流水有什么不同？洗衣流程不能反向进行，但洗衣流程不能反向进行，但该阶段有反向数据流，可能该阶段有反向数据流，可能会引起冒险！以后介绍。会引起冒险！以后介绍。25LOAD指令的回写（WRITE BACK）阶段Location 10: lw $1
29、, 0x100($2) 功能：$1 Mem($2) + 0x100IF/ID:ID/Ex RegisterEx/Mem RegisterMem/Wr RegisterPCDataMemWADiRADoIUnitAIRFileDiRaRbRwMemWrRegWr=1ExtOpExecUnitbusAbusBImmALUOpALUSrcMux1010RegDstRtRdImmPC+4PC+4RsRtPC+4ZeroBranch10ClkIfetchReg/DecExecMemWr各阶段所经各阶段所经DataPath已有，控制信号如何得到？已有，控制信号如何得到？该阶段有反向数据流，可能该阶段有反向
30、数据流，可能会引起冒险！以后介绍。会引起冒险！以后介绍。MemtoReg=126流水线中的CONTROL SIGNALS如何获得?主要考察: 第N阶段的控制信号，它取决于是某条指令的某个阶段。N = Exec, Mem, or Wr (只有这三个阶段有控制信号）例: Load的Exec段的控制信号如图中所示MemWrMemtoRegRegDst=0IF/ID:ID/Ex RegisterEx/Mem: Loads AddressMem/Wr RegisterPCDataMemWADiRADoIUnitAIRFileDiRaRbRwRegWrExtOp=1ExecUnitbusAbusBImmA
31、LUOp=AddALUSrc=1Mux1010RtRdI16PC+4PC+4RsRtPC+4ZeroBranch10IfetchReg/DecExecMemWr27流水线中的CONTROL SIGNALS如何获得?在取数/译码（Reg/Dec）阶段产生本指令每个阶段的所有控制信号Exec信号(ExtOp, ALUSrc, .) 在1个周期后使用Mem信号(MemWr,Branch) 在2个周期后使用Wr信号(MemtoReg, RegWr) 在3个周期后使用IF/ID RegisterID/Ex RegisterEx/Mem RegisterMem/Wr Register2Reg/Dec3 E
32、xec4 MemExtOpALUOpRegDstALUSrcBranchMemWrMemtoRegRegWrMainControlExtOpALUOpRegDstALUSrcMemtoRegRegWrMemtoRegRegWrMemtoRegRegWrBranchMemWrBranchMemWr5 Wr 各流水段部件在一个时钟内完成各流水段部件在一个时钟内完成某条指令的某个阶段某条指令的某个阶段的工作！的工作！所以，控制信号所以，控制信号也要保存在流水也要保存在流水段寄存器中！段寄存器中！在下个时钟到达时，把执行结果以及前面传递来的后面各阶段要用到的所有数据在下个时钟到达时，把执行结果以及前面
33、传递来的后面各阶段要用到的所有数据（如：指令、立即数、目的寄存器等）和控制信号保存到流水线寄存器中！（如：指令、立即数、目的寄存器等）和控制信号保存到流水线寄存器中！28流水线中的CONTROL SIGNALS通过对前面流水线数据通路的分析，得知：因为每个时钟都会改变PC的值，所以PC不需要写控制信号流水段寄存器每个时钟都会写入一次，也不需要写控制信号Ifecth阶段和Dec/Reg阶段都没有控制信号，因为功能都一样Exec阶段的控制信号有四个ExtOp (扩展器操作)：1- 符号扩展；0- 零扩展ALUSrc (ALU的B口来源)：1- 来源于扩展器；0- 来源于BusBALUOp (主控制
34、器输出，用于辅助局部ALU控制逻辑来决定ALUCtrl)RegDst (指定目的寄存器)：1- Rd；0- RtMem阶段的控制信号有两个MemWr (DM的写信号)：Store指令时为1，其他指令为0Branch (是否为分支指令)：分支指令时为1，其他指令为0Wr阶段的控制信号有两个MemtoReg (寄存器的写入源)：1- DM输出；0- ALU输出RegWr (寄存器堆写信号)：结果写寄存器的指令都为1，其他指令为029控制逻辑(CONTROL)的设计流水线控制逻辑的设计每条指令的控制信号在指令执行期间都不变与单周期控制逻辑设计类似设计过程控制逻辑分成两部分主控制逻辑：生成主控制逻辑：
35、生成ALUop和其他控制信号和其他控制信号局部局部ALU控制逻辑：根据控制逻辑：根据ALUop和和func字段生成字段生成ALUCtrl用真值表建立指令和控制信号之间的关系写出每个控制信号的逻辑表达式控制逻辑的输出（控制信号）在ID阶段生成，并存放在ID/EX流水段寄存器中，然后每来一个时钟跟着其它数据和信息传送到下一级流水段寄存器在同一时刻，不同阶段同时执行不同指令，不同的指令得到不同控制信号请复习单周期和多周期控制器设计。请复习单周期和多周期控制器设计。30蓝色部分是控制信号蓝色部分是控制信号31控制信号在流水线中的传递以及带来的问题在取数/译码（Reg/Dec）阶段产生本指令每个阶段的所
36、有控制信号Exec信号(ExtOp, ALUSrc, .) 在1个周期后使用Mem信号(MemWr,Branch) 在2个周期后使用Wr信号(MemtoReg, RegWr) 在3个周期后使用IF/ID RegisterID/Ex RegisterEx/Mem RegisterMem/Wr RegisterReg/DecExecMemExtOpALUOpRegDstALUSrcBranchMemWrMemtoRegRegWrMainControlExtOpALUOpRegDstALUSrcMemtoRegRegWrMemtoRegRegWrMemtoRegRegWrBranchMemWrBra
37、nchMemWrWr 保存在流水段寄存器中的信息（包括前面阶段传递来或执行的结果保存在流水段寄存器中的信息（包括前面阶段传递来或执行的结果及控制信号）一起被传递到下一个流水段！及控制信号）一起被传递到下一个流水段！所以，控制信号也要保存在流水段寄存器中！所以，控制信号也要保存在流水段寄存器中！RtData(这里是否会有问题？这里是否会有问题？)Rt和和Data在在RegWr后到达怎么办？后到达怎么办？同样，这里同样，这里也有问题！也有问题！32流水线中的“竞争”问题多周期中解决 Addr 和WrEn之间竞争问题的方法:在第 N周期结束时，让Addr信号有效在第N + 1周期让WrEn有效上述方
38、法在流水线设计中不能用，因为：每个周期必须能够写Register每个周期必须能够写MemoryClockIfetchReg/DecExecMemWrStoreIfetchReg/DecExecMemWrStoreIfetchReg/DecExecMemWrR-typeIfetchReg/DecExecMemWrR-type如何解决如何解决? 保证保证Addr信号信号在在WriteEnable信号之前到达信号之前到达33寄存器组的同步和存储器的同步解决方案: 将Write Enable和时钟信号“与”1. Addr, Data, 和 WrEn 必须在Clk边沿到来后至少稳定一个 set-up时间
39、2. Clk高电平时间 大于 写入时间ClkAddressDataWrEnReg FileorMemoryWrEnI_AddrI_DataReg FileorMemoryClkI_AddrI_WrEnAddressDataI_WrEnC_WrEnC_WrEnActual write等价于等价于须由电路专家确保不会发生须由电路专家确保不会发生“定时错误定时错误”（即：能合理设计（即：能合理设计“Clock”!）相当于单周期通路中的理想寄存器和存储器相当于单周期通路中的理想寄存器和存储器34流水线举例：考察流水线DATAPATH的数据流动情况End of Cycle 4: Loads Mem, R
40、-types Exec, Stores Reg, Beqs IfetchEnd of Cycle 5: Loads Wr, R-types Mem, Stores Exec, Beqs RegEnd of Cycle 6: R-types Wr, Stores Mem, Beqs ExecEnd of Cycle 7: Stores Wr, Beqs MemEnd ofCycle 4End ofCycle 5End ofCycle 6End ofCycle 7ClockCycle 1Cycle 2Cycle 3Cycle 4Cycle 5Cycle 6Cycle 7Cycle 8IfetchR
41、eg/DecExecMemWr0: LoadIfetchReg/DecExecMemWr4: R-typeIfetchReg/DecExecMemWr8: StoreIfetchReg/DecExecMemWr12: Beq (target is 1000)考察以下几个点的情况：考察以下几个点的情况：说明：后面仅考察数据流动情况，控制信号随数据同步流动因而不再说明。说明：后面仅考察数据流动情况，控制信号随数据同步流动因而不再说明。35第四周期结束时的状态：0:Loads Mem 4: R-types Exec 8: Stores Reg 12: Beqs IfetchIF/ID: Beq In
42、structionID/Ex: Stores busA & BEx/Mem: R-types ResultMem/Wr: Loads DoutPC = 16DataMemWADiRADoIUnitAIRFileDiRaRbRwRegWr=?ExtOp=xExecUnitbusAbusBImmALUOp=R-typeALUSrc=0Mux10MemtoReg=?10RegDst=1RtRdImmPC+4PC+4RsRtPC+4ZeroBranch=01012: Beqs Ifet8: Stores Reg4: R-types Exec0: Loads MemClkMemWr=0Clk如果如果Me
43、m阶段是阶段是Branch且且Zero为为1，会怎样？，会怎样？ ?s WrLoad指令前指令前某指令某指令（1）（2）（3）（5）（4）36第五周期结束时的状态：0:Lws Wr 4: Rs Mem 8: Stores Exec 12: Beqs Reg 16: Rs IfetchIF/ID: Instruction 16ID/Ex: Beqs busA & BEx/Mem: Stores AddressMem/Wr: R-types ResultPC = 20DataMemWADiRADoIUnitAIRFileDiRaRbRwRegWr=1ExtOp=1ExecUnitbusAbusBI
44、mmALUOp=AddALUSrc=1Mux10MemtoReg=110RegDst=xRtRdImmPC+4PC+4RsRtPC+4ZeroBranch=01016: Rs Ifet12: Beqs Reg8: Stores Exec4: R-types MemClkMemWr=0Clk同一周期寄存器有读和写，可能吗？同一周期寄存器有读和写，可能吗？利用时钟上升和下降沿两次触发，能利用时钟上升和下降沿两次触发，能做到前半周期写，后半周期读做到前半周期写，后半周期读寄存器的写口和读口可看寄存器的写口和读口可看成是独立的两个部件！成是独立的两个部件！0: Loads Wr2037第六周期结束时的
45、状态：4:Rs Wr 8: Stores Mem 12: Beqs Exec 16: Rs Reg 20: Rs IfetIF/ID: Instruction 20ID/Ex:R-types busA & BEx/Mem: Beqs ResultsMem/Wr: Nothing for StPC = 24DataMemWADiRA DoIUnitAIRFileDiRaRbRwRegWr=1ExtOp=1ExecUnitbusAbusBImmALUOp=SubALUSrc=0Mux10MemtoReg=010RegDst=xRtRdImmPC+4PC+4RsRtPC+4ZeroBranch=01
46、020:R-types Ifet 16: R-types Reg12: Beqs Exec8: Stores Mem4: R-types WrClkMemWr=1ClkIfetch和和Reg两个周两个周期每条指令执行的期每条指令执行的都一样！都一样！38第七周期结束时的状态：8:Stores Wr 12: Beqs Mem 16: Rs Exec 20: Rs Reg 24: Rs IfetIF/ID: Instruction 24ID/Ex:R-types busA & BEx/Mem: Rtypes ResultsMem/Wr:Nothing for BeqPC = 1000DataMem
47、WADiRA DoIUnitAIRFileDiRaRbRwRegWr=0ExtOp=xExecUnitbusAbusBImmALUOp=R-typeALUSrc=0Mux10MemtoReg=x10RegDst=1RtRdImmPC+4PC+4RsRtPC+4ZeroBranch=11024:R-types Ifet20: R-types Reg16: R-types Exec12: Beqs Mem8: Stores WrClkMemWr=0Clk假定相等，假定相等，则则Zero=1转移目标地转移目标地址送址送PC!这里出现反向数据流这里出现反向数据流!转移目标地址反向送给转移目标地址反向送
48、给PC可可能会导致控制冒险！能会导致控制冒险！39总结前面的流水线执行过程（有关BEQ）Branch指令何时确定是否转移？转移目标地址在第几周期计算出来？第六周期得到Zero和转移地址、第七周期控制转移地址送到PC输入端、第八周期开始才能根据转移地址取指令如果Branch指令执行结果是需要转移（称为taken），则流水线会怎样？ClockCycle 1 Cycle 2Cycle 3 Cycle 4Cycle 5Cycle 6Cycle 7Cycle 8IfetchReg/DecExecMemWr0: LoadIfetchReg/DecExecMemWr4: R-typeIfetchReg/De
49、cExecMemWr8: StoreIfetchReg/DecExecMemWr12: Beq (target is 1000)IfetchReg/DecExecMemWr16: R-typeIfetchReg/DecExecMemWrIfetchReg/DecExecMem24: R-type20: R-typeIfetchReg/DecExec1000: Target of Br40转移分支指令(BRANCH)引起的“延迟”现象虽然Beq指令在第四周期取出，但:目标地址在第七周期才被送到PC的输入端第八周期才能取出目标地址处的指令执行结果：在取目标指令之前，已有三条指令被取出，取错了三条指
50、令！这种现象称为控制冒险（Control Hazard ）（注：也称为分支冒险或转移冒险（Branch Hazard） ）Cycle 4 Cycle 5Cycle 6 Cycle 7Cycle 8Cycle 9Cycle 10 Cycle 11ClkIfetchReg/DecExecMemWrIfetchReg/DecExecMemWr16: R-typeIfetchReg/DecExecMemWrIfetchReg/DecExecMemWr24: R-type12: Beq(target is 1000)20: R-typeIfetchReg/DecExecMemWr1000: Target
51、 of Br41总结前面的流水线执行过程（有关LOAD）Load指令何时能把数据写到寄存器？第几周期开始写数据？第五周期写入、第六周期开始才能使用如果后面R-Type的操作数是load指令目标寄存器的内容，则流水线怎样？ClockCycle 1 Cycle 2Cycle 3 Cycle 4Cycle 5Cycle 6Cycle 7Cycle 8IfetchReg/DecExecMemWr0: LoadIfetchReg/DecExecMemWr4: R-typeIfetchReg/DecExecMemWr8: Store12: Beq (target is 1000)16: R-type24:
52、 R-type20: R-type1000: Target of Br42装入指令(LOAD)引起的“延迟”现象尽管Load指令在第一周期就被取出，但:数据在第五周期结束才被写入寄存器在第六周期时，写入的数据才能被用结果：在Load指令结果有效前，已经有三条指令被取出(如果随后的指令要用到Load的数据的话，就需要延迟三条指令才能用！)这种现象被称为数据冒险(Data Hazard) 或数据相关(Data Dependency)ClockCycle 1 Cycle 2Cycle 3 Cycle 4Cycle 5Cycle 6Cycle 7Cycle 8IfetchReg/DecExecMemW
53、rI0: LoadIfetchReg/DecExecMemWrPlus 1IfetchReg/DecExecMemWrPlus 2IfetchReg/DecExecMemWrPlus 3IfetchReg/DecExecMemWrR-Type43寄存器的使用方式对数据冒险有影响数据在第五周期的前半段写入寄存器在第五周期的后半段，写入的数据才能被用结果：在Load指令结果有效前，已经有两条指令被取出(如果随后的指令要用到Load的数据的话，就需要延迟两条指令才能用！)ClockCycle 1 Cycle 2Cycle 3 Cycle 4Cycle 5Cycle 6Cycle 7Cycle 8If
54、etchReg/DecExecMemWrI0: LoadIfetchReg/DecExecMemWrPlus 1IfetchReg/DecExecMemWrPlus 2IfetchReg/DecExecMemWrR-Type44第一讲内容小结指令的执行可以像洗衣服一样，分为N个步骤，并用流水线方式进行均衡时指令吞吐率提高N倍，但不能缩短一条指令的执行时间流水段数以最复杂指令所需步骤数为准（有些指令的某些阶段为空操作），每个阶段的宽度以最复杂阶段所需时间为准（尽量调整使各阶段均衡）以Load指令为准，分为五个阶段取指令段(IF)取指令、计算PC+4（IUnit：Instruction Memor
55、y、Adder）译码/读寄存器(ID/Reg)段指令译码、读Rs和Rt（寄存器读口）执行(EXE)段计算转移目标地址、ALU运算（Extender、ALU、Adder）存储器(MEM)段读或写存储单元（Data Memory）写寄存器(Wr)段ALU结果或从DM读出数据写到寄存器（寄存器写口）流水线控制器的实现IF和ID/Reg段不需控制信号控制，只有EXE、MEM和Wr需要ID段生成所有控制信号，并随指令的数据同步向后续阶段流动寄存器和存储器的竞争问题可利用时钟信号来解决流水线冒险：结构冒险、控制冒险、数据冒险（下一讲主要介绍解决流水线冒险的数据通路如何设计）45第二讲流水线冒险的处理流水线
56、冒险的几种类型数据冒险的现象和对策数据冒险的种类相关的数据是ALU结果：可以通过转发解决相关的数据是DM读出的内容：随后的指令需被阻塞一个时钟数据冒险和转发转发检测/ 转发控制数据冒险和阻塞阻塞检测/ 阻塞控制控制冒险的现象和对策静态分支预测技术动态分支预测技术缩短分支延迟技术流水线中对异常和中断的处理访问缺失对流水线的影响主主 要要 内内 容容46 Hazards：指流水线遇到无法正确执行后续指令或执行了不该执行的指令Structural hazards Data hazards: Control (Branch)hazards总结：流水线的三种总结：流水线的三种冲突冲突/冒险冒险（Haza
57、rd）情况）情况47MemSTRUCTURAL HAZARD（结构冒险）现象Time (clock cycles)LoadInstr 1Instr 2Instr 3Instr 4ALUMemRegMemRegALUMemRegMemRegALUMemRegMemRegALURegMemRegALUMemRegMemReg如果只有一个存储器，则在如果只有一个存储器，则在Load指令取数据同时又取指令的话，则发生冲突！指令取数据同时又取指令的话，则发生冲突！如果不对寄存器堆的写口和读口独立设置的话，则发生冲突！如果不对寄存器堆的写口和读口独立设置的话，则发生冲突！结构冒险也称为硬件资源冲突：同一个
58、执行部件被多条指令使用。结构冒险也称为硬件资源冲突：同一个执行部件被多条指令使用。48RegSTRUCTURAL HAZARD的解决方法Instr.OrderTime (clock cycles)LoadInstr 1Instr 2Instr 3Instr 4ALUImRegDmALUImRegDmALUImRegDmRegALURegDmRegALUImRegDmReg将将Instruction Memory (Im) 和和 Data Memory (Dm)分开分开将将寄存器读口寄存器读口和和写口写口独立开来独立开来Im为了避免结构冒险，规定流水线数据通路中功能部件的设置原则为：为了避免结构
59、冒险，规定流水线数据通路中功能部件的设置原则为：每个部件在特定的阶段被用！（如：每个部件在特定的阶段被用！（如：ALU总在第三阶段被用！）总在第三阶段被用！）RegBACK49DATA HAZARD现象add r1 ,r2,r3sub r4, r1 ,r3and r6, r1 ,r7or r8, r1 ,r9xor r10, r1 ,r11想一下，哪条指令的想一下，哪条指令的r1是老的值？是老的值？ 哪条是新的值？哪条是新的值？画出流水线图能很清楚理解！画出流水线图能很清楚理解！举例说明：以下指令序列中，寄存器举例说明：以下指令序列中，寄存器r1会发生数据冒险会发生数据冒险本讲介绍基本流水线，
60、仅考虑本讲介绍基本流水线，仅考虑RAW冒险冒险50DATA HAZARD ON R1Instr.OrderTime (clock cycles)add r1,r2,r3sub r4,r1,r3and r6,r1,r7or r8,r1,r9xor r10,r1,r11IFID/RFEXMEMWBALUImRegDmRegALUImRegDmRegALUImRegDmRegImALURegDmRegALUImRegDmReg最后一条指令的最后一条指令的r1才是新的值！才是新的值！如何解决这个问题？如何解决这个问题？51方案1: 在硬件上采取措施，使相关指令延迟执行Instr.OrderTime (
61、clock cycles)add r1,r2,r3sub r4,r1,r3and r6,r1,r7IFID/RFEXMEMWBALUImRegDmRegALUImRegDmRegstallstallstallALUImRegDmbubble bubble bubble bubbleImbubble bubble bubble bubbleImbubble bubble bubble bubbleIm 硬件上通过阻塞硬件上通过阻塞(stall)方式阻止后续指令执行，延迟到有新值以后！方式阻止后续指令执行，延迟到有新值以后！这种做法称为流水线阻塞，也称为这种做法称为流水线阻塞，也称为“气泡气泡Bu
62、bble” 缺点：控制相当复杂，需要改数据通路！缺点：控制相当复杂，需要改数据通路！ 52方案2: 软件上插入无关指令Instr.OrderTime (clock cycles)add r1,r2,r3sub r4,r1,r3and r6,r1,r7IFID/RFEXMEMWBALUImRegDmRegALUImRegDmReg 最差的做法：由编译器插入三条最差的做法：由编译器插入三条NOP指令，浪费三条指令的空间和时间指令，浪费三条指令的空间和时间nopnopnopALUImRegDmALUImRegDmRegALUImRegDmRegImALURegDmReg53方案3: 利用DATAPA
63、TH中的中间数据Instr.OrderTime (clock cycles)add r1,r2,r3sub r4,r1,r3and r6,r1,r7or r8,r1,r9xor r10,r1,r11IFID/RFEXMEMWBALUImRegDmRegALUImRegDmRegALUImRegDmRegImALURegDmRegALUImRegDmReg 仔细观察后发现：流水段寄存器中已有需要的值仔细观察后发现：流水段寄存器中已有需要的值r1！1. 把数据从流水段寄存器中直接取到把数据从流水段寄存器中直接取到ALU的输入端的输入端2. 寄存器写寄存器写/读口分别在前读口分别在前/后半周期，使写
64、入被直接读出后半周期，使写入被直接读出称为转发（称为转发（Forwading）或旁路（或旁路（Bypassing）在哪个流水段在哪个流水段R中？中？54硬件上的改动以支持“转发”技术(自学) 加加MUX，使流水段寄存器值返送，使流水段寄存器值返送ALU输入端输入端 假定流水段寄存器能读出新写入的值假定流水段寄存器能读出新写入的值 (否则，需要更多的转发数据否则，需要更多的转发数据)add r3, r2, r1Sub r5, r3, r4add r3, r2, r1Or r6, r2, r1Sub r5, r3, r4lw r3, 100(r1)Or r6, r2, r1Sub r5, r3,
65、r4lw r3, 100(r1)Or r6, r3, r1如果指令序列为：如果指令序列为：能用能用“转发转发”技术解技术解决这里的数据冒险吗决这里的数据冒险吗？ExMem55复习: LOAD指令引起的延迟现象Load指令最早在哪个流水线寄存器中开始有后续指令需要的值？ClockCycle 1 Cycle 2Cycle 3 Cycle 4Cycle 5Cycle 6Cycle 7Cycle 8IfetchReg/DecExecMemWrI0: LoadIfetchReg/DecExecMemWrPlus 1IfetchReg/DecExecMemWrPlus 2IfetchReg/DecExec
66、MemWrPlus 3IfetchReg/DecExecMemWrPlus 4实际上，在第四周期结束时，数据在流水段寄存器中已经有值。实际上，在第四周期结束时，数据在流水段寄存器中已经有值。采用数据转发技术可以使采用数据转发技术可以使load指令后面第二条指令得到所需的值指令后面第二条指令得到所需的值但不能解决但不能解决load指令和随后的第一条指令间的数据冒险，要延迟执行一条指令！指令和随后的第一条指令间的数据冒险，要延迟执行一条指令！这种这种load指令和随后指令间的数据冒险，称为指令和随后指令间的数据冒险，称为“装入装入- 使用数据冒险使用数据冒险(load- use Data Haza
67、rd)”若不采用转发，则在何时才若不采用转发，则在何时才能用使用能用使用Load指令的结果？指令的结果？延迟延迟2或或3条指令！条指令！56“FORWARDING”技术使LOAD-USE冒险只需延迟一个周期Instr.OrderTime (clock cycles)lw r1, 0(r2)sub r7,r1,r3and r6,r1,r7or r8,r1,r9IFID/RFEX MEMWBALUImRegDmRegALUImRegDmRegALUImRegDmRegImALURegDmReg采用采用“转发转发”后仅第二条指令后仅第二条指令 SUB r7,r1,r3 不能按时执行！需要阻塞一个周期
68、。不能按时执行！需要阻塞一个周期。（其它后续指令顺延）（其它后续指令顺延）发生发生“装入装入- 使用数据冒险使用数据冒险”时，需要对时，需要对load后的指令阻塞一个时钟周期！后的指令阻塞一个时钟周期！57方案1: 硬件阻止指令执行来解决LOAD-USEInstr.OrderTime (clock cycles)lw r1, 0(r2)sub r4,r1,r3IFID/RFEXMEMWBALUImRegDmRegstallbubble bubble bubble bubbleImand r6,r1,r7or r8,r1,r9ALUImRegDmRegALUImRegDmRegImALURegD
69、mReg用硬件阻塞一个周期用硬件阻塞一个周期 58方案2: 软件上插入NOP指令来解决LOAD-USEInstr.OrderTime (clock cycles)lw r1, 0(r2)sub r4,r1,r3IFID/RFEXMEMWB用软件插入一条用软件插入一条NOP指令！（有些处理器不支持硬件阻塞处理）指令！（有些处理器不支持硬件阻塞处理）例如：例如：MIPS 1 处理器没有硬件阻塞处理，而由编译器（或汇编程序员）处理器没有硬件阻塞处理，而由编译器（或汇编程序员） 来处理。来处理。nopand r6,r1,r7or r8,r1,r9ALUImRegDmRegALUImRegDmRegIm
70、ALURegDmRegALUImRegDmRegALUImRegDmReg59以下源程序可生成两种不同的代码，优化的代码可避免以下源程序可生成两种不同的代码，优化的代码可避免Load阻塞阻塞a = b + c;d = e f;假定假定 a, b, c, d ,e, f 在内存在内存方案3：编译器进行指令顺序调整来解决LOAD-USEFast code:lw $2, blw $3, clw $5, e add $1, $2, $3lw $6, fsw a, $1 sub $4, $5, $6swd, $4 Slow code:lw$2, blw $3, cadd $1, $2, $3sw a,
71、$1 lw $5, e lw $6, fsub $4, $5, $6swd, $4调整后调整后编译器的优化很重要！编译器的优化很重要！真正执行时需阻塞真正执行时需阻塞2次次真正执行时无需阻塞真正执行时无需阻塞60阶段小结：数据冒险的解决方法方法1：硬件阻塞（stall）方法2：软件插入“NOP”指令方法3：编译优化：调整指令顺序，能解决所有数据冒险吗？方法4：合理实现寄存器堆的读/写操作，能解决所有数据冒险吗？前半时钟周期写，后半时钟周期读，若同一个时钟内前面指令写入的数据正好是后面指令所读数据，则不会发生数据冒险方法5：转发（Forwarding或Bypassing 旁路）技术，能解决所有数
72、据冒险吗？若相关数据是ALU结果，则如何？可通过转发解决若相关数据是上条指令DM读出内容，则如何？不能通过转发解决，随后指令需被阻塞一个时钟或加NOP指令实现实现“转发转发”和和“阻塞阻塞” 要修改数据通路：要修改数据通路：（1）检测何时需要）检测何时需要“转发转发” ，并控制实现，并控制实现“转发转发”（2）检测何时需要）检测何时需要“阻塞阻塞”，并控制实现，并控制实现“阻塞阻塞”称为称为Load-use数据冒险！数据冒险！61带转发的流水线数据通路ForwardAForwardB62LOAD-USE DATA HAZARD（硬件阻塞方式）Instr.OrderTime (clock cyc
73、les)lw r1, 0(r2)sub r4,r1,r3IFID/RFEXMEMWBALUImRegDmRegImand r6,r1,r7or r8,r1,r9ALUImRegDmRegALUImRegDmRegImALURegDmReg检测点检测点需解决以下问题：需解决以下问题：(1) 判断什么条件下需要阻塞判断什么条件下需要阻塞 阻塞点阻塞点RegID/EX.MemRead and (ID/EX.RegisterRt=IF/ID.RegisterRs or ID/EX.RegisterRt=IF/ID.RegisterRt)前面指令为前面指令为Load 并且并且前面指令的目的寄存器等于当前
74、面指令的目的寄存器等于当前刚取出指令的源寄存器前刚取出指令的源寄存器(2) 修改数据通路来实现阻塞修改数据通路来实现阻塞: ID/EX控制信号清空控制信号清空,PC和和IF/ID内容不变内容不变bubble bubble bubblesub r4,r1,r363带“转发”和“阻塞”检测的流水线数据通路至此，数据冒险的至此，数据冒险的处理全部完成！处理全部完成！ID/EX.MemRead and (ID/EX.RegisterRt=IF/ID.RegisterRs or ID/EX.RegisterRt=IF/ID.RegisterRt)“写使能写使能”信号为信号为0，使，使PC和和IF/ID不
75、不变变使控制信号使控制信号清清0，阻塞，阻塞随后指令！随后指令！064CONTROL HAZARD的解决方法方法1：硬件上阻塞（stall）分支指令后三条指令的执行使后面三条指令清0或其操作信号清0，以插入三条NOP指令方法2：软件上插入三条“NOP”指令（以上两种方法的效率太低，需结合分支预测进行）方法3：分支预测（Predict）简单（静态）预测：总是预测条件不满足(not taken)或满足，即：继续执行分支指令的后续指令动态预测：根据程序执行的历史情况，进行动态预测调整，能达90%的预测准确率注：采用分支预测方式时，流水线控制必须确保错误预测指令的执行结果不能生效，而且要能从正确的分支
76、地址处重新启动流水线工作方法4：延迟分支（Delayed branch）（通过编译程序优化指令顺序！）把分支指令前面与分支指令无关的指令调到分支指令后面执行，也称延迟转移另一种控制冒险：另一种控制冒险：异常或中断控制冒险的处理异常或中断控制冒险的处理65简单（静态）分支预测方法基本做法总预测条件不满足(not taken)，即：继续执行分支指令的后续指令可加启发式规则：在特定情况下总是预测满足(taken)，其他情况总是预测不满足如：循环顶（底）部分支总是预测为不满足（满足）。能达65%-85%的预测准确率预测失败时，需把流水线中三条错误预测指令丢弃掉将三条丢弃指令的控制信号值设置为0，使其后
77、续过程中执行nop操作（注：涉及到当时在IF、ID和EX三个阶段的指令）性能如果转移概率是50%，则预测正确率仅有50%预测错误的代价预测错误的代价与何时能确定是否转移有关。越早确定代价越少那最早可以提前到哪个阶段呢？那最早可以提前到哪个阶段呢？66复习:CONTROL HAZARD现象虽然Beq指令在第四周期取出，但:第七周期才确定“是否转移”第八周期才转移到正确指令执行发生转移时，要在流水线中清除Beq后面的三条指令延迟损失时间片C：发生转移时，给流水线带来的延迟损失Cycle 4 Cycle 5Cycle 6 Cycle 7Cycle 8Cycle 9Cycle 10 Cycle 11I
78、fetchReg/DecExecMemWrIfetchReg/DecExecMemWr16: R-typeIfetchReg/DecExecMemWrIfetchReg/DecExecMemWr24: R-type12: Beq(target is 1000)20: R-typeClkIfetchReg/DecExecMemWr1000: Target of Br这里这里 C=367简单（静态）分支预测方法缩短分支延迟，减少错误预测代价可以通过调整“转移地址计算”和“分支条件判断”操作到ID阶段来缩短延迟缺点：增加处理部件和线路。优点：C=1（原来C=3）预测错误的检测和处理（称为“冲刷、冲洗
79、”- Flush）增加控制信号，为1时代表预测失败预测失败时，完成以下两件事：将转移目标地址-PC清除IF( & EX & MEM)段中信息延迟延迟C（1-3）个时钟周期！）个时钟周期！68动态分支预测方法简单的静态分支预测方法的预测成功率不高，所以应考虑动态预测动态预测基本思想：利用最近转移发生的情况，来预测下一次可能发生的转移实际执行时：验证并调整预测转移发生的历史情况记录在BHT中现在几乎所有的处理器都采用动态预测（现在几乎所有的处理器都采用动态预测（dynamic predictor）69分支历史记录表BHT指令预取指令预取器器分支指令地址分支指令地址转移转移目标目标地址地址预测预测位
80、位分支分支指令指令地址地址控制控制逻辑逻辑指令执行指令执行实际执行情况实际执行情况命中命中与否与否加入新项加入新项顺序取顺序取转移取转移取分支历史记录表分支历史记录表BHT=？查找查找选择选择预测预测 修正修正查找时发现都不相查找时发现都不相等，则等，则“未命中未命中”未命中说明什么？未命中说明什么？说明以前没有执说明以前没有执行过该分支指令行过该分支指令 命中时：命中时： 根据预测位，选择根据预测位，选择“转移取转移取”还是还是“顺序取顺序取”未命中时：未命中时： 加入新项，并填入指令地址和转移目标地址、初始化预测位加入新项，并填入指令地址和转移目标地址、初始化预测位70动态预测基本方法采用
81、一位预测位：总是按上次实际发生的情况来预测下次用1位（0或1）表示预测和实际转移情况可根据一个简单的预测状态图进行预测和调整采用二位预测位用2位（00,01,10,11）来表示预测和实际转移情况同样可按预测状态图进行预测和调整采用比较多的是二位预测位，也有采用二位以上采用比较多的是二位预测位，也有采用二位以上预测位。如：预测位。如：Pentium 4 的的BTB2采用采用4位预测位位预测位71一位预测状态图指令预取时，按照预测读取相应分支的指令1：选择“转移取”0：选择“顺序取”指令执行时，按实际执行结果修改预测位对照状态转换图来进行修改例如：对于一个循环分支若初始状态为0(再次循环时为0)，
82、则第一次和最后一次都错若初始状态为1，则只有最后一次会错预测发生预测发生发发生生不发生不发生预测不发生预测不发生不发生不发生 发生发生10正确正确错误错误错误错误正确正确 Loop: add $7, $3, $3 ; i*2 add $7, $7, $7; i*4add $7, $7, $5lw $6, 0($7); $6=Aiadd $1, $1, $6; g= g+Aiadd $3, $3, $4bne $3, $2, Loop Loop:g = g +Ai;i = i+ j;if (i != h) go to Loop:72举例：双重循环的一位动态预测into sum (int N)in
83、t i, j, sum=0;for (i=0; i N; i+) for (j=0; j N; j+) sum=sum+1;return sum; Loop-i: beq $t1,$a0, exit-i # 若若( i=N)则跳出外循环则跳出外循环 add $t2, $zero, $zero #j=0 Loop-j: beq $t2, $a0, exit-j # 若若(j=N)则跳出内循环则跳出内循环 addi $t2, $t2, 1 # j=j+1 addi $t0, $t0, 1 #sum=sum+1 j Loop-jexit-j: addi $t1, $t1, 1 # i=i +1 j
84、Loop-iexit-i: 外循环中的分支指令共执行外循环中的分支指令共执行N+1次，次，内循环中的分支指令共执行内循环中的分支指令共执行N(N+1)次。次。预测位初始为预测位初始为0，外循环只有最后，外循环只有最后1次次预测错误；跳出内循环时预测预测错误；跳出内循环时预测 位位变为变为1，再进入内循环时，第一次总是预测错误，并且任何一次循环的，再进入内循环时，第一次总是预测错误，并且任何一次循环的最后一次总是预测错误，因此，内循环有最后一次总是预测错误，因此，内循环有1+2(N1)次次预测错误。预测错误。N越大准确率越高！越大准确率越高！N=10, 分别分别90.9%和和82.7%N=100
85、, 分别分别99%和和98%73两位预测状态图基本思想：只有两次预测错误才改变预测方向11状态时预测发生（强转移），实际不发生时，转到状态10（弱转移），下次仍预测为发生，如果再次预测错误（实际不发生），才使下次预测调整为不发生00好处：连续两次发生不同的分支情况时，会预测正确预测发生预测发生发生发生预测不发生预测不发生不发生不发生预测发生预测发生预测不发生预测不发生发生发生不发生不发生 发生发生不发生不发生发生发生不发生不发生11100100正确正确错误错误正确正确错误错误正确正确正确正确错误错误错误错误预测发生：选择预测发生：选择“转移取转移取”预测不发生：选择预测不发生：选择“顺序取顺序
86、取”74举例：双重循环的两位动态预测into sum (int N)int i, j, sum=0;for (i=0; i N; i+) for (j=0; j addr“装入装入”：Memaddr-RegRtemp“加法加法”：RegRtemp+Reg%eax-RegRtemp“存数存数”：RegRtemp-Memaddr一个微操作相当于一条一个微操作相当于一条RISC指令，指令，译码生成的微操作序列译码生成的微操作序列被存放到被存放到Trace Cache中中106PENTIUM4 的20级超流水线(HYPER-PIPELINE)建立标志信建立标志信息息ZF/CF等，等，并将执行结并将执行
87、结果写入物理果写入物理寄存器。寄存器。对对BTB2中中预测是否正预测是否正确进行确认确进行确认及相应处理及相应处理在不同在不同的执行的执行部件中部件中执行。执行。每个部每个部件执行件执行时间长时间长短不同短不同被发射的被发射的MOP开始开始读取物理读取物理寄存器中寄存器中的源操作的源操作数，或从数，或从旁路由旁路由L1-D Cache读取。读取。每个队列按每个队列按FIFO将将MOP送到各自送到各自的调度器，在调的调度器，在调度器中进行数据度器中进行数据相关性检测，当相关性检测，当所有源操作都就所有源操作都就绪时，将绪时，将MOP发发射到对应的执行射到对应的执行部件。是部件。是“无序无序”发射
88、。发射。一个周期一个周期3条条MOP送送ROB。ROB有有126项，记录每个项，记录每个MOP及分配的资源及分配的资源和执行状态，根据和执行状态，根据资源资源分配情况进行分配情况进行寄存器重命名后，寄存器重命名后，分别送两个分别送两个MOP队队列中进行排队。列中进行排队。沿一个踪迹顺序取沿一个踪迹顺序取MOP，直到遇到一条，直到遇到一条转移转移MOP，通过，通过BTB2预测下个踪迹预测下个踪迹开始点，继续取开始点，继续取MOP送送ROB/Alloc/Ren部部件。预测目标处件。预测目标处MOP不在时，要通知指令不在时，要通知指令预取器，快从预取器，快从L2中取中取指令并译码。指令并译码。两个两
89、个drive段用于芯片内传输信号的驱动，使其保证长距离传输段用于芯片内传输信号的驱动，使其保证长距离传输整数运算微操作流水线为整数运算微操作流水线为20级，浮点为级，浮点为29级（执行阶段的长度不同）级（执行阶段的长度不同）107本讲小结有以下两种指令级并行(ILP)技术（即：高性能流水线形式）超流水线：更多的流水线级数多发射流水线：同时发射多个指令，有多条流水线同时进行静态多发射（VLIW处理器+编译器静态调度）动态多发射（超标量处理器+动态流水线调度）108本章总结1ClkCycle 1Multiple Cycle Implementation:IfetchRegExecMemWrCycl
90、e 2 Cycle 3 Cycle 4 Cycle 5 Cycle 6 Cycle 7 Cycle 8 Cycle 9 Cycle 10Load IfetchRegExecMemWrIfetchRegExecMemLoadStorePipeline Implementation:IfetchRegExecMemWrStoreClkSingle Cycle Implementation:LoadStoreWasteIfetchR-typeIfetchRegExecMemWrR-typeCycle 1Cycle 2单周期单周期, 多周期多周期 和和 流水线比较流水线比较109本章总结2指令流水线的
91、设计将每条指令的执行规整化为若干个同样的流水阶段每个流水阶段的执行时间一样，都等于一个时钟理想情况下，每个时钟有一条指令进入流水线，也有一条指令执行结束每个流水段中的部件都是组合逻辑加寄存器，组合逻辑中产生的结果在时钟到来时被存储到寄存器（如：程序计数器、条件码寄存器、流水段寄存器）每两个相邻流水段之间的流水线寄存器，用以记录所有在后面阶段要用到的各种信息，有哪些呢？控制信号、指令的代码、参加运算的操作数、指令运算结果、指令异常信息、寄存器读口地址、寄存器写口地址、存储器地址、新的PC值等。指令译码得到的控制信号通过流水线寄存器传送到后面各个流水段中110本章总结3指令流水线的局限性并不是每条
92、指令都有相同多个流水段并不是每个流水段都一样长随着流水线深度的增加，流水线寄存器的额外开销比例也增大指令在资源冲突、数据相关或控制相关时会发生流水线冒险指令流水线的执行效率吞吐率：比非流水线方式下大大提高指令执行时间：相对于非流水线方式，一条指令的执行时间延长了提高流水线指令效率的高级流水线技术超流水线：级数更多的流水线多发射流水线：同时发射多条指令的流水线静态多发射：VLIW结构、编译器静态推测动态多发射：超标量结构、硬件动态推测调度111本章总结4结构冒险（资源冲突）：多条指令同时使用同一个功能部件规定每个功能部件在一条指令中只能被用一次规定每个功能部件只能在某个特定的阶段被用指令存储器(
93、Code Cache)和数据存储器(Data Cache)分开数据冒险（数据相关）：前面指令的结果是后面指令的操作数软件阻塞：（如：编译器）在后面的数据相关指令前插入nop指令硬件阻塞：在后面数据相关指令的特定流水段插入“气泡”以“阻塞”指令继续执行，直到取得所需数据为止“转发”（旁路）：把前面指令执行过程中得到的数据直接传送到后面指令。对于取数后直接使用的情况（如：Load指令取出的数据是随后的运算指令的操作数），则采用“阻塞加转发”的方式解决数据冒险112本章总结5控制冒险（控制相关）：返回指令、分支指令等可能改变顺序增量的PC值，由于获取转移目标地址的时间较长，使得在目标地址产生前已经有指令被取到流水线中，如果已经取出执行的指令不是正确的指令，则发生控制冒险。软件阻塞：（如：编译器）在控制相关指令后面插入nop指令硬件阻塞：在控制相关指令后面的指令被取出前插入“气泡”，使流水线停顿若干时钟，直到控制相关指令得到正确的PC值为止采用“分支预测”技术。简单（静态）地预测每次分支结果都一样，或根据分支指令执行历史进行动态预测，动态预测能达到90%以上的成功率采用延迟分支技术。将前面一条与分支指令无关的指令放到分支指令后面执行，这样，流水线不会发生阻塞现象。这种对指令顺序进行调整的工作在程序编译阶段完成113本章作业3、5、7、9、10、11、126月4号交114
