Tournament and TAGE predictors: Worked examples — Hardware deep dive

This is the hands-on companion to Tournament and TAGE predictors (index 5.3.10). There we built the machinery: the local and global component predictors, the 2-bit selector, and the TAGE ladder of tagged tables. Here we drive that machinery through every situation it can meet — every counter value, every tie, every empty table, every degenerate input.

Before we start, three plain-words definitions we lean on all page:

Recall What does a 2-bit saturating counter mean?

A 2-bit counter holds one of four states: 00, 01, 10, 11 (the numbers 0–3). "Saturating" means it stops at the ends — adding 1 to 11 leaves it 11, subtracting 1 from 00 leaves it 00. Low half (00,01) = one choice, high half (10,11) = the other. The lone bit that flips as you cross the middle is the decision bit.

Recall What is the selector deciding in a tournament predictor?

Selector picks which component predictor to trust this time — not T vs NT, but local-vs-global. 00,01 → predictor 1, 10,11 → predictor 2.

The scenario matrix

Every worked example below is tagged with the cell it covers. The matrix lists every distinct behaviour this topic can throw at you.

#	Cell	What makes it distinct	Example
A	Selector: agree	both components right or both wrong → no move	Ex 1
B	Selector: disagree, P1 wins (no cross)	move down, stay in same half	Ex 2
C	Selector: saturation edge (both ends)	already at `00` or `11`, cannot move further	Ex 3
D	Selector: mid-crossing flip	the move that actually changes the chosen predictor	Ex 4
E	TAGE: no tag match (cold)	all tagged tables miss → base T0 provides	Ex 5
F	TAGE: longest-match wins	several tags match, pick the deepest table	Ex 6
G	TAGE: misprediction → allocate	provider wrong → new entry in a longer table	Ex 7
H	TAGE: useful-bit gate	when a correct prediction does / doesn't set useful	Ex 8
I	Real-world word problem	nested loop, count the history bits needed	Ex 9
J	Exam twist: accuracy algebra	plug numbers into the tournament error formula	Ex 10

Two special "degenerate" inputs are folded in: the cold table (empty entry, cell E) and the saturated counter (cell C) — the two places where the naive update rule would "want" to move but can't.

Tournament worked examples

The one rule we keep applying

Here P1 = local predictor, P2 = global predictor. Figure s01 is the picture we return to for every tournament example.

Figure s01 — the selector as a 4-point number line. The two teal dots on the left (00, 01) mean "trust P1 (local)"; the two orange dots on the right (10, 11) mean "trust P2 (global)". The dashed plum line at value 1.5 is the mid-crossing: the only place where a single step changes which predictor is chosen. The orange arrow (increment) pushes right when P2 uniquely wins; the teal arrow (decrement) pushes left when P1 uniquely wins; the "clamp" end-stops show where saturation freezes the counter.

Whenever an example asks "did the provider change?", find the start and end dots on this line and check whether they are the same colour (no change) or different colours (the plum line was crossed).

Forecast: One case both right, one case both wrong — does either one move the counter?

Which predictor is chosen? 10 is an orange dot in Figure s01 → use P2 (global) in both runs. Why this step? The selector picks the provider from the current value before the outcome is known.
Sub-case (a) — both correct. Local T ✓, Global T ✓ → the rule's third case → no move, sel = 10. Why? No unique winner ⇒ no evidence ⇒ freeze.
Sub-case (b) — both wrong. Local T ✗, Global T ✗ → also the third case → no move, sel = 10. Why show this separately? "Both wrong" is the easy-to-forget half of Cell A. If both components fail together, neither deserves blame relative to the other, so the selector must still freeze — moving would punish one arbitrarily.

Verify: In both sub-cases the value stays 2 (10) — start and end are the same orange dot, so the provider stays global. ✓

Forecast: We start deep in the teal half. P1 wins. Can a leftward step ever leave the teal half from here?

Score them. Local = NT ✓, Global = T ✗ → P1 uniquely correct. Why? The rule's first case is exactly "P1 correct AND P2 wrong."
Move down. $sel_{new} = max (0, 0 - 1) = max (0, - 1) = 0 =$ 00. Why? We reward the winner by drifting toward the low (teal) half where P1 lives — but 00 is already the leftmost teal dot, so the clamp holds it. (This doubles as a reminder that Cell B and Cell C can touch, but here the point is that we stay firmly in the teal half.)
Did the provider change? Start = 00 (teal), end = 00 (teal) — same colour in Figure s01, plum line never approached. Provider stays P1 (local). Why this framing? Cell B is defined as "reward P1 without changing the chosen predictor." Starting deep in P1's own half guarantees the step deepens confidence rather than flipping it — the clean opposite of Cell D.

Verify: $max (0, - 1) = 0$ ; start and end are the same teal dot, so provider is unchanged and no mid-cross occurred. ✓

Forecast: Both selectors are pinned against a wall and the "winner" is pushing them further into it. Can either move?

Sub-case (a) — bottom wall. P1 uniquely correct → rule says decrement: $sel_{new} = max (0, 0 - 1) = 0 =$ 00. Why the max? The counter is saturating; below 0 is not a state, so the left "clamp" end-stop in Figure s01 holds it.
Sub-case (b) — top wall. P2 uniquely correct → rule says increment: $sel_{new} = min (3, 3 + 1) = min (3, 4) = 3 =$ 11. Why the min? Symmetric saturation — the right clamp end-stop mirrors the left one. Above 3 is not a state.
Interpret both. At each wall, "trust in the winning predictor is already maximal"; more evidence for it just keeps it pinned. Why does this matter? Saturation at both ends is the hysteresis that resists oscillation — a single opposing win from the far edge cannot instantly flip the provider.

Verify: (a) $max (0, - 1) = 0$ ; (b) $min (3, 4) = 3$ . Both walls handled, no wraparound at either end. ✓

Forecast: 01 is the rightmost teal dot in Figure s01, one step from the plum line. Global wins. Does the step cross it?

Score. Global = T ✓, Local = NT ✗ → P2 uniquely correct → increment. Why? Second case of the rule.
Increment. $sel_{new} = min (3, 1 + 1) = 2 =$ 10. Why the min? Symmetric top saturation; here we're nowhere near it.
Read Figure s01. Start 01 (teal) → end 10 (orange): the dashed plum line at 1.5 was crossed. The high bit flipped 0→1 — provider changes local → global. Why highlight this? Only one step in each direction crosses the plum line; the other steps just deepen confidence within a colour. This crossing is the exact moment behaviour visibly changes — contrast with Ex 2, which stayed one colour.

Verify: $min (3, 2) = 2$ ; start dot teal, end dot orange ⇒ colours differ ⇒ provider flipped. ✓

TAGE worked examples

TAGE picks a provider by tag matching across tables of growing history length. Figure s02 draws the ladder: T0 (no history) at the bottom, then T1, T2, T3 with history lengths $4, 8, 16$ bits. The longest table whose tag matches wins.

Figure s02 — the TAGE ladder as stacked table rows. Each row shows a table, its history length, and its lookup result for one example branch. We scan top-down (the ink arrow on the left) looking for a tag hit. Here T3 (history 16) misses its tag, T2 (history 8) and T1 (history 4) both hit; because T2 is the deeper hit it becomes the provider (orange highlight). T0 at the bottom carries no tag and is the guaranteed fallback when every tagged row misses.

Prediction counters here are 3-bit signed, range $- 4$ to $+ 3$ ; predict T if counter $\geq 0$ , else NT.

Recall Why "longest match wins"?

A longer history is a more specific fingerprint of the situation. If it has learned this exact pattern, it's more reliable than a shorter, more general table. Bottom (T0) is the always-available fallback.

Forecast: Nothing tagged matches — is there anything left to answer with?

Scan tables top-down (Figure s02 arrow). T3 tag ✗, T2 ✗, T1 ✗. Why top-down? We want the longest tag hit; start deep and fall through.
Fall to base. No tagged match → provider = T0. Why T0 always works? T0 is indexed by PC only and has no tag, so it can never "miss" — it is the guaranteed fallback for cold/degenerate inputs.
Read T0's counter. $+ 1 \geq 0$ → predict T. Why the $\geq 0$ threshold? Signed counter: non-negative = leaning taken.

Verify: Provider = T0, prediction = T because $1 \geq 0$ is true. ✓

Forecast: Both T1 and T2 match but disagree in sign. Whose vote counts?

List matches (Figure s02). Matching tables: T1 (len 4) and T2 (len 8). Why list them? The rule compares history lengths, not counter strengths.
Pick the longest. $8 > 4$ → provider = T2 (the orange-highlighted row). Why not the more confident T1? Specificity beats confidence — T2 saw more context and still matched this branch's fingerprint.
Read T2's counter. $+ 2 \geq 0$ → predict T (even though T1 wanted NT with $- 2$ ). Why ignore T1? T1 is the alternate; it's only consulted for the useful-bit logic (Ex 8), not the final call.

Verify: Provider = T2, prediction = T because $2 \geq 0$ . T1's $- 2$ is overruled. ✓

Forecast: The 4-bit history wasn't enough. Which longer table gets the new entry — and what if none were free?

Update the provider counter. Wrong on a T prediction (actual NT) → decrement: $+ 1 \to 0$ . Why still $\geq 0$ ? $0 \geq 0$ still predicts T — one strike isn't enough to flip a 3-bit counter; that's the point of counters.
Restrict to longer tables. Provider = T1 (index $k = 1$ ). Only $T_{m}$ with $m > k$ are candidates: here {T2, T3}. Why longer only? The current length failed, so a more specific (longer) history is the hypothesis worth testing. Never allocate shorter — that throws away context.
Pick the victim by lowest useful bit. Among candidates, we can only overwrite an entry whose useful bit = 0 (a useless slot). T2 has useful = 1 → protected; T3 has useful = 0 → free to overwrite. So allocate in T3. Why the useful-bit gate? Overwriting a proven-useful entry would destroy knowledge; the useful bit is exactly the "do not evict me" flag. When several candidates are free, real TAGE prefers the shortest free table (closest to the failed length) so it climbs the ladder one rung at a time; here T3 is the only free one, so it wins outright.
What if NO candidate is free (all useful = 1)? Then TAGE allocates nothing this time and instead decrements the useful bits of the candidate entries (an ageing step). Why not force an eviction? Forcing out a useful entry would likely cause a future misprediction worse than the one we're fixing. Ageing lets a slot free up on the next miss, so allocation is merely postponed, never destructive.
Seed the new entry. Write T3's tag, set its counter to weakly match the actual outcome NT → counter $= - 1$ , useful bit $= 0$ . Why weak, not strong? A brand-new entry is untrusted; it must earn confidence over future visits.

Verify: Provider counter $1 \to 0$ (still $\geq 0$ , unchanged prediction direction — one miss doesn't flip). Candidate set = {T2,T3}; only T3 has useful = 0, so target = T3, seeded NT with counter $- 1 < 0$ . ✓

Forecast: Being right is nice — but does being right when you were also redundant earn a reward?

Fix who the alternate is. Matches = {T1, T3}; provider = longest = T3; alternate = next-shorter match = T1. T2 missed its tag, so it never enters this comparison. Why this matters? "Alternate" means next-shorter table that actually matched, not simply the table one rung below. A missed table is invisible here.
Sub-case (a): alternate wrong. T3 right, T1 wrong → T3 was necessary. Why increment? The useful bit measures "did this entry provide value a shorter match couldn't?" Here it clearly did → useful $+ 1$ .
Sub-case (b): alternate also right. T3 right, T1 right → T3 was redundant. Why NOT increment? T1 (cheaper, shorter) already covered it. Rewarding T3 here would protect a table that isn't earning its space → useful unchanged.
Consequence. Redundant deep entries drift to low useful and become victims for future allocations (Ex 7 step 3). Why is that healthy? It recycles hardware away from patterns a shorter table handles for free.

Verify: alternate = T1 (the only shorter matching table). Increment useful $⟺$ (provider correct) AND (alternate wrong). (a) → yes; (b) → no. ✓

Real-world & exam-style

Worked example Ex 9 — Cell I: word problem, how many history bits?

for (int i = 0; i < 3; i++)      // outer, 3 iterations
  for (int j = 0; j < 4; j++)    // inner, 4 iterations
    if (cond) { ... }            // Branch X, fully periodic

The inner loop's own back-edge (the "keep looping?" branch) repeats the same decision on a fixed period. What minimum global-history length $L$ (in branches) lets a TAGE table capture one full period of the inner loop's back-edge, and which table in the parent's ladder ( $L_{1} = 4, L_{2} = 8, L_{3} = 16$ ) is the shortest that suffices?

Forecast: The inner loop's own branch fires how many times per period before it repeats?

Count the inner branch's period. Inner runs $j = 0, 1, 2, 3$ then exits. The inner loop-back branch outcome sequence per outer iteration is $T, T, T, N T$ — period 4. Why period 4? Four inner conditional-branch resolutions before the pattern repeats.
History bits = period. To recognise a period-4 pattern you must remember the last 4 outcomes → $L \geq 4$ bits. Why exactly the period? A history register shorter than the period cannot distinguish two positions in the cycle that share a suffix; $L = 4$ gives a unique fingerprint for each phase.
Match to a table. In the parent's ladder $L_{1} = 4$ , table T1 is the shortest table that suffices; that is exactly why TAGE allocated into T1 in the parent's nested-loop example. Why not T0? T0 has no history (length 0) and would only learn the average bias, mispredicting the loop-exit every period.

Verify: Period = 4, minimum $L = 4$ , chosen table = T1 ( $L_{1} = 4$ ). ✓

Forecast: Selector is only 80% good — can the combo still beat the 87% global?

Write the model (from parent). $Err_{tour} = (1 - a_{s}) \cdot max (1 - a_{1}, 1 - a_{2}) + a_{s} \cdot min (1 - a_{1}, 1 - a_{2})$ Why this shape? With probability $a_{s}$ the selector chose the better predictor (gets the smaller error); with probability $1 - a_{s}$ it chose the worse one (larger error).
Fill in the per-predictor errors. $1 - a_{1} = 0.15$ , $1 - a_{2} = 0.13$ . So $min = 0.13$ , $max = 0.15$ . Why compute both? The formula weights the two extremes.
Evaluate with $a_{s} = 0.80$ . $Err_{tour} = 0.20 \times 0.15 + 0.80 \times 0.13 = 0.030 + 0.104 = 0.134$ Tournament accuracy $\approx 1 - 0.134 = 0.866 = 86.6%$ . Why interpret? This particular selector is slightly worse than the standalone global (87%) — it shows the model's honest edge case: a weak selector can dilute a strong component.
Redo with $a_{s} = 0.95$ . $Err_{tour} = 0.05 \times 0.15 + 0.95 \times 0.13 = 0.0075 + 0.1235 = 0.131$ Tournament accuracy $\approx 1 - 0.131 = 0.869 = 86.9%$ — now essentially matching the best component. Why the contrast? The exam trap is assuming "hybrid always $>$ best component." This coarse single- $a_{s}$ model shows it only wins once the selector is accurate enough; real hybrids beat both because they learn per-branch which to trust (a per-branch selector, not one global $a_{s}$ ).
Final answer. With $a_{s} = 0.80$ : error $= 0.134$ (86.6%, slightly below global's 87%). With $a_{s} = 0.95$ : error $= 0.131$ (86.9%). Conclusion: the tournament only pays off when the selector's own accuracy is high.

Verify: $0.2 (0.15) + 0.8 (0.13) = 0.134$ ; and $0.05 (0.15) + 0.95 (0.13) = 0.131$ ; best single predictor error $= min (0.15, 0.13) = 0.13$ , so a weak selector cannot beat it. ✓

Wrap-up

Recall Selector at

01, P2 wins a disagreement — new value and does provider change? $min (3, 1 + 1) = 2$ = 10; that crosses the plum mid-line, so provider flips local → global (Cell D).

Recall Selector at

00, both predictors wrong — new value? Both wrong is a tie ⇒ third case ⇒ freeze at 00 (Cell A, both-wrong half).

Recall TAGE: T1 and T3 tags both match, disagree — who provides?

The longer history table T3 provides; T1 becomes the alternate used only for the useful-bit test.

Recall TAGE misprediction, but every longer table's entry has useful = 1 — what happens?

No allocation this cycle; TAGE decrements those useful bits (ageing) so a slot frees up on a later miss. Allocation is postponed, never destructive.

Related: 5.3.8-Two-level-adaptive-predictors · 5.3.9-Gshare-and-local-predictors · 5.3.11-Branch-target-bufers · 5.4.2-Speculative-execution · 7.2.5-Cache-coherence-and-branch-predictors · Hinglish version