Down to the Metal

Part IX · Chapter 25

Pipelines and Speculation

The processor of Chapter 6 finished one instruction before starting the next. A modern core has hundreds of instructions in flight at once: it overlaps them, runs several side by side, reorders them, and even guesses which way the program will go before it knows. This chapter shows how, and what happened when those guesses turned out to leak secrets.

Making transistors faster only goes so far. Since the early 2000s, clock speeds have stayed at a few gigahertz, yet each new generation of processors runs programs faster. Most of the extra speed comes from doing more work in each clock cycle. The ideas behind it are surprisingly old, and they all start with doing laundry.

The pipeline

Imagine three loads of washing. Washing takes an hour and drying another hour. One load at a time, that's six hours. But as soon as the first load moves to the dryer, the washer is free, so you start the second. With both machines busy, all three loads are done in four hours. Each load still takes two hours; you just finish one every hour instead of every two.

A processor does the same with instructions. The classic RISC pipeline splits each instruction into five stages, each handled by its own part of the circuit: fetch the instruction (IF), decode it and read its registers (ID), execute it in the ALU (EX), access memory if needed (MEM), and write back the result (WB). With a new instruction entering every cycle, five are in progress at once, and one finishes every cycle.

There's a catch. Instructions often need each other's results. If add t1, t0, t2 comes straight after the load that fills t0, it reaches the decode stage before the load has written t0 back. That's a hazard, and the simplest fix is to stall: hold the add back for a few cycles. A cleverer fix is forwarding: extra wires pass a result straight from the end of one stage to the instruction that needs it, without waiting for write back.

Six RISC-V instructions. Try each way of running them, then let the compiler reorder them. Count the cycles.

RISC-V was designed with pipelines in mind: every instruction has the same simple layout, so decoding is quick, and only loads and stores touch memory. x86 instructions vary from 1 to 15 bytes, which makes them much harder to decode in a hurry. So modern x86 processors first translate each instruction into simpler internal steps, called micro-operations (µops), and pipeline those instead. Inside, an x86 core works a lot like a RISC one.

Guessing the way: branch prediction

Branches are the biggest problem for a pipeline. A conditional branch only knows whether to jump once it reaches the execute stage, but by then the fetch stage has already moved on, a few instructions further. A modern core's pipeline is much longer than five stages, and it fetches several instructions per cycle, so waiting for every branch would waste dozens of instruction slots each time. And programs branch roughly every five or six instructions.

So the processor guesses. A branch predictor remembers how each branch behaved in the past, predicts what it will do this time, and the core carries on fetching and executing along the predicted path. This is speculative execution. If the guess was right, no time was lost. If it was wrong, everything done on the wrong path is thrown away, the pipeline is flushed, and fetching restarts from the right place, which costs many cycles.

Pick a branch pattern and a predictor, and watch it learn. Which predictor handles which pattern?

A 2-bit counter needs two wrong guesses in a row to change its mind, so a loop's single exit doesn't fool it about the next run of the loop. Predictors that remember the recent history of branches can learn repeating patterns too. Real predictors combine several histories of different lengths, and get well over 95% of branches right in typical programs. Only truly random branches defeat them.

Superscalar and out of order

Once instructions can overlap, why not run several side by side? A superscalar core has several execution units (several ALUs, load and store units, multipliers) and starts several instructions every cycle. The performance cores of the processor this book was written on can decode 6 instructions per cycle.

But programs are full of instructions that wait: for a result from the one before, or for data from memory, which can take hundreds of cycles if it misses the caches (Chapter 9). An out-of-order core doesn't wait. It reads far ahead in the program, keeps a window of upcoming instructions, and starts each one as soon as its inputs are ready, whatever its place in the program.

One load misses the cache and takes 12 cycles. Compare an in-order core with an out-of-order one that can start two instructions per cycle.

Two more tricks make this work. Register renaming gives the core hundreds of hidden physical registers behind the 16 or 32 names in the instruction set, so that two unrelated uses of, say, rax don't have to wait for each other. And the reorder buffer keeps track of every instruction in flight, so that results are made final, or retired, strictly in program order. If an instruction causes an exception, or a branch turns out to have been mispredicted, everything after it is simply discarded, and the program can't tell anything happened out of order. The performance cores of the computer this book was written on can have 512 instructions in their reorder buffer at once.

When speculation leaks: Spectre

For decades, speculation seemed perfectly safe: wrong-path work was thrown away and never became visible. Then, in January 2018, researchers announced Spectre and Meltdown. Wrong-path instructions are thrown away, but their side effects on the caches aren't. If speculatively executed code loads a secret and then uses it to choose which memory to touch, that memory stays in the cache. An attacker can then time memory accesses, to find out which line is now fast to read, and so work out the secret.

Here's the idea in outline. A program checks that an index is inside an array before using it. The attacker trains the branch predictor with many valid indexes, then supplies one far outside the array. The predictor guesses "inside", and for a moment the processor speculatively reads memory it shouldn't, before the check catches up and the work is undone. But the cache remembers.

Defences came from every layer: new processor features, barrier instructions that stop speculation at sensitive points, changes to compilers and operating system kernels, and coarser timers in web browsers, so that web pages can't measure cache timings precisely. Newer processors are designed to be immune to the worst variants. Linux reports the status of each known problem on the computer it's running on.

Meanwhile, inside a real CPU

Here's branch prediction at work, measured on the computer this book was written on. A function adds up all the bytes in an array that are 128 or more. It runs over a million random bytes, then over the same bytes after sorting them:

long count_big(const unsigned char *v, int n) {
    long sum = 0;
    for (int i = 0; i < n; i++)
        if (v[i] >= 128)          /* the branch */
            sum += v[i];
    return sum;
}
random  : 0.291 s  (2.91 ns per element)
sorted  : 0.024 s  (0.24 ns per element)     ← the same work, 12 times faster

With random bytes, the branch is a coin toss, and the predictor is wrong about half the time. Sorted, the branch is "not taken" for the first half of the array and "taken" for the second, which any predictor gets right. Each wrong guess costs roughly (2.91 − 0.24) ÷ 0.5 ≈ 5 ns: about 25 clock cycles of thrown-away work. Compilers know this trick too. Left to itself, GCC avoided the branch completely, using a conditional move, cmovs, that picks one of two values without jumping. Then the order doesn't matter at all:

    test   sil, sil          ; is the byte 128 or more? (top bit set)
    cmovs  rcx, rdx          ; if so, total = total + byte, no branch

random  : 0.056 s  (0.56 ns per element)
sorted  : 0.056 s  (0.56 ns per element)

(To get the branchy version, we compiled with -fno-if-conversion, which tells GCC not to do this.) Next, superscalar execution. Four billion additions, first as one long chain where each add needs the result of the one before, then as four independent chains interleaved, pinned to one performance core:

dependent:   0.849 s  (0.212 ns per add)     ← one add per clock cycle, at about 4.7 GHz
independent: 0.317 s  (0.079 ns per add)     ← about 2.7 adds per cycle

Same instructions, same count. The only difference is whether they wait for each other. On one of the smaller efficiency cores, the same test gave 0.279 and 0.126 ns. Finally, what Linux says about the speculation problems on this processor (a few lines):

$ grep . /sys/devices/system/cpu/vulnerabilities/*      (trimmed)
meltdown:          Not affected
spectre_v1:        Mitigation: usercopy/swapgs barriers and __user pointer sanitization
spectre_v2:        Mitigation: Enhanced / Automatic IBRS; IBPB: conditional; …
spec_store_bypass: Mitigation: Speculative Store Bypass disabled via prctl
mds:               Not affected

Meltdown was fixed in the hardware of this processor's generation. Spectre can't be fixed completely without giving up speculation, so it's held back by a mix of hardware features and software barriers.

Try it yourself

  1. A five-stage pipeline runs 100 instructions with no stalls. How many cycles does it take? And without a pipeline?
    Show answerThe first instruction takes 5 cycles, then one more finishes every cycle: 5 + 99 = 104 cycles. Without a pipeline, 100 × 5 = 500 cycles, almost 5 times as long.
  2. In the pipeline demo, why can't forwarding remove the stall after the load?
    Show answerA load's data only arrives at the end of the MEM stage, but the next instruction needs it at the start of its EX stage, which happens at the same moment. There's no way to send data back in time, so one cycle must be lost, unless another instruction can fill the gap.
  3. A loop runs 8 times, again and again. What fraction of its closing branch does a 2-bit counter predict correctly once it's warmed up?
    Show answer7 out of 8, or 87.5%. It's wrong only on the exit, and one wrong guess moves the counter from "strongly taken" to "weakly taken", so it still predicts "taken" when the loop starts again.
  4. Why must an out-of-order core retire results in program order?
    Show answerSo that it can always undo work. If an instruction causes an exception, or a branch was mispredicted, every later instruction must have no visible effect. Keeping results private until they retire in order means the core can simply throw away anything after the problem.
  5. In the real experiment, the dependent chain ran one add per cycle. Why can't the processor do better, even with several ALUs?
    Show answerEach add needs the result of the one before it, and an add takes one cycle. However many ALUs there are, only one add in the chain can ever be ready at a time. The independent chains gave the core work it could do in parallel.

What we learned

One core can only go so fast. The processor this book was written on has twelve of them, running twenty threads. Next: multicore and concurrency, and why making cores cooperate is so tricky.