Control speculation · front end
Predict both direction and destination before decode can know either.
A branch history table estimates taken versus not taken. A branch target buffer supplies the destination. Global history adds context when one branch’s behavior depends on earlier branches.
The complete fetch contract
Correct direction is necessary, but it does not deliver target bytes.
useful next fetch = right direction ∧ right target ∧ target block deliveredA miss at any term creates lost fetch bandwidth.
Predictor FSM + trace
Two bits resist one unusual outcome.
States 0–1 predict not taken. States 2–3 predict taken.
Weakly not taken. Saturation prevents a counter from wrapping at either end.
- Choose actual outcomes to build a trace.
Remember only the last outcome
A mostly taken loop typically misses on exit and again on the next entry.
Keep hysteresis per branch PC
One loop exit weakens the taken prediction without immediately reversing it.
Use recent global context
Gshare XORs PC index bits with global history to separate correlated situations.
Predict where taken means
The BHT predicts direction. The BTB supplies a target early enough to avoid a fetch bubble.
Nested-loop source exercise
Trace B1, B2, and B3 from a weak-not-taken start.
Convention: T on B1/B2 means the loop continues. B3 is T when i == j. All counters begin WN (01); gshare begins with GHR 00 and uses PC[3:2] XOR GHR.
for (int i = 0; i < 2; i++) { // B1 · PC 0x100
for (int j = 0; j < 2; j++) { // B2 · PC 0x200
if (i == j) { /* work */ } // B3 · PC 0x300
}
}| Step | Branch / context | BHT entry | Counter | Predict | Actual | Result | Next |
|---|---|---|---|---|---|---|---|
| 1 | B3i=0, j=0 | B3 | WN | N | T | Miss | WT |
| 2 | B2j loop continues | B2 | WN | N | T | Miss | WT |
| 3 | B3i=0, j=1 | B3 | WT | T | N | Miss | WN |
| 4 | B2j loop exits | B2 | WT | T | N | Miss | WN |
| 5 | B1i loop continues | B1 | WN | N | T | Miss | WT |
| 6 | B3i=1, j=0 | B3 | WN | N | N | Hit | SN |
| 7 | B2j loop continues | B2 | WN | N | T | Miss | WT |
| 8 | B3i=1, j=1 | B3 | SN | N | T | Miss | WN |
| 9 | B2j loop exits | B2 | WT | T | N | Miss | WN |
| 10 | B1i loop exits | B1 | WT | T | N | Miss | WN |
Per-PC BHT: 9 mispredictions, 27 redirect cycles at the stated 3-cycle penalty. Independent local counters repeatedly relearn the behavior of these tiny loops.
Taken is known, but the target is not.
Fetch pauses or follows a temporary fall-through path until decode or execute computes the target and redirects. The direction predictor was right, yet no useful target block could be requested.
The next fetch cannot arrive on time.
An I-cache or instruction-TLB miss, a target crossing a fetch-block boundary, or insufficient fetch bandwidth can create bubbles even with correct BHT and BTB entries.
A hit can name the wrong destination.
Partial tags, replacement, or self-modifying/code-relocation effects can return a stale or aliased target. The front end redirects again after validation.
One PC may have many legitimate targets.
A PC-relative branch encodes a stable displacement. An indirect jump depends on a register value, object type, call history, or return stack. A single last-target BTB entry cannot represent that distribution well, so modern designs add indirect-target and return-address predictors.
Why is a 2-bit counter better than a 1-bit predictor?
A 1-bit predictor changes direction after every surprise. A loop that is taken many times and not taken once on exit will therefore miss on exit and often miss again on the next entry. A 2-bit saturating counter needs two contrary outcomes to reverse direction, preserving the loop’s dominant behavior.
What is the difference between a BHT and a BTB?
The BHT predicts whether a conditional branch will be taken, usually with counters indexed by branch PC and sometimes history. The BTB predicts the target address so fetch can request target instructions immediately. Correct direction without a usable target can still leave a bubble.