Slide 1Last time in Lecture 13Limitations of BHTsBranch Target BufferAddress CollisionsBTB is only for Control InstructionsBranch Target Buffer (BTB)Combining BTB and BHTUses of Jump Register (JR)Subroutine Return StackMispredict RecoveryIn-Order Commit for Precise ExceptionsBranch Misprediction in PipelineRecovering ROB/Renaming TableSpeculating Both Directions“Data in ROB” Design (HP PA8000, Pentium Pro, Core2Duo)CS152 AdministriviaSlide 18Slide 19Lifetime of Physical RegistersPhysical Register ManagementPhysical Register ManagementPhysical Register ManagementPhysical Register ManagementPhysical Register ManagementPhysical Register ManagementPhysical Register ManagementPhysical Register ManagementReorder Buffer Holds Active Instruction WindowSuperscalar Register RenamingSuperscalar Register RenamingMemory DependenciesIn-Order Memory QueueConservative O-o-O Load ExecutionAddress SpeculationMemory Dependence Prediction (Alpha 21264)Speculative Loads / StoresSpeculative Store BufferSpeculative Store BufferSlide 40AcknowledgementsMarch 11, 2010 CS152, Spring 2010CS 152 Computer Architecture and Engineering Lecture 14 - Advanced SuperscalarsKrste AsanovicElectrical Engineering and Computer SciencesUniversity of California at Berkeleyhttp://www.eecs.berkeley.edu/~krstehttp://inst.eecs.berkeley.edu/~cs152March 11, 2010 CS152, Spring 20102Last time in Lecture 13•Register renaming removes WAR, WAW hazards•Instruction execution divided into four major stages:–Instruction Fetch, Decode/Rename, Execute/Complete, Commit•Control hazards are serious impediment to superscalar performance•Dynamic branch predictors can be quite accurate (>95%) and avoid most control hazards•Branch History Tables (BHTs) just predict direction (later in pipeline)–Just need a few bits per entry (2 bits gives hysteresis)–Need to decode instruction bits to determine whether this is a branch and what the target address isMarch 11, 2010 CS152, Spring 20103Limitations of BHTsOnly predicts branch direction. Therefore, cannot redirect fetch stream until after branch target is determined.UltraSPARC-III fetch pipelineCorrectly predicted taken branch penaltyJump Register penaltyA PC Generation/MuxP Instruction Fetch Stage 1F Instruction Fetch Stage 2B Branch Address Calc/Begin DecodeI Complete DecodeJ Steer Instructions to Functional unitsR Register File ReadE Integer ExecuteRemainder of execute pipeline (+ another 6 stages)March 11, 2010 CS152, Spring 20104Branch Target BufferBP bits are stored with the predicted target address.IF stage: If (BP=taken) then nPC=target else nPC=PC+4later: check prediction, if wrong then kill the instruction and update BTB & BPb else update BPbIMEMPCBranch Target Buffer (2k entries)kBPbpredictedtarget BP targetMarch 11, 2010 CS152, Spring 20105Address CollisionsWhat will be fetched after the instruction at 1028?BTB prediction = Correct target =Assume a 128-entry BTBBPbtargettake2361028 Add .....132 Jump 100InstructionMemory2361032kill PC=236 and fetch PC=1032Is this a common occurrence?Can we avoid these bubbles?March 11, 2010 CS152, Spring 20106BTB is only for Control InstructionsBTB contains useful information for branch and jump instructions only Do not update it for other instructionsFor all other instructions the next PC is PC+4 !How to achieve this effect without decoding the instruction?March 11, 2010 CS152, Spring 20107Branch Target Buffer (BTB)• Keep both the branch PC and target PC in the BTB • PC+4 is fetched if match fails• Only taken branches and jumps held in BTB• Next PC determined before branch fetched and decoded2k-entry direct-mapped BTB(can also be associative)I-CachePCkValidvalidEntry PC=matchpredictedtargettarget PCMarch 11, 2010 CS152, Spring 20108Combining BTB and BHT•BTB entries are considerably more expensive than BHT, but can redirect fetches at earlier stage in pipeline and can accelerate indirect branches (JR)•BHT can hold many more entries and is more accurateA PC Generation/MuxP Instruction Fetch Stage 1F Instruction Fetch Stage 2B Branch Address Calc/Begin DecodeI Complete DecodeJ Steer Instructions to Functional unitsR Register File ReadE Integer ExecuteBTBBHTBHT in later pipeline stage corrects when BTB misses a predicted taken branchBTB/BHT only updated after branch resolves in E stageMarch 11, 2010 CS152, Spring 20109Uses of Jump Register (JR)•Switch statements (jump to address of matching case)•Dynamic function call (jump to run-time function address)•Subroutine returns (jump to return address)How well does BTB work for each of these cases?BTB works well if same case used repeatedlyBTB works well if same function usually called, (e.g., in C++ programming, when objects have same type in virtual function call)BTB works well if usually return to the same place Often one function called from many distinct call sites!March 11, 2010 CS152, Spring 201010Subroutine Return StackSmall structure to accelerate JR for subroutine returns, typically much more accurate than BTBs.&fb()&fc()Push call address when function call executedPop return address when subroutine return decoded fa() { fb(); }fb() { fc(); }fc() { fd(); }&fd()k entries(typically k=8-16)March 11, 2010 CS152, Spring 201011Mispredict RecoveryIn-order execution machines:–Assume no instruction issued after branch can write-back before branch resolves–Kill all instructions in pipeline behind mispredicted branch–Multiple instructions following branch in program order can complete before branch resolvesOut-of-order execution?March 11, 2010 CS152, Spring 201012In-Order Commit for Precise Exceptions• Instructions fetched and decoded into instruction reorder buffer in-order• Execution is out-of-order ( out-of-order completion)• Commit (write-back to architectural state, i.e., regfile & memory, is in-orderTemporary storage needed in ROB to hold results before commitFetch DecodeExecuteCommitReorder BufferIn-order In-orderOut-of-orderKillKillKillException?Inject handler PCMarch 11, 2010 CS152, Spring 201013Branch Misprediction in PipelineFetch DecodeExecuteCommitReorder BufferKillKillKillBranchResolutionInject correct PC•Can have multiple unresolved branches in ROB•Can resolve branches out-of-order by killing all the instructions in ROB that follow a mispredicted branchBranchPredictionPCCompleteMarch 11, 2010 CS152, Spring 201014t vt vt vRecovering ROB/Renaming TableRegister FileReorder bufferLoad UnitFU FUFUStore Unit< t, result
View Full Document
Unlocking...