JOVANA
Explore Library Glossary Getting Started Three Levels Fields How it works Mission
Join the mission
All guides

Speculation and Branch Prediction

An out-of-order core can run dozens of instructions ahead — but only if it knows which way each branch goes before the branch has actually decided. The answer is to bet. This guide shows how a CPU guesses the road ahead, runs down it speculatively, and quietly tears up the work when the bet was wrong.

Why a fast core cannot afford to wait at a fork

By now you have a powerful engine. The earlier guides in this rung gave you a superscalar core that issues several instructions per cycle, register renaming that dissolves the false dependences over register names, reservation stations and Tomasulo's algorithm that fire each instruction the moment its real operands are ready, and a reorder buffer that lets results finish out of order yet still commit in order. All that machinery exists to find dozens of independent instructions and run them at once. But there is a wall it keeps slamming into: the branch.

Recall the control hazard from the pipeline rung. A conditional branch like 'if x > 0, jump to L' does not know which way it goes until its condition is computed — and that may be several cycles away. Real programs branch about every five to seven instructions. If the core stalled at each branch until the outcome was known, the whole out-of-order machine would sit idle far more than it ran. A wide engine that pauses every six instructions is barely wider than a narrow one. To stay busy, the core simply cannot wait to know which way a branch goes.

So it does the only thing that keeps the pipeline full: it guesses. This is branch prediction — a bet on which fork in the road the program will take — and the running-ahead-on-a-guess that follows is speculative execution. The whole rest of this guide is about how the bet is made well, and what happens when it loses.

Predict the direction: from one bit to two

The cheapest guess is to assume a branch behaves the way it did last time. Keep one bit per branch: 'last time, taken' or 'last time, not taken', and predict the same again. This works astonishingly well because most branches are loops, and a loop's back-edge is taken hundreds of times in a row. But a single bit is brittle at exactly the seams. A loop that runs 100 times mispredicts twice: once on the final iteration (it predicts 'taken' but the loop now exits) and then again on the very next entry to the loop, because that single bit was just flipped to 'not taken' by the exit.

The fix is the classic two-bit predictor. Instead of one bit, keep a small saturating counter with four states — strongly-taken, weakly-taken, weakly-not-taken, strongly-not-taken — and predict 'taken' in the two taken states. One surprising outcome only nudges the counter one step; it takes two misses in a row to flip the actual prediction. Now a loop that exits once does not throw away its conviction: the single exit moves it from strongly-taken to weakly-taken, the prediction stays 'taken', and the next loop entry is correct. One added bit of hysteresis cuts the loop's mispredictions roughly in half.

Two-bit saturating counter (one per branch slot)

   11  strongly taken     -- predict TAKEN
   10  weakly   taken     -- predict TAKEN
   01  weakly   not-taken -- predict NOT taken
   00  strongly not-taken -- predict NOT taken

   branch resolves TAKEN     -> move one step up   (toward 11)
   branch resolves NOT-TAKEN -> move one step down (toward 00)

   loop run 100x with one exit:
     counter sits at 11 the whole time,
     the single exit nudges 11 -> 10 (still predicts TAKEN),
     so re-entering the loop is predicted correctly.
A two-bit counter needs two surprises in a row to change its mind, so a single loop exit no longer poisons the next entry.

When history rhymes: correlating and tournament predictors

Two-bit counters look at one branch in isolation, but branches are often correlated with each other. Picture 'if (a == 0) ...' followed soon by 'if (a == 2) ...'. Whenever the first is taken (a is zero), the second is guaranteed not taken (a cannot also be two). A per-branch counter cannot see this link. A correlating predictor can: it keeps a short global history register — the last handful of taken/not-taken outcomes across all branches — and uses that recent pattern, combined with the branch's own address, to index a table of two-bit counters. In effect it learns rules like 'after this exact recent sequence of branches, this branch usually goes this way.' Many real branches are predictable only in context, and this is how the hardware captures the context.

But no single scheme wins everywhere. Some branches are best predicted by their own local history (a loop counts the same way every time); others only make sense against the global pattern. So modern cores hedge with a tournament predictor: run two different predictors side by side — say a local one and a global/correlating one — and add a third small table, a chooser, that learns, per branch, which of the two has been more accurate lately. For each prediction the chooser picks the currently-better expert. It is a bet on top of a bet, and it routinely pushes accuracy past 95 percent — sometimes well past 98 — on ordinary code.

Predict the target too: the branch target buffer

Guessing the direction (taken or not) is only half the job. If the branch is taken, the core must also know where to fetch next — the target address — and it needs that in the very same cycle it fetches the branch, before the instruction has even been decoded. It cannot afford to decode the branch, read its instruction format, and compute the target the slow way; that would already cost the cycles prediction is meant to save. Enter the branch target buffer (BTB): a small cache, indexed by the branch's address, that remembers 'the last time we fetched a branch at this address, it jumped to here.'

So fetch works like this each cycle: take the current address, look it up in the BTB in parallel with reading the instruction. A BTB hit plus a 'taken' verdict from the direction predictor lets the very next fetch jump straight to the predicted target, with zero bubble. The direction predictor answers whether to jump; the BTB answers where to. Indirect jumps — a function pointer, a virtual method call, a switch — are harder, because the same instruction can jump to different targets on different runs, so cores add specialized predictors (like a return-address stack for function returns) to handle those well.

Running on a guess, and undoing it cleanly

Now the two halves meet. With a predicted direction and a predicted target, the core keeps fetching, renaming, and executing instructions down the guessed path — speculative execution — long before the branch's real condition is known. These instructions compute real results into renamed physical registers and sit in the reorder buffer, but they are flagged as speculative. The single rule that makes all of this safe is the one from guide two: nothing is allowed to commit until it is no longer speculative. An instruction can run early; it cannot make its effect permanent early.

  1. Predict: fetch reads the branch; the direction predictor says taken/not-taken and the BTB supplies a target. Fetch keeps going down the predicted path without pausing.
  2. Execute speculatively: instructions on the guessed path issue from reservation stations, compute into renamed registers, and land in the reorder buffer, every one tagged 'speculative'.
  3. Resolve: eventually the branch's real condition is computed and the prediction is checked against it.
  4. If right: clear the speculative flags. Those instructions are now ordinary, and they commit in program order through the reorder buffer as if nothing unusual happened.
  5. If wrong: flush every speculative instruction newer than the branch, throw away their renamed registers, restore the predictor and target hardware, and restart fetch at the correct address.

The recovery in the last step is the pipeline flush you met before, now wielded on an industrial scale: a wrong-path instruction may have computed all the way to a result, but because it never committed, that result never reached an architectural register or memory. Tearing it up is invisible to your program. This is the deep reason the machine stays trustworthy: it speculates freely but, thanks to in-order commit, the observable results are always exactly what a simple sequential CPU would have produced.

When one stream runs dry: simultaneous multithreading

Even with great prediction, a single instruction stream sometimes cannot keep a wide core busy — it hits a long-latency cache miss or a chain of dependent instructions, and execution units sit idle waiting. Simultaneous multithreading (SMT, marketed as Intel's Hyper-Threading) fills those gaps by keeping two or more hardware threads alive in the same core at once. Each thread has its own architectural state — its own program counter and architectural registers — but they share the execution units, reservation stations, and reorder buffer slots. When one thread stalls, instructions from the other are ready to issue, so the expensive hardware keeps working.

Be honest about what SMT buys: it improves throughput by harvesting idle slots, not the speed of any one thread — two threads sharing a core each run a bit slower than they would alone. It is a way to wring more total work out of transistors you have already paid for, especially when single-stream parallelism runs out. And that running-out is the cliff the final guide confronts: there is only so much independent work to be found in one instruction stream, the power cost of looking ever harder grows brutally, and that wall is exactly what pushed the industry off ever-fancier single cores and toward putting many cores on one chip.