What a CPU is, and how it works

Strip a CPU down far enough and you find one part, repeated tens of billions of times: the transistor, a switch that one voltage turns on and off. Wire a few together and you get a gate, a tiny machine that looks at its inputs and answers 1 or 0.

The NAND gate (“not and”) answers 0 only when both inputs are 1. It takes four transistors, and it has a party trick: every other gate can be built from NANDs alone. NOT is a NAND with its inputs tied together. AND is a NAND followed by a NOT. XOR takes four.

Pick a gate and flip the switches. Watch the signal walk through the circuit one gate at a time. That delay is real; every gate takes a few picoseconds to make up its mind, and a CPU’s clock speed is limited by the longest chain of them.

Build XOR, set A = 1 and B = 1, then flip B. Count the gate delays before the lamp agrees.

Two XORs, two ANDs and an OR make a full adder: it adds two bits plus a carry, and passes a carry on. Chain eight of them and you can add two bytes. That is the whole trick behind every number your computer has ever produced.

The chain has a flaw you can see. Each adder waits for the carry from its right-hand neighbour, so the answer ripples across the byte. On 64 bits that is too slow, so real ALUs use carry-lookahead adders that compute all the carries in parallel with more gates. Spending transistors to save time is the oldest trade in this notebook, and it comes back on every plate.

Then there is the edge of the world. Eight bits hold 0 to 255. Ask for 200 + 100 and the ninth bit falls off the end. Switch to signed and the very same bits mean −128 to 127. Two’s complement is the convention that lets one adder serve both: −1 is just 11111111, and adding 1 rolls it over to zero.

Make 127 + 1 in signed mode. The hardware did nothing wrong. Your interpretation did.

At 4 GHz one cycle lasts a quarter of a nanosecond, which is long enough for light to cross about 7.5 centimetres. Main memory sits a few centimetres away, behind a memory controller and a protocol, and it answers in roughly 90 nanoseconds. That is several hundred cycles of a core doing nothing.

The numbers are too small to feel, so the ladder rescales them: if one cycle took one second, an L1 cache hit would take four, a trip to RAM would take six minutes, and an SSD read would take a long weekend.

This is the single most important fact about performance on any processor. Arithmetic is cheap. Moving data is expensive. Almost every trick in the following plates, and in the GPU and TPU notebooks, is a way of not waiting for memory.

The answer to distance is to keep copies close. A cache is a small, fast memory next to the core that holds recently used data. It never fetches one number at a time: it fetches a whole line (64 bytes on most CPUs, four elements in this drawing), betting that if you wanted one value, you will soon want its neighbours.

Whether that bet pays depends on you. A two-dimensional array is stored row after row. Walk it row by row and each line you fetch serves four accesses: one miss, three hits. Walk it column by column and every access lands on a different line; with a small cache, each one is evicted before you come back for its neighbour.

Same array, same arithmetic, same answer. Run both and compare the cycle counts.

Walk by column, then raise the cache to 16 lines. The access pattern didn’t change; the working set started to fit.

Back to plate IV’s problem: a deep pipeline fetches instructions long before it knows which way a branch goes. Waiting would waste fifteen-odd cycles on every if. So the CPU guesses, runs ahead on the guess, and throws the work away if it was wrong.

The simplest useful predictor is a two-bit counter per branch. Taken pushes it right, not taken pushes it left, and it predicts whichever side it is on. Two bits instead of one means a single surprise doesn’t flip the prediction, which is exactly what a loop needs: taken, taken, taken… and one exit.

Real predictors keep long histories and correlate branches with each other; on typical code they are right well over 95% of the time. Which means the cheapest branch is a predictable one, and the most expensive is a coin toss. Try alternating on the two-bit counter for the worst case, then you decide and try to fool it.

A CPU, then, is a machine for running one stream of instructions as fast as physics allows, by overlapping, caching and guessing. The GPU notebook starts from the opposite bet: give up on speeding up one stream, and run thousands.