The adder from Part 4 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 4 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, and by the end of it every piece of the clerk will have been drawn down to gates.
Somewhere to put things
Start with memory. A gate computes but does not hold. Put inputs on a NAND and its output follows them, and the moment the inputs go away so does the answer. To store a bit you need a circuit that remembers its own state, and the trick, which is the same trick behind every register, every cache and every SRAM chip ever made, is feedback. Take two NOT gates and feed the output of each into the input of the other. Suppose the top one's output is 1. That 1 goes into the bottom gate, whose output is therefore 0, and that 0 goes back into the top gate, whose output is therefore 1, which is what we assumed. The loop agrees with itself. Now suppose instead that the top output is 0. Then the bottom output is 1, the top input is 1, and the top output is 0, which again agrees. There are two states the loop is happy in, and once it is in one it stays there for as long as the power is on, each gate propping the other up. A pair of NOT gates wired this way is called a latch, and it is one bit of memory.
The trouble is getting at it. A loop that refuses to change is no use unless you can change it on purpose, and you also need to look at it without disturbing it. So a real memory cell adds two more transistors, and I will call them doors, because that is what they do. Each is the n-type switch from Part 4: a wire on one side, a wire on the other, and a control gate that decides whether the two are joined.
Where the doors go. The loop has two sides, the output of the top NOT gate, which I have been calling Q, and the output of the bottom one, not Q. One door sits on each side. Beyond the doors run two long vertical wires called the bit lines, one carrying the bit and the other its opposite, which is why both sides of the loop are brought out rather than just one. Nothing else touches the loop.
Who works the doors. Both control gates hang off one horizontal wire, the word line. This is the fan-out from Part 4 once more, one wire and many control gates, all of them feeling the same voltage at the same instant, so the two doors can only ever open together or shut together.
The names come from the way cells are arranged. A memory chip is a grid of them, and the wires are shared. Every cell in a row hangs off the same word line, and every cell in a column hangs off the same pair of bit lines. Put a 1 on one word line and every door along that row opens at once, so a whole row of cells, a word of 32 or 64 bits, is joined to the bit lines in one go, while every other row keeps its doors shut and its bits to itself. One word line per row, one pair of bit lines per column: the address of a bit is which row and which column.
Now the three things a cell does, and what each kind of wire is for. The word line has one job: it opens and shuts the doors. The bit lines have one job: they are the path the bit travels along, in or out of the cell.
Holding. The word line is 0, so both doors are shut, and the loop is cut off from the bit lines. Whatever it was set to, it goes on holding, because the two NOT gates keep propping each other up and nothing on the bit lines can reach them. This is what a cell does almost all of the time.
Writing. Set the word line to 1, so both doors open. At the same moment, force the two bit lines to the value you want to store: 1 on the Q side and 0 on the other for a 1, the reverse for a 0. The bit lines are pushed by big transistors at the edge of the memory, and the two NOT gates inside the cell are tiny, so where the two disagree the bit lines win and the loop is forced into the new state. Set the word line back to 0, the doors shut, and the new value is locked in. The bit lines were the way in.
Reading. Set the word line to 1 again, but this time push nothing onto the bit lines. Now the only thing connected to them is the loop, so the loop sets them: the bit line on the Q side takes Q's value and the other takes the opposite. A small circuit at the foot of the column, the sense amplifier, looks at which of the two is higher and reports the bit. Then the word line goes back to 0. The bit lines were the way out, and the cell still holds its value afterwards.
That is a cell of SRAM, static random-access memory, and "static" means exactly this: keep the power on and it remembers, with nothing else required. Try all three operations below.
A cell of SRAM. The loop from the figure sits in the middle. Two doors, worked by the word line, connect its two sides to a pair of bit lines. Try holding, writing and reading.
Count the transistors. Each NOT gate is the two-transistor pair from Part 4, so the loop is four, and the two doors make six. Here is the same cell drawn all the way down at that level, with nothing hidden. Follow the thin control wires: the output of each NOT gate runs to the control gates of the other, which is the loop, and the word line runs to the control gates of both doors.
Thirty-two of those cells side by side hold one 32-bit number, and a small bank of those, with the wiring to read two of them and write one in the same tick, is a register file. Registers are the processor's desk: a few dozen slots, right next to the arithmetic, reachable in a single tick. SRAM is fast because there is nothing to wait for. The loop is already driving its answer before you ask. It is also expensive, six transistors and their wiring per bit, which is why a processor has only a few dozen registers and, as Part 6 will show, a few tens of megabytes of SRAM cache, not gigabytes.
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, and it takes the opposite bet. Instead of a loop that actively holds a bit, a DRAM cell stores it as a charge, a few tens of thousands of electrons, on a tiny capacitor, two conducting plates separated by an insulator, with one access transistor as the door between the capacitor and the bit line. One transistor per bit instead of six, and a capacitor dug down into the silicon as a deep, narrow well, so the cells pack many times denser than SRAM and cost a small fraction as much per bit.
The bet has two costs, and both matter enormously for the rest of this series. The first is that the capacitor leaks. The insulator is not perfect, the door is not perfectly shut, and the charge trickles away over a few tens of milliseconds, so a 1 slowly turns into a 0. Nobody rescues it except a memory controller that reads every row and writes it back, thousands of rows in turn, every 64 milliseconds, all day, whether or not anyone is using the memory. That is the "dynamic" in the name. The second cost is that reading a cell disturbs it. Opening the door lets the tiny charge spread out along the bit line, where a sense amplifier has to detect a change of a few hundredths of a volt and decide whether it saw a 1 or a 0, then write the answer back into the cell. All of that takes time, tens of nanoseconds against the fraction of a nanosecond a register needs, and Part 6 is entirely about that gap.
The same cell with the charge made visible. Write a 1, then let time pass and watch it leak. A sense amplifier reads anything above the halfway line as 1 and below it as 0, and rewriting the cell after a read is what "refresh" means.
| SRAM | DRAM | |
|---|---|---|
| Stores a bit as | a loop of two NOT gates that holds itself | a charge on a capacitor |
| Transistors per bit | 6 | 1, plus the capacitor |
| Needs refreshing | no | every 64 ms |
| Time to reach | under a nanosecond | tens of nanoseconds |
| Used for | registers, caches, anything on the processor die | main memory, graphics memory, the filing cabinet |
| Cost | high, so there are megabytes | low, so there are gigabytes |
A sense of time
Now the metronome. The clock is a signal that swings 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 the clock rises. 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.
The latch I built above will not do for this job. It changes as soon as its door is open, which is fine for a memory cell whose door you open on purpose, but hopeless for the registers that sit between stages of arithmetic. If a register simply copied its input whenever the clock was high, a fast gate could race a new value through during that half period and the result would depend on who arrived first. What a register needs is to copy its input at one instant, the rising edge, and ignore it the rest of the time. The circuit that does this is a flip-flop, and it is two latches in a row with opposite doors. The first is open while the clock is 0 and shuts when it rises. The second is the other way round. While the clock is low, the first latch follows the input and the second holds the old value. At the rising edge the first latch shuts, freezing whatever the input was at that instant, and the second opens and passes exactly that frozen value to the output. Nothing gets through except at the edge, and a register is just one flip-flop per bit.
A register listens only at the tick. Flip D as often as you like between ticks and nothing happens to Q. Press Tick and Q takes whatever D was at that instant, and keeps it until the next tick.
This is what turns timeless gates into a machine that does one thing and then another, and it also puts a hard ceiling on speed. Between one edge and the next, the value released by one register has to get all the way through the gates to the next register and settle there before the next edge arrives. Every gate along the way takes a little time, a few picoseconds in a modern chip, and a chain of them takes the sum. If the gap between ticks is shorter than the slowest chain, the register at the end captures a half-computed answer, and nothing downstream can tell that it did. So the gap has to be long enough for the slowest chain anywhere in the design, and that one chain sets the clock for the whole chip.
What has to happen between two ticks. At the first tick, register A releases a new value into a chain of gates. Each gate takes one unit of time to settle. At the second tick, register B captures whatever has arrived, finished or not. Set the chain length and the gap between ticks, then run one cycle.
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.
Side note: where the ticks come from. Every clock in a computer begins with a sliver of quartz. Quartz is piezoelectric: squeeze it and it produces a voltage, apply a voltage and it flexes, and a slice cut to a particular size will vibrate at one exact frequency, tens of millions of times a second, if you feed a little of its own output back to it, the way a bell rings at one note. A crystal on the motherboard or graphics card ticks at something like 25 or 100 MHz, stable to a few parts in a million, which is why your computer can keep time. That is far too slow for a processor, so inside the chip a circuit called a phase-locked loop multiplies it. The loop runs its own fast oscillator, divides that output down, compares the result with the crystal, and nudges the fast oscillator until the two agree, so that a 100 MHz reference becomes a 2.52 GHz core clock locked to it. The ratio can be changed on the fly, which is what "boost clock" means: the chip raises the multiplier when it is cool and has power to spare and lowers it when it does not. The last problem is delivery. The same edge has to reach hundreds of millions of flip-flops across a die two centimetres wide at as near as possible the same instant, and the wires it travels are branched into a tree, an H shape inside H shapes, laid out so that every path from the trunk to a leaf is the same length. Even so, the edge reaches different corners a few tens of picoseconds apart, a difference called skew that the designers have to budget for, and the clock tree with all its amplifying buffers is one of the largest single consumers of power on the chip, often a fifth or more of the total.
Side note: what if two parts run on different clocks? They do, all the time. A GPU's cores tick at one rate, its memory interface at another, the PCI Express link to the CPU at a third and the display outputs at a fourth, each with its own crystal or its own multiplier, and none of the edges line up. Inside one clock domain everything is safe, because every flip-flop hears the same edge and the gap between edges is long enough for every path. Across a boundary that guarantee is gone. A signal from one domain can change at the very instant a flip-flop in the other is capturing, and a flip-flop caught mid-change does something no digital circuit is supposed to do: it hangs between 0 and 1, in the no-man's land from Part 4, for an unpredictable time before falling one way or the other. This is called metastability, and it cannot be prevented, only made rare. The standard cure is a synchroniser, two flip-flops in a row on the receiving clock: the first may go metastable, but it has a whole clock period to settle before the second one looks, and the chance that it has not settled by then is astronomically small, one failure in centuries. For whole streams of data, the two sides share a small queue in memory that one side fills and the other drains, each on its own clock, with only the queue's counters crossing between them through synchronisers. Every path between a GPU's cores and its memory goes through one of these, and getting them right is a recognised specialist skill, because a mistake shows up as a machine that crashes once a week for no reason anyone can reproduce.
The slow carry, and the fast one
Remember the carry rippling through the four-bit adder in Part 4. Each full adder needs the carry from its neighbour before it can finish, so in a 32-bit adder the leftmost column cannot settle until the carry has crossed all the columns to its right, one or two gate delays each. That is a chain of sixty-odd gates, and if the whole of it had to fit between two ticks the clock could not run at a fraction of the speed it does. Watch it happen, and then watch the cure.
Two 8-bit adders racing. The top one is the ripple chain from Part 4: each column waits for the carry from its right-hand neighbour. The bottom one works out every carry directly from the inputs. Click bits to change the numbers, then press add and watch the time count.
The cure is to notice that each column can say in advance what it will do with a carry, before the carry arrives. If both of its inputs are 1 it will generate a carry no matter what comes in, and that flag is just A AND B. If exactly one input is 1 it will propagate whatever carry it receives, and that flag is A XOR B. If both are 0 it kills the carry. Those two flags depend only on the column's own inputs, so all thirty-two pairs of them are ready one gate delay after the numbers arrive. With them, the carry into any column becomes a formula rather than a wait. The carry into column 4 is 1 if column 3 generates, or column 3 propagates and column 2 generates, or 3 and 2 both propagate and 1 generates, or all three propagate and column 0 generates, or all four propagate and there was a carry in. That is a wide OR of ANDs, two gate levels deep however many columns it covers. Doing it for all thirty-two columns at once would take an absurd number of gates, so real adders look ahead within groups of four, then look ahead across the groups, and a 32-bit sum settles in a dozen or so gate delays rather than sixty. The gates are cheap and the time is not, and that trade, spending silicon to shorten the longest chain, is most of the art of making a clock go faster. Every arithmetic unit in a GPU is built with it.
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.
Every part of that loop is a circuit made from the pieces we now have, and here is the map before we open the boxes. Nothing in it is a different kind of thing from an adder. It is flip-flops, a few decoders and multiplexers, an incrementer, the arithmetic from Part 4, memory cells, and wires.
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.
The clerk, gate by gate
Three small circuits do most of the organising work in that diagram, and they turn up everywhere else in a chip too. Each is a few AND, OR and NOT gates. With them, plus the flip-flops and adders we already have, the program counter and the jump fall out in a few lines.
The decoder
A decoder takes a pattern of bits and lights exactly one output wire. Feed it the opcode bits of an instruction and it lights the control line for that instruction. Feed it an address and it lights one word line in a block of memory, which is how the fetch stage picks out a single row of the SRAM cells above. It is nothing but AND gates, one per output, each wired to look for its own pattern.
A decoder: two opcode bits in, one of four control lines out. Each output is an AND gate wired to the pattern it is looking for, using the plain bit where the pattern has a 1 and the inverted bit where it has a 0. A dot is a connection. A plain crossing is not.
The multiplexer
A multiplexer is a switch with no moving parts: several inputs, one output, and a few select bits that say which input to copy. The register file uses one to put the register an instruction asks for onto the wires to the adder. The program counter uses one to choose between "the next line" and "the jump target". Inside, it is the decoder again with one extra input on every AND gate and an OR gate to gather the results.
A multiplexer: four inputs, two select bits, one output. It is the decoder again, with each AND gate given a third input, one of the data lines, and an OR gate collecting the four results. Whichever input the select bits point at is copied to the output, and the other three are ignored.
The program counter
Now the clerk's bookmark. The program counter is a register, one flip-flop per bit, that captures a new value at every tick. Between ticks two candidates are prepared for it. An incrementer, which is a chain of half adders from Part 4 with a 1 fed into the bottom, works out the current value plus one. And the instruction being executed, if it is a jump, offers a target address. A multiplexer picks one of the two, and at the tick the register takes it.
The program counter: a four-bit register, an incrementer made of four half adders, and a multiplexer. Between ticks the incrementer works out PC + 1 and the multiplexer chooses between that and the jump target. At the tick, the register captures the choice.
Comparing, and deciding to jump
The last piece is the one that gives a program the power to decide. A comparison is arithmetic with a short answer. To ask whether two numbers are equal, XOR them bit by bit, so that each XOR reports whether its pair differs, and OR all the reports together: if nothing differs, they are equal. To ask whether a number is zero, OR its bits and invert. To ask which of two is bigger, subtract one from the other, using the trick from Part 4, and look at the sign bit that falls out. Each of these produces a single wire, a flag, that the processor keeps in a register alongside the result. A conditional jump then needs exactly one more gate. The decoder says "this instruction is a jump-if-zero", the flag says "the last result was zero", an AND gate combines them, and its output is the select line of the program counter's multiplexer. Take the jump, or take the next line.
Comparing two numbers, and deciding whether to jump, in gates. Click the bits of A and B. Four XOR gates ask, bit by bit, whether they differ, a wide OR collects the answers, and a NOT turns "any differ" into "equal". A wide NOR of A alone gives "A is zero". Then one AND gate combines the flag with the decoded instruction to decide what the program counter does next.
That AND gate is worth a second look, because a great deal of what follows in this series hangs on it. Its inputs are not ready until the compare has finished, which is not until the previous instruction has finished, and until it is ready the processor cannot know which instruction comes next. Hold onto that too.
Running a program
Here is the whole clerk at work: our running calculation as a short program in a made-up but typical instruction set. The first version is a straight line, six instructions. The second does the multiplication by repeated addition, the way a machine without a multiplier would, and needs a compare and a jump to loop. Step through both and watch the program counter.
A toy processor. The first program computes y = w × x + b with w = 3, x = 5, b = 2 in a straight line. The second does the multiplication the slow way, by adding 5 to a running total three times, using a compare and a jump. Press Tick to advance the clock one instruction at a time.
program (in memory)
registers
data memory
Six ticks for the straight line, fifteen for the loop, one calculation each. 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. It also lets the clock run faster, for the reason the chain demo showed: each stage is a shorter chain of gates between two registers, so the gap between ticks can shrink. 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 AND gate at the end of the compare demo. 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, because the AND gate could not say which way to go until the compare had finished.
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. Every piece of it has now been drawn down to gates, and every gate down to transistors. 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 8 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.