Aliasing, Tournament Predictors, and Per-Branch Selection

A history-based predictor is not uniformly better than a simple one. It is better on branches with correlation and worse on branches whose history is noise, because the noise scatters their counters across many table entries and each entry gets too few observations. The two populations coexist in every real binary, often within the same function. The response is to build both predictors, run them in parallel, and learn per branch which one to trust. This is a tournament predictor, and the interesting part is not the two predictors but the third structure that decides between them.

The cost of a wrong index

Every predictor that hashes into a table accepts interference. Two forms of it exist and they are worth distinguishing, because they motivate different fixes.

Capacity aliasing happens when two branches map to the same entry. The entry’s counter then reflects a mixture, and neither branch is predicted well. Adding ways or a tag turns silent mixing into a detectable miss, which is an improvement: a miss with a fallback prediction is better than a confident wrong answer.

History-induced aliasing happens when one branch’s own history values map to the same entry. A branch whose behaviour depends on a 10-bit history but whose counter table has 8-bit indexing will see two different histories collide, and the counter will be trained on both. The fix is not more table but better history selection — using the history bits that actually correlate with the outcome.

The two failure modes trade against table size in opposite directions, and a single predictor cannot optimise for both across all branches. That asymmetry is what a tournament exploits.

Two components, one decision

A tournament predictor consists of a base predictor and an alternative predictor, plus a chooser.

The base predictor is usually a bimodal table: cheap, per-address, no history. Its weakness is correlated branches; its strength is that a branch with a stable bias gets a dedicated counter that is never disturbed by history.

The alternative is a history-indexed predictor, gshare or a two-level scheme. Its weakness is branches whose outcome is not predictable from global history — for those, its index is effectively random and its counters are noise. Its strength is exactly the correlated cases.

The chooser is a table of small counters indexed by branch address, holding the current preference. On each resolution, the chooser’s counter is incremented if the history-based predictor was right and the base was wrong, decremented in the opposite case, and left alone if both agreed. The counter’s high bit is the choice. A two-bit counter is enough; a three-bit counter with hysteresis reduces oscillation when the two predictors alternate in correctness.

The Alpha 21264’s published predictor is the canonical instance of this arrangement: a two-level local-history predictor as the base, a global-history table as the alternative, and a choice table whose counter selects per branch. The chooser’s index is the branch address, so a branch that behaves differently in different phases will have its preference trained toward whichever predictor was right in the most recent phase, which is the desired behaviour.

What the chooser itself can get wrong

The chooser is a predictor, and it has a failure mode that the two main predictors do not: it can be wrong about which of two correct answers to prefer. The cost is bounded — a wrong choice is only wrong when the two predictors disagree, which is a minority of resolutions — but it is not zero.

Three cases matter.

Both predictors wrong. The chooser’s update rule leaves it unchanged, which is correct; there is no information about which to prefer. A design that incremented the chooser whenever the history predictor was right would learn from a case where it was right by luck.

One predictor systematically better in a phase. The chooser tracks it with its own counter, but the counter’s hysteresis delays the switch by a few resolutions. With a two-bit counter, a change in the better predictor takes two consistent observations to flip the choice, which costs two mispredictions per phase change per branch. Three bits triples the delay. This is the same accuracy-versus-adaptivity trade as the direction counters themselves, applied one level up.

Chooser aliasing. The chooser’s table is indexed by address and is smaller than the main tables, so it collides more. Two branches sharing a chooser entry means the preference learned for one applies to the other. The mitigation is to make the chooser’s index include some history or to give it more ways, both of which cost area.

A simulation of the selection mechanism

The chooser logic is small enough to state completely. This version uses a signed two-bit counter per address and a bimodal base plus a gshare alternative:

class Tournament:
    def __init__(self, bits=10, hist_bits=8):
        self.mask = (1 << bits) - 1
        self.hist_mask = (1 << hist_bits) - 1
        self.base = [2] * (1 << bits)      # bimodal, 2 bits per entry
        self.alt = [2] * (1 << bits)       # gshare, 2 bits per entry
        self.choice = [1] * (1 << bits)    # 0 = base, 3 = alt
        self.ghr = 0
        self.hist_bits = hist_bits

    def _idx(self, pc):
        return (pc >> 2) & self.mask

    def predict(self, pc):
        i = self._idx(pc)
        alt_i = ((pc >> 2) ^ self.ghr) & self.mask
        p_base = self.base[i] >= 2
        p_alt = self.alt[alt_i] >= 2
        self._last = (i, alt_i, p_base, p_alt)
        return p_alt if self.choice[i] >= 2 else p_base

    def update(self, pc, taken):
        i, alt_i, p_base, p_alt = self._last
        # step both predictors toward the outcome
        self.base[i] += 1 if taken else -1
        self.base[i] = min(3, max(0, self.base[i]))
        self.alt[alt_i] += 1 if taken else -1
        self.alt[alt_i] = min(3, max(0, self.alt[alt_i]))
        # reward the component that was right, using the pre-update prediction
        if p_alt != p_base:
            self.choice[i] += 1 if (p_alt == taken) else -1
            self.choice[i] = min(3, max(0, self.choice[i]))
        self.ghr = ((self.ghr << 1) | int(taken)) & self.hist_mask

Two details in this code matter more than the structure. First, the choice counter is updated only when the two components disagree, which is what keeps the chooser from being trained by redundant agreement. Second, the base and alternative are both updated on every resolution regardless of which was selected. That is deliberate: if only the selected predictor were trained, the other would go stale and the chooser could never switch back. Keeping both trained costs an extra write port per cycle, which is a real hardware cost and one of the reasons tournament predictors are larger than their accuracy alone suggests.

Storage accounting

The accounting is worth doing because tournament predictors are often compared on equal-storage terms.

A tournament with two 1K-entry tables of two-bit counters and a 1K-entry choice table uses 2 Kbit for each main table plus 2 Kbit for the chooser: 6 Kbit total. A single gshare table with 3K entries and two-bit counters uses 6 Kbit and has three times the entries. Which wins depends entirely on how many branches are correlated.

Published comparisons from the 1990s generally found that a tournament beat either component alone at equal storage across the workloads measured, with the margin varying widely. That result is not a law: on a workload with uniformly correlated branches, the alternative predictor alone uses the storage better, because the chooser’s bits are spent on decisions that are always the same.

Where the chooser meets the fetch cycle

A tournament lookup is three table reads in parallel — base, alternative, and chooser — and only then a mux. Adding the branch target buffer makes it four. All four must complete in the cycle that fetches the block containing the branch, so the tables are small and simple by necessity: direct-mapped, no more than a couple of ways, with counters packed into wide words so that one read yields many entries.

That packing has a consequence worth naming. When a table is read a word at a time and only one entry of the word is used, the other entries in the word are speculative reads of neighbouring indices, which is harmless. But when the table is written, writing a single two-bit counter means a read-modify-write of the enclosing word, or a byte-enable write. Designs choose the latter and pay for the byte-enable path in the SRAM’s ports. This is one reason predictor update bandwidth, not storage, is often the binding constraint: a wide machine retiring four instructions per cycle can produce up to four branch outcomes in one cycle, and each needs a counter update in two tables plus a chooser update. The standard answer is to widen the storage granularity so that a single write can carry several updates, which in turn constrains how counters are laid out relative to the index.

The structural lesson that leads to TAGE

The tournament’s weakness is that the alternative predictor uses one fixed history length. A branch correlated with the last 4 branches and a branch correlated with the last 16 want different lengths, and a single register cannot serve both: too short misses the long correlation, too long dilutes the short one.

The tournament also spends its chooser bits on a binary decision. A design that had, instead, several predictors with different history lengths and a mechanism for preferring the longest one that has a useful entry would avoid the fixed choice. That is exactly the structure of TAGE (geometric history lengths in TAGE predictors), which replaces the tournament’s two-way choice with an ordered set of tables and a “longest match wins” rule. The chooser’s role survives there in a different form: each table entry carries a confidence counter that says whether its prediction is worth using, which is the same information the tournament’s chooser holds, distributed per entry rather than per branch.

The lineage is worth stating plainly because it explains why tournament predictors are still in shipping cores: the base bimodal table is cheap and never catastrophically wrong, and the chooser handles the heterogeneous distribution of real code without needing a history length that suits every branch. The cost is the third table and the second write port, and the benefit is that the chooser adapts across workloads whose branch structure differs by an order of magnitude.