Decoded: TAGE, the branch predictor that keeps several histories at once

Before you start

Open only what you need; each one is a short refresher.

What a branch predictor guesses, and why it matters

A conditional branch is an instruction that may or may not jump. A pipelined processor fetches the next instructions before the branch resolves, so it has to guess the direction. A wrong guess (a misprediction) throws away the work fetched down the wrong path, typically 10 to 20 cycles on a modern core. Predictors are compared by MPKI, mispredictions per thousand instructions: lower is better.

Two-bit saturating counters

The simplest learned predictor is a table of small counters. A counter counts up on a taken outcome and down on a not-taken one, saturating at the ends; its sign (or top bit) is the prediction. The two-bit version needs two surprises in a row before it flips, which stops a single odd outcome from undoing a stable pattern. TAGE's tagged entries use a 3-bit signed counter in the same spirit: the sign predicts, and a value of 0 or −1 is called weak.

Global history and gshare

The global history is a shift register of the most recent branch outcomes, one bit per branch. Branches correlate with what happened just before them, so indexing a table with (program counter XOR history), the gshare predictor, captures patterns a per-address counter cannot. The question TAGE answers is how long that history should be: some branches need 5 bits of context, others need hundreds.

Partial tags

A tag stored next to a table entry records which branch (and history) the entry was trained on. Checking the tag on lookup turns a silent collision (two branches sharing one counter) into a detectable miss. TAGE stores short, partial tags of about 8 to 12 bits: cheap, and good enough to make false matches rare.

XOR folding

Exclusive-or (XOR) of two bits is 1 when they differ, and XOR-ing the same bit twice cancels. To squeeze a long bit string into a few bits, cut it into chunks and XOR the chunks together: every input bit still influences the result, and because XOR is reversible, a bit can later be removed by XOR-ing it in again.

1. The idea: several history lengths that grow geometrically (paper §3.1)

Earlier predictors had to pick one history length for everything. The observation behind TAGE, inherited from Seznec's O-GEHL predictor, is that different branches want very different amounts of context, and that the useful lengths are spread out roughly exponentially: short histories matter to many branches, very long ones to a few. TAGE therefore keeps a base predictor T0, a plain program-counter-indexed table of two-bit counters, plus M tagged tables T1 … TM, each indexed with a hash of the program counter and the most recent L(i) history bits, where

L(i) = (int)(αⁱ⁻¹ · L(1) + 0.5)

so the lengths form a geometric series. The paper's own example is α = 2 and L(1) = 2 for eight components, giving {0, 2, 4, 8, 16, 32, 64, 128}, and it adds that the exact formula does not matter but the general form does: most storage goes to short histories, a little to very long ones. The name is the recipe: TAgged GEometric history length. Each tagged entry holds three things (§3.2): a signed prediction counter ctr (3 bits; the sign is the prediction), a partial tag, and an unsigned useful counter u (2 bits) that the update rules use to decide which entries may be replaced. The history itself (§2.3) is a shift register of outcomes that also records non-conditional branches as taken bits, kept alongside a short path history of one address bit per branch, so that two different paths with the same outcomes do not look identical. Move the sliders to see how the series behaves.

2. Prediction: the longest history that recognises the branch wins (paper §3.2.1)

All tables are read at once. T0 always answers; a tagged table answers only if its stored tag matches the tag computed from the current program counter and history. The prediction comes from the hitting tagged component with the longest history, or from T0 when nothing hits. The paper fixes two words that the rest of the design hangs on: the provider is the component that ultimately gives the prediction, and the alternate prediction (altpred) is what would have been predicted had the provider missed. Its own example: tag hits on T2 and T4 and misses on T1 and T3 make T4 the provider and T2 the source of altpred; with no hit at all, altpred is the default prediction. The figure starts from that example and walks the lookup one step at a time.

3. Newly allocated entries: when the alternate prediction is the better bet (paper §3.2.4)

A freshly allocated entry delivers the prediction the very next time its (history, program counter) pair appears, and on some programs those entries mispredict at a very high rate. The paper found that for such programs it is better to follow altpred while the provider is still new, that whether this helps is a property of the whole program, and that one shared 4-bit counter can learn it dynamically. No extra bookkeeping marks an entry as new: the paper treats an entry as newly allocated when its useful counter is zero and its prediction counter is weak (0 or −1), and reports that this approximation performs the same as recording the fact explicitly. The figure replays ten lookups and shows the shared counter earning, and losing, its trust.

4. Update: the useful counter decides who stays (paper §3.2.2 and §3.2.3)

The paper attributes the weak results of the earlier PPM-like tagged predictor to its update policy, and spends its care here. After the outcome is known: on a correct prediction only the provider's prediction counter moves toward the outcome. The useful counter of the provider is touched only when altpred differed from the final prediction, that is when the provider actually changed the answer: u goes up if the provider was right and down if it was wrong. u doubles as an age: periodically the column of most-significant bits of every u is cleared, and next time the column of least-significant bits, every 256K branches in the paper, so an entry that stops being useful drifts back toward replaceable. On a misprediction the provider's counter is updated and then, if the provider T_i is not the longest-history table, at most one new entry is allocated in some T_k with k > i. The rules: (A) if a candidate with u = 0 exists, allocate there, otherwise decrement every candidate's u and allocate nothing, so a persistent misprediction eventually frees a slot; (B) when two candidates are free, the shorter-history one is chosen with twice the probability of the longer, which breaks ping-pong fights between branches competing for one entry (a linear-feedback register suffices); (C) the new entry starts at weak-correct with u = 0, so until it helps it is the natural next victim. The paper's rationale (§3.2.3) is that one (branch, history) pair should leave the smallest possible footprint, and that u approximates a least-recently-useful policy. Pick a scenario and step through it.

5. Implementation: indices, tags, and folding a long history (paper §2.3 and §3.8)

Each tagged table needs an index (which entry to read) and a tag (how to confirm it is the right one), both computed from the program counter and the history. They must not be the same function, or every collision in the index would also be a tag match and the tag would detect nothing. The paper leaves the hash functions open (§3.8.1: even single-stage three-input XOR functions cost only about one percent of accuracy) and notes that the tag computation can overlap the table read, so the hash may be elaborate without slowing the prediction. The practical problem is the long history: a table with 2¹⁰ entries needs a 10-bit index, but the last table may look at hundreds of history bits, and recomputing a full XOR fold on every branch would be far too slow. The standard answer, used in the reference TAGE predictors that followed the paper, is a folded history register per table and per use (index and tag), updated incrementally: when a new outcome enters the history, rotate the folded register by one, XOR the incoming bit in at position 0, and XOR the outgoing bit (the one that just left the L-bit window) out at position L mod W, where W is the fold width. That is three operations whatever L is. The figure draws the specification on the left (the L-bit window stacked in W-bit rows, one XOR per column) and the register update on the right, with an arrow for every bit, and shows that at every step the two agree, including the tempting off-by-one that puts the outgoing bit at the wrong column.

6. What the paper measured (paper §3.4)

The paper's central result (§3.4.1) is that at an equal number of tables TAGE beats O-GEHL, the best previous geometric-history predictor, at every storage budget, by about 0.2 mispredictions per thousand instructions: for eight-component predictors at 64 Kbits, 2.61 misp/KI against 2.83; at 1 Mbit, 2.05 against 2.27; and a 128-Kbit TAGE matches a 512-Kbit O-GEHL (2.36 against 2.34). A five-component TAGE still beats the eight-component O-GEHL, going beyond eight components gives no significant return, and the gain is traced to the update policy (§3.4.2), not to tuning. The chart below draws only the numbers the paper states.

What the paper showed (paper §7)

The paper's own conclusion is that predictors must exploit several history lengths at once, and that for a geometric series of lengths, partial tags are a more storage-effective way to combine them than the adder trees of O-GEHL: at an equal number of tables TAGE is more accurate with less hardware complexity (no dynamic history-length fitting, a shorter global history), and the same principle yields ITTAGE, an indirect-branch target predictor (§5). Three ideas carry it. A geometric series of history lengths covers both the branches that need five bits of context and the ones that need hundreds, with a handful of tables. Partial tags turn table collisions into detectable misses, so the longest history that actually recognises a branch can be trusted over shorter ones. And a tiny useful counter, with graceful aging, decides which entries have earned their place, so a misprediction costs at most one new entry. Later championship predictors, including Seznec's L-TAGE and the TAGE-SC-L family, are TAGE with components bolted on; the core described here is unchanged.

Sources and credits

Paper — André Seznec and Pierre Michaud. A case for (partially) TAgged GEometric history length branch prediction. Journal of Instruction-Level Parallelism, vol. 8, 2006. jilp.org (PDF)
Companion paper — André Seznec. The L-TAGE branch predictor. Journal of Instruction-Level Parallelism, vol. 9, 2007. Its section 2 restates the TAGE rules; the lesson names it where it adds a refinement. jilp.org (PDF)
Figures — All figures on this page are original drawings written for this lesson from the paper's text, with illustrative values where the paper gives none. Nothing is reproduced from the paper's figures.