A worked mechanism
Direction accuracy does not account for every fetch bubble.
This additive teaching budget assumes 1,000 base cycles. Direction misses and target-delivery holes are disjoint and never overlap another stall.
Base execution
1,000 cycles
The useful instruction work would need 1,000 cycles with no listed front-end penalties.
Wrong direction
+60 cycles
20 branch misses each incur a fixed three-cycle redirect cost.
Right direction, late target
+10 cycles
Five other taken branches each wait two cycles for a usable target.
Total front-end cost
1,070 cycles
Both categories consume cycles, although only the first reduces direction accuracy.
Work it through
What an accuracy headline omits
A direction-only report counts 20 misses. This fixture still loses another 10 cycles on correctly predicted branches whose targets arrive late.
Total added cost is 70 cycles; the direction-miss budget alone predicts only 60.
Watch for this
Real stalls can overlap. Do not add raw performance-counter events as independent cycle costs without checking their definitions.
Check your reasoning
Trace direction result, target availability, fetch delivery, redirect boundaries, and overlap before attributing CPI.
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
A strong prediction survives one contrary 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
From strongly taken, one loop exit weakens the prediction without reversing it. From weakly taken, that exit changes the prediction to not taken.
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. The per-PC model has no aliasing; gshare shares four counters. These PCs all have index bits 00. Each outcome updates the model before the next branch; speculative history and recovery are omitted.
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 modeled redirect cycles with a fixed, non-overlapping 3-cycle penalty per miss. 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 in a strong state needs two consecutive contrary outcomes to reverse direction. From a weak state, one contrary outcome reverses it. A loop that has trained the counter strongly taken can therefore retain its taken prediction through one exit.
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.
Put it into practice
Explain the mechanism. Test your reasoning.
Use the experiment above to support your answer, then apply the idea in the question bank.
Continue the learning path
Next: Cache coherence
Track readers, writers, dirty ownership, invalidation, intervention, false sharing, and write-policy consequences across private caches.