A Machine That Follows Instructions

The adder from Part 3 has a strange property once you notice it. It has no idea of time. Put two numbers on its input wires and the sum appears on the output wires a few billionths of a second later, and it stays there for as long as the inputs do. Change the inputs and the output changes. It never waits, never remembers, and never does anything next.

That is a problem, because w × x + b is not one operation. It is a sequence: fetch w and x, multiply them, fetch b, add it, put the result somewhere. A computer is a machine that does things in order, and the arithmetic units of Part 3 cannot do that by themselves. This part adds the three things they are missing: somewhere to keep numbers, a sense of time, and something to read the instructions. Jon Stokes's book pictures this as a calculator with a file clerk standing next to it, and I have never found a better image. The calculator does the sums. The clerk fetches the numbers from the filing cabinet, tells the calculator what to do, and files the result. This part is about the clerk.

Somewhere to put things

Start with memory. A gate computes but does not hold. To store a bit you need a circuit that stays put: two NOT gates feeding into each other, so that whichever one is on keeps the other off, and the pair sits in that state indefinitely. Add a couple of transistors to let you read and overwrite it and you have a cell of SRAM (static random-access memory), six transistors per bit. Thirty-two of them side by side hold one 32-bit number, and a small bank of those is called a register. Registers are the processor's desk: a few dozen slots, right next to the arithmetic, reachable in a single tick.

The filing cabinet is bigger and further away. The main memory of a computer, the gigabytes of RAM on the motherboard or the graphics card, is built from DRAM (dynamic random-access memory), which stores each bit as a charge on a tiny capacitor with one transistor as a gatekeeper. One transistor per bit instead of six is why DRAM is cheap and dense, and it comes with two costs that matter enormously for the rest of this series: the capacitor leaks, so every cell has to be read and rewritten dozens of times a second just to keep its value, and it is far slower to reach than a register. Part 5 is entirely about the second cost.

A sense of time

Now the metronome. The clock is a signal that ticks between 0 and 1 billions of times a second, and every register in the processor is wired to capture whatever is on its input wires at the instant of the tick. Between ticks, the gates do their work, signals ripple through adders and multipliers, and the registers ignore all of it. At the tick, the results are captured and become the inputs for the next round.

This is what turns timeless gates into a machine that does one thing and then another. It also puts a hard ceiling on speed: the gap between ticks has to be long enough for the slowest chain of gates to finish, or a register would capture a half-computed answer. Remember the carry rippling through 32 adders in Part 3. Chains like that set the clock. An RTX 4090 boosts to 2.52 GHz, which is 2.52 billion ticks a second, or about 0.4 nanoseconds each. Light itself travels 12 centimetres in that time. Signals in copper are slower, and a chip is a couple of centimetres across, so at these speeds a wire from one side of the die to the other is a serious engineering problem in its own right, before any gates are involved.

The clerk's loop

With registers and a clock, we can describe what a processor does, and it is the same loop that every processor since 1945 has run. A program is a list of instructions stored in memory, one after another, each a short pattern of bits. A special register, the program counter, holds the address of the next one. Then, forever:

The processor fetches the instruction at the address in the program counter. It decodes it, which means a block of gates looks at the bit pattern and works out which circuit to activate and which registers to involve. It executes it, which for arithmetic means putting the right registers on the input wires of the right unit and, at the next tick, capturing the result. Then it adds one to the program counter and goes round again.

The set of bit patterns a processor understands is its instruction set. An Intel or AMD chip speaks x86, a phone chip speaks Arm, and an Nvidia GPU speaks a language of its own that the driver translates into. The instruction sets differ in detail but every one of them contains the same few families: move data between memory and registers, do arithmetic on registers, compare things, and jump to a different instruction. That last one is what makes a program more than a list, and it is where CPUs and GPUs part ways, so hold onto it.

Here is our running calculation as a six-instruction program in a made-up but typical instruction set. Step through it.

Six ticks, one calculation. Every program you have ever run is this loop, billions of times a second, with the instructions being a great deal less tidy.

Doing more than one thing per tick

If you watched the demo closely, something should bother you. Each tick did one thing, and while the multiplier was working the fetch circuitry sat idle, and while an instruction was being fetched the multiplier sat idle. Most of the processor is doing nothing most of the time.

The fix, which took over the industry in the 1980s, is the assembly line. Split the loop into stages, fetch, decode, execute, write back, and let each stage work on a different instruction at the same time. While instruction 3 is executing, instruction 4 is being decoded and instruction 5 is being fetched. This is pipelining, and it does not make any single instruction finish faster, it makes instructions complete more often, one per tick instead of one per four ticks. A modern CPU core has a pipeline a dozen or more stages deep, and on top of it does two further things Stokes spends half his book on: it fetches and decodes several instructions per tick (superscalar execution), and it runs them in whatever order their inputs happen to be ready, rather than the order they were written (out-of-order execution), sorting the results back into the right order afterwards.

All of this machinery, the pipeline, the multiple decoders, the reorder logic, exists for one purpose: to keep the arithmetic units busy when a single stream of instructions keeps stalling. And the thing it stalls on most is the jump.

The trouble with "if"

Remember the fourth family of instructions, the jump. A jump says "instead of the next instruction, go to this other one", and a conditional jump says "go there only if this register is zero", or greater, or whatever. That is how a program expresses every if, every loop, every decision. It is also poison for a pipeline. If the fetch stage is five instructions ahead of the execute stage, and the instruction being executed turns out to be a jump, then the five instructions already in the pipeline are the wrong ones and have to be thrown away.

CPUs answer this with a branch predictor: a block of gates and memory that watches which way each jump has gone before and guesses which way it will go next, so the fetch stage can keep going down the likely path. Modern predictors are right well over ninety-five per cent of the time, and they are enormous. A very large fraction of a CPU core's transistors is spent on predicting, reordering, and caching, all in service of making one thread of instructions run without ever waiting. The actual adders and multipliers are a small island in the middle.

Where this leaves us

A processor core is the calculator and the clerk: arithmetic units, a bank of registers, a clock, and a control loop that fetches, decodes, and executes one instruction after another. The loop is the same in a laptop CPU and in a GPU. What differs is what surrounds it.

A CPU core surrounds the loop with vast machinery for running one instruction stream as fast as physically possible: deep pipelines, out-of-order execution, branch predictors. A GPU makes a different choice. Instead of one clerk and one calculator working flat out, it has one clerk reading each instruction aloud to 32 calculators at once, each holding its own numbers. That single design decision is most of what makes a GPU a GPU, and Part 7 is where we open it up. Before we can, we have to face the thing both designs are really fighting against, which is not the arithmetic and not the instructions. It is how long it takes to fetch a number from the filing cabinet.

Next: The Memory Wall: why a processor that can add in a third of a nanosecond spends most of its life waiting for memory, the ladder of caches that tries to hide it, and the two very different strategies CPUs and GPUs use to cope.