5.3.10 · D5Advanced Microarchitecture
Question bank — Tournament and TAGE predictors
This bank hunts the misconceptions that hide inside Tournament and TAGE predictors. Each item is a one-line reveal: read the prompt, commit to an answer out loud, then check. The answers give the reasoning, not just a verdict — that reasoning is the thing worth remembering.
Prerequisites you should already trust: 5.3.8-Two-level-adaptive-predictors, 5.3.9-Gshare-and-local-predictors. A branch's fate feeds 5.4.2-Speculative-execution, and the target address comes from 5.3.11-Branch-target-bufers.
First, the vocabulary these questions assume
Before the traps, pin down every word and symbol they lean on — otherwise the "gotcha" is unfair.
Look at the ladder before reading further — the figure fixes the ordering in your mind.
The selector's decision is a simple threshold — the figure shows the counter as a dial.
True or false — justify
A saturating counter is a small counter that stops at its minimum and maximum instead of wrapping around; it needs repeated evidence before it changes its verdict.
The tournament selector is a per-branch (or per-hash) 2-bit saturating counter that says which component predictor to trust, not what the branch does.
The provider in TAGE is the single table whose entry actually supplies the prediction on a given lookup — the longest-history table whose tag matched.
TF — A tournament selector predicts whether the branch is taken or not-taken.
False — the selector never predicts the branch outcome; it only chooses which component predictor (predictor 1 = local, predictor 2 = global) gets to answer. The chosen component predicts taken/not-taken.
TF — If both component predictors are correct, the selector still moves toward the one that "won".
False — the update rule only moves the selector when the two components disagree in correctness; if both are right (or both wrong) it holds at , because there is no evidence favoring one over the other.
TF — A tournament predictor can never beat its single best component predictor.
False — because different branches favor different components, routing each branch to its better component can beat either component measured alone; that is the whole point of meta-prediction.
TF — TAGE's base predictor T0 uses global history like the tagged tables.
False — T0 has : it is a plain PC-indexed biased predictor with no history, the always-available fallback used when no tagged table's tag matches.
TF — In TAGE, all tagged tables that match are consulted and their votes averaged.
False — TAGE picks a single provider: the matching table with the largest index (longest history). Longer history means more specific pattern, so it wins outright — no averaging.
TF — TAGE's history lengths grow linearly (4, 8, 12, 16, …).
False — the sequence grows geometrically (e.g. ) so a small number of tables covers a huge range of pattern lengths without spending entries on redundant nearby lengths.
TF — A longer-history TAGE table is always more accurate than a shorter one for the same branch.
False — longer history is more specific, which helps only if the branch actually depends on that much history; for a short-pattern branch, extra history bits are noise and the shorter table is better, which is why the useful bit and tag matching decide the winner.
TF — Once the selector saturates toward the global predictor (), a branch can never switch back to local.
False — saturation only means it takes several consecutive disagreements-in-the-other-direction to walk back down; behaviour change (e.g. a new loop phase) supplies exactly that evidence and the counter returns toward .
Spot the error
Error — "The selector is updated toward predictor 2 whenever predictor 2 is correct."
Wrong: it moves toward predictor 2 (global) only when predictor 2 is correct and predictor 1 (local) is wrong — i.e. . If both are correct there is no reason to shift trust.
Error — "On a TAGE misprediction, we allocate a new entry in a shorter-history table to react faster."
Wrong: allocation goes to a longer-history table with , where was the provider that mispredicted. Its history length was insufficient to distinguish this case, so we try a more specific, longer pattern.
Error — "TAGE tags exist so that two branches with different PCs but the same history index share one entry efficiently."
Wrong: tags exist to detect and prevent exactly that collision. A mismatched tag means the entry belongs to a different context, so TAGE treats the table as not-matching there.
Error — "A tournament predictor with an 80% -accurate selector performs worse than either component alone."
Wrong: even an imperfect selector yields a weighted blend of the two error rates that is typically better than either component, because it still steers most branches to their stronger predictor.
Error — "The useful bit is incremented every time a TAGE entry predicts correctly."
Wrong: the provider 's useful bit is incremented only when is correct and the next-shorter table would have been wrong — i.e. when this longer entry actually added value. Rewarding every correct prediction would make every entry look useful and break victim selection.
Error — "Because TAGE has multiple tables, it does not need a base predictor."
Wrong: T0 is essential. On a brand-new branch no tagged table has an allocated matching entry, so T0's biased guess is the only prediction available.
Error — "The global predictor uses the last N outcomes of this branch's PC."
Wrong: that describes the local predictor (per-PC history). The global predictor uses the Global History Register — outcomes of the last N branches regardless of PC — which is what lets it capture correlation between different branches.
Why questions
Why — Why does the selector use a saturating counter instead of a single bit?
A single bit would flip on every disagreement, causing oscillation; a 2-bit saturating counter (–) demands consistent evidence before crossing the threshold, giving stability while still adapting to genuine phase changes.
Why — Why does TAGE allocate in a longer table (, ) after a misprediction rather than just retraining the current provider ?
A misprediction from the longest matching table means history length cannot separate the two behaviours; retraining the same entry would just thrash it, so TAGE reaches for a longer, more discriminating pattern .
Why — Why do geometric history lengths cover "any" needed length with few tables?
For any required length there is a table with in the sequence ; geometric spacing means each step roughly doubles the reach, so a handful of tables spans from a few bits to dozens without gaps that matter.
Why — Why is a local predictor good for loop-counter branches but a global predictor good for correlated branches?
A loop's taken/not-taken pattern depends only on its own recent history (local, PC-indexed), whereas a branch whose outcome tracks an earlier branch depends on other branches' outcomes recorded in the Global History Register.
Why — Why can a tournament predictor route "local for branch A, global for branch B" simultaneously?
The selector is indexed per branch (via a hash of the PC), so each branch has its own trust counter and converges to its own best component independently.
Why — Why does TAGE need per-entry tags but a simple gshare predictor does not?
Gshare accepts aliasing as noise, but TAGE must know whether the longest-index matching table's entry truly belongs to this branch-and-history context; the tag confirms ownership so a stale entry from another context is not trusted as the provider.
Edge cases
Edge — A branch is seen for the very first time in TAGE. Which predictor answers?
T0 (the base predictor, ) — no tagged table has an allocated, tag-matching entry yet, so the biased fallback is used and (if wrong) triggers allocation in a longer table .
Edge — Both component predictors are wrong on a tournament branch. Does the selector move?
No — the update rule holds when both are wrong (as when both are right), since neither component demonstrated superiority this time.
Edge — Every TAGE table's tag matches for a lookup. Which one provides the prediction?
The one with the largest index among the matches (longest history ); longer history is the most specific context and outranks all shorter matches regardless of their counter values.
Edge — TAGE wants to allocate but all longer tables' candidate entries have their useful bit set.
No victim can be safely evicted, so allocation typically fails this time; the periodic decrement of useful bits eventually frees low- victims, and meanwhile the existing provider keeps predicting.
Edge — The selector counter sits exactly at the boundary and the favored component flips.
That boundary is where a single disagreement tips the choice; that is intended — near the middle the predictor is genuinely undecided and should switch readily, while values pushed to the extremes ( or ) resist switching.
Edge — A biased branch (almost always not-taken, e.g. error handling). Which mechanism handles it cheaply?
T0's PC-indexed 2-bit counter alone captures the strong bias; no tagged table needs to be spent, so TAGE conserves its long-history resources for branches that actually need them.
Recall One-line self-test
Selector chooses ==which component (low = local, high = global), provider is the longest-index tagged table whose tag matches, allocation goes to a longer table , , useful bit rewards being correct when would have been wrong==.