Global History and the Gshare Index

The bimodal predictor indexes its table by the branch’s address alone, so it treats each branch as an independent source of behaviour. Compiled code is not like that. Whether a loop’s inner branch is taken is determined by an outer loop’s counter; whether an if is taken is often determined by a test a few instructions earlier; whether a branch after a call is taken depends on the callee’s return value. The outcomes of nearby branches carry information about each other, and a predictor that ignores that information leaves accuracy on the table. Global history predictors use the recent outcome stream as part of the index, which is a way of making the table’s state conditional on the program’s recent control flow rather than only on the branch’s own address.

The history register

A global history register (GHR) is a shift register of the last $h$ branch outcomes, one bit each, with the newest outcome shifted in at one end. Its width is the predictor’s correlation depth: a 12-bit GHR records the last 12 branches, which is enough to capture the correlation between nested loops and short dependent chains, and not enough to capture a pattern that depends on a 40-instruction-long computation.

The register is updated at resolution of each branch — or, in designs that update speculatively, at prediction time with undo on misprediction. The distinction matters: a speculatively updated GHR is ahead of the committed one, so the predictions issued on the wrong path were made from a history that will later be corrected. That is not a correctness problem as long as the repair restores the register, but it means the predictor’s internal state during speculation is not the architectural history.

The GHR is the cheap part: $h$ bits, a shift, and a mux. The expensive part is the table it indexes, because the number of distinct (branch, history) pairs is exponential in $h$. A table that could hold every combination for a 12-bit history and a 12-bit address would need $2^{24}$ entries. Real designs hold far fewer and let combinations share entries, which is the source of the interference problem described below.

Hashing the two inputs together

The naive two-level design gives each branch its own table indexed by history. That is the classic (m, n) scheme: $m$ bits of branch address select a history register, and the $n$-bit history indexes a table of counters. Its cost is a per-branch history register and a large table, and its accuracy depends on the branch having a stable correlation pattern with its own past.

Gshare takes the opposite approach: one shared table, one global history register, and an index formed by XORing the branch address with the history. With $k$-bit index, history, and address slices:

$$\text{index} = \text{PC}[k+1:2] \oplus \text{GHR}[k-1:0]$$

The XOR is the whole idea. A branch at address A with history H maps to a unique entry as long as the pair is unique, and the table’s capacity is shared across all branches rather than partitioned. The XOR spreads different history values for the same branch across different sets, so a branch with a strongly correlated pattern can use several entries — one per relevant history — instead of being stuck with one counter that averages the pattern away.

A worked example makes the mechanism concrete. Take a table of 256 entries (8-bit index), 8-bit history, and consider a branch at address 0x1A4:

def gshare_index(pc, ghr, bits=8):
    # drop the low two address bits: instructions are 4-byte aligned
    addr = (pc >> 2) & ((1 << bits) - 1)
    return addr ^ (ghr & ((1 << bits) - 1))

# history 0b00000000 -> index 0b01101001
# history 0b00000001 -> index 0b01101000  (adjacent set)
# history 0b10000000 -> index 0b11101001  (distant set)
print(gshare_index(0x1A4, 0b00000000))
print(gshare_index(0x1A4, 0b00000001))
print(gshare_index(0x1A4, 0b10000000))

The consequence of the XOR is that a branch’s counters are scattered across the table in a pattern determined by the history it saw. Collisions are governed by the XOR: two lookups share an entry only if addr1 ^ h1 == addr2 ^ h2. Because the history is mixed into the index, a single branch’s distinct history patterns no longer average into one counter, and two branches at different addresses do not collide merely because their address slices agree. The price is that the index is no longer a clean function of branch identity, so unrelated (branch, history) pairs can still contend. Capturing correlation at that price is what made gshare the standard baseline for predictor research in the 1990s.

What a history-indexed counter means

An entry in a gshare table is not “how often was this branch taken”. It is “how often was this branch taken when the last $h$ branches went like this”. The counter is therefore a conditional probability estimate, and it can be nearly always-taken for one history and nearly always-not-taken for another. A branch that is taken if and only if the previous branch was taken needs two entries, and gshare will learn both.

This also explains why the counter needs only two bits in the common case: for a fixed history value, the branch’s behaviour is usually deterministic, so the counter saturates quickly. Where the branch is genuinely random given the history, no amount of table state helps, and a wider counter merely increases the hysteresis.

The learning period is the cost. Each of the distinct history patterns a branch encounters must be observed enough times to train its counter. A branch inside a doubly nested loop sees one history pattern for most of its executions and a different one near the loop boundaries, so the interesting entries are exactly the ones that get the fewest observations. This is why predictors add loop-specific components and why the training problem, not the storage problem, dominates the accuracy of highly-tuned designs.

The interference problem

Gshare’s index is a hash, and hashes collide. Two costs follow.

Destructive aliasing. A branch’s entry can be overwritten by another branch (or another history value of the same branch) that maps to the same index. When that happens, the counter reflects a mix of two behaviours and predicts neither well. Because the table is small relative to the number of (branch, history) pairs in a real program, some interference is unavoidable; the design question is whether the hot branches are protected from the cold ones.

History-length sensitivity. A GHR that is too short misses long correlations; one that is too long includes bits that are irrelevant to the branch and therefore multiply the number of distinct index values the branch uses, spreading its training over many entries that each get few observations. The optimum differs by workload: integer code with nested loops favours longer history, floating-point code with long independent chains favours shorter. Published studies of gshare found that accuracy as a function of history length is fairly flat near the optimum and degrades on both sides, which is fortunate, since the optimum cannot be known in advance.

Both problems have the same structural answer: make the index less collision-prone and make the history length adaptive. The first leads to set-associative predictor tables and to tagged entries that detect a collision instead of silently averaging through it. The second leads to the multi-length history tables of TAGE. Between those two poles sits the tournament predictor, which keeps a history-based predictor and a bimodal one side by side and learns which to trust per branch.

Why history indexing is not free at fetch time

The GHR must be read, XORed with the address, and the table accessed all within the fetch cycle. The XOR is one gate delay; the table access is the same as any other small array. The real constraint is that the GHR’s value at the moment of prediction must correspond to the history that precedes the branch being fetched, and a fetch block may contain several branches. If the block contains two branches, the second branch’s prediction depends on the outcome of the first, which is not yet known.

Real designs handle this by predicting only the first branch in a fetch block, or by computing speculative intra-block history — assuming the predicted outcome of the first branch to form the history for the second. The latter requires either replication of the predictor for each position in the block or a serial chain of lookups, both of which cost area or latency. This is the fetch-block granularity problem again: a predictor that is accurate per branch can still be limited by how many branches the front end can process per cycle.

The baseline everyone measures against

Gshare’s importance is not that it is the best predictor; it is that it is the simplest predictor that captures correlation, and therefore the control against which later designs are compared. Any claim that a new structure improves prediction has to beat gshare at the same storage, because gshare’s cost is a table of two-bit counters and one XOR per lookup. That is a low bar to beat on accuracy and a high bar to beat on cost, which is exactly the tension that drives the designs in aliasing, tournaments, and predictor selection and TAGE.