Learning from the past: 1-bit and 2-bit history tables, and the BTB

Hardware that learns at run time

Lesson 4 left the branch problem half solved. A static rule — always not taken, always taken, backward taken and forward not — is fixed before the program runs, so it cannot tell a loop that runs a million times from an if that flips with the data. In the five-stage pipeline of this course the branch outcome and its target are computed in ID, so every wrong guess costs one cycle: the wrong-path instruction becomes a NOP and fetch restarts at the right address.

The notes state the key assumption plainly (p. 54): "if a branch behaved a certain way in the past, it's likely to behave the same way again". It is temporal locality applied to control flow. The hardware that exploits it is two tables, both consulted in the Instruction Fetch stage:

• the Branch Outcome Predictor answers whether — Taken (T) or Not Taken (NT) — from the run-time history of this branch, or of other branches too. In this chapter it is a Branch History Table (BHT);
• the Branch Target Buffer (BTB) answers where: it returns the Predicted Target Address (PTA), the address the processor will fetch from if the branch is predicted taken. It is "useful only when BOP predicts Taken; irrelevant if Not Taken" (p. 54), because the not-taken successor is simply PC + 4.

A fetch then works in three steps (p. 54): the outcome predictor says T or NT; if T, the BTB supplies the PTA; the next instruction is fetched from the PTA or from PC + 4. Notice when: at the end of IF, before the instruction is decoded. Both tables are indexed with the PC of the instruction being fetched — the hardware does not yet know that it is a branch. Keep that in mind: it is why one of the two tables needs tags and the other does not.

The notes list the four cases of a right or wrong guess (p. 55); with the branch resolved in ID a wrong guess always costs the same one cycle:

Look at the symmetry of that table. A dynamic predictor does not change what a misprediction costs — the pipeline fixes that: one cycle here, fifteen to twenty in a deep out-of-order core (Agner Fog's measurements on real Intel and AMD cores; background, not in the notes). It changes how often you pay. In the formula sheet's "CPI = 1 + stall cycles per instruction" the branch term reads as follows (lesson 4 wrote the same thing as \(1 + f_b \cdot \text{penalty} \cdot p_{\text{mis}}\)):

Two predictors, two stakes. With one instruction in five a branch (\(f_b = 0.2\)) and \(P = 1\), a predictor that is right 80 % of the time adds \(0.2 \times 0.2 \times 1 = 0.04\) to the CPI; one that is right 90 % adds \(0.02\). Make the penalty 15 cycles and the same two numbers become \(0.60\) and \(0.30\) — a \(1.6\times\) against a \(1.3\times\) slowdown on a base CPI of 1. That is why the industry kept inventing predictors long after the first one worked.

The predictor decides how often you pay for a branch; the pipeline decides how much.

One bit per branch: remember the last outcome

The simplest learning machine remembers one thing per branch: what it did last time.

Two phrases of p. 56 are worth keeping verbatim for an open question: the BHT is "a cache-like structure that maps branch addresses to prediction states", and its history is implicit — "rather than storing an explicit sequence of past outcomes, each entry implicitly encodes the recent behavior of the branch through its FSM state". Explicit history registers come in the next lesson; here the whole past of a branch is compressed into one or two bits.

With one bit the machine has two states. The bit is the last outcome: if it says T, predict Taken; if NT, predict Not Taken. After the branch resolves, a correct prediction leaves the bit alone and a wrong one flips it — which is the same as writing the actual outcome into the bit.

Indexing: low-order bits of the PC, and no tags

Which entry belongs to which branch? The notes (p. 57): "use k lower bits (right side) of the branch's address as the index", which gives \(2^k\) entries; and, in bold, "No tags: any branch with the same low-order bits shares the entry (can cause interference)". One practical detail: instructions are four bytes long and aligned, so the lowest two address bits are always 00 and a real table takes its \(k\) bits just above them; the exam phrase "low-order bits" is fine.

Why is a table without tags acceptable? Because the worst a wrong entry can do is a wrong prediction, which the pipeline catches when the branch resolves: correctness is never at stake, only accuracy — and a tag would cost more bits than the one or two it protects. Two branches whose addresses agree in the \(k\) index bits overwrite each other's state: the conflict problem (p. 57), called branch predictor aliasing in the deepening on the next lesson's pages. The partial cures (p. 58) are the obvious ones: a bigger table, so that fewer branches collide, and hashing the address bits to spread out branches that share low-order bits.

Example 5 of the notes: two misses on a loop

Now the puzzle of the hook, on the loop the exam papers use. The 10 June 2025 paper writes it with ADDI.U $R1, $R0, 0 and ADDI.D $F2, $F0, $F0; the 2026 paper drops the dollar signs, and so does this notebook:

INIT:  ADDUI R1, R0, 0
       ADDUI R2, R0, 40      ; R2 = 20 in the June 2025 paper
LOOP:  LD    F0, 0(R1)
       FADD  F2, F0, F0
       SD    F2, 0(R1)
       ADDUI R1, R1, 4
       BNE   R1, R2, LOOP

With R2 = 40 the BNE is executed ten times: taken nine times and not taken at the exit — the pattern the notes write as T T T T T T T T T NT (p. 57). Suppose the loop has been run before, so the entry still holds the NT of the previous exit. Walk the ten executions:

Two misses, and both have a reason. At the exit the bit still says T, because the branch was taken nine times in a row; the NT is mispredicted and flips the bit. At the next entry the bit says NT, because that is what the branch did last — the T is mispredicted and flips it back. "With 100% of 10 iterations, the BHT only catches 8 out of 10 iterations, the accuracy is 80%" (p. 57). A one-off anomaly costs two misses: the surprise itself, and its echo one execution later, when the predictor has just learned the anomaly and the old behaviour resumes. A one-bit predictor is always exactly one step behind. That is half of the puzzle.

The notes name two shortcomings (p. 57): the bit flips after a single misprediction, unstable on exactly the loops it should excel at, and the conflicts above. A bigger table does nothing for the loop exit: that miss is not interference, it is the inability of one bit to represent "nine times T, then NT".

Two bits: tolerate one surprise

The cure is a predictor that does not change its mind after one surprise. The notes call the 1-bit behaviour flip-flopping: "1 misprediction is enough to change the prediction", two misses per loop, "exiting the loop (NT mispredicted as T)" and "re-entering the loop (T mispredicted as NT)" (p. 59). The fix is a second bit that records not the last outcome but the predictor's confidence.

The rule of motion: an outcome that agrees with the prediction pushes the state toward the strong end; an outcome that contradicts it moves the state toward the other side. From a strong state it lands in the weak state of the same direction — the prediction survives one anomaly. From a weak state it crosses the line and the prediction flips; how far it crosses is where the two drawings of this machine differ. The notes' figure (p. 59) is reproduced below; the two dashed arcs are the alternative described right after it.

Look closely at the two vertical arrows of the notes' figure: from WT a Not Taken jumps straight to SNT, and from WNT a Taken jumps straight to ST. That is the machine of Hennessy & Patterson's figure, the course's reference book. A pure saturating counter — count up on Taken, down on Not Taken, stop at 3 and at 0 — would instead go WT → WNT and WNT → WT, the dashed arcs. On every loop pattern of this course the two machines give identical tables; they differ only when the outcome alternates while the machine sits in a weak state:

Neither machine learns the alternation — the saturating counter is always one step behind, the notes' machine at least settles on NT and gets every other outcome right. Both are "2-bit predictors". For the exam: write the state names, which are unambiguous, reproduce the figure you were shown in class, and if a pattern alternates say which machine you use.

Effect on the loop: one miss instead of two

Back to the ten-iteration loop, second run, the entry left in WT by the previous exit (p. 60):

"Exit NT causes 1 misprediction, but FSM moves from Strongly Taken to Weakly Taken. So the prediction remains Taken" (p. 60). At the next entry the branch is taken, the prediction is Taken, and the state returns to ST. "Only 1 misprediction per loop, improving accuracy to 90% (from 80%)." The weak state absorbed the exit without forgetting the bias.

Why two bits and not four? The studies Hennessy & Patterson report show that 2-bit counters get almost all the benefit of longer ones, and a longer counter is slower to follow a real change of behaviour — the balance between "prediction stability" and "adaptability" of p. 60. A bias of nine to one is as much as a counter can ever learn.

The exam table: 10 June 2025, Question 5

The only official exercise on these pages is a quiz worth 3 points. The loop is the one above with R2 = 20, so R1 takes 4, 8, 12, 16, 20 at the BNE: five executions, outcomes T T T T NT. The twist: a "single-entry 2-bit Branch History Table initialized in the state Strongly Not-Taken" — the loop has never run, and the entry starts as far from Taken as it can. The paper's table has three rows and one column per iteration, with the first column filled in:

Three misses in five executions: a misprediction rate of 3/5 = 60 %, and the state left after the last update is ST → Weakly Taken. Three sanity checks save you from the distractors (60, 90, 99, 100, 80 %): 100 % and 99 % are impossible, because any counter that has seen two Taken in a row predicts the third right; 90 % is not a whole number of misses out of five (read as an accuracy, it is the notes' ten-iteration loop); 80 % would be four misses, and an entry started in SNT already predicts right at the third execution — read as an accuracy, 80 % is 1 miss in 5, the answer of someone who counted the exit and forgot that the two warm-up misses count. In the third column the notes' figure gives Strongly Taken instead of Weakly Taken (WNT → ST on a Taken); the prediction is Taken either way, and so is the rest of the table.

One thing no counter can do, whatever its width: predict a pattern. The exit of a counted loop is perfectly predictable — after nine Taken comes a Not Taken, every time — and so is a branch that alternates T NT T NT; both defeat every counter, because a counter stores a bias, not a sequence. Capturing the sequence needs explicit history: lesson 6.

Where to? The branch target buffer

Suppose the BHT is perfect. In IF the processor knows the BNE will be taken. Where does it fetch from? The target is PC plus the offset encoded in the instruction, and in our pipeline that sum is computed in ID — one cycle too late. The notes' deepening says it in one sentence (p. 63): "even if we can predict that the branch will be taken, we still don't know where to fetch from". The fetch unit must "stall instruction fetch, or fetch sequentially and later flush": one bubble on every taken branch, even when the direction was predicted correctly.

The structure is that of a direct-mapped cache (p. 61). The branch address is split into a tag and an index; the index selects one entry; the stored tag is compared with the address tag, and only an equal tag is a hit — the tags "ensure the indexed entry really belongs to the current branch". Each entry holds the tag and the PTA, "often combined with T/NT bits from a Branch History Table (1-bit or 2-bit)" (Figure 17 of the notes), so one lookup answers both questions. Only taken branches are stored, and an entry is written when a taken branch resolves and its target is known (p. 64): the first execution of every branch is a cold miss, as in any cache.

The notes summarise the behaviour in their Table 4 (p. 62). The cost column is the one you add yourself, for the course pipeline:

On a hit with a Taken prediction "the next PC is immediately set to the target address, in the same cycle" (p. 64): a correctly predicted taken branch now costs nothing. On a miss "it's as if there's no BTB for that branch at all" (p. 64): fetch defaults to PC + 4, ID computes the real target, a taken branch costs its usual cycle — and the entry is allocated, so the next execution hits. "Clearly, the best option is to have a BTB with a certain rate of misses rather than no BTB at all." The two advantages the notes list (p. 62) are the words for an open question: it "eliminates delay from calculating the branch target address manually" and "enables speculative instruction fetch from correct target, improving pipeline efficiency".

Why the BTB has tags and the BHT has none

Here the "indexed before decode" remark pays off. A BTB hit means "the instruction at this address is a taken branch, and here is where it goes" — and the fetch unit acts on it at once. Without tags, any instruction whose low-order address bits match a stored branch would hit, and the fetch of an ordinary FMUL would be redirected into the middle of a loop: a wrong-path fetch that must be detected and undone. With tags a miss safely means "treat this as not a branch". The BHT can live without tags because its one or two bits are only used once the instruction is known to be a branch, and a wrong bit costs accuracy, never correctness.

The BHT predicts whether and may be wrong; the BTB predicts where and must not redirect a non-branch — so the BTB carries tags.

What a BTB is worth, in cycles and in bits

Hennessy & Patterson's textbook example gives the expected penalty per branch when a BTB is present. Call \(p_{hit}\) the hit rate, \(p_{ok}\) the accuracy of the prediction on a hit and \(p_{taken}\) the fraction of taken branches. A branch costs \(P\) cycles in two situations only:

1. A branch costs \(P\) cycles exactly when fetch went the wrong way. With a BTB there are two ways for that to happen; a miss on a not-taken branch is not one of them, because PC + 4 was the right choice anyway.

2. Case A — a hit whose prediction was wrong. Probability \(p_{hit}\,(1 - p_{ok})\), cost \(P\):

   \[ p_{hit}\,(1 - p_{ok})\,P \]

3. Case B — a miss on a branch that turns out taken: fetch defaulted to PC + 4. Probability \((1 - p_{hit})\,p_{taken}\), cost \(P\):

   \[ (1 - p_{hit})\,p_{taken}\,P \]

4. Add the two. With the textbook's numbers — 90 % hits, 90 % accuracy on a hit, 60 % of branches taken — and \(P = 1\):

   \[ \begin{aligned} \text{penalty} &= p_{hit}\,(1 - p_{ok})\,P \\ &\quad + (1 - p_{hit})\,p_{taken}\,P \end{aligned} \] \[ = 0.9 \times 0.1 + 0.1 \times 0.6 = 0.15 \]

   cycles per branch. (The textbook's own pipeline resolves branches a stage later, \(P = 2\), and gets 0.30.) Multiply by \(f_b\) for the contribution to the CPI.

And why keep two tables instead of one big BTB with direction bits? Count the bits. With 32-bit addresses and 1024 entries the tag has \(32 - 10 - 2 = 20\) bits, the PTA 30 (word-aligned) and the counter 2: 52 bits per entry, 6.5 KB for the table. A 2-bit BHT with 4096 entries — four times as many branches — costs \(4096 \times 2\) bits = 1 KB. Direction is cheap and tolerates collisions, so it gets a large untagged table; targets are expensive and must not collide, so they get a small tagged one. Hence what the BTB does not do (p. 64): it does not decide the direction, does not compute the target, does not replace the BHT; "it simply remembers previously computed target addresses for quick access during fetch, like a cache for branch targets". And only taken branches, because the "target" of a not-taken branch is PC + 4, which the fetch unit already has.

The puzzle resolved, and the words for the open question

Back to the loop of the hook: always taken 90 %, one bit 80 %, two bits 90 %. The dynamic predictor only ties with the static rule — so what was it for? For every branch whose bias the compiler cannot know: the loop that runs twice in one run and a million times in another, the if that follows the data. There the static rule is a coin toss and the counter learns in two executions — with no delay slots, no profiling run, no recompilation. And with a BTB beside it the nine correctly predicted taken branches cost 0 cycles instead of 1 each. The simplest learner lost to the dumbest rule on the one loop where that rule was already perfect; the second bit and the target buffer are what make learning pay.

The January 2026 paper asked "What are the main benefits to introduce the dynamic branch prediction in a modern microprocessor?", and the June 2026 paper wants "the main concepts and benefits" of "dynamic branch prediction and speculative execution" in five lines. Five lines, each with its why:

• Fewer mispredictions, lower CPI. The predictor shrinks \(1 - a\) in \(\text{CPI} = \text{CPI}_{\text{ideal}} + f_b(1 - a)P\); the penalty \(P\) is untouched.
• Adapts at run time. Input-dependent branches, trip counts and program phases that no compile-time rule can know; "if a branch changes its behavior at runtime, future predictions adjust accordingly" (p. 55).
• Essential in deep and wide pipelines. The work lost per misprediction grows with depth times issue width: in Onur Mutlu's ETH Zürich example (background, not in the notes) a 20-stage, 5-wide machine with a branch every five instructions fetches 500 instructions in 100 cycles at 100 % accuracy, 120 at 99 %, 300 at 90 %, 900 at 60 %.
• Enables speculative execution. Instructions beyond an unresolved branch are fetched, issued and executed, and must not update registers or memory before it resolves — here the flush before WB guarantees it, in a speculative Tomasulo machine the reorder buffer does (lesson 17).
• Independent of compiler and ISA. No delay slots to fill, no profile, no hints; the same binary runs faster on a better core.

The matching five lines for "Explain the main purpose to introduce the Branch Target Buffer" (January 2026, Question 2) are the model answer in the exam section below. Their skeleton: whether versus where; the target is computed in ID; a tagged cache read in IF; the stored target in the same cycle, zero cycles on a hit; filled when a taken branch resolves; PC + 4 and the normal penalty on a miss.