Branches that talk to each other: correlating and two-level predictors

Two branches, one variable: where the per-branch table goes blind

Recall from lesson 5: a branch history table (BHT) is indexed by the low-order PC bits, has no tags, and holds a tiny state machine per entry — one bit or two (Strongly/Weakly Taken, Weakly/Strongly Not Taken) — whose state is the prediction; the branch target buffer (BTB) is the tagged cache that supplies where to fetch when the prediction says Taken.

Every BHT entry looks at one thing, that branch's own past. The notes open §2.6.4 (p. 65) with the simplest case where that is not enough:

if (x > 0)   // Branch A
   ...
if (x > 0)   // Branch B
   ...

Branch B behaves like Branch A because both test the same condition, and "a normal predictor doesn't know this. It treats A and B independently" (p. 65). Hennessy and Patterson sharpen the example with a variable that changes between the tests — in RISC-V in the book, here in the papers' mnemonics, with d in R1 and R0 as the zero register:

      BNE   R1, R0, L1      ; b1: taken if d != 0
      ADDUI R1, R0, 1       ;     d = 1
L1:   SUBI  R3, R1, 1       ;     R3 = d - 1
      BNE   R3, R0, L2      ; b2: taken if d != 1
      ...
L2:

Three cases. d = 0: b1 not taken, d becomes 1, b2 not taken. d = 1: b1 taken, b2 not taken. d = 2: both taken. So if b1 is not taken, b2 is certainly not taken — a correlation no per-branch counter can see. Let d alternate 2, 0, 2, 0 and give each branch a 1-bit entry initialised Not Taken; the prediction is the bit before the branch, the bit after is the outcome.

Eight predictions, eight misses: the bit always holds the previous outcome and the pattern flips every time. What decides b2 is not what b2 did last time but what b1 did a moment ago.

The right panel is the notes' (1,1) correlating predictor (p. 67): a 1-bit global history stores the last branch outcome and selects one of two 1-bit tables (T1 if the last branch was taken, T2 if not); the low-order PC bits index the selected table. Each branch now has two entries, written below as "if last NT / if last T", all initialised NT; the history starts at NT.

Two misses, both on cold entries, then a perfect record. The column "GH before b1" is b2's previous outcome, which encodes the previous value of d: b1 is predicted from the last b2, b2 from the current b1 — the two branches predict each other.

A per-branch counter answers "what did this branch do last time?"; a correlating predictor answers "what did this branch do last time it was in this situation?"

The (m, n) predictor: a history register that picks the table

Generalise the right panel of Fig. 1 and you get the notes' general case (p. 65): in an (m, n) correlating predictor the outcomes of the last m branches select one of \(2^m\) prediction tables of n-bit entries. The four steps, in the order the hardware takes them:

1. Track the last m branches: their outcomes, in program order, whichever branches they were, are shifted into an m-bit Global History Register (GHR), Taken = 1, Not Taken = 0.
2. Select a table: the GHR value picks one of the \(2^m\) tables.
3. Index it with k low-order bits of the branch PC.
4. Predict with the n-bit entry — the last outcome (n = 1) or the four-state machine of lesson 5 (n = 2); after the branch resolves, update the entry and shift the outcome into the GHR.

In memory (p. 66): \(2^m\) tables of \(2^k\) entries of n bits. The plain 2-bit BHT of lesson 5 is the (0, 2) predictor of this family — no history bits, one table. And the tables, selected by the GHR and indexed by the PC, are one table of \(2^{m+k}\) entries indexed by the concatenation of the GHR and the PC bits.

The shift convention, and the (2,2) walkthrough done right

An exercise is only as right as its shift convention. The notes' (p. 69), for m = 2: 00 both Not Taken; 01 last Taken, penultimate Not Taken; 10 last Not Taken, penultimate Taken; 11 both Taken — shift left, newest outcome on the right. The opposite convention exists elsewhere, so state yours at the top of an exercise.

Now the notes' (2,2) example (pp. 69–70): branches A, B and C in program order, outcomes Taken, Not Taken, Taken; four tables of 2-bit counters, one per GHR value; GHR starting at 00. Each branch is predicted from the table the GHR selects at that moment, the entry is updated, the outcome shifted in — Table 3. For C the notes assume Weakly Taken in table 10: Taken is predicted and is right; the entry moves to Strongly Taken, the GHR becomes 01 again.

Each (branch, context) pair has its own counter, which converges where a single counter would flip-flop; and because the history also holds the branch's own previous outcomes, b1 was fixed in Table 2 although it comes first. Pan, So and Rahmeh, who published the scheme in 1992, priced it at "up to 11% additional accuracy at the extra hardware cost of one shift register".

Same budget, two designs

History bits are not free: tables multiply as \(2^m\), each context must be trained, and distant outcomes are mostly noise. The honest comparison is at equal storage, as Hennessy and Patterson make it on SPEC89.

1. A (2,2) predictor with 1024 entries per table: \(2^m \cdot n \cdot 2^k = 4 \cdot 2 \cdot 1024\).

   \[ \text{storage} = 8192 \text{ bits} = 1 \text{ KB} \]

2. A plain 2-bit BHT — the (0,2) predictor — with the same 8192 bits holds 8192 / 2 entries.

   \[ \text{entries} = 4096 \]

3. Their SPEC89 measurement (background from the textbook): the (2,2) with 1024 entries per table mispredicts less than the 4096-entry 2-bit BHT, and even than one with unlimited entries (eqntott: about 6 % against 18 %). Unlimited entries remove aliasing, not the lack of context.

4. The address of an entry in the single-table view: GHR = 10, PC bits = 1011, k = 4.

   \[ \text{index} = 10\,\Vert\,1011 = 101011_2 = 43 \]

Two levels: a history register and a pattern table — global or local

Yeh and Patt gave the family its general shape in 1991; the notes present it as two-level adaptive branch prediction (p. 71): a history-tracking component and a pattern-based prediction component, with the exam vocabulary of both:

• A Branch History Register (BHR): a shift register of the most recent outcomes — "k-bit" in the notes' letter; this lesson writes h for the history length and keeps k for the PC bits. Global — one register for all branches, the GHR above — or local, "separate register for each branch": in hardware, a table of history registers indexed by the PC.
• A Pattern History Table (PHT): a table of 2-bit saturating counters, indexed with the content of the BHR.

The process (p. 71): index the PHT with the BHR, read the counter, predict Taken if it is in a Taken state; afterwards update the counter and shift the outcome in. The (m, n) predictor is one member — global history, table by history, row by PC; the variants differ only in whose history (global or local) and how the PHT is indexed (history alone, history ‖ PC, history ⊕ PC).

What local history buys: the loop exit

The loop of the June 2025 paper, whose 2-bit table lesson 5 filled in, runs five iterations: the BNE goes T T T T NT, and again on the next execution.

LOOP: LD    F0, 0(R1)
      FADD  F2, F0, F0
      SD    F2, 0(R1)
      ADDUI R1, R1, 4
      BNE   R1, R2, LOOP      ; R1 = 0, R2 = 20: T T T T NT

A 2-bit counter mispredicts the exit every time: it holds a bias, and no counter can express "after four taken comes a not-taken". Yet the exit comes at the same place in every pass. A local history of 4 bits makes it visible: before the fifth iteration the branch's own history is 1111, before the first 1110, and each context gets its own counter. The smallest example that fits in a table: a 3-iteration loop, pattern T T NT, 2 bits of local history (older, newer), counters initialised Weakly Taken:

Two warm-up misses while the counter of context "T,T" is dragged from Weakly Taken to Weakly Not Taken, then nothing: three contexts, three converged counters, the pattern memorised. A plain 2-bit counter on the same stream, started Strongly Taken, misses every third execution for ever — 4 of 12. The rule:

With h ≥ N − 1 every position in the pattern has its own history, so after warm-up the exit is predicted like the others. A global register can do the same only if the loop body holds no other branch; otherwise their outcomes dilute the pattern — the reason tournament designs such as the Alpha 21264 of 1998 keep both kinds. Yeh and Patt's 1991 figure: "97 percent accuracy on nine of the ten SPEC benchmarks, compared to less than 93 percent for other schemes".

Time to race them. The arena feeds one stream to eight predictors, from the two static rules and the BHTs of lesson 5 to the (1,1), the (2,2), gshare and a local two-level predictor with h history bits. Counters start Strongly Not Taken (the June 2025 initialisation), 1-bit entries Not Taken, histories at 0; a toggle switches the 2-bit entries from the saturating counter (pp. 69, 71) to the four-state figure of p. 59.

gshare and aliasing: let every branch reach every entry

Two named members of the family (p. 72). The Global Adaptive predictor (GA) indexes the PHT with the global history alone: one BHR shared by all branches captures their correlation. gshare (the name is McFarling's, 1993) is, in the notes' words, "designed to improve the indexing of the PHT and reduce aliasing (i.e., different branches mapping to the same PHT entry)": the index is the XOR of the BHR with the low-order PC bits of the branch. The notes' Table 7:

By hand, h = 4: PC bits 1011 under history 0110 give 1011 ⊕ 0110 = 1101, entry 13 of 16; a second branch with PC bits 0101 under the same history lands on 0011, entry 3 — separated.

Why XOR rather than concatenation, when both fit h index bits? Concatenation must split them, m for the history and h − m for the PC: each branch reaches only \(2^m\) entries, its own partition, and branches whose low h − m PC bits agree collide in every context. With XOR all h PC bits and all h history bits take part: a branch reaches all \(2^h\) entries as the history varies, and under the same history two branches never share one. XOR is still many-to-one (\(2^{2h}\) pairs onto \(2^h\) entries), so aliasing is reduced, not removed.

Aliasing done right: harmless with tags, harmful without

The notes end with a deepening on aliasing (pp. 72–73): "two or more distinct entities become indistinguishable to the hardware or software". The idea is right, two of its three examples are wrong, and the difference is the point: an index collision happens in every structure indexed by a few address bits, and what it costs depends on whether there is a tag.

Branch-predictor aliasing is the untagged case: "different branches map to the same entry in a branch predictor table (e.g., BHT, PHT)" and pollute each other's prediction (p. 73) — harmless for correctness, since a prediction is a guess the pipeline checks, costly for accuracy. Caches and BTBs carry a tag because their payload must never be wrong. Two red pens on the notes' other examples:

The warm-up puzzle, resolved

Where did the information come from, if b2's own history was worthless? From b1, a few instructions earlier — and, for b1, from the previous b2: the global history register carries the last outcome, and in that program the last outcome is the value of d. A per-branch counter cannot see other branches; a correlating predictor sees them through one shift register — its whole advantage, and with the tables each context must train, its whole cost.

What the papers ask: counting accesses, initialisation and size

Three exam habits, all in the May 2025 midterm (notes pp. 538–541; quiz texts are the paper's, solutions the note author's, recomputed here).

Habit 1: count the executions of the branch, not the iterations

Quiz 5 gives a top-tested loop and a 1-entry 1-bit BHT initialised Taken, and asks how many BHT accesses and mispredictions, "assuming only the branch instruction accesses the BHT":

      ADDI R1, R0, 0
      ADDI R2, R0, 100
LOOP: BEQ  R1, R2, DONE
      ADD  R5, R5, R4
      ADDI R1, R1, 1
      J    LOOP
DONE:

The BEQ executes for R1 = 0, 1, …, 100 — the exit test is the 101st execution; the unconditional J does not touch the BHT. Outcomes: Not Taken 100 times, then Taken.

Two mispredictions — one artificial (initialisation), one real (exit) — in 101 accesses; the bottom-tested loop of June 2025 executes its BNE five times for five iterations. The rule: branch at the bottom, N executions; test at the top, N + 1.

Habit 2: initialisation and size both change the count

Quiz 4 — "the number of mispredictions depends on the initialization and the size of the Branch History Table", true or false, motivate: true, for two reasons the motivation must name. Initialisation sets the start-up misses: a 2-bit entry started Strongly Not Taken misses twice before predicting a loop branch Taken (the 60 % of June 2025), started Strongly Taken it misses none. Size sets aliasing: no tags, so a small table lets unrelated branches overwrite each other's state (Fig. 4, right).

Habit 3: from accuracy to CPI

Quiz 6, third statement: "The introduction of dynamic branch predictors improves the CPI metric." True, by the formula the notes give on p. 541 — copy it onto your A4 sheet, since the course's example sheet has no branch formula at all.

A better predictor changes only \(a\); the penalty belongs to the pipeline — and that is why the percentage points matter: at \(f_b = 0.2\) the step from 90 % to 97 % accuracy is worth 0.014 CPI with \(P = 1\) and 0.28 with \(P = 20\).

The bridge to speculation

The June 2026 open question pairs "dynamic branch prediction" with "speculative execution". A prediction is only useful if the processor acts on it before the branch resolves — fetching, issuing, even executing the instructions after it. They must not touch registers or memory until the branch is known: their results wait in the reorder buffer; on a misprediction every entry younger than the branch is flushed, nothing architectural is undone, the PC is set right and fetch resumes. Lessons 5 and 6 decide how often that happens; lesson 17 builds the buffer.