Tournament and TAGE predictors: Visual walkthrough

This page rebuilds one single result in pictures: how does TAGE decide which of its many tables gets to predict a branch? We will earn every symbol before we use it. By the end you will be able to trace a branch through the whole machine on paper.

If a word here feels unexplained, it is built in an earlier step. Nothing is assumed from the parent note — we start below zero.

Step 1 — What is a branch, and what is "history"?

WHAT. A branch is an instruction like if (x > 0) jump. Its outcome is one of two things: T (taken, we jump) or NT (not taken, we fall through). We label the address of the branch instruction its PC (Program Counter — literally which line of code we are at).

WHY. Before predicting whether we take a branch, we need a written record of what recently happened. That record is the Global History Register (GHR): a row of bits, newest on the right, where each bit is one past branch outcome (1 = T, 0 = NT).

PICTURE. Look at the figure. The GHR is a sliding row of bits. Every time any branch resolves, we shove its outcome in on the right and the oldest bit falls off the left — like a queue.

Step 2 — Why not just one history length? (the core tension)

WHAT. We must pick how many bits of GHR to feed the predictor. Call that number $L$ (the history length).

WHY. Here is the tension the whole design solves:

A loop counter branch (T,T,T,T,NT) only needs the last few outcomes — small $L$ (say $L = 4$ ).
A correlated branch (if a>0 far away decides if b>0 here) needs many outcomes back — large $L$ (say $L = 32$ ).

If you fix one $L$ , you are wrong for the other kind of branch: too short underfits (misses the pattern), too long dilutes (needs impossibly many table entries to cover every history combination).

PICTURE. The figure shows the same branch fed by a short window vs a long window. Short window = few possible patterns, learns fast, but blind to distant causes. Long window = sees the cause, but there are astronomically many patterns to memorise.

The resolution: keep many predictors, each at a different $L$ , and let them compete. That is the geometric ladder we build next. See also 5.3.8-Two-level-adaptive-predictors for the single-length ancestor.

Step 3 — The geometric ladder of tables

WHAT. TAGE holds a stack of small tables. The bottom is the base predictor $T_{0}$ (uses no history — pure PC bias). Above it sit tagged tables $T_{1}, T_{2}, T_{3}, T_{4}$ , each assigned a history length that grows geometrically:

L_{1} = 4, L_{2} = 8, L_{3} = 16, L_{4} = 32

Term by term: $L_{i}$ is how many GHR bits table $i$ looks at. "Geometric" means each length is roughly a fixed multiple of the one below (here $\times 2$ ), not a fixed addition.

WHY geometric and not $4, 8, 12, 16$ ? Because branch correlations live at wildly different distances. Doubling covers a huge span ( $4 \to 32$ ) with only 4 tables. If we added $+ 4$ each time we would need many more tables to reach $L = 32$ , wasting hardware. Doubling gives broad coverage cheaply — that is the whole point of the "Geometric" in TAGE.

PICTURE. A staircase: $T_{0}$ on the ground (no window), then each step up peers through a window twice as wide.

Ratio check: $L_{1} r^{3} = 4 \cdot 2^{3} = 32 = L_{4}$ . ✓

Step 4 — How one table is addressed: index and tag

WHAT. Each tagged table $T_{i}$ has rows. To find this branch's row we compute an index — an address into the table — by hashing (scrambling together) the PC and the first $L_{i}$ bits of GHR:

index_{i} = hash (PC, GHR [0 : L_{i} - 1])

Because many different (PC, history) combos can scramble to the same row (a collision), each row also stores a tag: a second, independent hash of (PC, history) that we compare to confirm "yes, this row really belongs to me."

WHY a tag at all? Without it, two unrelated branches landing in the same row would silently corrupt each other's prediction. The tag is a fingerprint: if the stored tag ≠ the fingerprint we just computed, this row is not ours — treat the table as not matching.

PICTURE. One row = three fields: the tag (fingerprint), a prediction counter (which way to guess), and a useful bit (built in Step 7). The index picks the row; the tag confirms it.

Recall Why does the base

$T_{0}$ have no tag? $T_{0}$ is indexed by PC alone and always answers (it is the safety net). It can never "not match", so there is nothing to confirm — no tag needed. ::: Because $T_{0}$ is a plain PC-indexed 2-bit counter that must ALWAYS supply a fallback prediction, so it can't decline — a tag (which lets a table say "not me") would be meaningless.

Step 5 — The prediction: longest matching table wins

WHAT. Now the central result. On a branch we:

Compute all indices $index_{0}, \dots, index_{4}$ at once (in parallel).
Read each row and compare its stored tag to the freshly-computed fingerprint.
Among all tables whose tag matches, pick the one with the largest $i$ (longest history). Call it the provider.
Output the provider's counter sign: T if $ctr \geq 0$ , else NT.
If no tagged table matches, the provider is $T_{0}$ .

WHY longest? A longer history that still recognises this situation has conditioned its guess on strictly more context — it is the most specific witness. A short table might match by coincidence; a long matching table has seen this precise sequence and survived. Specificity beats generality when it applies, and the tag guarantees it applies.

PICTURE. Four tables light up green (match) or grey (miss). Here $T_{1}$ and $T_{3}$ match; $T_{2}, T_{4}$ miss. The arrow crowns $T_{3}$ the provider because $3 > 1$ .

Step 6 — Edge & degenerate cases (all of them)

WHAT. Four situations must never surprise us. Each is drawn in the figure panel.

(a) No table matches — brand-new branch, empty tables. Provider $= T_{0}$ . We still emit a guess (its PC bias). Never a crash.

(b) Only $T_{0}$ has ever seen this branch — same as (a): use base. This is the cold start every branch begins in.

(c) Two tables match, longer one is wrong — we still trust the longer (Step 5 rule), but Step 7's allocation will grow a still-longer table to fix it. Being wrong is how TAGE learns which length it needs.

(d) Counter exactly at the boundary — $ctr = 0$ predicts T (rule is $\geq 0$ ). A counter that saturates at $+ 3$ or $- 4$ cannot overflow; it just stays pinned — this is why it is called a saturating counter, and it prevents a single fluke from flipping a confident branch.

PICTURE. Four mini-panels, one per case, showing the provider chosen (or the saturated counter refusing to move).

Step 7 — Update: reward the provider, allocate on failure, and the useful bit

WHAT. When the true outcome arrives, TAGE does three things.

Update the provider counter. Move it toward the truth: if actual = T, do $ctr \leftarrow min (+ 3, ctr + 1)$ ; if actual = NT, $ctr \leftarrow max (- 4, ctr - 1)$ . The $min / max$ are the saturation — the counter never leaves $[- 4, + 3]$ .
On a wrong prediction, allocate a fresh entry in some longer table $T_{m}$ with $m > k$ (provider was $T_{k}$ ). Give a longer history a chance — the current length clearly wasn't enough (this is exactly edge case (c)).
The useful bit $u$ . Set $u = 1$ on a provider entry when it predicted correctly and the next-shorter matching table would have been wrong — proof this entry earned its keep. Periodically all $u$ are reset toward 0; entries stuck at $u = 0$ are the ones we overwrite when we need room. This is victim selection: forget the entries that never help.

WHY allocate longer, never shorter? If a long matching table was already wrong, a shorter one (less context) has no chance of doing better — going the other way is hopeless. Growth is the only direction that adds information.

PICTURE. Left: provider counter nudged toward the true outcome (saturating). Right: a misprediction spawns a new tagged entry one rung up the ladder.

The one-picture summary

The whole life of one prediction: compute indices → check tags → longest match provides → predict from its counter → on resolution, update / allocate longer / manage useful bits. The staircase, the fingerprint match, the crowned provider, and the feedback arrows all in one frame.

Recall Feynman retelling — tell it back in plain words

Imagine a branch walks up to a row of witnesses. Each witness has watched a different amount of the past: one glanced at the last 4 events, another at the last 8, then 16, then 32. Every witness also carries a fingerprint card so it can honestly say "I actually recognise this exact scene" or stay quiet. TAGE listens only to witnesses who recognise the scene, and among those it believes the one who watched the most history — because that witness's guess is built on the most context. If nobody recognises the scene, an ever-present ground-floor witness (the base predictor) gives a rough PC-based hunch so we always have an answer. When the truth comes out, we nudge the chosen witness's confidence toward what really happened (but never past its limits — that's the saturating counter). If even our most-experienced witness got it wrong, we recruit a new witness with an even longer memory, because clearly we needed to look further back. And witnesses who never once made a difference get quietly retired to free up seats. That loop — recognise, trust the longest, correct, grow longer on failure — is the entire engine, and it climbs past 95% accuracy on real programs. Next stop: 5.3.11-Branch-target-bufers tells us where a taken branch jumps, and 5.4.2-Speculative-execution shows what all this guessing buys us.

Related builds: 5.3.9-Gshare-and-local-predictors, 7.2.5-Cache-coherence-and-branch-predictors.