How Do Tournament and TAGE Predictors Correlate History?

Tournament and TAGE branch predictors bridge global program execution patterns and individual branch behavior by combining multiple prediction mechanisms that index into different history lengths. While a Tournament predictor dynamically arbitrates between a dedicated local predictor and a global predictor for each branch, TAGE generalizes this concept using tagged tables indexed by geometric global history lengths alongside a base bimodal table. Both architectures recognize that some branches depend primarily on their own past outcomes, whereas others are governed by the path of recent branches leading up to them.

Why Branch Prediction Needs Both Global and Local Context

Modern pipelined processors rely on accurate branch prediction to keep instruction fetch units supplied without stalling on control hazards. A single branch instruction can behave differently depending on two distinct sources of correlation:

• Local history captures the recent outcomes of the same static branch instruction, which is effective for loop branches or branches that alternate in regular patterns.
• Global history captures the outcomes of the last \(k\) dynamic branches executed across the entire program, which is effective for correlated branches whose outcomes depend on prior conditional checks.

Relying solely on local history fails when a branch's direction is determined by an earlier if statement elsewhere in the code. Relying solely on global history fails when unrelated branches pollute the global history register (GHR) and alias away a branch's own repeating pattern.

How Tournament Predictors Arbitrate Between Local and Global

A Tournament branch predictor—famously implemented in the Alpha 21264—addresses this trade-off by running a local predictor and a global predictor in parallel and using a meta-predictor (or selector) to choose between them.

Architecture of a Tournament Predictor

1. Local Predictor: Uses a two-level structure. The branch's Program Counter (PC) indexes into a Local History Table (LHT) to retrieve the branch's recent \(m\)-bit outcome pattern. That pattern then indexes into a Local Pattern History Table (PHT) of saturating counters to produce a local prediction.
2. Global Predictor: Uses the \(k\)-bit Global History Register (GHR), often combined with the PC via XOR or concatenation, to index into a Global PHT of saturating counters.
3. Choice (Meta) Predictor: A table of 2-bit saturating counters, indexed by the PC (or PC combined with global history), tracks which of the two predictors has been more accurate for that branch.

Correlation Through Dynamic Selection

When a branch resolves, the Tournament predictor updates the local and global PHTs as usual, and updates the choice counter only when the two predictors disagree:

• If the global predictor was correct and the local predictor was wrong, the choice counter increments toward selecting global.
• If the local predictor was correct and the global predictor was wrong, the choice counter decrements toward selecting local.

In this way, the Tournament predictor correlates global history with local behavior by assigning each branch to whichever context best models it, rather than blending both contexts into a single hash.

How TAGE Predictors Correlate Multiple History Lengths

The TAGE (TAgged GEometric history length) predictor, introduced by Seznec and Michaud, moves beyond a binary choice between one local table and one global table. Instead, it uses a base predictor (\(T_0\)) paired with a series of tagged predictor components (\(T_1, T_2, \dots, T_M\)) that each use progressively longer global history lengths.

Geometric History Lengths

The history lengths \(L(i)\) for each tagged table \(T_i\) form a geometric series:

\[L(i) = \left\lfloor \alpha^{i-1} \cdot L(1) + 0.5 \right\rfloor\]

where \(L(1)\) is a short history length and \(\alpha > 1\) is a constant ratio. Short-history tables capture tight local-like correlations, while long-history tables capture deep, program-wide path correlations.

Tagged Lookup and Longest-Match Selection

Each tagged table \(T_i\) is indexed by a hash of the PC and the folded \(L(i)\)-bit global history, and stores a partial tag derived from another hash of the PC and history, a prediction counter, and a usefulness counter (\(u\)).

During a lookup:

1. All tables \(T_0\) through \(T_M\) are queried in parallel.
2. \(T_0\) is a tagless bimodal table indexed only by the PC, providing a default local-only prediction.
3. Among all tagged tables \(T_1 \dots T_M\) that produce a tag hit, the predictor selects the one with the longest history length (the provider component).
4. If no tagged table hits, the prediction falls back to \(T_0\).

Implicit Correlation of Local and Global Behavior

TAGE correlates local branch behavior with global history without needing a separate local history table. Because every table index and tag includes the PC, a branch's identity is always bound to its global history context. When a branch behaves purely according to its own local bias, \(T_0\) handles it. When a branch depends on a specific sequence of prior branches, a tagged table \(T_i\) allocates an entry for that \((\text{PC}, \text{GHR}[0..L(i)-1])\) pair. If an even longer global context resolves an ambiguity, a higher table \(T_j\) (\(j > i\)) allocates an entry and overrides \(T_i\) via longest-match priority.

Comparing Tournament and TAGE Correlation

By replacing a single global history length and a binary meta-predictor with tagged geometric history tables, TAGE achieves higher prediction accuracy across diverse workloads while naturally unifying local bias and global path correlation.