From Atoms to Data Centers: How a Modern Processor Finds Parallelism in a Serial Program

Keller starts from the bottom: atoms are assembled into materials such as doped silicon and metal, on which engineers build transistors, then logic gates, then functional units like adders or instruction parsers. Those units are assembled into processing elements, and a modern computer contains perhaps 10 to 20 coherent ones. On top of that sit the instruction set, assembly language, and higher-level languages such as C, C++, Java and JavaScript.

Building a computer begins with a target: what is it for, and how fast does it need to be? An organization of a thousand people then works across many disciplines to hit that target. Asked where the magic enters the hierarchy, Keller says he is agnostic about it and enjoys every layer.

Instruction sets, he notes, stay stable for long stretches. They encode a small set of basic operations such as load, store, multiply, add, subtract and conditional branch, and about 90% of execution time falls on just 25 or so opcodes. An architecture that has been around for 25 years works because those basics were defined long ago.

An old computer fetched instructions and executed them in order. A modern one fetches large numbers of instructions, say 500, finds the dependency graph between them, and runs independent pieces on separate units, deeply out of order. Keller jokes that the market for simple, clean, slow computers is zero, so the machine people buy may be built cleanly but must be complicated underneath.

To keep results correct, the machine carries bookkeeping tables and rules about memory ordering so operations appear to finish in the right order. Keller contrasts this with GPUs, which run simple programs over a million pixels where the order does not matter. He calls one kind "found parallelism" and the other "given parallelism": the screen does not care which pixel is processed first, so you can declare it parallel up front.

He illustrates with reading a book. A human reads sentence after sentence as one serial narrative, but if you diagrammed it, you could see that "tall and smart" can be reordered without changing meaning, while "the tall man is wearing the red shirt" creates dependencies. Found parallelism means discovering those reorderable pockets, which in real programs turn out to be large. How hard it is, he says, comes down mostly to transistor count.

Keller says out-of-order execution gains about 10x: an in-order machine takes around three cycles per instruction because of operation latency, while a modern one reaches roughly 0.3 to 0.5. That depends on both the amount of found parallelism and the predictability of the program. Branches occur about every six instructions, so to keep a 600-instruction window useful the predictor must get about 99 of 100 branches right.

Predicting a branch means guessing which way a decision will go before it is resolved. In a loop that runs a million times, for example, the machine can bet that the value is still greater than one. Host Lex Fridman is stunned that this works so accurately, and Keller says the real story behind it is surprisingly simple at first.

The history of predictors is, in his words, a little sad. Twenty years ago machines recorded which way a branch went last time and predicted the same, which was about 85% accurate. Adding a small counter reached 92%, and using history of how the code got there improved it further.

Today's predictors look something like a neural network, doing deep pattern recognition over execution flows in several ways and choosing the best result; Keller calls it a little supercomputer inside the computer. Reaching 85% took about a thousand bits, while 99% takes tens of megabits, so going from a 50-instruction window to 500 required three or four orders of magnitude more bits.

Even a wrong guess can be partly salvaged. If the machine executed down the wrong path, it flushes the pipeline, but designers are looking at remembering results that did not depend on the branch, much as a reader's understanding of the next paragraph is sometimes unaffected by misreading the last. The hardware tracks whether data changed to decide whether to recompute.

Asked how much of this is art and how much is science, Keller compares it to choosing a route: shortest, fastest or most scenic. Designing a computer means making hundreds of such decisions, each with hundreds of options that interact in complicated ways. He jokes that this is the Robert Frost road-less-taken problem for computer designers.

Some people are very good at making intuitive leaps, he says, while others cannot leap but excel at evaluating alternatives. A good team contains many kinds of people, and he suspects only a few would count as artistic. His summary is that computer design is 99% perspiration, with the 1% inspiration being really important.

Does a program give the same result every time? For a correct C program, Keller says, that is a definitional statement. Early 3D graphics acceleration could produce different results across runs of the same scene, which some people accepted, but when the high-performance computing world began using GPUs for calculation, they thought it was a bad idea.

In modern AI, he notes, data precision is low and the input data is unbelievably noisy, so it is fair to ask why the computation should not be noisy too. People have experimented with algorithms that speed up by being noisy, such as stopping a network's narrowing computation graph early and starting the next iteration. Still, for developers a program that gives different answers each run is annoying to debug, so everybody wants a switch that forces determinism.

Keller finishes with the point that people often miss: hardware can deliver a deterministic answer even though its execution flow is highly non-deterministic. Run a program a hundred times and it never executes the same way twice, yet the same input produces the same answer every time.