Computer ArchitectureSpeculative ExecutionComputerArchitecture
Computer Architecture Computer Architecture Specula1ve Execu1on
Review: Branch TypesNumber ofTypeDirectionatWhen is nextfetchtimepossible nextfetch addressfetch addresses?resolved?2ConditionalUnknownExecution(registerdependent)1Always takenDecode (PC +Unconditionaloffset)1CallDecode (PC +Always takenoffset)ManyReturnAlways takenExecution(registerdependent)IndirectManyAlways takenExecution(registerdependent)Different branch types can be handled differentlyComputerArchitecture2
Computer Architecture Review: Branch Types Type Direction at fetch time Number of possible next fetch addresses? When is next fetch address resolved? Conditional Unknown 2 Execution (register dependent) Unconditional Always taken 1 Decode (PC + offset) Call Always taken 1 Decode (PC + offset) Return Always taken Many Execution (register dependent) Indirect Always taken Many Execution (register dependent) 2 Different branch types can be handled differently
Review: How to Handle Control DependencesCritical to keep the pipeline full with correct sequence ofdynamic instructions.Potential solutionsiftheinstructionisacontrol-flowinstruction:Stall the pipeline until we know the next fetch addressGuess the next fetch address (branch prediction)Employ delayed branching (branch delay slot)Do something else (fine-grained multithreading)Eliminate control-flow instructions (predicated execution)Fetchfrom bothpossiblepaths (if youknowtheaddressesofbothpossiblepaths)(multipathexecution)ComputerArchitecture
Computer Architecture Review: How to Handle Control Dependences • Critical to keep the pipeline full with correct sequence of dynamic instructions. • Potential solutions if the instruction is a control-flow instruction: • Stall the pipeline until we know the next fetch address • Guess the next fetch address (branch prediction) • Employ delayed branching (branch delay slot) • Do something else (fine-grained multithreading) • Eliminate control-flow instructions (predicated execution) • Fetch from both possible paths (if you know the addresses of both possible paths) (multipath execution) 3
How to Handle ControlDependencesCritical to keep the pipeline full with correct sequence ofdynamic instructions.Potential solutions if the instruction isa control-flowinstruction:Stall the pipeline until we know the next fetch addressGuess the next fetch address (branch prediction)Employdelayedbranching(branchdelayslot)Do something else (fine-grained multithreading)Eliminate control-flow instructions (predicated execution)Fetch from both possible paths (if you know the addressesof both possible paths) (multipath execution)ComputerArchitecture
Computer Architecture How to Handle Control Dependences • Critical to keep the pipeline full with correct sequence of dynamic instructions. • Potential solutions if the instruction is a control-flow instruction: • Stall the pipeline until we know the next fetch address • Guess the next fetch address (branch prediction) • Employ delayed branching (branch delay slot) • Do something else (fine-grained multithreading) • Eliminate control-flow instructions (predicated execution) • Fetch from both possible paths (if you know the addresses of both possible paths) (multipath execution) 4
Review: Branch Prediction: Idea: Predict the next fetch address (to be used in thenext cycle) Requires three things to be predicted at fetch stage:Whetherthefetched instruction is abranch(Conditional) branch directionBranch target address (if taken)Observation: Target address remains the same for aconditional direct branch across dynamic instances Idea: Store the target address from previous instance andaccess it with the Pc- Called Branch Target Buffer (BTB) or Branch Target AddresSCacheComputerArchitecture
Computer Architecture Review: Branch Prediction • Idea: Predict the next fetch address (to be used in the next cycle) • Requires three things to be predicted at fetch stage: – Whether the fetched instruction is a branch – (Conditional) branch direction – Branch target address (if taken) • Observation: Target address remains the same for a conditional direct branch across dynamic instances – Idea: Store the target address from previous instance and access it with the PC – Called Branch Target Buffer (BTB) or Branch Target Address Cache 5