The idea: guess the branch, pay only when wrong

A pipelined processor fetches a new instruction every cycle. After a branch it must fetch the next instruction before it knows whether the branch is taken: the comparison happens later, in the Memory stage on the pipelined MIPS of Harris and Harris (Figure 7.47), or in the Decode stage with early branch resolution (Figure 7.58).

So the fetch stage predicts. It keeps fetching along the guessed path; these instructions are speculative. When the branch resolves, a right guess costs nothing. A wrong guess (a misprediction) flushes the speculative instructions and fetch restarts on the right path. Branches are about one instruction in five, so the quality of the guess sets the CPI.

The page runs three small MIPS programs on an ideal 5-stage pipeline (F D E M W, full forwarding, no other stalls), one branch at a time, and compares five predictors. The cyan rows of the pipeline diagram are speculative, the red rows are flushed.

The misprediction penalty and CPI

If the branch is decided in stage M, three younger instructions are already in F, D and E. A misprediction flushes all three: the branch misprediction penalty is 3 cycles. Deciding in D leaves only one wrong instruction, in F: 1 cycle. For N instructions:

cycles = N + 4 (filling the pipeline) + penalty × mispredictions
CPI    = cycles / N
Nested loops, 2-bit predictor (6 of 15 mispredicted, N = 48)PenaltyCyclesCPI
branch resolved in M (Demo 3)348 + 4 + 18 = 701.46
early branch resolution in D (Demo 5)148 + 4 + 6 = 581.21

Modern processors have 15 to 20 pipeline stages and fetch several instructions per cycle, so a misprediction throws away dozens of instructions. That is why they spend so much hardware on prediction.

Static prediction

A static predictor guesses without looking at history.

  • Always not taken: fetch just goes on with PC + 4. This is what the plain pipeline does. Every taken branch is a misprediction, and loop branches are taken almost every time: 11 of 15 wrong on the nested loops (Demo 4).
  • Backward taken, forward not taken (BTFN): a branch to a lower address closes a loop, so predict taken; a branch to a higher address skips the body of an if, so predict not taken. It is right on every loop iteration but the last: 6 of 15 on the nested loops, as good as the 2-bit counter there. It cannot learn an if that is taken half the time.

The branch target buffer

To fetch the target in the very next cycle, the fetch stage must know from the PC alone that the instruction is a branch and where it goes; the instruction has not even been decoded. The branch target buffer (BTB) is a small cache indexed by the PC. Here it is direct mapped: 8 entries, index = PC[4:2] (the word address bits), tag = the PC bits above. An entry holds:

FieldMeaning
V, tagvalid, and which PC the entry belongs to (compared like a cache tag)
targetwhere the branch went last time (the branch target address PC + 4 + offset × 4)
statethe prediction state: a 1-bit or 2-bit counter

A BTB miss means fetch does not know the instruction is a branch, so it fetches PC + 4. The first time each branch runs is therefore a guess of not taken (a cold miss, like in a cache), and the entry is written when the branch resolves. A BTB that is too small has conflicts: with 2 entries (index = PC[2]) both loop branches of the nested loops land in entry 1 and evict each other, so each finds the other's entry and starts cold again. 2-bit mispredictions go from 6 to 8 (Demo 6): B1 now misses twice per inner loop, like a 1-bit predictor, because it restarts cold every time.

1-bit predictor: two misses per loop

The simplest dynamic predictor stores one bit per branch: what it did last time. Take the inner loop branch bne $t1,$0,inner of the nested loops, which does T T T N four times per outer iteration (Demo 2):

  • On the exit (N) the bit says taken: miss, and the bit becomes 0.
  • The next time the inner loop starts, its first branch is taken, but the bit says not taken: a second miss.

So a 1-bit predictor mispredicts twice per execution of an inner loop: B1 is wrong 6 times out of 12 (1 cold + 1 exit + 2 × (entry + exit)), 8 of 15 in all.

2-bit saturating counter

The 2-bit predictor keeps a counter from 0 to 3 that counts up when the branch is taken and down when it is not, and stops at the ends (it saturates). The top bit is the prediction. One surprise moves it from strongly to weakly, but the prediction stays; only two wrong guesses in a row change it.

State diagram of the 2-bit saturating counter: states 00 strongly not taken, 01 weakly not taken, 10 weakly taken, 11 strongly taken; a taken branch moves one state right, a not-taken branch one state left, stopping at the ends; 10 and 11 predict taken
Taken branches push the counter right, not-taken ones push it left; the prediction flips only after two wrong guesses in a row.
CounterStatePredictionAfter TAfter N
11strongly taken (ST)taken1110
10weakly taken (WT)taken1101
01weakly not taken (WNT)not taken1000
00strongly not taken (SNT)not taken0100

On the loop exit the counter drops from ST to WT, still predicting taken, so the next entry into the loop is predicted right: one miss per inner loop. B1 is wrong 4 times out of 12 (1 cold + 3 exits), 6 of 15 in all (Demo 3). Here a new BTB entry starts weakly toward what the branch just did (10 after a taken branch).

The inner loop branch does T T T N twice; the 1-bit predictor misses on each loop exit and again on the next entry, 2 misses per loop; the 2-bit counter drops only from 11 to 10 on the exit, keeps predicting taken and misses only the exit
A 1-bit predictor misses twice per inner loop (exit and re-entry); a 2-bit counter misses only the exit.

Counters fail on a branch that alternates: in Demo 7 the if (i & 1) branch does T N T N…, the 2-bit counter swings between WT and WNT and is wrong all 8 times, exactly like the 1-bit predictor.

Global history (gshare)

What a branch does often depends on what the previous branches did. A global history register (GHR) keeps the outcomes of the last few branches (2 here, 1 = taken). The gshare predictor uses a pattern history table (PHT) of 2-bit counters indexed by PC XOR GHR, so the same branch uses a different counter for each recent history. The BTB still supplies the target.

gshare: PC bits 4 to 2 XOR the 2-bit global history register give an index into a pattern history table of 8 two-bit counters; the top bit of the chosen counter is the predicted direction and the BTB gives the target
gshare picks the counter with PC XOR recent history, so one branch can learn a different answer for each pattern of the branches before it.
  • Demo 7: in the alternating loop, the history before the if branch tells which iteration it is, and gshare drops the mispredictions from 10 to 6 of 16.
  • Demo 8: in if (i & 1) a++; if (i & 1) b += i; the second branch always does what the first one did. Its history (the last bit of the GHR) says exactly that, so after warming up gshare predicts it right every time: 6 of 24 mispredicted against 18 for the 2-bit counter.

The price is warm-up and sharing: each branch now needs several counters trained, and two (branch, history) pairs can map to the same PHT entry. On the plain nested loops gshare is worse than the 2-bit counter (9 against 6).

All predictors side by side

Mispredicted branches (of all branches) with the branch resolved in M and an 8-entry BTB (Demo 9 runs the last column):

PredictorNested loops (15)Loop with an if (16)Correlated ifs (24)
always not taken111115
BTFN6610
1-bit81018
2-bit61018
gshare (2-bit history)966

The programs are tiny, so the cold misses weigh a lot: every dynamic predictor starts with a BTB miss on every branch. Real programs run each branch thousands of times, and 2-bit counters reach about 90 % accuracy; the history-based predictors of modern CPUs (tournament, TAGE, perceptron) reach 95–99 %.

The pipeline itself, with its pipeline registers, forwarding and the flush of a taken branch, is drawn cycle by cycle on The MIPS Pipeline: Hazards and Forwarding; the BTB is a cache like the ones on How a CPU Cache Finds, Misses and Replaces.

What the page leaves out

  • One branch is in flight at a time, and the predictor is updated when the branch resolves. A real fetch stage meets the next branch before the previous one resolves, so it updates the history speculatively and repairs it on a misprediction.
  • No data hazards: the programs have no loads, and forwarding covers every dependency, so flushes are the only lost cycles.
  • The cycle count includes the 4 cycles that fill the pipeline, so CPI is a little above 1 + penalty × mispredictions / N.
  • On a BTB miss every predictor guesses not taken. A real design that decodes in D could still apply a static rule there, at the cost of a 1-cycle bubble.
  • No return address stack for jr $ra, no indirect-branch prediction, no tournament or TAGE predictors, no branch delay slot (the real MIPS executes the instruction after a branch anyway; Harris and Harris leave it out too).
  • The BTB and the PHT are tiny so that every entry can be drawn.