hazards(结构冒险大多发生在)

MorePipeline1BasicRISCPipeliningBasicidea:Eachinstructionspends1clockcycleineachofthe5executionstages.During1clockcycle,thepipelinecanprocess(indifferentstages)5differentinstructions.2SimpleRISCDatapathIFIDEXMEMWBProgram

CounterNextPCInst.

Reg.Load

fr.Mem.

Data3DescriptionofPipeStages4Hazards5ThehazardsofpipeliningPipelinehazardspreventnextinstructionfromexecutingduringdesignatedclockcycleThereare3classesofhazards:StructuralHazards:ArisefromresourceconflictsHWcannotsupportallpossiblecombinationsofinstructionsDataHazards:OccurwhengiveninstructiondependsondatafromaninstructionaheadofitinpipelineControlHazards:Resultfrombranch,otherinstructionsthatchangeflowofprogram(i.e.changePC)6Howdowedealwithhazards?Often,pipelinemustbe

stalledStallingpipelineusuallyletssomeinstruction(s)inpipelineproceed,another/otherswaitfordata,resource,etc.7StallsandperformanceStallsimpede(阻止)progressofapipelineandresultindeviationfrom1instructionexecuting/clockcyclePipeliningcanbeviewedto:DecreaseCPIorclockcycletimeforinstructionLet’sseewhataffectstallshaveonCPI…CPIpipelined=IdealCPI+Pipelinestallcyclesperinstruction1+PipelinestallcyclesperinstructionIgnoringoverheadandassumingstagesarebalanced:8Evenmorepipelineperformanceissues!Thisresultsin:Whichleadsto:Ifnostallsinidealcasespeedup==numberofpipelinestages91.StructuralhazardsMostcommoninstancesofstructuralhazards(结构冒险大多发生在):Whenafunctionalunitnotfullypipelined(完全流水)WhensomeresourcenotduplicatedenoughOnewaytoavoidstructuralhazardsistoduplicateresourcesPipelinesstallresultofhazards,CPIincreasedfromtheusual“1〞10AnexampleofastructuralhazardALURegMemDMRegALURegMemDMRegALURegMemDMRegALURegMemDMRegTimeALURegMemDMRegLoadInstruction1Instruction2Instruction3Instruction4What’stheproblemhere?Theprocessorhasacombinedinstruction+datamemorywithonly1readport11Howisitresolved?ALURegMemDMRegALURegMemDMRegALURegMemDMRegTimeALURegMemDMRegLoadInstruction1Instruction2StallInstruction3BubbleBubbleBubbleBubbleBubblePipelinegenerallystalledbyinsertinga“bubble〞orNOP12Oralternatively…Inst.#12345678910LOADIFIDEXMEMWBInst.i+1IFIDEXMEMWBInst.i+2IFIDEXMEMWBInst.i+3stallIFIDEXMEMWBInst.i+4IFIDEXMEMWBInst.i+5IFIDEXMEMInst.i+6IFIDEXClockNumberLOADinstruction“steals〞aninstructionfetchcyclewhichwillcausethepipelinetostall.Thus,noinstructioncompletesonclockcycle813Rememberthecommoncase!But,insomecasesitmaybebettertoallowthemthantoeliminatethem.Thesearesituationsacomputerarchitectmighthavetoconsider:IspipeliningfunctionalunitsorduplicatingthemcostlyintermsofHW?Doesstructuralhazardoccuroften?What’sthecommoncase?142.DatahazardsWhydotheyexist???Pipeliningchangesorder(i.e.read/writeaccessestooperands)Orderdiffersfromorderseenbysequentiallyexecutinginstructionsonunpipelinedmachine(流水执行序不同于非流水机器的顺序执行指令序)Considerthisexample:ADDR1,R2,R3SUBR4,R1,R5ANDR6,R1,R7ORR8,R1,R9XORR10,R1,R11AllinstructionsafterADDuseresultofADDADDwritestheregisterinWBbutSUBneedsitinID.Thisisadatahazard15IllustratingadatahazardALURegMemDMRegALURegMemDMRegALURegMemDMRegMemTimeADDR1,R2,R3SUBR4,R1,R5ANDR6,R1,R7ORR8,R1,R9XORR10,R1,R11ALURegMemADDinstructioncausesahazardinnext3instructionsb/c(because)

registernotwrittenuntilafterthose3readit.16DatahazardspecificsThereareactually3differentkindsofdatahazards!ReadAfterWrite(RAW)WriteAfterWrite(WAW)WriteAfterRead(WAR)Assumethathazardswilluseinstructionsi&j.iisalwaysissuedbeforej.Thus,iwillalwaysbefurtheralonginpipelinethanj.Withanin-orderissue/in-ordercompletionmachine,we’renotasconcernedwithWAW,WAR17ThreeTypesofDataHazardsThereareactually3differentkindsofdatahazards!Let

i

beanearlierinstruction,

j

alaterone.RAW(readafterwrite)jtriestoreadavaluebefore

i

writesitWAW(writeafterwrite)i

andj

writetosameplace,butinthewrongorder.发生条件：Onlyoccursif>1pipelinestagecanwrite(in-order)WAR(writeafterread)j

writesanewvaluetoalocationbeforei

hasreadtheoldone.发生条件：Onlyoccursifwritescanhappenbeforereadsinpipeline(in-order).18Readafterwrite(RAW)hazardsWithRAWhazard,instructionjtriestoreadasourceoperandbeforeinstructioniwritesit.Thus,jwouldincorrectlyreceiveanoldorincorrectvalueGraphically/Example:Canusestallingorforwardingtoresolvethishazard…ji…InstructionjisareadinstructionissuedafteriInstructioniisawriteinstructionissuedbeforeji:ADDR1,R2,R3j:SUBR4,R1,R619ForwardingItcanactuallybesolvedrelativelyeasily–withforwardingInthisexample,resultoftheADDinstructionnotreallyneededuntilafterADDactuallyproducesitCanwemovetheresultfromEX/MEMregistertothebeginningofALU(whereSUBneedsit)?Generallyspeaking:Forwarding

occurswhenaresultispasseddirectlytofunctionalunitthatrequiresit.Resultgoesfromoutputofoneunittoinputofanother20Whencanweforward?ALURegMemDMRegALURegMemDMRegALURegMemDMRegMemTimeADDR1,R2,R3SUBR4,R1,R5ANDR6,R1,R7ORR8,R1,R9XORR10,R1,R11ALURegMemSUBgetsinfo.fromEX/MEMpiperegisterANDgetsinfo.fromMEM/WBpiperegisterORgetsinfo.byforwardingfromregisterfileRuleofthumb: Iflinegoes“forward〞youcandoforwarding. Ifitsdrawnbackward,it’sphysicallyimpossible.21DataHazardDetection22HazardDetectionLogicExample:Detectingwhetheraninstructionthathasjustbeenfetchedneedstobestalledbecauseofaprecedingload.23ForwardingSituationsinDLX24HWChangeforForwardingMuxMuxALUZero?DatamemoryID/EXEX/MEMMEM/WB25Forwarding:Itdoesn’talwaysworkALURegIMDMRegALURegIMDMALURegIMTimeLWR1,0(R2)SUBR4,R1,R5ANDR6,R1,R7ORR8,R1,R9RegIMLoadhasalatencythatforwardingcan’tsolve.Pipelinemuststalluntilhazardcleared(startingwithinstructionthatwantstousedatauntilsourceproducesit).26ThesolutionALURegIMDMRegRegIMIMTimeLWR1,0(R2)SUBR4,R1,R5ANDR6,R1,R7ORR8,R1,R9BubbleBubbleBubbleALURegRegIMALUDMInsertionofbubblecauses#ofcyclestocompletethissequencetogrowby127DatahazardsandthecompilerCompilershouldbeabletohelpeliminatesomestallscausedbydatahazardsi.e.compilercouldnotgenerateaLOADinstructionthatisimmediatelyfollowedbyinstructionthatusesresultofLOAD’sdestinationregister.Techniqueiscalled“pipeline/instructionscheduling〞28AsimpleExampleAclevercompilercanoftenrescheduleinstructionstoavoidastall.Asimpleexample:Originalcode:

lwr2,0(r4)

addr1,r2,r3Note:Stallhappenshere!

lwr5,4(r4)Transformedcode:

lwr2,0(r4)

lwr5,4(r4)

addr1,r2,r3Nostallneeded!

29SimpleRISCPipelineStallStatistics%ofloadsthatcauseastall30Writeafterwrite(WAW)hazardsWithWAWhazard,instructionjtriestowriteanoperandbeforeinstructioniwritesit.ThewritesareperformedinwrongorderleavingthevaluewrittenbyearlierinstructionGraphically/Example:…ji…InstructionjisawriteinstructionissuedafteriInstructioniisawriteinstructionissuedbeforeji:DIVF1,F2,F3j:SUBF1,F4,F631Writeafterread(WAR)hazardsWithWARhazard,instructionjtriestowriteanoperandbeforeinstructionireadsit.Instructioniwouldincorrectlyreceivenewervalueofitsoperand;Insteadofgettingoldvalue,itcouldreceivesomenewer,undesiredvalue.Graphically/Example:…ji…InstructionjisawriteinstructionissuedafteriInstructioniisareadinstructionissuedbeforeji:DIVF7,F1,F3j:SUBF1,F4,F6323.Control(Branch)HazardsSupposethenewPCvalueisnotcomputeduntiltheMEMstage.Thenwemuststall3clocksaftereverybranch!33BranchHazardsneedtoconsiderhazardsinvolvingbranches:Example:40: beq $1,$3,2844: and $12,$2,$548: or $13,$6,$252: add $14,$2,$272: lw $4,50($7)34PipelineimpactonbranchHowdowedealwiththis?AlwaysstallAssumebranch-not-takenBranchdelayslots35AssumebranchnottakenOnaverage,branchesaretaken½thetimeIfbranchnottaken…ContinuenormalprocessingElse,ifbranchistaken…NeedtoflushimproperinstructionfrompipelineCutsoveralltimeforbranchprocessingin½36AssumebranchnottakenCase1:nottakenExecutionproceedsnormallynopenalty37AssumebranchnottakenCase2:takenbranchBubblesinjectedinto3stagesduringcycle538Sum:BranchPenaltyImpactAssume16%ofallinstructionsarebranches4%unconditionalbranches:3cyclepenalty12%conditional:50%taken,3cyclepenaltyForasequenceofNinstructions(assumeNislarge)Ncyclestoinitiateeach3*0.04*Ndelaysduetounconditionalbranches0.5*3*0.12*NdelaysduetoconditionaltakenAlso,anextra4cyclesforpipelinetoemptyTotal:1.3*N+4totalcycles(or1.3cycles/instruction)(CPI)30%PerformanceHit!!!(Badthing)39BranchdelayslotDelayslot:FindoneinstructionthatwillbeexecutednomatterwhichwaythebranchgoesBranchesalwaysexecutenext1or2instructionsInstructionsoexecutedsaidtobeindelayslotbranchinstruction

Delayslotinstruction1

Delayslotinstruction2

Delayslotinstructionn

branchtargetiftaken

Branchdelayslotoflengthn40SchedulingDelayedBranchADDR1,R2,R3ifR2=0thenifR2=0thenSUBR4,R5,R6ADDR1,R2,R3ifR1=0thenSUBR4,R5,R6ADDR1,R2,R3ifR1=0thenADDR1,R2,R3ifR1=0thenADDR1,R2,R3SUBR4,R5,R6ORR7,R8,R9SUBR4,R5,R6ADDR1,R2,R3ifR1=0thenSUBR4,R5,R6ORR7,R8,R9FrombeforeFromtargetFromfallthrough41SchedulingDelayedBranchWheretogetinstructionstofillbranchdelayslot?BeforebranchinstructionalwaysvaluableFromthetargetaddress:onlyvaluablewhenbranchtakenFromfallthrough:onlyvaluablewhenbranchnottaken42FastBranchResolutionPerformancepenaltycouldbemorethan30%Deeperpipelines,somecodeisverybranchheavyFastBranchResolutionAdderinIDforPC+immediatetargetsOnlyworksforsimpleconditions(compareto0)Comparingtworegistervaluescouldbetooslow4344NewPipelineLogic45ExampleAssumethefollowingMIPSinstructionmix:WhatistheresultingCPIforthepipelinedMIPSwithforwardingandbranchaddresscalculationinIDstagewhenusingabranchnot-takenscheme?CPI=IdealCPI+Pipelinestallclockcyclesperinstruction=1+stallsbyloads+stallsbybranches=1+.3x.25x1+.2x.45x1=1+.075+.09=1.165Type Frequency Arith/Logic 40% Load 30%ofwhich25%arefollowedimmediatelybyaninstructionusingtheloadedvalueStore 10% branch 20%ofwhich45%aretaken46Exceptions47TypesofExceptions(Interrupts,Faults)I/Odevicerequest,timereventInvokingOSservicesfromauserprogramTracing(single-stepping)throughprogramBreakpointsIntegerarithmeticoverflow,dividebyzeroFParithmeticanomaly(overflow,underflow,etc.)Pagefault(pagenotinphysicalmemory)MisalignedmemoryaccessMemory-protectionviolation(acc.mem.notalloc’edtoproc.)Illegal(undefinedorunimplemented)instructionHardwaremalfunctionPower-relatedinterrupt(e.g.batterylow,powerfailure)……48ExceptionCharacterization1Synchronousvs.asynchronousEventsynchronizedwithprogramexecution?Synchronous:eventoccurssameplaceeverytimeAsynchronous:causedbydevicesexternaltoCPU&memory,alsohwmalfunctionsUserrequestedvs.coercedEventcausedintentionallybyuserprogram?Requested:usertaskasksforitCoerced:hweventnotundercontrolofuserprogram49ExceptionCharacterization2Usermaskable(canbedisabled)ornotCaneventbedisabled?Maskable:eventthatcanbedisabledbyusertaskWithininstructionsorbetweeninstructionsDoeseventpreventinstructionfromcompleting?Within:duringexecutionoftask,hardtohandle,usuallysynchronoussinceinstructionistriggerResumevsterminateDoestheprogramcontinuefromwhereitleftoffafterexceptionishandled,ordoesitstop?Terminating:executionalwaysstopsaftertheinterrupt50RestartableExceptionsRequirements:Exceptionmayoccurwithininstruction.Programmustcontinueafterexceptionishandled.Examples:Virtualmemorypagefault.Difficultbecause:Pipelinestatemustbesaved.Oneapproach,foreasycases:1.Forceatrapinst.intopipelineonnextIF.2.Clearpipelinebehindfaultinginstruction.3.ExceptionhandlersavesPCoffaultinginstr.51Precisevs.ImpreciseHandlingMachinesmaysupporteitherorbothmodesofexceptionhandling:Preciseexceptionhandling:Correctlyimplementallpossiblecombinationsofexceptionsinallcircumstances.Maybearequirementforsomesystems/applications.Maybe10xslower!Easierforintegerthanfloating-point.Usefulfordebuggingcode.Impreciseexceptionhandling:Onlycorrectlyimplementthemostcommoncases.Softwaremayavoidsomeexceptions.Onlystatisticalguaranteesofcorrectness,throughtesting.52ExceptionsinDLXpipelineInstructionFetch,&MemorystagesPagefaultoninstruction/datafetchMisalignedmemoryaccessMemory-protectionviolationInstructionDecodestageUndefined/illegalopcodeExecutionstageArithmeticexceptionWrite-BackstageNone!53Out-of-OrderExceptionsConsiderthefollowingcodesequence:LWIFIDEXMEMWBADDIFIDEXMEMWBTheADDmaycauseanexceptionduringIF,beforeLWcausesanexceptionduringMEM!Can’trestartPContheADD!Solution:Notetheexceptioninastatusvector,carriedalong.Disablewritesforthatinstruction.Resolveallexceptionsatalatestage(e.g.WB).54PipeliningComplicationsComplexaddressingmodesandinstructionsAutoincrementaddressmodes:causesregisterchangeduringinstructionexecutioninterrupts?NeedtorestoreregisterstateAddsWARandWAWhazardssincewritesnolongerinlaststageFloatingpoint:longexecutiontime;outofordercompletion55StoppingandStartingExecutionMostdifficultexceptionoccurrenceshave2properties TheyoccurwithininstructionsTheymustberestartableThepipelinemustbeshutdownsafelyandthestatemustbesavedforcorrectrestartingRestartingisusuallydonebysavingPCofinstructionatwhichtostartBranchesanddelayedbranchesrequirespecialtreatmentPreciseexceptionsallowinstructionsjustbeforetheexceptiontobecompleted,whilerestartinginstructionsaftertheexception56Multi-cycleOperations57Multi-cycleOperationsforFP58PipelinedMultiple-IssueFPU59Out-of-ordercompleteNoticeinstructionsmaycompleteout-of-order:MULTDIFIDM1M2M3M4M5M6M7MEWBADDDIFIDA1A2A3A4MEWBLDIFIDEX

MEWBSDIFIDEX

MEWB60TypicalFPCodeSeq.WAR.StallsClockCycleNumberInstruction1234567891011121314151617L.DF4,0(R2)IFIDEXMEWBMUL.DF0,F4,F6IFIDstallM1M2M3M4M5M6M7MEWBADD.DF2,F0,F8IFstallIDstallstallstallstallstallstallA1A2A3A4MEWBS.DF2,0(R2)IFstallstallstallstallstallstallIDEXstallstallstallME61Structurehazards62Sum:multiple-cyclesproblemsRaisesthepossibilityofWAWhazards,andstructuralhazardsinMEM&WBstages.Structuralhazardsmayoccurespeciallyoftenwithnon-pipelinedDIVunit.Out-of-ordercompletionimpactsexceptionhandling.63附录：TheMIPSR4000Pipeline64TheMIPSR4300PipelineManufacturedbyNEC64-bitprocessorimplementsMIPS64ISAUsedinembeddedapplicationsNintendo-64(任天堂)gameprocessor,networkrouter,…MultipleEXstagesforfloating-pointpipelineOut-of-ordercompletion,preciseexceptionsNECVR4122:Integerdata