Tournament and TAGE predictors: Exercises — Hardware deep dive

These problems build from recognising the parts of a hybrid predictor up to designing one. Do each on paper before opening the solution. Everything you need was built in the parent note; where a term first appears here we re-anchor it so you never meet a symbol cold.

Two objects reappear throughout, so let's pin them down once. Figure s01 draws both side by side: the selector on the left (which predictor to trust) and the TAGE counter on the right (taken or not, and how sure). Refer back to it whenever a counter value appears.

Definition The two counters you will keep touching

Selector (choice) counter — a 2-bit saturating counter (left half of figure s01). "2-bit" means it holds a number $0, 1, 2, 3$ . "Saturating" means it sticks at the ends: $3 + 1$ stays $3$ , $0 - 1$ stays $0$ (a normal counter would wrap $3 \to 0$ ). It answers one question: which of my two component predictors do I trust right now? Throughout this page predictor 1 = the local predictor (per-branch history) and predictor 2 = the global predictor (shared global history) — this pairing never changes. By the parent's rule, ${00, 01}$ (i.e. values $0, 1$ , the blue cells) → predictor 1 (local), ${10, 11}$ (values $2, 3$ , the yellow cells) → predictor 2 (global).

TAGE prediction counter — a 3-bit signed counter running $- 4, - 3, \dots, + 3$ (right half of figure s01). "Signed" means it carries a $\pm$ sign. It answers taken or not-taken, and how sure?: predict Taken if the value is $\geq 0$ (green cells), Not-Taken if $< 0$ (red cells). Its magnitude is confidence.

Level 1 — Recognition

Problem 1.1 (L1)

A tournament predictor's selector holds the value $2$ (binary $10$ ). Which component predictor does it choose, and why?

Recall Solution 1.1

The parent's mapping (and the colours in figure s01): values ${0, 1}$ → predictor 1 (local), values ${2, 3}$ → predictor 2 (global). $2 \in {2, 3}$ , so the selector picks predictor 2 (the global predictor). Why: the top bit of the 2-bit counter is the decision. $2 = 1 0_{2}$ , top bit $= 1$ → predictor 2. The bottom bit is just "how strongly."

Problem 1.2 (L1)

In TAGE, a prediction counter reads $- 1$ . Taken or Not-Taken?

Recall Solution 1.2

Rule: predict Taken iff counter $\geq 0$ . Here $- 1 < 0$ , so predict Not-Taken. The value $- 1$ also tells us confidence is low (it's one step from flipping to $0$ = weakly Taken).

Problem 1.3 (L1)

TAGE has a base table $T_{0}$ and tagged tables $T_{1}, T_{2}, T_{3}$ with history lengths $L_{1} = 4, L_{2} = 8, L_{3} = 16$ bits. On a lookup, tags match in $T_{1}$ and $T_{3}$ but not $T_{2}$ . Which table provides the prediction?

Recall Solution 1.3

TAGE always uses the longest matching history (most specific). Matches are $T_{1}$ ( $L = 4$ ) and $T_{3}$ ( $L = 16$ ). Longest is == $T_{3}$ ==. A gap at $T_{2}$ is fine — TAGE does not require a contiguous chain of matches, only the single longest hit.

Level 2 — Application

Throughout this level, remember the base table $T_{0}$ has history length $L_{0} = 0$ — it is indexed by PC alone, uses no branch history, and always exists as a fallback. The tagged tables $T_{1}, T_{2}, T_{3}$ carry $L_{1} = 4, L_{2} = 8, L_{3} = 16$ bits, matching Problem 1.3.

Problem 2.1 (L2)

A selector currently holds $1$ . On this branch: predictor 1 (local) is correct, predictor 2 (global) is wrong. Apply the parent's update rule. What is the new selector value, and does the chosen predictor change?

Recall Solution 2.1

Update rule (parent): $selector_{new} = ⎩ ⎨ ⎧ max (0, sel - 1) min (3, sel + 1) sel pred 1 correct AND pred 2 wrong pred 2 correct AND pred 1 wrong otherwise$ Here pred 1 right, pred 2 wrong → first case: $max (0, 1 - 1) = 0$ . Choice before: $1 \in {0, 1}$ → predictor 1. Choice after: $0 \in {0, 1}$ → predictor 1. No change — but we moved deeper into the predictor-1 region (more confident).

Problem 2.2 (L2)

Same selector at $1$ , but this time both predictors are correct. New value?

Recall Solution 2.2

Both correct → third case: selector unchanged = $1$ . Why the design does this: if both agree and are right, there's no evidence for preferring one over the other, so we don't move. The selector only learns from disagreements.

Problem 2.3 (L2)

A branch runs a repeating stream where predictor 1 is right and predictor 2 wrong on every branch. The selector starts at $2$ . Trace it over 3 branches.

Recall Solution 2.3

Every step is case 1: $max (0, sel - 1)$ .

Branch 1: $2 \to 1$
Branch 2: $1 \to 0$
Branch 3: $0 \to 0$ (saturates)

Final = == $0$ ==. The chosen predictor flips from predictor 2 (at $2$ ) to predictor 1 (at $1$ ) after just one branch, then keeps sinking toward maximum confidence in predictor 1.

Problem 2.4 (L2)

In TAGE with base $T_{0} (L_{0} = 0)$ and tagged tables $T_{1} (4), T_{2} (8), T_{3} (16)$ , table $T_{2}$ (the provider) mispredicts. Where does TAGE try to allocate a new entry, and why not a shorter table?

Recall Solution 2.4

Rule: on misprediction by provider $T_{k}$ , allocate in some $T_{m}$ with $m > k$ . Provider is $T_{2}$ , so the only longer table available is == $T_{3}$ == ( $L = 16$ ). Why not shorter? $T_{2}$ 's 8 bits of history were insufficient to distinguish this case — shorter history is strictly less specific, so it would fail too. A longer history can separate patterns $T_{2}$ conflated. If $T_{3}$ has a free (low-useful) entry, TAGE allocates there; if $T_{3}$ is full of useful entries, no allocation happens this time (TAGE waits rather than evict a proven entry).

Level 3 — Analysis

Problem 3.1 (L3)

Two component predictors have accuracies $a_{1} = 0.85$ (local) and $a_{2} = 0.87$ (global). The selector chooses correctly with probability $a_{s} = 0.80$ . First derive the tournament error model from scratch, then plug in the numbers. Is the tournament better than either predictor alone?

Recall Solution 3.1

Deriving the model. On any branch the selector does one of two things: it points at the right predictor for that branch, or the wrong one. Let $a_{s}$ = probability it picks the better one.

With probability $a_{s}$ the selector nails the better choice, so our error equals the smaller of the two error rates, $min (1 - a_{1}, 1 - a_{2})$ .
With probability $1 - a_{s}$ the selector mis-chooses and we're stuck with the larger error, $max (1 - a_{1}, 1 - a_{2})$ .

A probability-weighted average of these two outcomes gives exactly $Err_{tour} \approx (1 - a_{s}) \cdot max (1 - a_{1}, 1 - a_{2}) + a_{s} \cdot min (1 - a_{1}, 1 - a_{2}) .$ So the two terms are not arbitrary: $min$ is the reward for choosing well, $max$ is the penalty for choosing badly, each weighted by how often that happens. (An oracle with $a_{s} = 1$ collapses this to pure $min$ — the best possible.)

Plugging in. Errors: $1 - a_{1} = 0.15$ , $1 - a_{2} = 0.13$ . So $max = 0.15$ , $min = 0.13$ . $Err_{tour} \approx 0.20 \cdot 0.15 + 0.80 \cdot 0.13 = 0.030 + 0.104 = 0.134$ Best single predictor error $= 0.13$ (global). Tournament error $= 0.134$ is worse than the global-alone error here! Why: the selector is only 80% good and the two predictors are close in skill (0.85 vs 0.87). A weak selector wastes the tiny gap. Tournaments win when different branches favour different predictors (so the effective per-branch $min$ is much lower than either global average) — the single-number model above understates that structural benefit. See Problem 3.2.

Problem 3.2 (L3)

Now model the realistic case. Suppose half the branches are "local-friendly" (local 95%, global 70%) and half are "global-friendly" (local 70%, global 95%). A perfect (oracle) selector picks the best per branch. What accuracy does the oracle tournament reach, and how does it compare to using local-only or global-only across all branches?

Recall Solution 3.2

Local-only accuracy $= \frac{1}{2} (0.95) + \frac{1}{2} (0.70) = 0.825$ . Global-only accuracy $= \frac{1}{2} (0.70) + \frac{1}{2} (0.95) = 0.825$ . Oracle tournament: on each half it takes the better predictor $= 0.95$ , so $= \frac{1}{2} (0.95) + \frac{1}{2} (0.95) = 0.95$ . Insight: neither single predictor beats $82.5%$ , yet the oracle hits $95%$ — a $+ 12.5$ point jump. This is why tournaments exist: they exploit that branches split into populations with different needs, something a single average-accuracy number hides.

Problem 3.3 (L3)

TAGE tables use geometric history lengths $L_{i} = L_{1} \cdot r^{i - 1}$ . Given $L_{1} = 2$ and $L_{5} = 32$ with 5 tables, find the common ratio $r$ and list all five lengths.

Recall Solution 3.3

Geometric: $L_{5} = L_{1} r^{4}$ , so $32 = 2 r^{4} \Rightarrow r^{4} = 16 \Rightarrow r = 2$ . Lengths: $L_{1} = 2, L_{2} = 4, L_{3} = 8, L_{4} = 16, L_{5} = 32$ — exactly the ladder drawn in figure s02. Why geometric, not linear (2,4,6,8,10)? History-need is roughly logarithmic — a handful of branches need very long history. Doubling covers the huge range $2 \to 32$ with only 5 tables; a linear ladder would need 16 tables to reach 32 in steps of 2, wasting hardware on lengths nobody uses.

Figure s02 makes the resource argument visual: each bar is a table, its length is its history depth, and the "×2" between rungs is why five short bars span from $2$ to $32$ .

Level 4 — Synthesis

Problem 4.1 (L4)

A TAGE useful bit is incremented when the entry predicts correctly and the next-shorter matching table would have predicted incorrectly. Suppose entry $E$ in $T_{3}$ predicts Taken (correct), and the entry in $T_{2}$ that also matched would have predicted Not-Taken (incorrect). What happens to $E$ 's useful bit, and what does this mean strategically?

Recall Solution 4.1

Both conditions hold: $E$ correct and shorter table wrong → useful bit is incremented. Meaning: $E$ is earning its keep. It exists only because the longer history captured something the shorter one got wrong. A high useful bit protects $E$ from eviction; if it were $0$ , $E$ would be a candidate victim when a new allocation needs space. This is TAGE's way of asking each long-history entry: "are you actually adding information the cheaper table lacks?"

Problem 4.2 (L4)

Design trace. A branch inside a doubly-nested loop needs 8 bits of history to predict well, but TAGE currently only has an entry in $T_{1}$ ( $L = 4$ ). Walk the sequence of events (mispredict → allocate → learn) that leads TAGE to the correct table. Assume tables $T_{1} (4), T_{2} (8), T_{3} (16)$ .

Recall Solution 4.2

Now: $T_{1}$ is the longest match, so it provides. With only 4 bits it conflates two different outer-loop contexts → it mispredicts.
Allocate: provider is $T_{1}$ , so TAGE allocates in a longer table, $m > 1$ → try $T_{2}$ ( $L = 8$ ). New entry gets a fresh 3-bit counter, useful bit $0$ .
Learn: next visits, $T_{2}$ 's 8-bit index now separates the two contexts. Its counter trains toward the correct direction; each correct-while- $T_{1}$ -wrong sets its useful bit.
Steady state: $T_{2}$ becomes the longest match and the provider; $T_{1}$ 's stale entry ages out. TAGE has discovered the branch needs 8 bits — nobody told it; the mispredict-then-lengthen loop found it.

Problem 4.3 (L4)

Combine both ideas. In a tournament predictor whose two components are themselves a short-history and a long-history predictor, the selector partly duplicates TAGE's longest-match logic. Give one concrete advantage TAGE has over this 2-component tournament.

Recall Solution 4.3

A 2-component tournament offers exactly two history lengths and a coin-flip selector between them. TAGE offers many lengths (4–6 tables) and, crucially, chooses the length deterministically by tag match rather than by a trained selector that can be wrong. Advantages: (1) finer granularity — a branch needing 8 bits isn't forced to a coarse 4-or-32 choice; (2) no selector misprediction penalty — the longest tag match is unambiguous, whereas a selector counter can point the wrong way for several branches after a phase change; (3) per-entry usefulness tracking lets TAGE reclaim dead history cheaply. That's why high-end TAGE exceeds tournament accuracy ( $> 95%$ vs $\sim 90 - 93%$ ).

Level 5 — Mastery

Problem 5.1 (L5)

Full pipeline reasoning. A processor fetches while a branch is unresolved (this is speculative execution). It runs at 4 GHz, retires 4 instructions/cycle, and keeps 192 instructions in flight. A misprediction discards all in-flight work and refills. Two predictors are offered: Tournament at $92%$ accuracy, TAGE at $96%$ . If branches are $20%$ of instructions, compute the misprediction rate per instruction for each, and the ratio of wasted-work between them.

Recall Solution 5.1

Fraction of instructions that are branches $= 0.20$ . Mispredict rate per branch: Tournament $= 1 - 0.92 = 0.08$ ; TAGE $= 1 - 0.96 = 0.04$ . Misprediction rate per instruction $= 0.20 \times (branch miss rate)$ :

Tournament: $0.20 \times 0.08 = 0.016$ (1.6 mispredicts per 100 instructions).
TAGE: $0.20 \times 0.04 = 0.008$ (0.8 per 100).

Each mispredict flushes up to 192 in-flight instructions, so wasted work is proportional to the mispredict count. The ratio is $0.016/0.008 = 2$ : the tournament predictor triggers twice as many flushes, so it throws away roughly twice as much speculative work per instruction as TAGE. Concretely, per 1000 instructions the tournament wastes about $16 \times 192 \approx 3072$ instruction-slots of work versus $8 \times 192 \approx 1536$ for TAGE. This is why the extra transistors for TAGE pay off — halving the flush rate roughly doubles useful throughput on branchy code. (The refilled front-end feeds from the branch target buffer, which supplies where to fetch once whether is predicted.)

Problem 5.2 (L5)

Corner cases. For each degenerate input, state what the predictor does and why it's safe: (a) TAGE lookup where no tagged table matches. (b) Selector at exactly the boundary — value $1$ , and predictor 1 keeps being wrong while predictor 2 is right, three branches in a row. (c) A TAGE prediction counter at its extreme $+ 3$ that then mispredicts.

Recall Solution 5.2

(a) No tag match: fall back to the base predictor $T_{0}$ (PC-indexed 2-bit counter, history length $L_{0} = 0$ ). $T_{0}$ always exists and always answers — TAGE is never undefined. This is the "cold branch" / capacity-miss safety net. (b) Boundary crossing: value $1$ chooses predictor 1. Each branch is case 2 ( $min (3, sel + 1)$ ): $1 \to 2 \to 3 \to 3$ (saturates). The choice flips to predictor 2 the instant we hit $2$ (after the first branch), then hardens. Saturation at $3$ stops runaway. (c) Extreme counter mispredicts: $+ 3$ means "strongly Taken" but actual was Not-Taken. Being signed & saturating, it steps toward the truth: $+ 3 \to + 2$ (still predicts Taken — one wrong outcome shouldn't flip a strongly-trained entry). It takes several Not-Takens ( $+ 3 \to + 2 \to + 1 \to 0 \to - 1$ ) to flip the prediction. This hysteresis is deliberate: it ignores one-off noise, only flipping under sustained new behaviour.

Recall Self-test checklist

Can you now, from memory, do each of these? ::: (1) split a 2-bit selector into choice+strength; (2) apply the 3-case selector update; (3) pick TAGE's longest-matching provider and know the $T_{0}$ fallback; (4) explain allocate-longer-on-miss and the useful bit; (5) compute geometric history lengths; (6) turn accuracy into per-instruction mispredict rate and wasted work.

Related builds: 5.3.9-Gshare-and-local-predictors (the components inside the tournament), 5.3.8-Two-level-adaptive-predictors (where global history registers come from), 7.2.5-Cache-coherence-and-branch-predictors (multicore interactions).