CS4100计算机结构Pipelining课件

Pipelining-1OutlinevAn overview of pipeliningvA pipelined datapathvPipelined controlvData hazards and forwardingvData hazards and stallsvBranch hazardsvExceptionsvSuperscalar and dynamic pipeliningPipelining-2vLaundry example:Ann,Brian,Cathy,Dave each have one load ofclothes to wash,dry,and foldWasher takes 30 minutesDryer takes 40 minutes“Folder”takes 20 minutesABCDPipelining Is Natural!Pipelining-3vSequential laundry takes 6 hours for 4 loadsvIf they learned pipelining,how long would it take?ABCD3040203040203040203040206 PM7891011MidnightTaskOrderTimeSequential LaundryPipelining-4vPipelined laundry takes 3.5 hours for 4 loads ABCD6 PM7891011MidnightTaskOrderTime304040404020Pipelined Laundry:Start ASAPPipelining-5Pipelining LessonsvDoesnt help latency of single task,but throughput of entirevPipeline rate limited by slowest stagevMultiple tasks working at same time using different resourcesvPotential speedup=Number pipe stagesvUnbalanced stage length;time to“fill”&“drain”the pipeline reduce speedupvStall for dependencesABCD6 PM789TaskOrderTime304040404020Pipelining-6Single cycle vs.PipelineClkCycle 1Cycle 2Cycle 3Cycle 4Cycle 5Cycle 6Cycle 7Cycle 8Cycle 9 Cycle 10LoadPipeline Implementation:ClkSingle Cycle Implementation:LoadStoreWasteIfetchRegExecMemWrIfetchRegExecMemWrStoreIfetchRegExecMemWrR-typeCycle 1Cycle 2Pipelining-7Pipeline PerformanceSingle-cycle(Tc=800ps)Pipelined(Tc=200ps)Pipelining-8Instr.OrderTime(clock cycles)Inst 0Inst 1Inst 2Inst 4Inst 3ALUImRegDmRegALUImRegDmRegALUImRegDmRegALUImRegDmRegALUImRegDmRegWhy Pipeline?Because the Resources Are There!Single-cycle DatapathPipelining-9OutlinevAn overview of pipeliningvA pipelined datapathvPipelined controlvData hazards and forwardingvData hazards and stallsvBranch hazardsvExceptionsvSuperscalar and dynamic pipeliningPipelining-10Designing a Pipelined ProcessorvExamine the datapath and control diagramStarting with single cycle datapathSingle cycle control?vPartition datapath into stages:IF(instruction fetch),ID(instruction decode and register file read),EX(execution or address calculation),MEM(data memory access),WB(write back)vAssociate resources with stagesvEnsure that flows do not conflict,or figure out how to resolvevAssert control in appropriate stagePipelining-11Multi-Execution StepsBut,use single-cycle datapath.Pipelining-12Split Single-cycle DatapathWhat to add to split the datapath into stages?FeedbackPathPipelining-13Pipeline registers(latches)Add Pipeline RegistersvUse registers between stages to carry data and controlPipelining-14vIF:Instruction FetchFetch the instruction from the Instruction MemoryvID:Instruction DecodeRegisters fetch and instruction decodevEX:Calculate the memory addressvMEM:Read the data from the Data MemoryvWB:Write the data back to the register fileCycle 1Cycle 2Cycle 3Cycle 4Cycle 5IfetchReg/DecExecMemWrLoadConsider loadPipelining-15ClockCycle 1Cycle 2Cycle 3Cycle 4Cycle 5Cycle 6Cycle 7IfetchReg/DecExecMemWr1st lwIfetchReg/DecExecMemWr2nd lwIfetchReg/DecExecMemWr3rd lwPipelining loadv5 functional units in the pipeline datapath are:Instruction Memory for the Ifetch stageRegister Files Read ports(busA and busB)for the Reg/Dec stageALU for the Exec stageData Memory for the MEM stageRegister Files Write port(busW)for the WB stagePipelining-16vIR=memPC;PC=PC+4IF Stage of loadIR,PC+4Pipelining-17ID Stage of loadvA=RegIR25-21;B=RegIR20-16;Pipelining-18EX Stage of loadvALUout=A+sign-ext(IR15-0)Pipelining-19MEM State of loadvMDR=memALUoutPipelining-20WB Stage of loadvRegIR20-16=MDRWho will supply this address?Pipelining-21Cycle 1Cycle 2Cycle 3Cycle 4IfetchReg/DecExecWrR-typeThe Four Stages of R-typevIF:fetch the instruction from the Instruction MemoryvID:registers fetch and instruction decodevEX:ALU operates on the two register operandsvWB:write ALU output back to the register filePipelining-22vWe have a structural hazard:Two instructions try to write to the register file at the same time!Only one write portClockCycle 1Cycle 2Cycle 3Cycle 4Cycle 5Cycle 6Cycle 7Cycle 8Cycle 9IfetchReg/DecExecWrR-typeIfetchReg/DecExecWrR-typeIfetchReg/DecExecMemWrLoadIfetchReg/DecExecWrR-typeIfetchReg/DecExecWrR-typeOps!We have a problem!Pipelining R-type and loadPipelining-23Important ObservationIfetchReg/DecExecMemWrLoad12345IfetchReg/DecExecWrR-type1234vEach functional unit can only be used once per instructionvEach functional unit must be used at the same stage for all instructions:Load uses Register Files write port during its 5th stageR-type uses Register Files write port during its 4th stageSeveral ways to solve:forwarding,adding pipeline bubble,making instructions same lengthPipelining-24ClockCycle 1Cycle 2Cycle 3Cycle 4Cycle 5Cycle 6Cycle 7Cycle 8Cycle 9IfetchReg/DecMemWrR-typeIfetchReg/DecMemWrR-typeIfetchReg/DecExecMemWrLoadIfetchReg/DecMemWrR-typeIfetchReg/DecMemWrR-typeIfetchReg/DecExecWrR-typeMemExecExecExecExec12345Solution:Delay R-types WritevDelay R-types register write by one cycle:R-type also use Reg Files write port at Stage 5MEM is a NOP stage:nothing is being done.R-type also has 5 stagesPipelining-25Cycle 1Cycle 2Cycle 3Cycle 4IfetchReg/DecExecMemStoreWrThe Four Stages of storevIF:fetch the instruction from the Instruction MemoryvID:registers fetch and instruction decodevEX:calculate the memory addressvMEM:write the data into the Data MemoryAdd an extra stage:vWB:NOPPipelining-26vIF:fetch the instruction from the Instruction MemoryvID:registers fetch and instruction decodevEX:compares the two register operandselect correct branch target addresslatch into PCAdd two extra stages:vMEM:NOPvWB:NOPCycle 1Cycle 2Cycle 3Cycle 4IfetchReg/DecExecMemBeqWrThe Three Stages of beqPipelining-27Pipelined DatapathPipelining-28Graphically Representing PipelinesvCan help with answering questions like:How many cycles to execute this code?What is the ALU doing during cycle 4?Help understand datapathsPipelining-29Example 1:Cycle 1Pipelining-30Example 1:Cycle 2Pipelining-31Example 1:Cycle 3Pipelining-32Example 1:Cycle 4Pipelining-33Example 1:Cycle 5Pipelining-34Example 1:Cycle 6Pipelining-35OutlinevAn overview of pipeliningvA pipelined datapathvPipelined controlvData hazards and forwardingvData hazards and stallsvBranch hazardsvExceptionsvSuperscalar and dynamic pipeliningPipelining-36Pipeline Control:Control SignalsPipelining-37Fig.4.22Group Signals According to StagesvCan use control signals of single-cycle CPU Pipelining-38vPass control signals along just like the dataMain control generates control signals during ID Data Stationary ControlFig.4.50Pipelining-39IF/ID RegisterID/Ex RegisterEx/MEM RegisterMEM/WB RegisterIDEXMEMExtOpALUOpRegDstALUSrcBranchMemWrMemtoRegRegWrMainControlExtOpALUOpRegDstALUSrcMemtoRegRegWrMemtoRegRegWrMemtoRegRegWrBranchMemWrBranchMemWWBData Stationary Control(cont.)vSignals for EX(ExtOp,ALUSrc,.)are used 1 cycle latervSignals for MEM(MemWr,Branch)are used 2 cycles latervSignals for WB(MemtoReg,MemWr)are used 3 cycles laterPipelining-40WB Stage of loadvRegIR20-16=MDRWho will supply this address?Pipelining-41Datapath with ControlPipelining-42lw$10,20($1)sub$11,$2,$3and$12,$4,$5or$13,$6,$7add$14,$8,$9Lets Try it OutPipelining-43Example 2:Cycle 1Pipelining-44Example 2:Cycle 2Pipelining-45Example 2:Cycle 3Pipelining-46Example 2:Cycle 4Pipelining-47Example 2:Cycle 5Pipelining-48Example 2:Cycle 6Pipelining-49Example 2:Cycle 7Fig.6.34Pipelining-50Example 2:Cycle 8Fig.6.34Pipelining-51Example 2:Cycle 9Pipelining-52Summary of Pipeline BasicsvPipelining is a fundamental conceptMultiple steps using distinct resourcesUtilize capabilities of datapath by pipelined instruction processingvStart next instruction while working on the current onevLimited by length of longest stage(plus fill/flush)vNeed to detect and resolve hazards vWhat makes it easy in MIPS?All instructions are of the same lengthJust a few instruction formatsMemory operands only in loads and storesvWhat makes pipelining hard?hazardsPipelining-53OutlinevAn overview of pipeliningvA pipelined datapathvPipelined controlvData hazards and forwarding(R-Type and R-Type)vData hazards and stalls(Load and R-type)vBranch hazardsvExceptionsvSuperscalar and dynamic pipeliningPipelining-54Pipeline HazardsvPipeline Hazards:Structural hazards:attempt to use the same resource in two different ways at the same timevEx.:combined washer/dryer or folder busy doing something else(watching TV)Data hazards:attempt to use item before readyvInstruction depends on result of prior instruction still in the pipelineControl hazards:attempt to make decision before condition is evaluatedvEx.:wash football uniforms and need to see result of previous load to get proper detergent levelvBranch instructionsvCan always resolve hazards by waitingpipeline control must detect the hazardtake action(or delay action)to resolve hazardsPipelining-55MemInstr.OrderTimeLoadInstr 1Instr 2Instr 3Instr 4ALUMemRegMemRegALUMemRegMemRegALUMemRegMemRegALURegMemRegALUMemRegMemRegStructural Hazard:Single MemoryPipelining-56Pipeline Hazards IllustratedIF ID EX MEM WBStructuralHazardIF ID .timePipelining-57MemInstr.OrderTimeLoadInstr 1Instr 2Instr 3Instr 4ALUMemRegMemRegALUMemRegMemRegALUMemRegMemRegALURegMemRegALUMemRegMemRegUse 2 memory:data memory and instruction memoryStructural Hazard:Single MemoryPipelining-58InstructionmemoryAddress4320AddAddresultShiftleft 2InstructionIF/IDEX/MEMMEM/WBMux01AddPC0WritedataMux1RegistersReaddata 1Readdata 2Readregister 1Readregister 216SignextendWriteregisterWritedataReaddata1ALUresultMuxALUZeroID/EXDatamemoryAddressFeedback PathPipelining-59Data HazardsIMRegIMRegCC 1CC 2CC 3CC 4CC 5CC 6Time(in clock cycles)sub$2,$1,$3Programexecutionorder(in instructions)and$12,$2,$5IMRegDMRegIMDMRegIMDMRegCC 7CC 8CC 91010101010/-2 0-20-2 0-2 0-20or$13,$6,$2add$14,$2,$2sw$15,100($2)Value of register$2:DMRegRegRegRegDMPipelining-60Types of Data HazardsThree types:(inst.i1 followed by inst.i2)vRAW(read after write):i2 tries to read operand before i1 writes itvWAR(write after read):i2 tries to write operand before i1 reads itGets wrong operand,e.g.,autoincrement addr.Cant happen in MIPS 5-stage pipeline because:vAll instructions take 5 stages,and reads are always in stage 2,and writes are always in stage 5vWAW(write after write):i2 tries to write operand before i1 writes itLeaves wrong result(i1s not i2s);occur only in pipelines that write in more than one stageCant happen in MIPS 5-stage pipeline because:vAll instructions take 5 stages,and writes are always in stage 5Pipelining-61Pipeline Hazards Illustrated IF ID EX MEM WB IF ID EX MemRAW(read after write)Data HazardWAW Data Hazard(write after write)IF ID EX MEM WBWAR Data Hazard(write after read)IF ID EX MEM WB IF ID EX MEM WBtimePipelining-62Handling Data HazardsvUse simple,fixed designsEliminate WAR by always fetching operands early(ID)in pipelineEliminate WAW by doing all write backs in order(last stage,static)These features have a lot to do with ISA designvInternal forwarding in register file:Write in first half of clock and read in second halfRead delivers what is written,resolve hazard between sub and addvDetect and resolve remaining onesCompiler inserts NOP(software solution)Forward(hardware solution)Stall(hardware solution)Pipelining-63Software SolutionvHave compiler guarantee no hazardsvWhere do we insert the NOPs?sub$2,$1,$3and$12,$2,$5or$13,$6,$2add$14,$2,$2sw$15,100($2)vProblem:this really slows us down!Pipelining-64Data HazardsIMRegIMRegCC 1CC 2CC 3CC 4CC 5CC 6Time(in clock cycles)sub$2,$1,$3Programexecutionorder(in instructions)and$12,$2,$5IMRegDMRegIMDMRegIMDMRegCC 7CC 8CC 91010101010/-2 0-20-2 0-2 0-20or$13,$6,$2add$14,$2,$2sw$15,100($2)Value of register$2:DMRegRegRegRegDMInsert two nopsPipelining-65Data Hazards:ForwardingIMRegIMRegCC 1CC 2CC 3CC 4CC 5CC 6Time(in clock cycles)sub$2,$1,$3Programexecutionorder(in instructions)and$12,$2,$5IMRegDMRegIMDMRegIMDMRegCC 7CC 8CC 91010101010/-20-20-20-20-20or$13,$6,$2add$14,$2,$2sw$15,100($2)Value of register$2:DMRegRegRegRegDMPipelining-66Datapath with ForwardingPipelining-67Control:Detecting Data HazardsvHazard conditions:1a.EX/MEM.RegisterRd=ID/EX.RegisterRs1b.EX/MEM.RegisterRd=ID/EX.RegisterRt2a.MEM/WB.RegisterRd=ID/EX.RegisterRs2b.MEM/WB.RegisterRd=ID/EX.RegisterRtvTwo optimizations:Dont forward if instruction does not write register=check if RegWrite is assertedDont forward if destination register is$0=check if RegisterRd=0Pipelining-68Detecting Data Hazards(cont.)vHazard conditions using control signals:At EX stage:EX/MEM.RegWrite and(EX/MEM.RegRd0)and(EX/MEM.RegRd=ID/EX.RegRs)At MEM stage:MEM/WB.RegWrite and(MEM/WB.RegRd0)and(MEM/WB.RegRd=ID/EX.RegRs)(replace ID/EX.RegRt for ID/EX.RegRs for the other two conditions)Pipelining-69vUse temporary results,e.g.,those in pipeline registers,dont wait for them to be writtenResolving Hazards:ForwardingPipelining-70Datapath with ForwardingPipelining-71Forwarding LogicvForwarding:input to ALU from any pipe reg.Add multiplexors to ALU input Control forwarding in EX=carry Rs in ID/EXvControl signals for forwarding:If both WB and MEM forward,e.g.,add$1,$1,$2;add$1,$1,$3;add$1,$1,$4;=let MEM forwardEX hazard:vif(EX/MEM.RegWrite and(EX/MEM.RegRd0)and(EX/MEM.RegRd=ID/EX.RegRs)ForwardA=10MEM hazard:vif(MEM/WB.RegWrite and(MEM/WB.RegRd0)and(EX/MEM.RegRd ID/EX.Reg.Rs)and(MEM/WB.RegRd=ID/EX.RegRs)ForwardA=01(ID/EX.RegRtID/EX.RegRs,ForwardB ForwardA)Pipelining-72Example 3:Cycle 3Pipelining-73Example 3:Cycle 4Fig.6.41Pipelining-74Example 3:Cycle 5Pipelining-75Example 3:Cycle 6Fig.6.42Pipelining-76OutlinevAn overview of pipeliningvA pipelined datapathvPipelined controlvData hazards and forwarding(R-Type and R-Type)vData hazards and stalls(Load and R-type)vBranch hazardsvExceptionsvSuperscalar and dynamic pipeliningPipelining-77vlw can still cause a hazard:if is followed by an instruction to read the loaded reg.Cant Always ForwardUse stalling or compiler to resolvePipelining-78StallingvStall pipeline by keeping instructions in same stage and inserting an NOP insteadPipelining-79Datapath with Stalling UnitvForwarding controls ALU inputs,hazard detection controls PC,IF/ID,control signalsPipelining-80Control:Handling StallsvHazard detection unit in ID to insert stall between a load instruction and its use:if(ID/EX.MemRead and (ID/EX.RegisterRt=IF/ID.RegisterRs)or (ID/EX.RegisterRt=IF/ID.registerRt)stall the pipeline for one cycle(ID/EX.MemRead=1 indicates a load instruction)vHow to stall?Stall instruction in IF and ID:not change PC and IF/ID=the stages re-execute the instructionsWhat to move into EX:insert an NOP by changing EX,MEM,WB control fields of ID/EX pipeline register to 0vas control signals propagate,all control signals to EX,MEM,WB are deasserted and no registers or memories are writtenPipelining-81Example 4:Cycle 2Pipelining-82Example 4:Cycle 3Pipelining-83Example 4:Cycle 4Pipelining-84Example 4:Cycle 5Pipelining-85Example 4:Cycle 6Fig.6.49Pipelining-86Example 4:Cycle 7Pipelining-87OutlinevAn overview of pipeliningvA pipelined datapathvPipelined controlvData hazards and forwardingvData hazards and stallsvBranch hazardsvExceptionsvSuperscalar and dynamic pipeliningPipelining-88InstructionmemoryAddress4320AddAddresultShiftleft 2InstructionIF/IDEX/MEMMEM/WBMux01AddPC0WritedataMux1RegistersReaddata 1Readdata 2Readregister 1Readregister 216SignextendWriteregisterWritedataReaddata1ALUresultMuxALUZeroID/EXDatamemoryAddressFeedback PathPipelining-89Pipeline Datapath with Control SignalsPipelining-90vWhen decide to branch,other inst.are in pipeline!Branch HazardsPipelining-91Handling Branch HazardtPredict branch always not takenlNeed to add hardware for flushing inst.if wronglBranch decision made at MEM=need to flush instruction in IF/ID,ID/EX by changing control values to 0tReduce delay of taken branch by moving branch execution earlier in the pipelinelMove up branch address calculation to IDlCheck branch equality at ID(using XOR)by comparing the two registers read during IDlBranch decision made at ID=one instruction to flushlAdd a control signal,IF.Flush,to zero instruction field of IF/ID=making the instruction an NOPtDynamic branch predictiontCompiler rescheduling,delay branchPipelining-92Pipeline with FlushingPipelining-93Example 5:Cycle 3Pipelining-94Example 5:Cycle 4Pipelining-95Dynamic Branch PredictionvIn deeper and superscalar pipelines,branch penalty is more significantvUse dynamic prediction(e.g.loop)Branch prediction buffer(i.e.,branch history table)Indexed by recent branch instruction addressesStores outcome(taken/not taken)To execute a branchvCheck table,expect the same outcomevStart fetching from fall-through or targetvIf wrong,flush pipeline and flip predictionPipelining-961-Bit Predictor:ShortcomingvInner loop branches mispredicted twice!outer:inner:beq,inner beq,outerlMispredict as taken on last iteration of inner looplThen mispredict as not taken on first iteration of inner loop next time aroundPipelining-972-Bit PredictorvOnly change prediction on two successive mis-predictionsPipelining-98Calculating the Branch TargetvEven with predictor,still need to calculate the target address1-cycle penalty for a taken branchvBranch target bufferCache of target addressesIndexed by PC when instruction fetchedvIf hit and instruction is branch predicted taken,can fetch target immediatelyPipelining-99vPredict-not-taken+branch decision at ID=the following instruction is always executed=branches take effect 1 cycle later0 clock cycle penalty per branch instruction if can find instruction to put in slot(50%of time)Instr.OrderTime(clock cycles)addbeqmiscALUMemRegMemRegALUMemRegMemRegMemALURegMemReglwMemALURegMemRegDelayed BranchPipelining-100OutlinevAn overview of pipeliningvA pipelined datapathvPipelined controlvData hazards and forwardingvData hazards and stallsvBranch hazardsvExceptionsvSuperscalar and dynamic pipeliningPipelining-101Exceptions and Interruptsv“Unexpected”events requiring changein flow of controlDifferent ISAs use the terms differentlyvExceptionArises within the CPUe.g.,undefined opcode,overflow,syscall,vInterruptFrom an external I/O controllervDealing with them without sacrificing performance is hard4.9 ExceptionsPipelining-102Handling ExceptionsvIn MIPS,exceptions managed by a System Control Coprocessor(CP0)vSave PC of offending(or interrupted)instructionIn MIPS:Exception Program Counter(EPC)vSave indication of the problemIn MIPS:Cause registerWell assume 1-bitv0 for undefined opcode,1 for overflowvJump to handler at 8000 00180Pipelining-103An Alternate MechanismvVectored InterruptsHandler address determined by the causevExample:Undefined opcode:C000 0000Overflow:C000 0020:C000 0040vInstructions eitherDeal with the interrupt,orJump to real handlerPipelining-104Handler ActionsvRead cause,and transfer to relevant handlervDetermine action requiredvIf restartableTake corrective actionuse EPC to return to programvOtherwiseTerminate programReport error using EPC,cause,Pipelining-105Exceptions in a PipelinevAnother form of control hazardvConsider overflow on add in EX stageadd$1,$2,$1Prevent$1 from being clobberedComplete previous instructionsFlush add and subsequent instructionsSet Cause and EPC register valuesTransfer control to handlervSimilar to mispredicted branchUse much of the same hardwarePipelining-106Pipeline with ExceptionsPipelining-107Exception PropertiesvRestartable exceptionsPipeline can flush the instructionHandler executes,then returns to the instructionvRefetched and executed from scratchvPC saved in EPC registerIdentifies causing instructionActually PC+4 is savedvHandler must adjustPipelining-108Exception ExamplevException on add in40sub$11,$2,$444and$12,$2,$548or$13,$2,$64Cadd$1,$2,$150slt$15,$6,$754lw$16,50($7)vHandler80000180sw$25,1000($0)80000184sw$26,1004($0)Pipelining-109Exception ExamplePipelining-110Exception ExamplePipelining-111Multiple ExceptionsvPipelining overlaps multiple instructionsCould have multiple exceptions at oncevSimple approach:deal with exception from earliest instructionFlush subsequent instructions“Precise”except