Computer architectureLesson 2 of 3 in the course Pipelining and parallelism

Branch Prediction: Strategies, History, and Speculative Execution

5 flashcards · 5 quiz questions · 5 match pairs · 5 fill-in sentences · English

Save course
Lesson progress
0 / 5

Your progress is kept in this browser only.Sign up to save it

Summary

This lesson explains what branch predictors do and why they are essential to keeping a processor pipeline busy.

A program’s control flow may depend on a condition, such as an if–then–else statement. At the machine level, this is commonly implemented with a conditional jump. The jump is either taken, transferring execution to another address, or not taken, continuing with the next sequential instruction.

All flashcards

How does a two-bit saturating counter resist a single unusual branch outcome?
From a strong prediction state, it takes two contrary outcomes to change its predicted direction.
How do local and global branch predictors differ?
A local predictor tracks history for each branch; a global predictor shares history across branches.
What is a hybrid branch predictor?
A predictor that combines multiple prediction mechanisms, often using selection or voting.
What makes an indirect branch different from a conditional branch?
An indirect branch may select among multiple target addresses, rather than just taken or not taken.
What is the purpose of a fast predictor with a slower override?
The fast predictor supplies an early answer, while the slower predictor can improve accuracy by replacing it.

Quiz questions

  1. Under the backward-taken, forward-not-taken rule, how is a branch with a target address lower than its own address predicted?Answer: It is predicted taken.
  2. What is aliasing in a branch-prediction table?Answer: Different branches map to the same table entry and can interfere.
  3. How does gshare select an entry in its prediction table?Answer: It XORs global history with bits of the branch address.
  4. What can happen in next-line prediction even when the processor quickly supplies the next instruction line?Answer: Some fetched instructions may later be discarded.
  5. How does a perceptron predictor's resource growth with history length compare with classical schemes whose tables grow exponentially?Answer: Its resource requirements grow linearly with history length.

Based on the Wikipedia article Branch predictor, licensed CC BY-SA 4.0. Adapted into a summary, flashcards and quizzes.

More in Computer architecture

All Computer architecture lessons
Computer architectureInstruction Pipelining: Stages, Hazards, and Performance Trade-offs5 flashcards · 5 quiz questions · 4 gamesPlay free →Computer architectureCPU Cache Organization, Policies, Addressing, and Hierarchies5 flashcards · 5 quiz questions · 4 gamesPlay free →Computer architectureOut-of-Order Execution: Scheduling, Renaming, and Retirement5 flashcards · 5 quiz questions · 4 gamesPlay free →Computer architectureMemory Hierarchy: Storage Levels, Locality, and Tiering5 flashcards · 5 quiz questions · 4 gamesPlay free →Computer architectureData and Control-Flow Addressing Modes in Processor Architectures5 flashcards · 5 quiz questions · 4 gamesPlay free →