1981-1990s

Branch Prediction

A pipelined processor has to fetch the next instruction before it knows whether the branch in front of it will be taken. So it guesses, and carries on working on the strength of the guess. If it guessed right, nothing was lost. If it guessed wrong, everything started since has to be thrown away. Smith's 1981 paper measured the strategies against each other and the two-bit saturating counter won; what is worth watching is not its accuracy but its state, because it takes two consecutive surprises to change its mind.

A guess, the state behind it, and what being wrong costs

1 The pipeline, and the branch that has not been decided yet

The branch has not been decided yet and the pipeline cannot wait. Pick a pattern of outcomes and a predictor to face it.

The branch behaves like this

The predictor

the pipeline: 5 stages, so a wrong guess throws away 4

2 A guess, and the work carried out on the strength of it

The first sixteen branches. The two state columns are the point: watch how often the state moves without the guess moving with it.

Each branch: the state before the guess, the guess, what actually happened, whether it was right, and the state afterwards
#	state before	guess	actual	outcome	state after
1	weakly not taken	not taken	not taken	right	strongly not taken
2	strongly not taken	not taken	taken	WRONG	weakly not taken
3	weakly not taken	not taken	taken	WRONG	weakly taken
4	weakly taken	taken	taken	right	strongly taken
5	strongly taken	taken	taken	right	strongly taken
6	strongly taken	taken	taken	right	strongly taken
7	strongly taken	taken	taken	right	strongly taken
8	strongly taken	taken	taken	right	strongly taken
9	strongly taken	taken	taken	right	strongly taken
10	strongly taken	taken	taken	right	strongly taken
11	strongly taken	taken	not taken	WRONG	weakly taken
12	weakly taken	taken	taken	right	strongly taken
13	strongly taken	taken	taken	right	strongly taken
14	strongly taken	taken	taken	right	strongly taken
15	strongly taken	taken	taken	right	strongly taken
16	strongly taken	taken	taken	right	strongly taken

3 Right: nothing was lost, and nothing had to be undone

guessed right: 179 of 200
accuracy: 90 per cent

A right guess costs nothing at all. The work carried out on the strength of it was work that needed doing, so nothing has to be undone.

4 Wrong: unwind it, and count what the guess cost

guessed wrong: 21
thrown away: 84 stages thrown away
total work: 284 against 200 if every guess had been right
the overhead: 42 per cent more work

Two bits of state get 90 per cent here against 81 per cent for one bit. The counter needs two consecutive surprises before it changes its guess, so a rare exception costs one mistake instead of two.

All three predictors against all six patterns. The alternating row is the one to read.

Each pattern, and the accuracy of each of the three predictors on it
pattern	no state	one bit	two bit
always taken	100 per cent	100 per cent	100 per cent
never taken	0 per cent	100 per cent	100 per cent
alternating	50 per cent	0 per cent	0 per cent
one in ten	10 per cent	80 per cent	90 per cent
nine in ten	90 per cent	81 per cent	90 per cent
a run of each	52 per cent	88 per cent	76 per cent

on this pattern the best of the three is always taken, at 90 per cent

What this page checked when it loaded.

Each claim, whether it held, and the values behind it
claim	held	measured
on a rare exception the two-bit counter beats the one-bit one	yes	21 wrong against 39
and it is wrong about once per exception, not twice	yes	21 wrong in 200
strict alternation is the worst case for a one-bit predictor	yes	200 wrong in 200
and the two-bit counter gets every single one of them wrong	yes	0 right out of 200, where a coin gets half
so a predictor with no state at all beats it on this pattern	yes	100 against 0
a predictor with no state is right as often as the branch is taken	yes	20 of 200
spent time is the ideal plus the stages thrown away	yes	396 = 200 + 49 x 4

What is real here, and what is not

Five pipeline stages, where a modern processor has fifteen to twenty

The cost of a wrong guess here is four stages refilled, which matches the classic five-stage teaching pipeline and no processor you own. A deep out-of-order machine throws away far more, which is exactly why prediction accuracy became worth spending transistors on: the penalty grew with the pipeline. The ratio on this page is therefore an understatement, and the direction of the understatement is worth knowing.

Nothing here is timed, and the patterns are not real programs

Every number is a count. The six patterns are arithmetic — every tenth, every other, runs of eight — not traces of anything that ever ran. A real branch in a real program is correlated with other branches nearby, which is the whole subject of the two-level predictors that came ten years after Smith and is not modelled here at all.

One branch, with no table and no aliasing

There is a single predictor here following a single branch. Real hardware has a table of counters indexed by the branch address, several branches share an entry when the addresses collide, and that aliasing is a genuine source of mispredictions that this page cannot show. Adding a table would have made the state column, which is the reason this machine exists, impossible to read.

More state is not always better, and the page does not hide it

On a strictly alternating branch the two-bit counter is wrong every single time and a predictor with no state at all is right half the time. On runs of eight the one-bit predictor beats the two-bit one. Both results are in the comparison table rather than in a footnote, because a page that only showed the counter winning would be selling it.

Sources

Logical Art builds interactive explanations of difficult machines.

The machines:

1935-1991 RangekeeperThe answer is on both sides of the equation, so it had to be a machine.
1964-1990s AbendThe loop you did not write, and the day it cost to get it wrong.
1975 Front PanelA working 1975 Altair 8800 you program by flipping switches.
1980s 300 BaudA real dial-up modem and the BBS on the other end of it.
1994 WinsockThe two seconds after the modem stopped screeching, before anything worked.
2020s LLM LabTrain a tiny language model and watch every number as it learns.

Smaller pieces, on the studio itself: Morse, Baudot, Punch Cards, Interlace, Bitwise, Stored Program, Trigger, Bit, Nibble, Byte, Transistor, Hamming, Huffman, Core Memory, The Interrupt, Score Reel, CRC, Page Fault, ASCII, CPU Cache, Race, Fifteen Planes, B-tree, Backoff, Checkout, Diffie-Hellman, Fringes, LZ77, Zero Address, Signature, Z-Characters, Merkle Proof, Branch Prediction, Interleave, Eight Sprites, DNS, Floating Point, Slow Start, UTF-8, Masking, PageRank, Merge Collapse, Count Distinct.

A Logical Art machine by RoamingPigs, Inc. Built by Cisco Caceres in Las Vegas, NV.