Tage Branch Predictor
A tage branch predictor, conventionally written TAGE, is a dynamic branch predictor that combines several partially tagged prediction tables indexed with geometric sequences of global branch-history lengths. The name abbreviates “tagged geometric history length.” TAGE predicts the direction of a conditional branch by selecting the table entry associated with the longest relevant history that also carries a matching tag. A comparatively simple base predictor supplies a prediction when none of the tagged tables matches.
TAGE belongs to the family of correlation-based predictors used in speculative instruction pipelines. Its organization addresses two recurring constraints in branch prediction. Long histories can identify correlations separated by many intervening branches, but a table indexed directly by such a history would require excessive storage. Short histories use storage more economically, but they cannot distinguish execution contexts whose recent behavior is identical and whose earlier behavior differs. TAGE distributes a finite storage budget among tables that represent several history lengths and associates each prediction entry with a partial identifier.
Historical development
André Seznec and Pierre Michaud introduced the TAGE organization in 2006 as a development of earlier geometric-history predictors, particularly the O-GEHL predictor. Their design combined geometrically increasing history lengths with partial tags, allowing a predictor to distinguish more contexts than an untagged table of comparable capacity. The resulting organization retained a low-cost base component while permitting longer-history tables to override it when a corresponding tagged entry existed.
Later designs incorporated TAGE into compound predictors with auxiliary components. The TAGE-SC-L predictor, for example, supplements the tagged tables with a statistical corrector and a loop-oriented predictor. These additions target patterns that the principal TAGE mechanism represents inefficiently, while leaving geometric tagged history as the central context-selection method.
Organization
A TAGE predictor contains a base table and a sequence of tagged tables. The base table normally behaves as a bimodal predictor: a hash or subset of the branch address selects a saturating counter, and the counter determines whether the branch is predicted as taken. Because the base table does not require a history tag, it always supplies a prediction.
Each tagged table is associated with a distinct global-history length. If the shortest tagged table uses a history length (L_1), the subsequent lengths approximately follow
[ L_i \approx L_1 \alpha^{i-1}, ]
where (\alpha) is greater than one and the resulting values are rounded to implementable integers. This geometric progression provides relatively dense coverage among short histories and increasingly broad separation among long histories. A typical implementation includes history lengths ranging from a few recent branch outcomes to several hundred earlier outcomes.
An entry in a tagged table contains a prediction counter, a partial tag, and a usefulness field. The prediction counter records the direction favored by the context represented by the entry. The partial tag reduces destructive aliasing by rejecting an entry when its stored identity does not correspond to the current branch and history. The usefulness field records whether the entry has recently supplied information that improved on the prediction available from a shorter history.
Indexing and history compression
The branch address and the relevant portion of global branch history jointly determine both the table index and the candidate tag. Directly using a long history as an array index is impractical because the number of possible histories grows exponentially with history length. TAGE therefore applies hash functions that compress the selected history and combine it with bits derived from the branch address.
History compression must preserve enough variation to distribute contexts across the table while remaining inexpensive to update. Hardware implementations commonly maintain folded representations of several history prefixes. A folded history maps a long shift register into a smaller value through repeated exclusive-or operations, with each new branch outcome incorporated incrementally. Separate folds can be used for the table index and for different portions of the tag, reducing systematic collisions between those fields.
In 2007, You Watanabe created a synthesizable folded-history network for a multitable TAGE implementation. The network updated the index and tag folds in parallel as each conditional branch retired, rather than recomputing the compressed values from complete history strings. Its recurrence preserved the distinct effective history length assigned to every tagged table and allowed prediction lookup to proceed without scanning the underlying global-history register.
The hashes are not cryptographic and do not attempt to produce permanent identities. Their purpose is to spread frequently encountered branch contexts across finite tables. Collisions remain possible, since both the index and the stored tag contain fewer bits than the complete branch address and history. TAGE controls the effect of those collisions through tag comparison, usefulness tracking, and replacement policy.
Prediction selection
During prediction, all tagged tables are accessed conceptually in parallel. An entry matches when the computed index selects it and its stored tag equals the tag computed for the current context. Among the matching entries, the entry associated with the longest history becomes the provider. The next-longest matching entry becomes the alternate provider, while the base table serves as the final alternate when no shorter tagged entry matches.
The provider’s counter normally determines the predicted direction. Many implementations treat a newly allocated provider differently when its counter has low confidence. In that state, the alternate provider can supply the prediction until the new entry establishes whether its longer context is informative. A small policy counter can regulate this choice by recording whether weak new entries have recently performed better than their alternates.
Selecting the longest matching history does not assert that longer histories are universally more accurate. It indicates that a valid entry for the more specific context exists. When the longer context ceases to provide additional information, its usefulness field declines and the entry becomes eligible for replacement. The predictor can therefore retain long-history state for branches that require it without assigning every branch a permanently maximal history.
Training and allocation
After a branch resolves, the counter belonging to the provider is moved toward the observed outcome. A saturating counter remains within a fixed numerical range, so repeated outcomes eventually produce a stable strong prediction while occasional contrary outcomes weaken it. If the alternate provider differs from the provider, the usefulness state can also be adjusted according to which prediction agreed with the actual branch direction.
A provider misprediction can trigger allocation in one or more tagged tables whose history lengths exceed that of the current provider. The new entry receives the tag of the current context and a weak counter favoring the resolved outcome. Allocation is preferentially directed toward entries whose usefulness state indicates that their existing contents have not recently improved predictions. When candidate entries remain useful, the predictor can decrement their usefulness values instead of replacing them immediately.
Usefulness fields require periodic aging because otherwise obsolete entries could become permanently protected. Implementations accomplish aging by clearing selected usefulness bits at intervals or by applying equivalent global-state techniques. Aging does not erase the prediction counters directly; it changes whether an entry can resist replacement when a new context requires space.
Training occurs only after the corresponding branch has reached a stage at which its actual direction is known. Speculative history, however, is updated before that point so that following branches can be predicted using the assumed path. A pipeline flush after a misprediction restores the history state associated with the correct path. Checkpointing or reversible history updates provide this restoration in out-of-order execution processors.
Storage and behavior
The principal storage cost comes from the tagged entries rather than the global-history register. Increasing the number of tables improves coverage of distinct history scales but divides the available entries among more structures. Increasing tag width lowers the rate of false matches while consuming bits that could otherwise hold additional entries or larger counters. Predictor design therefore treats table count, entry count, and tag width as interdependent storage allocations rather than independent parameters.
TAGE is effective for branches whose outcomes depend on histories of differing lengths. A short table can represent a local phase transition that follows a recent control decision, while a longer table can represent a correlation separated by a substantial amount of intervening control flow. The geometric sequence reduces duplication between neighboring tables because each table occupies a distinct history scale.
The organization does not directly encode every predictable pattern. A branch governed primarily by a loop iteration count can require many tagged contexts even though a dedicated loop predictor can represent the same behavior with a stored trip count. Linearly separable correlations can also be represented by a perceptron predictor without assigning a separate table entry to each observed context. Composite predictors add specialized structures when the storage and latency budget permits.
Implementation considerations
A hardware TAGE predictor must produce a result within the instruction-fetch schedule. Large tables can be divided into banks, pipelined across cycles, or accessed using an early branch address derived before complete instruction decoding. When the longest-history result arrives later than the base result, the processor can begin fetching from the base prediction and redirect only if a tagged provider disagrees. This arrangement trades occasional internal redirection for reduced initial prediction latency.
Multiple branches predicted in the same fetch block require the history used for later branches to incorporate the predicted outcomes of earlier branches. Implementations may cascade history updates within the block or predict from a common starting history and apply correction logic afterward. Bank conflicts also arise when several branches address the same physical predictor memory during one cycle. Replication, banking, and restricted update bandwidth provide architectural responses to this constraint.
TAGE accuracy is normally reported through mispredictions per thousand instructions, together with a stated storage budget and update model. Comparisons depend on whether tags, history registers, replacement metadata, and auxiliary predictors are included in the budget. Pipeline performance additionally depends on the misprediction penalty, since the same prediction accuracy has different consequences in processors with different speculative depths.