Tournament and TAGE predictors

Overview

Modern wide-issue processors retire only a handful of instructions per cycle (typically 4–8 per cycle), yet keep hundreds of instructions in flight across many pipeline stages. Branch instructions create fundamental uncertainty about what to fetch next—and a single wrong guess can flush all that in-flight work. Tournament and TAGE (Tagged Geometric History Length) predictors represent the evolution from simple adaptive schemes to hybrid meta-predictors that combine multiple prediction strategies. Classic tournament (hybrid) predictors reach ~90–93% accuracy; high-end TAGE variants push beyond 95% on real workloads.

Think of it like having multiple weather forecasters—one excels at predicting rain, another at temperature. You track their accuracy and listen to whoever's been right lately for the current question.

Tournament Predictors: The Meta-Prediction Architecture

What Is a Tournament Predictor?

A tournament predictor (also called hybrid or meta-predictor) combines two or more component predictors using a selector (or choice predictor) that tracks which component has been most accurate recently.

Selector: A2-bit saturating counter per branch (or per set indexed schemes) that votes:

• 00, 01 → Use predictor 1
• 10, 11 → Use predictor 2
• Updated based on which predictor was correct

How Tournament Selection Works

For each branch at PC = 0x4000:

1. Both predictors make predictions:

   • Local predictor → T
   • Global predictor → NT

2. Selector reads its counter (say, selector[hash(PC)] = 01 → use local)

3. Fetch proceeds with local's prediction (T)

4. On resolution:

   • Actual outcome: T
   • Local was correct → increment selector toward local (01 → 01 stays)
   • Global was wrong → selector doesn't move toward global

The selector adapts: if global starts doing better, repeated correctness shifts the counter toward 10, 11.

Why saturating counters? Prevents oscillation—requires consistent evidence to switch, but adapts when behavior changes (e.g., entering a new loop).

Branch A: Local predictor learns the loop's T, T, .., NT pattern (strong on iteration count).

Branch B: Global predictor sees correlation—if many A's were T (high arr[i]), then B likely T (high sum).

Initially, selector might favor local for A. But B shows no local pattern—global wins for B, selector shifts. The processor ends up using local for A, global for B, achieving the best of both worlds.

Derivation: Why the Selector Works

Start from first principles of prediction error:

For a single predictor with accuracy $a_1$:

For two predictors with accuracies $a_1, a_2$:

An oracle selector (always picks the best) achieves this. A realistic selector with its own accuracy $a_s$ approximates it:

Why this is better: Even if $a_s =0.8$ (selector is 80% accurate at choosing), you get weighted benefit from both predictors, typically better than either alone.

For real workloads:

• Local: ~85% accurate
• Global: ~87% accurate
• Tournament: ~90–93% accurate (meta-learning exploits that different branches need different strategies)

TAGE: Tagged Geometric History Length

What Problem Does TAGE Solve?

Tournament predictors are limited by their fixed history lengths. Some branches need10 bits of history (nested loops), others need 50+ (complex corelated control flow). Using only one length wastes resources or underfits.

TAGE (Briz et al., 2006) uses multiple tables with geometrically increasing history lengths and tagged entries to match the right history length to each branch.

TAGE Architecture

Tagged Tables (T1, T2, .., Tn): Typically 4-6 tables, each indexed by:

where $L_i$ is the history length for table $i$ (e.g., $L_1=4, L_2=8, L_3=16, L_4=32$—geometric series).

Each entry contains:

• Tag: Partial PC + history hash (for collision detection)
• Prediction counter: 3-bit signed counter (−4 to +3, predict T if≥ 0)
• Useful bit: Tracks whether this entry has provided correct predictions

How TAGE Makes a Prediction

1. Compute all indices for $T_0, T_1, \ldots, T_n$ using PC and varying history lengths.

2. Check tags at each indexed entry. Find longest matching table (highest $i$ where tag matches).

3. Use that table's prediction:

   • If $T_3$ matches: use $T_3$'s counter
   • If only $T_1$ matches: use $T_1$'s counter
   • If none match: use $T_0$ (base predictor)

4. On resolution:

   • Update the provider component (the one that made the prediction)
   • If prediction was wrong, allocate a new entry in a longer-history table (give it a chance)
   • Update useful bits to track which tables are contributing

Why allocate longer? The current history length wasn't enough. Try a more specific pattern.

Useful bit: Incremented when this entry predicts correctly and the next-shorter table would have predicted incorrectly. Decremented periodically. Low-useful entries can be replaced (victim selection).

Early in execution:

• $T_0$ (base): Predicts weakly T (biased from other code)
• Misprediction → allocate in $T_1$ (4-bit history)

After a few iterations:

• $T_1$ learns the inner loop pattern (T, T, T, T, NT)
• Correct predictions → useful bit incremented

When outer loop changes:

• Outer loop iteration affects pattern (new i → different data values)
• $T_1$ starts mispredicting → allocate in $T_2$ (8-bit history)
• $T_2$ learns the two-level pattern (inner × outer)

Result: TAGE automatically discovers that this branch needs 8 bits of history, not 4, by trying progressively longer scales.

Derivation: Why Geometric History Lengths?

Consider the resource trade-off:

• Total entries: $N$ (fixed hardware budget)
• If using uniform lengths (all 16-bit), you have $N$ entries at one scale.
• If using geometric ($L_1=2, L_2=4, L_3=8, L_4=16, L_5=32$), distribute $N$ entries across 5 tables.

Coverage: Geometric ensures you can match any history length $L$ by picking the table with $L_i \leq L < L_{i+1}$. The relative precision loss is bounded:

where $r$ is the geometric ratio (typically $r=2$). With $r=2$, maximum relative error is 50%, but in practice, most branches have characteristic scales (loops are often powers of 2 in length).

Why not linear (4, 8, 12, 16)? Wastes entries on mid-range lengths. Branches either need very short or very long history—geometric spacing concentrates resources at extremes.

Tournament vs. TAGE: When to Use Each

Modern CPUs: Most use TAGE or TAGE variants (Intel Skylake onward, AMD Zen, ARM Neoverse). Tournament predictors were dominant in the 2000s (Alpha 21264, Pentium 4) but have been supplanted.

Why it feels right: The name "tournament" suggests a real-time competition where the best wins.

The fix: The selector uses past accuracy to predict future accuracy. It's a meta-predictor itself, with its own 2-bit state machine. During phase changes (e.g., entering a new function), the selector might still favor the wrong predictor for a few branches until it adapts.

Impact: Tournament accuracy≠ max(local, global) accuracy. It's typically better than either alone, but not perfect. Mispredictions still occur during selector adaptation.

Why it feels right: More information → better prediction, so $T_n$ (longest) should dominate.

The fix: Longer history ≠ better prediction if the branch doesn't have that much correlation. A random branch with no pattern benefits from the base predictor (simple bias), not from64 bits of uncorrelated history. TAGE uses tag matching to ensure the history is relevant—if the tag doesn't match, that entry isn't about this branch's pattern.

Impact: Forcing longest history causes aliasing (unrelated branches collide in high-history tables, polluting predictions). TAGE's allocation policy ensures you only use long history when needed.

A tournament predictor is like having two friends who are good at guessing: one watches yesterday, one watches the whole week. You keep score: whoever's been right more lately, you listen to them.

TAGE is even smarter: it keeps five guessers, each watching different time scales—1 day, 3 days, a week, a month, a season. When you ask "Will they play today?", TAGE checks all five and uses the most specific one that has seen this exact situation before (like, "Last time they were tired all week AND had a test, they didn't play").

So TAGE can handle simple patterns (just look at yesterday) and complex patterns (need the whole season's data) without wasting space on the wrong time scale.

Connections

• 5.3.8-Two-level-adaptive-predictors — TAGE extends two-level by using multiple history lengths
• 5.3.9-Gshare-and-local-predictors — Tournament combines gshare (global) with local
• 5.3.11-Branch-target-bufers — Predicted direction is useless without predicted target
• 5.4.2-Speculative-execution — Wrong predictions waste all speculative work
• 7.2.5-Cache-coherence-and-branch-predictors — Multi-core systems share branch history

For Tournament: "Two predictors duel, selector is the judge—judge uses past wins to pick the future winner."

#flashcards/hardware

What is the key innovation of a tournament predictor? :: It combines multiple component predictors (typically local + global) using a selector that tracks which has been more accurate recently, allowing the processor to use the best strategy for each branch type.

Concept Map

Hinglish (regional understanding)