The pipeline and the fortune-teller

The last chapter ended with a promise: a processor can guess the future, and sometimes it gives away other people’s secrets. We start with the guessing, and with the most famous question in the history of Stack Overflow. On June 27, 2012, a programmer who went by GManNickG posted a short C++ program and asked: “Why is processing a sorted array faster than processing an unsorted array?” The program takes an array of 32,768 random numbers from 0 to 255, adds up the ones that are at least 128, and repeats this a hundred thousand times. If the array is sorted first, it runs in 1.93 seconds instead of 11.54. The numbers are the same, the sum is the same, and the sorting is done before the stopwatch starts. When this chapter was written, the question had a score of more than 27,000, higher than any other question on the site.

We can repeat the experiment in the sandbox. It has C: in Chapter 33 we ran it with the tcc compiler. The program is the same, except that it repeats the sum a thousand times rather than a hundred thousand, to fit into a cell’s ten seconds. But first, a bet.

We get the effect too: the sorted array is summed several times faster. Maybe it’s a quirk of C? Here is the same thing in Python.

In Python the sorted list is also noticeably faster, though the gap is smaller. The interpreter spends tens of nanoseconds of its own work on each number (we talked about that work in Chapter 33), and what sorting speeds up drowns in the rest. It doesn’t drown completely, though. The cause, then, lies in the processor itself: for some reason it cares about the order in which it meets the same branch. To see why, we have to look inside a modern processor, starting with the problem that made it so complicated.

The wall: the clock stops climbing

Moore’s law, meanwhile, kept working: there were more and more transistors on a die. The clock hit its ceiling, yet programs kept getting faster, because the new transistors went into doing several things at once. Inside a core, each instruction was split into stages and several instructions were kept in flight together; the processor also learned to guess where the program would go next and to execute the guess in advance. Outside, several cores were put on one die, and each was taught to add eight numbers with a single instruction. We’ll take these ideas one at a time. The first came from a laundry.

The laundry

A laundry has three machines: a washer, a dryer and an ironing press. Each handles a basket in half an hour. Four baskets come in. You could go in order: wash the first, dry it, iron it, and only then start the second. Each basket takes an hour and a half, and the four take six hours. But while the first basket is in the dryer, the washer stands idle, though the second basket is waiting. So load it. Half an hour later the first goes under the press, the second into the dryer, the third into the washer, and all three machines are busy.

Now the four baskets are done in three hours: an hour and a half for the first, then another one every half hour. No basket got any faster: each still spends an hour and a half in the laundry. What got faster is the laundry. It used to turn out a basket every hour and a half, and now it turns one out every half hour. The time one job takes from start to finish is its latency; the number of jobs finished per unit of time is the throughput. A pipeline leaves the first alone and multiplies the second. David Patterson and John Hennessy explain the processor with a laundry like this one in their classic textbook on computer architecture.

For the laundry, $k = 3$ and $n = 4$: six half-hour cycles instead of twelve. For a thousand baskets the speedup is already almost threefold. So a pipeline of twenty stages could, in the ideal case, do the work almost twenty times faster. But only if the stages are equal. Suppose drying takes forty minutes. Then the press stands idle, baskets pile up in front of the dryer, and the laundry turns out a basket every forty minutes: the slowest stage sets the pace. Try it yourself.

The pipeline in a processor

Recall Iskra-8 from Chapter 32. It works in a loop: fetch, decode, execute. The instruction memory does the fetching, the decoder the decoding, the ALU the executing, and then the result is written to a register. These are different parts of the circuit, and while the ALU is adding for one instruction, the decoder could be taking apart the next one, and the memory could be handing out the one after that. Processors have been built this way since the 1960s. The arrangement is called a pipeline, and its steps are called stages. A pipelined Iskra-8 would have four stages: fetch (F), decode (D), execute (E) and write-back (W).

The depth of the pipeline is tied to the clock rate. The length of a cycle is set by the slowest stage (the dryer again), and in a circuit that means the longest chain of gates, as in the adder of Chapter 30. The finer you slice the work, the shorter the longest chain and the faster the clock can tick. The gigahertz race of the 2000s was built on this: the first Pentium 4 (2000) had a pipeline of 20 stages, and its Prescott version (2004) had 31. But in a processor, unlike a laundry, the baskets depend on one another.

Hazards

Take the summing program from Chapter 32, which adds $3 + 2 + 1$.

Put it through a pipeline and we hit three kinds of obstacles at once. They are called pipeline hazards.

Data hazards. The instruction ADD R2, R0 comes right after LDI R2, 0 and wants to read R2. But the previous instruction writes its zero there only at its last stage, in the same cycle in which ADD already wants to take it. The simplest way out is to wait: an empty cycle, a bubble, goes into the pipeline. A better way is forwarding: the result the ALU has just computed travels along a separate wire straight back to the ALU’s input for the next instruction, without waiting to be written to the register. Almost every processor does this.

Control hazards. The instruction JNZ loop decides where to go next: back to ADD or on to ST. It decides at the execute stage, once the zero flag is known. But two cycles earlier the fetch stage already had to pick up the next instruction. Which one? The pipeline can wait, and then it loses two cycles at every branch. In our three-instruction loop that makes the whole job almost twice as slow. In a processor with twenty stages, waiting at every branch would eat up everything the pipeline gained: programs have a branch every few instructions.

Structural hazards. Two instructions need the same unit in the same cycle: say, one is fetching an instruction from memory while another writes to that memory. The cure is hardware: the units are duplicated. That is why the L1 cache of Chapter 34 is split in two, one half for instructions and one for data.

Compare the three approaches in the diagram. Waiting is simplest, but slow. Guessing “not taken” means carrying on fetching instructions in order: if the guess is right, nothing is lost; if not, the instructions fetched by mistake are thrown away, and the pipeline loses the same two cycles as with waiting. Guessing “taken” pays off better for this loop: of the three JNZ branches, two jump back, and the miss comes only on the way out. In a loop of a thousand rounds that’s one miss in a thousand. A fast processor has to guess, and the whole question is how to guess well.

The fortune-teller

The diagram itself suggests the simplest rule. A backward branch is most likely the end of a loop body, so it will be taken; a forward branch most likely jumps around some if, so it won’t. This rule remembers nothing and therefore costs almost nothing. But it knows nothing about our if (data[i] >= 128). It’s better to watch how a branch behaved before. The part of the processor that does this on the fly, its fortune-teller, is called the branch predictor.

The first idea is to remember one bit for each branch, whether it was taken last time, and to guess that it will do the same again. For a loop that almost works: inside the loop the branch is taken every time, and the bit says “taken.” There are two misses per run of the loop: on the way out, when the branch isn’t taken for the first time, and on the next entry into the loop, because the bit remembers the exit and now says “not taken.”

A second bit removes the second miss. Give the branch a counter from 0 to 3. If the branch is taken, add one; if not, subtract one; the counter never goes above 3 or below 0. The values 2 and 3 mean “taken,” 0 and 1 mean “not taken.” Now the branch has to fool the fortune-teller twice in a row to change its mind: one exit from the loop moves the counter from 3 to 2, and on the next entry the prediction is still “taken.” This is a two-bit saturating counter, a finite-state machine with four states, of the same kind as the traffic light in Chapter 31. It was invented twice, independently, in the late 1970s: by Tom McWilliams and Curt Widdoes for the S-1 supercomputer at the Lawrence Livermore Laboratory, and by Jim Smith at Control Data.

Press “Steps” and follow the variable state. The counter gets the first branch of all wrong: it starts at “not taken” and has to warm up. After that it misses once at each exit from the loop. Play against it yourself: before each branch, guess whether it will be taken, while the fortune-teller makes its own guess at the same time.

On loops and on long runs of identical outcomes the counter hardly ever misses. On “every other” it misses every time, though a person spots the pattern within three moves. A predictor that remembers the last few outcomes and keeps a separate counter for each pattern catches such patterns quickly. The predictors in modern processors are more elaborate still: they take the history of hundreds of branches into account and get the overwhelming majority right. But one thing is beyond any fortune-teller, and that is chance. Here are the branches from our puzzle.

The puzzle solved

In the sorted array the condition data[i] >= 128 is false sixteen thousand times in a row, then true sixteen thousand times in a row. The counter misses only where the outcome changes: in the cell above, twice per pass; when the passes repeat, as in the C measurement, four times, at the switch inside a pass and at the switch between passes. In the shuffled array the outcome is a coin toss, and the fortune-teller is wrong half the time: sixteen thousand times per pass. Each miss is expensive. Everything the pipeline managed to fetch and start after the branch is thrown away, and the work starts again from the right instruction. On modern processors, whose pipelines are long, that costs 10 to 20 cycles. Sixteen thousand misses at fifteen cycles each is a quarter of a million cycles lost per pass, more than all the rest of the loop’s work. That is why the shuffled array takes several times longer to add up.

The answer on Stack Overflow came from a user called Mysticial five minutes after the question was posted, and it has a score of more than 35,000. It opens with “Consider a railroad junction” and explains the same idea with a switchman. Stopping every train to ask the driver which way it’s going would take too long, so the switchman guesses; if he guessed wrong, the train brakes, backs up and sets off again.

Doing without the branch

If a branch is hard to predict, you can remove it. Adding a number only if it’s at least 128 is the same as adding the number multiplied by the result of the comparison, by 1 or by 0. A mask is faster still. In C the expression -(x >= 128) is either 0 or −1, and −1 in two’s complement is all ones. A bitwise AND with such a mask either leaves the number as it is or turns it into zero. No branches are left in the loop, and there is nothing to guess.

Without the branch the order no longer matters: the shuffled array is summed as fast as the sorted one. Compilers know this trick. With optimization turned on, a modern compiler often turns such a branch into arithmetic or into a conditional move instruction on its own, which is why many people who repeated the 2012 experiment with newer compilers saw no difference at all. But tcc optimizes nothing and shows the processor as it is. The lesson is worth keeping: in a hot loop, a branch whose outcome looks like a coin toss costs tens of cycles, and sometimes it’s cheaper to remove it than to guess.

The fortune-teller doesn’t wait

So far the fortune-teller only chose which instruction to fetch next. A modern processor goes further: it executes the guessed instructions right away, tens and hundreds of instructions ahead, without waiting to find out whether the guess was right. It also reorders instructions: if the next instruction needs data that is still on its way from memory, the processor gets on with the following, independent ones. All of this is done in draft. The results go into a special buffer and become final, landing in registers and memory, only when every branch before them has been confirmed. If the fortune-teller was wrong, the draft is thrown away, and the program never learns what the processor got up to. This is called speculative execution.

The promise sounds strict: everything a program can see—its registers, its memory, its result—will be as if the instructions had run one at a time, in program order. For more than twenty years everyone believed that was enough. Then someone remembered the cache. When a draft instruction reads memory, the line it needs comes from RAM into the cache. The draft is thrown away, but the line stays in the cache. Registers and memory are rolled back; the cache is not. We know from Chapter 34 that this can be seen: a line in the cache is read in a few nanoseconds, a line in RAM in about a hundred. Time is a result too. Nobody had counted it as one.

A ghost in the cache

You can understand how it works without a single line of attack code. Picture a librarian who runs to the stacks in advance, while the reader is still filling in the request slip. The library’s rule says: “If the reader’s card number is valid, bring the book whose number is written in that reader’s file.” An attacker hands in a slip with a forged card number that points to someone else’s file. While the card is being checked, the nimble librarian has already run off and put on the counter the book whose number is in the other person’s file. The check fails, and the librarian politely refuses. But the book is still on the counter. Now the attacker asks for every book in turn and notes which one is handed over instantly: its number is the one written in the other person’s file. The counter is the cache, the running to the stacks is speculative execution, and the card check is an array bounds check that the processor guessed would pass.

When a secret is learned from a by-product of the work, such as time, power use or noise, it’s called a side-channel attack. Spectre showed that the branch if (i < size) protects data only when instructions run in order. A speculating processor looks past it before it has worked out the condition.

The whole industry joined in the repairs. Operating systems hid their memory from programs; in Linux the patch is called KPTI. It noticeably slows down programs that make many system calls, which are the subject of the next chapter. At dangerous spots, compilers learned to put barriers that forbid the processor to guess. Newer processors fixed Meltdown in hardware. And browsers, where your bank and someone else’s ads run side by side on one processor, made their clocks coarser: if you can’t measure time precisely, you can’t tell the cache from memory. Check how coarse your browser’s clock is.

Many laundries

The pipeline, the fortune-teller and the drafts squeeze everything they can out of a single stream of instructions, but they too have a limit: beyond it, the dependencies in the program itself get in the way. When the clock hit its ceiling in the mid-2000s, it became simpler to spend the spare transistors on copies of the whole processor on one die. Each copy, a core, runs its own program, with its own pipeline and its own fortune-teller. The first dual-core processors for ordinary computers came out in 2005; today a phone may have eight cores and a server a hundred. How many does the course sandbox have? We’ll ask, and then put it to the test by dividing the same work among one, two and four processes.

ProcessPoolExecutor starts several Python processes and hands them pieces of the work. Processes rather than threads, because in ordinary CPython threads take turns holding one shared interpreter lock and can’t compute at the same time; that lock and threads in general are the subject of Chapter 39.

The result is puzzling. Plenty of cores are visible (when this chapter was written the sandbox saw fourteen; your number may differ), yet two and four processes are no faster than one, and often slower, even though each got a half or a quarter of the work. The answer is in the second line: the sandbox gets one core’s worth of processor time. The cores are there, but we aren’t allowed to work on them. The counters at the ends of the lines show how this is enforced. However many processes run, one core is busy on average, and as soon as the processes together use up their share of time, they are stopped until the next share. Who decided this and who keeps count is a question for the operating system, which we reach in the next chapters. For now, remember that cores in a list are not yet a speedup.

One instruction, many numbers

There is a kind of parallelism that needs neither cores nor anyone’s permission. An ordinary instruction adds two numbers. A vector instruction adds eight pairs at once: the processor has wide registers of 128, 256 or even 512 bits, and a 256-bit register holds eight 32-bit numbers. The idea is called SIMD, for single instruction, multiple data. Such instructions reached mass-market processors in the 1990s for the sake of video and sound, where the same operation is repeated on millions of numbers.

Python keeps vector instructions out of reach: each of its numbers is a separate object somewhere in memory. The numpy library, though, keeps numbers in a dense array, as in Chapter 14, and walks through it with a loop written in C, where vector instructions do the work. Rewriting a computation so that it runs over whole arrays at once is called vectorization. Here is our puzzle in three forms.

The Python loop is the slowest by a factor of tens. The more interesting difference is between the two numpy versions. The expression data >= 128 gives an array of Trues and Falses, and data[mask] uses it to copy the chosen elements into a new array: once again a branch for every number, and once again the fortune-teller has to call a coin toss. np.where(condition, data, 0) works differently. For each number it computes both options and takes the right one without any branch, as the mask did in C. Code like this fits vector instructions and comes out several times faster again. The last line prints the vector instruction sets numpy found on the sandbox’s processor: on ARM processors these are NEON and ASIMD, on Intel and AMD, SSE and AVX.

Take the idea to its limit and you get the GPU, the graphics processor. It has thousands of simple cores with no clever fortune-teller and no long drafts, but they all run the same program at once on different data, each for its own pixel on the screen. They thrive on problems with no branches and no dependencies, where one operation is repeated millions of times. The main work of neural networks, multiplying huge matrices, turned out to be a problem of this kind, which is why neural networks are trained on graphics cards (more on that in Chapter 63).

Amdahl’s law

Suppose we have as many cores as we like, and they are all ours. How much faster will a program run on a thousand cores? The answer came from Gene Amdahl, whom we met in Chapter 16: he came up with open addressing for the IBM 701 assembler and later became chief architect of the IBM System/360. In April 1967, at the AFIPS conference in Atlantic City, he argued against the idea, fashionable at the time, of building computers out of many identical processors. His argument went like this. Every program has a part that can’t be divided: preparing the data, collecting the results, steps that each wait for the one before. That part sets a ceiling, however many processors you add.

The numbers are sobering. If 95% of the work runs in parallel, the program speeds up 5.9 times on 8 cores, 15.4 times on 64, 19.6 times on 1024, and never more than 20 times. On a thousand cores the last five percent, the part that can’t be divided, takes up almost all the time. This is Amdahl’s law.

Amdahl’s law is less a verdict than a set of directions. It tells you where to look: in the serial part. If 10% of a program runs on one core, the ceiling is 10, and speeding up what already divides is pointless. The profiler from Chapter 13 helps find the serial part.

There is another way to look at it. In 1988 John Gustafson and Edwin Barsis of Sandia National Laboratories noticed that people who get new processors take on bigger problems: a weather forecast on a finer grid, a model with more particles. The parallel part grows with the number of cores, the serial part doesn’t, and the speedup grows almost in proportion to the number of cores. Both views are right, each for its own kind of problem: Amdahl’s when you need the answer faster, Gustafson’s when you need a bigger one.

Finally, the fraction $p$ needn’t be guessed: it can be measured. Run the program on one core and on $N$, get the speedup $S$, and solve Amdahl’s equation for $p$. Alan Karp and Horace Flatt proposed evaluating parallel programs this way in 1990. If the serial fraction computed like this grows as $N$ grows, the cores are getting in each other’s way, sharing memory or waiting for one another. That is one of the tasks below.

Tasks

Three tasks: build a fortune-teller, speed up a loop with vectors, and work out how many cores are worth buying.

What next

Part IV is over. Starting from bits, we went up through gates, the adder and memory, built a processor and saw how it cheats time. And all along we talked about the processor as if it were busy with our program alone.

Two experiments in this chapter say otherwise. The sandbox sees many cores, but it is allowed to work on only one: somebody decided so and enforces the quota. Meltdown showed that there are walls between programs on the same processor: the operating system’s memory is closed to an ordinary program, and a crack in that wall became world news. A hundred programs are running on one processor right now: a browser, music, mail, this sandbox. Who decides which of them gets to run, and who builds the walls between them? The operating system, and Part V begins with it. Its first chapter is a tour of the live system on which every cell of this course has run.