Geometric History Lengths in TAGE Predictors

The tournament predictor’s fixed history length is its structural limitation. A branch correlated with the last three branches and a branch correlated with the last forty need different history widths, and one register cannot be both. The obvious fix — several history registers of different lengths, each with its own table — runs into a new problem immediately: with several tables and no way to tell a real match from a collision, a long-history table will confidently predict from an entry that belongs to a different branch. TAGE is the design that makes the multi-length idea work, and its two essential contributions are a tag per entry and an ordering rule that prefers the longest match.

Why longer history is not monotonically better

Before the mechanism, the constraint. Accuracy as a function of history length is not a curve that rises to a plateau; it rises to a peak and then falls, and the peak is at a different place for different branches.

Consider a branch whose outcome equals the outcome of the branch ten instructions earlier. A history register of 8 bits does not include that outcome, so the branch appears unpredictable. A register of 12 bits includes it and the branch becomes nearly deterministic. Extend to 20 bits and the extra bits included are irrelevant to this branch: they take different values on different executions, so the branch now maps to many distinct table entries, each trained with a fraction of the observations. The predictor gets worse, not better, purely from adding information.

So a single fixed length is a compromise that is wrong in both directions simultaneously. What a predictor needs is per-branch selection of the history width, discovered at run time. TAGE approximates that by having many lengths available at once and choosing among them per branch, per prediction.

Tables with geometrically increasing history

The structure is a base predictor plus $M$ tagged components. The base is a plain bimodal table with no history, which guarantees that every branch has at least a mediocre prediction.

Component $i$ is indexed by a hash of the branch address and the low $L_i$ bits of the global history register, where the $L_i$ grow geometrically:

$$L_i \approx L_1 \cdot 2^{,i-1}$$

with $L_1$ a few bits and $M$ components reaching a few hundred bits of history in aggressive designs. Geometric growth is what makes the set cover a wide range with few tables: with a factor of two and five components starting at 5 bits, the lengths are 5, 10, 20, 40, 80 — a range that spans sixteenfold using five tables. Linear growth would need sixteen tables to reach the same maximum.

Each tagged entry holds a tag — a few bits derived from the full index inputs, so that a collision is detectable — a signed counter for the direction, and a small usefulness counter. The usefulness counter is the confidence measure that decides whether the entry’s prediction is trustworthy and whether the entry deserves to be replaced.

The base table has none of this. It is indexed by the address alone and holds a plain saturating counter, exactly as described in two-bit saturating counters.

The prediction rule

The prediction proceeds in three steps.

1. Look up all components in parallel, using the same branch address and the corresponding history slice for each. This is a parallel access, not a serial chain, so the latency does not grow with $M$; the area does.
2. Among the components whose tag matches, take the one with the longest history. Call it the provider. A tag match is what distinguishes a real entry from an aliased one.
3. If the provider’s counter is confident enough — above a threshold set by the design — use its prediction. Otherwise use the alternate prediction, which is the prediction of the next-longest matching component, or the base if no other component matched.

The alternate-prediction rule is the subtle part. When the provider is weakly confident, its prediction may be worse than a shorter-history prediction that has seen more training. Falling back to the next-longest match rather than to the base keeps the fallback relevant to the branch, and it is the mechanism that makes weak entries harmless.

A provider with a high-magnitude counter is trusted regardless of what shorter components say. That is the opposite of the tournament’s chooser, which learns a per-branch preference; TAGE encodes the preference in the entry’s own confidence, which adapts per history value rather than per branch.

The update rule and entry allocation

The update is where TAGE earns its complexity, and it is best described as a policy for spending entries.

When the prediction is correct, the provider’s counter is incremented toward the outcome, and its usefulness counter is incremented, up to a maximum. When the prediction is wrong, the provider’s counter is decremented, and its usefulness is decremented.

If the prediction was wrong and no component with a longer history than the provider matched, an entry is allocated in one of the longer-history components. The choice among them is a heuristic: prefer a component with no matching entry, and prefer a component whose entry has low usefulness, so that weakly useful entries are evicted first. The new entry’s counter is initialised weakly toward the correct outcome, and its usefulness starts at zero.

The effect is that long-history tables fill with entries only for branches that actually need them. A branch that the short tables already predict correctly never causes an allocation in a long table, because allocations happen only on misprediction. This is the property that keeps TAGE’s long tables from being polluted by the majority of branches, which are predictable with short history.

Two further details matter in practice. First, on a misprediction the alternate predictor — not the provider — is also updated, so that the fallback path does not go stale. Second, usefulness decays: some designs decrement all usefulness counters periodically or on a misprediction elsewhere, so that an entry that was once valuable but no longer is can be evicted. Without decay, the long tables fill with entries that were useful once and are now dead, and the predictor loses the ability to adapt to a phase change.

Tags, and what they cost

The tag is the mechanism that makes a long-history table usable. Without it, a component indexed by 40 bits of history into a table of a few thousand entries has an enormous collision rate: the index space is vastly larger than the table, so most lookups hit an entry belonging to a different (branch, history) pair, and the predictor would confidently use it. With a tag, a collision is detected and the lookup falls through to a shorter component.

The cost is storage per entry and a comparator per entry. A tag of 8 to 12 bits roughly doubles an entry’s size compared with a bare two-bit counter, and the comparator is a small XOR-and-reduce. For a table of a few thousand entries per component, the tag array dominates the area, which is why TAGE’s component count and entry counts are chosen together: more components means more tag storage for the same total prediction bits.

The tag also has to be derived from the same inputs as the index. If the index is hash(PC, history) and the tag is a different slice of the same hash, the pair is effectively a wider index split into “which set” and “which entry within the set”. That is exactly the structure of a set-associative cache, which is the right way to think about a TAGE component: it is a cache of predictions keyed by (branch, history), with the tag as the key check and the counter as the value.

Why TAGE displaced the alternatives

The design’s advantage is that it handles the heterogeneous distribution of real branch behaviour without a chooser and without a fixed history length. Short-history components capture tight correlations; long-history components capture the few branches with long-range dependence, and the allocation policy keeps the long tables small and relevant. The base table guarantees a floor.

The cost is the number of parallel table accesses per prediction, which is $M+1$ reads of small arrays. Each read is a hash computation and a tag comparison, and all of them happen in the fetch cycle. This is why TAGE implementations in real cores use modest component counts and modest table sizes per component, and why the predictor is often the largest single structure in the front end.

The other cost is the tuning surface: the history length series, the confidence threshold, the allocation policy, and the usefulness decay rate all interact, and their best values depend on the workload. Evaluations of the design show that accuracy holds up across a range of these choices, but is not insensitive to them, and a badly chosen series can lose to a tournament predictor of similar size.

Where the design meets its limits

Three limits are worth naming.

Very long histories are hard to index. A history of 200 bits cannot be used as an index slice without a strong hash, and the hash must be cheap enough to compute in the fetch cycle. Designs compress long history into a folded value, which is a hash of the full register, and accept that the fold can produce identical indices for different histories.

Short, phase-changing patterns still cost. A branch whose pattern changes between phases trains long-history entries that are wrong in the new phase, and the usefulness decay must be fast enough to evict them without being so fast that legitimate entries are discarded.

Speculative history must be repaired. TAGE’s index depends on the global history register, so a mispredicted branch corrupts the index for every prediction issued after it on the wrong path. The repair is the checkpointed history described in misprediction recovery, and it must restore the register exactly, because a one-bit error changes the index of every subsequent lookup.

The line from bimodal counters through gshare and tournaments to TAGE is a line of increasing specificity about what to condition on. Each step adds state that distinguishes cases the previous design conflated: history distinguishes correlated from uncorrelated branches, tags distinguish real matches from collisions, and length distinguishes short correlations from long ones. What none of them addresses is what happens to the machine’s other state when the prediction is wrong, and that residual is the part of speculation the squash cannot reach.