Build a Microprocessor
Start with a light switch and finish with a working CPU that runs programs you write yourself. Each part is built from the parts before it, so nothing has to be taken on trust.
No hardware background needed No maths beyond counting
Read a little, then play with the widget under it. Every box below is real: the adders really add, the flip-flops really remember, and the CPU at the end really executes the machine code that the assembler produces from your typed program. If a widget confuses you, click things until it doesn't. That is exactly how hardware engineers learn too.
Every step
What a processor is
Open a laptop, find the biggest black square on the board, and that's it: the processor. Under the lid is a sliver of silicon the size of a fingernail holding tens of billions of microscopic switches. It has no idea what a photo is, what a song is, or what a game is. It knows how to do about a hundred childishly simple things, like "add these two numbers" and "fetch this number from memory."
What silicon has to do with any of this
Silicon is the main ingredient of ordinary sand, purified until a slice of it is very nearly one perfect crystal. It is used because it can be persuaded to carry electricity in some places and block it in others, which is exactly what a switch needs.
A chip is a thin wafer of that crystal with patterns printed into it. Step 2 is where those patterns start to matter.
No single trick explains it. What explains it is speed and obedience: the processor does billions of those tiny steps per second, forever, in exactly the order you specify. Everything else is built out of those steps stacked high: operating systems, browsers, neural networks.
Here is the plan. We build the tower from the bottom up:
A computer is not one clever machine. It's a stack of stupid machines, where each level is built out of the level under it and hides that level's messiness. Nobody understands all of it at once. Engineers work one layer at a time. So will we.
"A stack of stupid machines", said another way
Think about reading. Ink makes letters, letters make words, words make sentences, sentences make an argument. While you follow the argument you are not thinking about ink, and you do not have to.
A computer is stacked the same way, and each step here adds one level. When we reach the top the bottom is still down there doing its work. We just stop looking at it.
What GHz means
Hertz means "times per second". A kilohertz is a thousand of those, a megahertz a million, a gigahertz a billion. So a 3 GHz chip is being told "now" three billion times a second.
Step 10 builds the wire that does the telling. Until then, treat GHz as nothing more than a count of how often the machine takes its next step.
Switches and the two-state wire
Before transistors, before chips: a battery, a bulb, and a switch. Electricity flows in a loop. Break the loop and the bulb goes dark. That's the entire physical basis of computing.
This next step is where computing begins. Stop thinking "the bulb is lit." Start thinking "the wire is carrying a 1." Voltage present = 1 = true = yes. No voltage = 0 = false = no. We just decided that electricity means information. Nothing in physics forced that choice. We made it up, and the whole industry runs on it.
What voltage actually is
Electricity in a wire behaves a little like water in a pipe. Voltage, measured in volts, is the push behind it. Current is how much actually flows. A battery supplies the push, and the wire gives it somewhere to go.
From here on we ask only one question about any wire: is there a push on it or not. That yes or no is the entire information.
Series and parallel, in plain words
Two switches are in series when the current has to get past the first one to reach the second, like two doors along a single corridor. Both have to be open for anything to get through.
They are in parallel when the current has a choice of two routes, like two doors into the same room. Either one being open is enough.
That's worth sitting with for a second. Nobody designed "AND" into the universe. It fell out of the shape of the circuit. Wiring switches one way gives you both; wiring them another way gives you either. Arrangement is logic.
Why two levels and not ten
A wire could carry ten different voltages and count from 0 to 9 directly, and a few early machines did work that way. The trouble is noise: every wire picks up small stray voltages from everything around it and the closer the levels sit, the more easily one is mistaken for its neighbour.
With only "clearly on" and "clearly off" there is a wide gap in the middle, so a signal can be knocked about quite badly and still be read correctly. Nothing later depends on this, so skip it happily.
The transistor: a switch with no finger
A hand-operated switch is useless for computing: a computer has to flip its own switches, billions of times a second. So we need a switch that is flipped by electricity instead of by a finger. That device is the transistor, and it is the single most manufactured object in human history.
A transistor has three connections:
- Gate: the control wire (the "finger")
- Source and Drain: the two ends of the switch (the "contacts")
Put voltage on the gate and current can flow from source to drain. Remove it and the path closes off. No moving parts, no wear, and it switches in well under a billionth of a second.
A switch with nothing that moves
Picture a garden hose lying across a table with your foot resting on it. Press down and nothing flows. Lift your foot and water runs. Almost nothing moved, and your foot never touched the water.
In a transistor the gate is the foot. Voltage on the gate changes the silicon just underneath it, enough to open or close a path for current, while taking nothing from the current it controls.
How fast is a billionth of a second
A billionth of a second is a nanosecond. Light, the fastest thing there is, crosses about 30 centimetres in one. A transistor can switch several times in that span.
One comparison makes the rest of the course easier: a nanosecond is to a second roughly as a second is to thirty years.
A modern phone chip holds roughly 15-20 billion transistors. If each transistor were a grain of rice, that chip would be a pile weighing about 400 tonnes. The smallest features are only a few dozen atoms wide, and the wires between them a few hundred atoms apart. We won't design at that level, but everything above is built from exactly this one component.
How anyone makes something a few dozen atoms wide
Chips are printed rather than assembled. Light shines through a patterned mask onto a wafer coated in a chemical that changes wherever the light lands, and the exposed parts are then washed away. Repeat with a few dozen masks and the layers of a chip build up.
The whole wafer is patterned at once, however many transistors the pattern contains, which is why the cost of a chip depends on its area rather than on how much is squeezed into it. Nothing later depends on this.
Floating outputs, and the pair that fixes them
One thing has been quietly missing. A voltage is never an amount on its own: it is always a difference between two points, the way a height is always a height above something. So every circuit picks one point, declares it to be zero, and measures everything else against it. That point is called ground, and the other end of the battery, held at the full supply voltage, is called the supply rail."This wire is carrying a 1" is short for "this wire has been joined to the supply rail", and "carrying a 0" is short for "joined to ground".
Why a difference, and not just an amount
A step is not two metres tall on its own. It is two metres above the floor. If you moved the floor, the number would change and the step would not. Voltage works the same way: a battery does not put 3 volts somewhere, it holds one terminal 3 volts above the other.
That is why every diagram from here on has two horizontal lines across it, one at the top marked +V and one at the bottom marked 0 V. They are the two things every other voltage is measured between, and every gate in this course is wired to both.
Which raises a question the last step stepped over. A single transistor can join the output wire to a rail. What is the output when the channel is closed and it is joined to nothing?
A wire joined to neither rail is floating. It is not a 0, and it is not a secret third value the machine can use. It is the absence of an answer and a meter on it reports whatever charge happens to be left over there. Two readings of the same floating wire need not agree. Nothing downstream can be built on it.
So a real circuit has to drive its output both ways: something has to pull it down to make a 0, and something else has to pull it up to make a 1. One transistor cannot do both, because it has one channel and one gate and it either conducts or it does not. Two can, if they are arranged so that exactly one of them is conducting for any input.
Could you not just use a resistor instead of the second transistor?
You can, and outside a chip people often do: a resistor from the wire up to the supply rail holds it at 1 until a transistor pulls it down. It is called a pull-up, and it is how a push-button gets wired to a real circuit board. Embedded Systems builds one.
Inside a chip it is a bad bargain. While the transistor is pulling down, the resistor is still pulling up, so current flows the whole time the output is 0, and a few billion of those adds up to a hot chip and a flat battery. A second transistor costs almost no area, switches fully off, and draws nothing while it sits there. That is the trade the whole industry made.
Two transistors, and you own your first gate outright. Feed the pair a signal and the output is always the opposite of it, always driven, and always at a full rail voltage. That is a NOT gate, also called an inverter. It is the thing nothing in the first two steps could do: turn a 1 into a 0.
Why "complementary", and where the name CMOS comes from
Two things are complementary when each one is exactly what the other is not. The pair here is complementary in that sense. The PMOS conducts when its gate is low and the NMOS when its gate is high, so for any input one is open and the other is shut. There is never a moment when both are.
Almost every chip made today is built this way, and the technology is named after it: CMOS, for complementary metal-oxide-semiconductor. The metal-oxide-semiconductor part is the sandwich from the last step, a metal plate over an insulating oxide over silicon. The C is the pair.
Logic gates
Nobody designs chips transistor-by-transistor any more than a novelist thinks about ink chemistry. We package a few transistors into a gate: a box with input wires, one output wire, and a fixed rule. From here on, transistors disappear from the story. This is our first act of hiding a layer.
"Gate" again? It meant something else a minute ago
It did, and the clash is unfortunate. On a transistor, the gate is the control wire. A logic gate is a different thing: a small circuit of a few transistors, drawn and used as one box, with a fixed rule from its inputs to its output.
From now on the box is what we draw, and the transistors inside it stop being mentioned. That is the bargain at every layer: fewer details, bigger ideas.
There are only a handful of gates worth knowing, and you already invented two of them with light switches.
What a truth table is, exactly
A truth table lists every combination the inputs can be in, one per row, and what the output does for each. Two inputs that are each 0 or 1 give four rows, and those four are every case there is.
That makes it the complete definition of a gate. Two circuits with the same truth table behave identically, however differently they are wired inside, and we lean on that fact all the way to Step 15.
Where the gate names come from
AND, OR and NOT mean roughly what the English words mean. An N on the front means "and then flip the answer", so NAND is not-and and NOR is not-or.
XOR is short for "exclusive or", and it means one or the other but not both. That is closer to how people usually use the word "or" in speech than plain OR is, which is why OR surprises beginners more often than XOR does.
NAND and NOR from four transistors
The last step built a gate with one input. Gates with two inputs are built the same way, and the whole design decision is a choice you already made in Step 1 with a bulb and two switches: series or parallel. Two transistors in series only conduct when both are open. Two in parallel conduct when either one is.
A gate has a pull-down side made of NMOS below the output and a pull-up side made of PMOS above it, and the two sides have to be opposites of each other. Where one needs both of its transistors, the other needs either of its own. Get that wrong and the output floats for some inputs and shorts for others, which is the failure you just met.
Why the pull-up side is opposite, and not the same
Take the two NMOS in series, below the output. They pull the output down only when A and B are both 1. For every other input the output must be pulled up instead, so the pull-up side has to conduct whenever A and B are not both 1, which is to say whenever either of them is 0.
A PMOS conducts when its gate is low. So "either input is 0" is two PMOS in parallel. The two sides say the same thing from opposite directions, and that is what makes exactly one of them conducting for every input.
NAND costs four transistors. NOR costs four. AND costs six, because the pair is naturally inverting. The cheapest thing four transistors can do is answer "not both", so to get "both" you bolt an inverter on the end and pay for two more. OR costs six for the same reason. NOT costs two.
That price list is the answer to something Step 3 asserted and could not show. A factory would rather be good at manufacturing one kind of gate, and the kind it picks is NAND, because NAND is what the silicon wants to make. The friendly-sounding gates, the ones named after English words, are the expensive ones.
Why not build a three-input gate the same way
You can, and chips do. Three NMOS in series below and three PMOS in parallel above gives a three-input NAND for six transistors, which is cheaper than two two-input NANDs plus an inverter.
It stops paying off quite quickly. Each transistor added to a series stack makes the pull-down weaker and slower, because the current has to get through all of them, so a stack of eight is unusable in practice even though it is correct on paper. Four is a common limit. Nothing later in this course depends on knowing that.
Where the little circle on a gate symbol comes from
Step 3 drew NAND and NOR with a small circle on the nose, and called it the answer being flipped. Now it has a physical cause. The circle marks an inversion, and the inversion is not something added to the gate: it is what a complementary pair does when you drive its gates and read its output.
Which is why the gates without a circle are the ones with more transistors in them. An AND symbol has no circle, and the reason is that a circle has been cancelled by a second one you cannot see, drawn inside the box as two more transistors.
From a truth table to a circuit
Here is the part that makes everything after it possible, and it is a recipe rather than an insight. Write down what you want as a truth table. Then: one AND for every row whose output is 1, with a NOT in front of each input that has to be 0 in that row, and finally one OR across all of them. That circuit computes that table. Always. For any table, of any size.
Each of those ANDs is called a term, and a term is 1 for exactly one row of the table and 0 for every other row. Since no two rows can happen at once, at most one term is ever 1, so an OR across the terms is 1 exactly when the table says 1. The whole construction is called a sum of products, because an OR was once written as a sum and an AND as a product.
Why an AND is a "product" and an OR is a "sum"
Treat 0 and 1 as numbers for a moment. Multiply them: the answer is 1 only when both are 1, which
is exactly AND. Add them, and cap the answer at 1: the answer is 1 when at least one of them is, which
is exactly OR. So an AND behaves like multiplication and an OR like addition, and the older books
write them as AB and A + B.
You do not need that notation here, and this course keeps writing AND and OR in words. The name "sum of products" is worth knowing anyway, because every book and every chip designer uses it.
What "three-input AND" means on the palette
AND3 is an AND gate with three input pins instead of two, and it outputs 1 only when all three are 1. It is drawn with the same symbol, because the number of inputs is read off the wires rather than the shape. The last step built one out of transistors: three in series below, three in parallel above.
Two two-input ANDs chained together do the same job, so you never strictly need it. It is on the palette because a term over three inputs is one gate rather than two, and the recipe reads more clearly when a term is one gate.
The recipe leans on two rules for moving an inversion around, and both are worth having by name. The first is De Morgan's law: an inversion moves through a gate by swapping AND for OR, or OR for AND, and inverting both of the inputs. NOT(A AND B) is the same as NOT A OR NOT B. The second is double negation: two inversions on one signal cancel. The tempting mistake is to move the inversion and forget to swap the gate, and that gives a circuit that is not the one you started with.
Is the recipe ever the best circuit?
Sometimes, and not often. For a table with a single 1 in it the recipe gives exactly one term and there is nothing to save. For most tables there is something to save. Finding the smallest circuit for a given table is a hard problem in general, and the tools chip designers use spend real computer time on it without always finding the best answer either.
Which is why the recipe matters more than the shortcuts. A correct circuit you can always get in a minute beats a small circuit you might get eventually, and every automatic tool starts from the recipe and improves it. Nothing later in this course needs the shortcuts.
Everything from NAND
Step 3 promised that every other gate can be built from NAND gates alone, and asked you to take it. You can now work it out instead, in two moves. The recipe from the last step turns any truth table into a circuit made of nothing but ANDs, ORs and NOTs. So if each of those three can be built out of NANDs, then every truth table there is can be built out of NANDs, and there is nothing left to prove.
All three are short. A NAND with the same wire fed into both of its inputs is a NOT, because the only rows that can now happen are 0,0 and 1,1. A NAND followed by that NOT is an AND. And an OR is De Morgan's law wired up: invert both inputs, then NAND them.
Getting a NOT gate out of a NAND, slowly
Feed the same wire into both inputs of a NAND. The only rows that can now happen are 0,0 and 1,1. NAND outputs 0 only when both inputs are 1, so 0,0 gives 1 and 1,1 gives 0.
The output is the opposite of the input, which is a NOT gate. Every other construction starts from that: build the pieces you need, then flip whatever came out the wrong way round.
Notice which direction the saving runs in. Built out of transistors, NOT costs two and NAND costs four, so a NOT out of a NAND costs four rather than two and is a waste on its own. What you buy for that waste is a factory that only has to be good at one thing. You also buy a design you can shave afterwards, because a NAND followed by a NAND often collapses into fewer gates than the recipe asked for.
Is NAND the only gate that can do this?
No. NOR can do it too, by the mirror image of the same three constructions, and for the same reason: it is a gate that inverts and it can be made to ignore one of its inputs. A gate with both of those properties is called universal, and NAND and NOR are the only two-input gates that are.
AND is not universal, and neither is OR, because nothing built from them can ever turn a 1 into a 0. That is the wall Step 1 ran into with switches, and it took a second kind of transistor to get over it. Nothing later depends on this.
Two transistor types make a pair. A pair makes NOT. Two pairs make NAND. NAND plus the recipe makes every truth table there is. From here the transistors really can drop out of the story, and when they come back it will be to answer a question about cost or about time rather than about whether something is possible.
"Truth table" and "term", in one place
A truth table lists every combination the inputs can be in, one row each, and what the output does for each. Two inputs give four rows, three give eight, and n inputs give 2 to the power of n. A table is the complete description of a gate or a circuit: two circuits with the same table behave identically, however differently they are wired inside.
A term is one AND from the recipe, covering one row of the table. A circuit built as an OR across terms is a sum of products. Those three words are the whole vocabulary needed for the rest of this course.
How long a gate takes
A gate does not answer the instant its inputs change. Its output is a small store of charge, and the transistors underneath have to move that charge before the next gate can read it. The wait is called propagation delay, it is measured in picoseconds, and for the gates in this course it runs from about 12 ps for a NOT to about 45 ps for an XOR.
Delays add. If a signal has to pass through four gates to reach the output, the output cannot be right until all four have had their turn, one after another. So the speed of a circuit is set by its critical path: the longest run of gates between anything holding a value and anything else. Not the longest wire. The most gates.
How long is a picosecond
A picosecond is a thousandth of a nanosecond, and a nanosecond is a thousandth of a millionth of a second. Light crosses about a third of a millimetre in one picosecond, which is roughly the width of three human hairs.
Two numbers to hold on to. A 3 GHz clock ticks once every 333 picoseconds, so a gate at 20 ps fits about sixteen deep inside one tick. And a signal crossing a centimetre of wire on a chip takes around 60 ps, which is more than one gate, which is why long wires eventually matter too.
Every timing question from here on is the same question: how long is the critical path. A clock that ticks faster than the critical path asks a circuit for an answer it has not finished working out. What it gets back is not a slightly wrong answer. It is whatever the wires happened to be carrying at that instant.
Which brings the awkward part. While a circuit is settling, its wires carry values that are simply wrong: some signals have arrived and others have not, so the gates in the middle are working on a mixture of old and new. An output can move to a value it is not going to keep, and then move again. That is a glitch. It is not a fault to be fixed. It is what settling looks like.
Why not just look at the output when it is right
Because nothing in the circuit knows when that is. A gate has no way to tell a settled input from an unsettled one: it sees a voltage and it responds. If a glitch reaches something that remembers, the wrong value gets stored and no amount of settling afterwards will take it back out.
So the answer is to wait, on purpose, for longer than the critical path, every time, whether the circuit needed it or not. Step 10 gives that waiting a name and a wire, and Step 17 is where a design is chopped up so that the waiting can be made shorter.
Where a gate's delay number comes from
It is measured, not derived. A factory characterises each gate in its library over temperature, supply voltage and how much load is hung on the output, and ships a table. The numbers in this course are one plausible set, chosen so that the arithmetic the page does out loud is the arithmetic the model does. NAND is 18 and NOT is 12, so AND is 30, because an AND really is a NAND with a NOT after it.
Real tables are messier. A gate is slower when it is driving more gates, slower when the chip is hot, and slower when the supply voltage sags, and a design has to work at the worst combination of all three. Nothing later depends on this.
Counting in binary
Our wires only hold 0 or 1. To handle numbers bigger than one, we use more wires, the same way you handle numbers bigger than nine by using more digits.
One wire's answer, a single 0 or 1, has a name: it is a bit. The word is short for binary digit, and a bit is the smallest piece of information there is, because nothing is smaller than a plain yes or no. Eight wires side by side carry eight bits, and from here on we count bits the way you count digits.
In the decimal number 407, each position is worth ten times the one to its right: 4 hundreds, 0 tens, 7 ones. Binary works identically, except each position is worth two times the one to its right: 128, 64, 32, 16, 8, 4, 2, 1. There is no deep difference. Ten fingers gave us base 10; two voltage levels give us base 2.
Reading a binary number by hand
Write the column values above the bits, biggest on the left: 128, 64, 32, 16, 8, 4, 2, 1. Then add
up the columns that have a 1 underneath. So 00001011 is 8 + 2 + 1 = 11.
Going the other way, take the biggest column value that fits and keep going with what is left. For
100: 64 fits, leaving 36; 32 fits, leaving 4; 4 fits, leaving 0. Bits on for 64, 32 and 4 gives
01100100.
1111 is 15, and the next column is worth 16. Eight bits (a byte) covers 0 to 255.Hexadecimal: binary for humans
0110110110110101 is unreadable and easy to miscopy. So engineers chunk bits into groups of
four and give each group a single symbol: 0-9 then A-F. That's hex. One hex digit = exactly 4 bits,
which is why you'll see hex everywhere in this page: 0x6DB5 is the same 16 bits, but you can
actually read it aloud.
Why sixteen symbols, and why letters
Four bits have sixteen patterns, 0000 up to 1111, which is 0 to 15. Ten
of those already have digits, so six more symbols were needed and the alphabet was to hand: A is 10,
B is 11, and so on to F for 15.
The 0x in front is only a label meaning "read what follows as hex", so that
0x20 is not mistaken for twenty.
What that little raised 5 means
25 is five 2s multiplied together: 2 × 2 × 2 × 2 × 2 = 32. The small raised number counts how many 2s there are, and says nothing about what to multiply by.
These are the powers of two, and they are worth half-knowing by sight: 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024. They come up constantly, because each extra bit doubles how many different things a group of wires can say.
0x1F. You pick up one more coin. What does it show?Building an adder
Time to make the machine actually do arithmetic. Add two bits and there are exactly four cases:
0 + 0 = 0
0 + 1 = 1
1 + 0 = 1
1 + 1 = 2 ← doesn't fit in one bit! Write 0, carry 1.Look at the two output columns. The sum bit is 1 when the inputs differ, which is XOR. The carry bit is 1 only when both are 1, which is AND. Two gates, and we can add. This is called a half adder.
Carrying, the way you already do it
Adding 7 + 5 on paper, you write 2 and carry 1, because 12 will not fit in a single digit column. Binary uses the same rule with a smaller column: 1 + 1 is 2, which will not fit in one bit, so you write 0 and carry 1.
The adder's two output wires are exactly the two things you write down: the digit that stays in this column, and the one that moves to the left.
00 = 0,
1+0 = 01 = 1, 1+1 = 10 = 2. Two gates, doing arithmetic.The full adder
The half adder has a flaw: to add multi-bit numbers, each column must also accept a carry coming in from the column to its right. So we need three inputs: A, B, and Carry-in. Chain two half adders and OR their carries, and you have a full adder, the workhorse of all computer arithmetic.
Why three inputs and not two
Do a column addition on paper and look at any column except the rightmost. It has three things coming into it: the two digits, plus whatever was carried in from the right.
A half adder can only cope with two, so it can only ever do the rightmost column. A full adder handles the general case, which is why the machine we chain together in a moment is built from full adders.
11 = 3. Correct.
The OR at the end is right because a carry can never be generated by both half adders at once.Chaining them: the ripple-carry adder
Now the payoff. Line up eight full adders, one per bit column, and wire each carry-out into the next adder's carry-in. That's a machine that adds two 8-bit numbers, exactly like the column addition you learned in primary school, done in wire.
Where "ripple" comes from, and how it gets beaten
The carry has to travel one column at a time, like a rumour going down a line of people, so the leftmost answer is not trustworthy until the message has reached the end. Eight columns means eight delays stacked up.
A carry-lookahead adder works out separately, and all at once, whether each column will create a carry or merely pass one along, then computes every carry in one go. It costs many more gates and is much faster. Nothing later in the course needs it.
Negative numbers (and why subtraction is free)
We can add. Can we subtract? Building a whole second machine for subtraction would be wasteful, and it turns out to be unnecessary, because of a trick called two's complement.
Think of a 3-digit odometer. Roll it back one click from 000 and you get 999. So on that odometer, 999
behaves like −1: add 1 to it and you're back at 000. Binary works the same way. In 8 bits,
11111111 behaves exactly like −1, because adding 1 rolls it over to 00000000.
The odometer, done with real bits
Start at 00000000 and roll back one click. Every wheel turns over and you land on
11111111. Add 1 to that and the carries run all the way off the left-hand end, leaving
00000000 again.
So in every sum, 11111111 and −1 do the same thing. The hardware never decides which
of the two it "really" is. That reading is ours to choose.
The rule: to negate a number, flip every bit and add 1. Then throw your subtractor away:
A − B is just A + (−B), computed by the adder you already built.
"Flip every bit and add 1", worked through once
Take 5 in eight bits: 00000101. Flip every bit and you get 11111010. Add
1 and you get 11111011. That pattern is −5.
Check it by adding 5 back: 11111011 + 00000101 rolls over to
00000000, with the last carry falling off the end. Which is what −5 + 5 ought to give.
Two's complement is a design decision that removes hardware. One adder now handles addition, subtraction, comparison, and negation. Great engineering usually looks like this: not a cleverer machine, but a representation that makes the machine unnecessary.
Signed and unsigned: the same bits, two answers
11111011 is 251 if you read it as a plain positive number, and −5 if you read it as
two's complement. Both readings are correct. The bits carry no hint about which was meant.
That is why programming languages make you say which kind you want, and why mixing the two up produces bugs the machine cannot notice on your behalf.
Two of the buttons use an idea we have not built yet. << 1 slides every bit one place to the left, which doubles the number, the same way sliding a decimal number left multiplies it by ten. >> 1 slides them one place right, which halves it. Sliding right leaves a gap at the top, and the two RIGHT SHIFT buttons decide what gets fed into it: a copy of the sign bit, so a negative number stays negative, or a plain 0.
FLAGS are four one-bit answers the machine keeps about the result it has just produced. ZERO means the answer was 0. NEGATIVE means the top bit came out 1. CARRY-OUT means the unsigned answer needed one more bit than there was room for. OVERFLOW means the signed answer went out of range, the way 127 + 1 does in a signed byte, which is the first of the presets above. Step 8 is where flags start doing real work. Here they are something to watch.
01111111. Add one and it becomes 10000000,
and in two's complement a leading 1 means negative, so the score reads −128. Nothing broke and nothing
warned you: the adder did exactly its job, and the interpretation fell off a cliff. This is the
shape of a whole family of real bugs, where a health bar, an altitude or a follower count suddenly goes
hugely negative.Compute everything, then pick one
A program is a list of orders for the machine, and one of the orders people write most often is "if this is true then do that, otherwise do the other thing". Hardware has no way of doing that. Every circuit on the chip is powered all the time and is computing all the time. A wire cannot decide to sit this one out. So how does a processor ever make a choice?
It cheats: it computes everything at once and then picks one answer. The picker is called a multiplexer, or mux: a data selector with several inputs, one output, and control wires that say which input wins. It's the traffic switch of the whole chip.
A multiplexer as a railway junction
Several tracks come in, one track leaves, and a lever decides which incoming train carries on. The trains on the other tracks are real and still moving. They simply do not get the junction.
Swap the trains for numbers and the lever for a couple of control wires, and that is a multiplexer.
Why n select wires choose between 2n inputs
Each select wire is a yes or a no, so two wires have four combinations: 00, 01, 10, 11. One combination per input. Three wires give eight combinations, and so on.
It is the torch counting from Step 4 doing a job. A group of wires can name one thing out of two to the power of however many wires there are.
In the picture above, a mux is the tall wedge marked MUX. A diagram of a whole chip has no room for that shape. There it shrinks to a small narrow box wedged between the bigger blocks, with several wires arriving and one leaving. You will find three of them in the finished CPU, and each one is a place where the machine makes a decision: which number to feed the ALU, where to take the result from, which register to write. Muxes are where a processor's choices live.
What is a register?
A register is a small box inside the processor that holds one number, ready to be used right now. Picture the two or three sheets of scrap paper on the desk in front of you: not much room, but everything on them is within arm's reach. Our processor will have eight of these boxes, named R0 to R7.
We build one properly in Step 11, out of the remembering circuit from Step 9. Until then, whenever a sentence says "register", read it as "one of the eight little boxes the processor keeps its working numbers in".
The same idea run backwards
A mux takes many inputs and passes one along. Run the idea the other way and you get a demultiplexer: one input, many outputs, and control wires deciding which output the value reaches. The vending machine in the question above really wants one of those.
Both are the same thought about naming one thing out of many, so you can leave the second name behind safely. The processor we build uses only muxes.
The ALU
Now we can build the first component a computer engineer would recognise by name. The Arithmetic Logic Unit takes two numbers and an operation code, and produces a result. Internally it's exactly the trick from Step 7: run an adder, an AND, an OR, an XOR, and a comparator all at the same time, then let a mux pick the one the op-code asked for.
AND took one bit on each input. How can it take two whole numbers?
It does not, quite. An 8-bit AND is eight separate AND gates standing side by side, one for each column. The first gate is fed bit 0 of A and bit 0 of B, the second gets bit 1 of each, and so on up the row. Every gate answers only for its own column, and nothing travels sideways.
That is the same widening trick as Step 5, where eight full adders side by side made an 8-bit adder. The one difference is that adding has to pass a carry along the row, and AND, OR and XOR do not, which is why they are the quickest things in the ALU.
What an op-code is
A number that names an operation. Say 0 means add, 1 means subtract, 2 means AND, and now a few wires carrying a number are enough to tell the ALU which job you want done.
Which numbers mean what is decided by whoever designs the machine. Step 12 is where we choose ours and write the list down properly.
It also reports flags, little status bits describing the result. Zero is the
important one. Every time a program asks "are these two numbers the same?", the machine answers by
subtracting one from the other and looking at the Zero flag. A 1 there means they matched.
How subtracting answers "are these equal?"
To ask whether 42 and 42 are equal, the machine subtracts one from the other and looks at the answer. 42 − 42 is 0, the Zero flag comes on, and the answer is yes.
Try 42 − 41. The result is 1, the Zero flag stays off, and the two were not equal. One subtraction settles every equality question the machine will ever be asked.
if statement you've ever written eventually gets decided.
Then try SLT (set-if-less-than), which outputs 1 or 0. That's < in hardware.The other flags a real ALU reports
Alongside Zero, most processors keep Carry (the answer needed one more bit than there was room for), Negative (the top bit came out 1) and Overflow (the signed answer went out of range, like the 127 + 1 from Step 6).
Programs read them to catch exactly the accidents Step 6 showed. TOY-16 only needs Zero, so treat the other three as interest rather than homework.
Memory: making a circuit remember
Everything so far is combinational: outputs depend only on the inputs right now. Remove the inputs and the answer evaporates. But a computer must hold values while it works on them: a calculator that forgot the first number would be useless.
What "combinational" means, and why it needs a name
A combinational circuit is one whose output depends only on what its inputs are doing right now. Every gate, adder and mux so far has been one. Take the inputs away and nothing is left behind.
The word for the other sort, where the answer also depends on what happened earlier, is sequential. This step is where our machine grows its first sequential part.
The trick is almost absurd. Take the output of a gate and feed it back into its own input. The circuit now has a history: it can sit in one of two stable states forever, holding a bit. A circuit with exactly two states it can rest in is called bistable:"bi" for two,"stable" for sits still. The plainest one there is has a name of its own, the SR latch, after its two inputs SET and RESET.
Why a loop of gates can hold a value
Take two NOT gates in a ring. If the first outputs 1, the second outputs 0, and that 0 goes back into the first, which keeps it outputting 1. The ring agrees with itself, so it sits still.
Start it the other way round and it agrees with itself just as contentedly at 0. Two arrangements that both hold, which is one bit remembered, with nothing anywhere that "saves" anything.
Press SET and RESET together and the latch goes into a nonsense state: both outputs equal, and when you release, it settles unpredictably. Circuits that can enter unpredictable states are unacceptable in a processor, which is why the raw SR latch is never used directly. The fix is the next widget.
The D flip-flop: memory you can trust
We want a box with one data input, one output, and one rule: copy D to Q only at the instant the clock ticks; ignore D completely the rest of the time. That's a D flip-flop. It is the single most important component in synchronous digital design. Almost everything in the rest of this course that remembers a value is built from these.
SET, RESET, D and Q: what the letters stand for
SET means "make it 1" and RESET means "make it 0". D is the data input, the value waiting to go in, and Q is the output, the value being held at the moment.
Q is the conventional label for the stored output; it is not an abbreviation used in the circuit. "Synchronous" in the paragraph above means the state changes on the shared clock edge.
Try: wiggle D as much as you like and Q won't move. Now hit the clock, and Q snaps to whatever D was at that moment. Then read the bottom row from the left: Q is a copy of whatever D happened to be at each dashed line, and nothing else. That discipline ("change only on the edge") is what keeps a billion-transistor chip from descending into chaos.
The clock
A processor's clock is a wire that alternates 0,1,0,1,… forever, driven by a quartz crystal. It carries no data. Its only job is to tell every flip-flop on the chip "now".
This turns a tangle of gates with messy, unequal delays into a machine that advances in clean discrete steps. Between two ticks, signals scramble through the logic and settle down; on the tick, the flip-flops capture whatever has settled. The rule that sets the speed limit for the whole chip:
Ticks per second, and how long one tick lasts
Frequency is how many ticks happen per second. The period is how long one tick lasts, and each is one divided by the other. At 3 GHz there are three billion ticks a second, so one tick lasts a three-billionth of a second, which works out at about 333 picoseconds.
A picosecond is a thousandth of a nanosecond. Light gets about a third of a millimetre in one.
The clock period must be longer than the slowest path between any two flip-flops. One sluggish circuit anywhere on the chip slows down everything. This single sentence explains most of what chip designers spend their careers doing.
Try: push the clock faster than the logic can settle and watch the register capture a mixture of arrived and still-old bits. Real chips can also enter a temporarily undecided, metastable state. This is the same timing mistake that makes an overclocked PC crash. Run in reverse, it also explains why “undervolting” is safest at lower speeds.
How a lump of quartz keeps time
A slice of quartz cut to a particular size flexes at one particular rate, the way a tuning fork sounds one note. Squeeze quartz and it produces a small voltage; apply a voltage and it flexes. Wire those two facts into a loop and it hums at its own rate, millions of times a second, and drifts very little.
The same component keeps a wristwatch honest. On a chip, its steady hum is multiplied up to the gigahertz the processor runs at.
Why the clock is the most awkward wire on a chip
Every flip-flop needs the tick, so the clock has to reach millions of places, and it has to arrive at all of them within a whisker of the same moment. Arriving late in one corner is called clock skew. It eats into the same slack the question above worked out.
Designers grow a carefully balanced tree of clock wires so every branch is about the same length. Nothing later depends on this.
Registers and the register file
One flip-flop stores one bit. Line up 16 side by side, wired to the same clock, and you have a 16-bit register, a box holding one number, updated all at once.
A CPU needs a small pile of these for scratch work. Ours will have eight registers named R0-R7. They're the fastest storage in the machine: no address decoding, no waiting, right next to the ALU. This is what people mean when they say a variable "lives in a register".
The pile is packaged as a register file with a very specific set of ports, chosen to match what one instruction needs: read two values, write one value, all in the same clock cycle.
What a "port" is
A port is a bundle of wires with one job, together with the wires that say which register it should be looking at. A read port carries a register number in and that register's value out.
Two read ports means two of those bundles side by side, so two different registers can be looked at in the same instant. It is not one bundle being used twice in quick succession.
RegWrite to be on. RegWrite is the enable signal that decides whether
the selected register changes on the clock edge. Reads remain combinational in this design.Main memory (RAM)
Eight registers isn't much. Bulk storage lives in RAM: a big array of cells. An array is a row of boxes all the same size, numbered from 0 upwards, so you can name any one of them by giving its number. Here you supply that number, called the address, and get back the data stored there. RAM is slower than a register (further away, and it needs address decoding), which is precisely why registers exist.
What "address decoding" means
A memory with 1024 cells has to turn a 10-bit address into "wake up exactly one of these 1024 cells, and leave the other 1023 alone". The circuit that does it is a tree of gates called a decoder, and like all logic it takes time to settle.
The register file barely does any of this, because it is choosing between eight boxes rather than thousands. Small and near is the whole of its advantage.
Registers and RAM, as a desk and a filing cabinet
Registers are the few sheets of paper on the desk in front of you. One glance and they are in your hands. RAM is the filing cabinet across the room: far more room in it, but you have to stand up, find the right drawer, and walk back.
Nobody works out of the cabinet directly. You fetch what you need onto the desk, do the work there, and put the results back. Load and store instructions are the walking.
ADD R1, R2, R3 must fetch R2 and R3 in the same cycle.
The hardware's shape is dictated by the instruction set's shape. Design decisions at the top ripple all
the way down to the wires.Designing an instruction set
We have parts. Now we need a plan: what should this machine be able to be told to do? The list of commands a processor understands, and their exact binary encoding, is the instruction set architecture (ISA). It's the contract between hardware and software: the only thing programmers see, and the thing the hardware must implement exactly.
We'll design a small RISC machine. RISC means Reduced Instruction Set Computer: few instructions, all the same size, all simple, memory touched only by dedicated load and store instructions. It's the philosophy behind MIPS, ARM and RISC-V, which is to say behind essentially every phone and, increasingly, every laptop on Earth.
Reduced from what, exactly?
Before RISC, the fashion ran the other way: hundreds of instructions, of different lengths, some of them doing quite elaborate jobs in a single go. That style got the name CISC afterwards, for Complex Instruction Set Computer, and the x86 chips in most desktops are its descendants.
Fewer, simpler, same-sized instructions turned out to be easier to make fast, and modern x86 chips quietly chop their complicated instructions into simple ones inside. Safe to skip.
The complete instruction set
Fifteen instructions. That's the entire vocabulary of the machine, and it is enough to compute anything computable, given enough memory and patience.
"Anything computable" sounds like a very big claim
It is, and it holds. In the 1930s Alan Turing worked out what the smallest possible complete machine has to be able to do and the list is startlingly short: add, compare two things, read and write memory, and change what it does next based on a comparison. TOY-16 can do all four, so anything any computer anywhere can work out, TOY-16 can work out too.
Slowly, and only if you hand it enough memory. Speed and room are what separate it from the chip in your phone, not ability. Nothing later in the course depends on this, so it is safe to enjoy and move on.
I have not seen != before
!= is read "is not equal to". It is the ≠ sign from maths, typed on a keyboard that has
no ≠ key, so an exclamation mark stands in for "not". Rs != Rt means "Rs and Rt are holding
different numbers".
Its partner == means "is equal to". It is doubled up so it cannot be confused with a
single =, which in most programming languages means "put this value in here" rather than
"these two are the same". Both turn up in the table above: BEQ jumps when two registers are
equal, BNE jumps when they are not.
Rs, Rt, Rd: which register is which?
Rs and Rt are the two registers an instruction reads. The s is for source; the t is just the letter
after it, for the second one. Rd is the register it writes, d for destination. So
ADD Rd, Rs, Rt reads two registers and writes a third.
Some instructions have no room for three register fields. ADDI Rt, Rs, imm spends part of
the word on the constant, so it has only two, and the write goes to Rt instead. The rule that never
changes is the order on the line: whatever an instruction writes to is named first.
That is what the machine can be told to do. Next comes the harder half of the contract: turning each of these lines into a number the hardware can actually read.
Packing an instruction into sixteen bits
One more piece of vocabulary first. A word is what a machine calls its natural bite of bits, and every machine picks its own size. TOY-16's word is sixteen bits, which is why a register holds sixteen bits, one slot of memory holds sixteen bits and one instruction is exactly one word long.
Meet TOY-16
Our CPU: 16-bit words, 8 registers, 16-bit instructions. Every instruction is exactly one word. The top 4 bits are the opcode (which operation), and the remaining 12 bits are laid out in one of three formats:
What a "field" inside an instruction is
A field is a fixed group of bits inside the instruction word with a fixed meaning: these three bits name the destination register, those six carry a constant, and so on. One word, chopped into labelled pieces.
Because the pieces sit in the same places in every format, the wires that read a field can be attached in one position and never move. That is what the caption above is getting at.
Assemble one by hand
Machine code is just numbers. Build an instruction below and watch its 16 bits appear. This is precisely what an assembler does, and what the CPU will decode in Step 15.
What an assembler is
Machine code is numbers, and writing programs as numbers is miserable work. So we write
ADD R1, R2, R3 instead, and a small program looks up the opcode, packs the register
numbers into their fields, and hands back the 16 bits.
That program is an assembler, and there is one waiting for you in Step 16. It does no thinking on your behalf: one line of text becomes one instruction, every time.
What an "immediate" is
An immediate is a constant written into the instruction itself, like the 5 in "add 5 to R1". It arrives with the instruction, instead of being fetched from a register or from memory first.
The name comes from the value being there immediately, with nothing to look up. It is also why the size of the instruction word puts a hard limit on how big such a constant can be, which is what the question below is about.
Why those numbers and not others
Four opcode bits, three register bits, six immediate bits. Those look arbitrary until you try to choose them yourself, so now that every word in the sentence means something, here is the choice as a machine you can operate.
The four challenges at the bottom are the interesting part, and challenge 1 cannot be solved at all, which is the point of it.
LUI to load the upper
bits, and ARM stitches constants together from pieces. The instruction word is a budget, and constants
are what you sacrifice first.One datapath, every instruction
Now we connect everything into one circuit that can execute any instruction in the set. Every instruction goes through the same five phases:
- Fetch: read the instruction at the address in the Program Counter
- Decode: split it into fields, read the register operands
- Execute: put the ALU to work
- Memory: access RAM, if this instruction needs it
- Write back: store the result into a register
The program counter (PC) is one more register, holding the address of the current instruction.
Add 1 to it each cycle and the machine walks through your program by itself. Load something else into it
and you have jumped. That's all a jump, a loop, a function call, or an if ever is.
The program counter as a finger on a list
Keep your finger on the line of a recipe you are working through. Finish the line, move the finger down one. That is the PC, and adding 1 to it is the whole of "and then do the next instruction".
Putting the finger somewhere else instead is a jump. Moving it back up is a loop, and deciding whether to move it based on a flag is a branch.
Data flows left to right: PC → instruction memory → registers → ALU → data memory → back to registers. Two loops break that flow: the write-back line curving along the bottom, and the next-PC line returning along the top. Those two loops are what makes it a computer rather than a calculator.
Now pick BEQ. Two more lines light up, and both of them run backwards. One carries the ALU's
Zero flag to the Next-PC logic, so the machine finds out whether the two numbers matched. The
other carries the sign-extended offset, which is how far to jump. That is the whole mechanism: a
comparison at one end of the chip deciding which instruction runs next. Every if and every
loop you will ever write comes down to those two wires.
What "sign-extended" means
A branch offset is stored in 6 bits, but it has to be added to a 16-bit PC. Padding it with zeros on the left would be fine for positive offsets and would turn every negative one into a large positive number, so every backward jump would fly off in the wrong direction.
Sign extension copies the offset's top bit into all the new bits instead. 111011 is −5
in 6 bits, and 1111111111111011 is −5 in 16 bits. Same value, more bits.
AND instruction is executing. It has nothing to do with memory. So what is
data memory doing during that instruction?RegWrite decide what counts; everything else is discarded work.
(Modern chips do add "clock gating" to switch off idle blocks, but that's a power optimisation bolted
on afterwards, not how the logic thinks.)Why real machines add 4 to the PC and not 1
Our instruction memory holds one whole instruction per numbered slot, so the next instruction is at PC + 1. Most real machines number memory in bytes, and one of their instructions occupies four bytes, so the next one sits at PC + 4.
Same idea, different unit of counting. Worth knowing only so that the 4 does not puzzle you the first time you read about a real processor.
Control signals from a truth table
The datapath is a city of roads with the traffic lights missing. The control unit supplies them. It's a small block of pure logic that takes the 4-bit opcode and outputs a handful of yes/no signals telling every mux which way to point and every memory whether to write.
And here is the punchline of the whole course: the control unit is just a truth table. Same device as Step 3, only wider. Opcode in, control signals out. Nothing more mysterious than the AND gate you started with.
Designing a control unit on a sheet of paper
Write the sixteen possible opcodes down the left of a page and put one column across the top for each control signal. Fill in each row with the 0s and 1s that instruction needs. You have now designed the control unit.
Turning that page into gates is mechanical work, and tools do it without being clever. The thinking was the table.
What a ROM is
ROM is read-only memory: a grid of cells whose contents are fixed when the chip is made. Give it an address and it hands back the word stored there. It never forgets, because nothing is being remembered so much as wired in.
A truth table with the opcode as the address is exactly the shape a ROM suits, which is why some processors keep their control table in one instead of building it out of gates.
MemToReg without MemRead writes a 0 into a register rather than a word from memory, because nothing is driving the memory output.What microcode is
Some processors go a step further and let one instruction walk through several rows of an internal table, so a single instruction becomes a short program written in a private language that nobody outside the chip ever sees. That is microcode.
It lets a manufacturer repair a mistake in a chip that has already shipped, by sending out a new table. Ours is a plain table with one row per instruction, and nothing later needs the idea.
SW (store word), RegWrite is 0. Why does that matter so much?RegWrite = 0. In hardware,"do nothing" must be
actively commanded.Your CPU, running
Everything is built. Below is the finished TOY-16: an assembler, the datapath from Step 14, the register file from Step 11, the ALU from Step 8, wired together and running.
Write assembly on the left. Press Assemble to turn it into machine code. Then Step through one instruction at a time and watch the wires light up, or press Run and let it fly.
How to read a line of TOY-16 assembly
Each line is one instruction: the name of the operation first, then what it works on. In
ADD R1, R2, R3 the destination comes first, so it means "put R2 plus R3 into R1".
Anything after a # is a note to yourself and is ignored.
A word followed by a colon, like loop:, is a label. It marks that spot in the
program so a branch can say "go to loop" and nobody has to count addresses by hand.
What pressing Assemble actually did
Assemble turned each line into one 16-bit number and laid those numbers out in instruction memory. Nothing has run yet. The machine code you can now see is the same sort of thing you built by hand in Step 13.
Step runs one instruction: the PC picks out a word, the control unit reads its opcode, the wires that matter light up, a result lands somewhere, and the PC moves on.
My program runs forever and I do not know why
Nearly always, the branch that should end the loop is never true. Check that the counter really changes on every trip round, and check which way the comparison points, since a loop that tests the wrong direction never finishes.
Stepping is the cure. Run five or six instructions by hand and watch the one register that ought to be moving. If it is not moving, you have found the bug.
You went from a bulb and a switch to a stored-program computer. Every layer is present and none of it was hand-waved: the ALU inside that simulator is the same adder logic you rippled carries through in Step 5, and the loop in your program works because of the flip-flop feedback trick from Step 9. A real CPU is this, with more instructions, more registers, and vastly more engineering for speed.
BNE R1, R2, loop and the PC does not jump to
loop. What must have been true at that moment?BNE means "branch if not equal", so it takes the jump when Zero is 0. Here
it didn't jump, so Zero must have been 1 and the registers matched. That inverting bit is the
BrNotZero signal from Step 15, and it is the only difference between
BNE and BEQ anywhere in the machine.SW instruction runs. Watch the registers: none of them
change. But the ALU definitely produced a number, and that number definitely arrived at the register
file's write port. Why is no register damaged?Pipelining
Our CPU does one instruction per clock tick, and the tick has to be long enough for the slowest instruction to crawl all the way from PC to write-back. Meanwhile the instruction memory sits idle for 80% of that time, having finished its job in the first phase.
Think of a laundromat. Wash, dry, fold. Doing one whole load before starting the next wastes two of three machines at all times. Instead, start washing load 2 while load 1 is drying. Each load still takes the same time, but loads come out three times as often.
Two different meanings of "faster"
Latency is how long one thing takes from start to finish. Throughput is how many things finish per hour. A load of washing still takes its full three hours; the laundromat simply finishes more loads in a day.
Almost every argument about computer speed turns out to be about which of those two the two people meant.
That's pipelining. Split the datapath into five stages with registers between them, and keep five instructions in flight at once.
Press ▶ Play and watch the blocks form a diagonal staircase. Any column holding more than one block is a moment when the machine is working on several instructions at once. Then press One at a time and watch the staircase stretch into a slow single line, which is what the processor in Step 16 was doing.
Watch the throughput number. Latency per instruction doesn't improve at all: each one still takes 5 stages. What improves is how many finish per second. Nearly every "performance" trick in computing is this same distinction.
Why cutting the work up lets the clock speed up
From Step 10: the tick has to be long enough for the slowest stretch of logic between two flip-flops. In our single-cycle machine that stretch runs the whole width of the datapath.
Put flip-flops in four places along the way and the longest stretch is now about a fifth as long, so the tick can be about a fifth as long too. No piece of logic got quicker. The work was cut into smaller pieces, and smaller pieces let "now" be called out more often.
Overlapping instructions like this creates a brand new class of problem, one that could not exist while the machine did one thing at a time. The next step is nothing but that problem and its fixes.
Pipeline hazards
Here are two ordinary instructions, one after the other:
ADD R1, R2, R3 # work out R2 + R3 and put it in R1
SUB R4, R1, R5 # take R5 away from R1On the single-cycle machine this was safe, because the first instruction was completely finished before the second one started. In a pipeline it is not. The second instruction reads its registers in ID, its second tick. The first instruction does not file its answer into R1 until WB, its fifth. The reader gets there first and picks up whatever R1 held before. That is a data hazard: the right instructions in the right order, giving the wrong answer, purely because they now overlap.
Remind me what IF, ID, EX, ME and WB are
They are the five phases from Step 14, shortened to two letters each so they fit in a table cell. IF is fetch the instruction. ID is decode it and read its registers. EX is put the ALU to work. ME is touch memory, if this instruction needs to. WB is write the result back into a register.
In a pipeline each of those is a separate tick, and five different instructions can be sitting in the five phases at the same moment. The tables in this step are one row per instruction and one column per tick.
Fix one: forwarding
The answer exists earlier than the register file admits. The ALU has finished computing R1 at the end of EX, three ticks before it is written back. So run an extra wire from the ALU's output straight back to the ALU's input, and let the next instruction take the value from there. That wire is called forwarding, and the lab below lets you switch it off and on.
Press Forwarding OFF and count the bubbles and the total. Then press Forwarding ON and watch them vanish, because a wire now carries the answer straight out of the first instruction's EX stage into the second one's, without waiting for it to be filed away in the register file. Nine cycles becomes seven, and that is one extra wire doing it.
Fix two: stalling, for when forwarding cannot reach
Forwarding can only hand a value backwards in space, never backwards in time. If the value does not exist yet at the moment the next instruction needs it, there is nothing to forward, and the only remaining move is to make the pipeline wait: freeze the instructions behind for a tick and let a bubble travel through instead. That is stalling. It is the fix of last resort, because a stalled tick is a tick in which the machine did nothing.
What is a compiler?
So far you have written TOY-16 assembly by hand, one line for one instruction. Almost nobody writes a whole program that way. People write in a language that reads more like maths and English, and a program called a compiler translates what they wrote into instructions like the ones you have been writing.
A compiler is an assembler that thinks. It decides which registers to use, works out the addresses, and, as the next lab shows, shuffles the instructions into an order that leaves the processor with less waiting to do. What comes out the other end is a list of ordinary instructions, no cleverer than yours, just chosen carefully.
The other hazard: not knowing where to go next
Data hazards are about values. The second kind is about addresses. When the machine fetches a
BEQ, it will not know whether the branch is taken until the ALU has done the comparison, three
ticks later, and by then it has already fetched two or three more instructions from the wrong place. That
is a control hazard.
The fix is to guess. The machine picks the more likely of the two paths, carries on fetching down it, and if the guess turns out wrong it throws that work away and starts again from the right address. This is branch prediction, and it is not the desperate measure it sounds: a loop goes round many times and exits once, so "assume the branch behaves the way it behaved last time" is right well over 95% of the time on real programs. Speculation of this kind is a core part of modern processor speed rather than a niche optimisation.
How guessing turned into a security hole
A processor that guesses runs ahead on work it may have to throw away. Throwing away the results is easy. Throwing away the traces is not, because data dragged into the cache during a wrong guess stays sitting there afterwards. That is where the Spectre and Meltdown security flaws of 2018 came from.
Spectre and Meltdown timed those leftovers to work out secrets the program was never allowed to read directly. Interesting, and entirely safe to skip.
There is a third kind of hazard, and it is the dull one
A structural hazard is two stages wanting the same piece of hardware in the same tick. Fetch wants to read memory while an older load is also reading memory, and there is only one memory.
The fix is to build more hardware, which is why a real chip keeps its instructions and its data in two separate caches instead of one. Nothing later in the course depends on this.
Caches and the memory wall
One inconvenient fact dominates modern computer design: processors got fast much quicker than memory did. A modern core can execute a few instructions per nanosecond. Fetching a value from main memory takes around 80 nanoseconds. That's hundreds of instructions' worth of standing still.
The fix is a cache: a small, very fast memory near the core holding recently used data. It works because real programs are predictable: they reuse the same variables (temporal locality) and walk through neighbouring addresses (spatial locality).
What a cache line is
Memory does not hand over one number at a time. It hands over a block of neighbouring bytes, usually 64 of them, called a cache line, because once the trip is being made the neighbours cost almost nothing extra.
So asking for one value quietly brings in the values sitting next to it. That is the whole reason walking through an array in order is cheap, and the question below turns on it.
Register: effectively free, since it's part of the instruction. L1 cache: ~4 cycles. L2: ~14. L3: ~50. Main memory: ~250. An SSD, the flash storage a laptop keeps its files on: ~200,000. Scale it up: if an L1 hit took one second, main memory would take about a minute, and reading an SSD would take over half a day.
L1, L2, L3: what the numbers mean
Caches come in a few sizes, stacked. L1 is tiny and sits right beside the core. L2 is bigger and a little further away. L3 is bigger again and usually shared between all the cores. A miss in one asks the next one out, and a miss in the last one asks main memory.
Each level trades size against speed, for the same reason your desk is smaller than the filing cabinet in Step 11.
I have not seen "big-O" before
Big-O is shorthand for how the amount of work grows as the problem gets bigger, ignoring constants. Both versions of that grid loop do a million additions, so both have the same big-O.
The point of the question is that the same big-O can still hide a difference of several times in real seconds, because counting operations says nothing about where the numbers were sitting when you asked for them.
Building it for real
Nobody draws these diagrams to make a chip. Engineers write the hardware down as text, in a hardware description language: Verilog/SystemVerilog or VHDL. It looks like programming, but it isn't: you are describing structure and simultaneous behaviour, not a sequence of steps. Everything happens at once, all the time.
"Describing" hardware, as opposed to programming it
In a program, one line runs and then the next one runs. In Verilog, every line you write is a piece of circuit that exists all the time. Two lines are two pieces of hardware, both live, both doing their job on every signal that arrives.
That is why the code below looks familiar and behaves oddly if you read it as a list of steps. Read it as a wiring diagram written out in words.
Here is our register file and ALU as real, synthesisable code. Compare it against the ALU you drove in Step 8 and the register file you clocked in Step 11. It is the same machine.
The punctuation in this code means nothing to me
A short key, so you can read it rather than stare at it. module … endmodule
wraps up one block of hardware and names its wires, the way we drew a box round a gate in Step 3.
[15:0] after a name means "this is not one wire, it is sixteen, numbered 15 down to 0".
3'd0 is a literal: three bits wide, written in decimal, value 0.
&, | and ^ are AND, OR and XOR applied one bit per column,
exactly as in Step 8. assign means "wire this permanently to that". <=
inside a clocked block means "load this on the next tick" rather than "less than or equal".
case picks one line out of many by matching a value, which is a mux written in words.
case.always @(*) and
always @(posedge clk). The first describes combinational logic: gates, no memory. The
second describes flip-flops. That one distinction is the practical form of everything in Steps 9-10.What "synthesisable" means
You can write plenty of Verilog that no factory could ever build: descriptions with no possible circuit behind them, or checks written purely to poke at the design while testing it. Code is synthesisable when a tool can turn it into real gates.
The unbuildable rest is still useful. It is what a testbench is made of, and testing on a laptop is where nearly all the bugs get caught.
From text to silicon
- Simulate: run the design against a testbench on your laptop. Catch bugs here; they get exponentially more expensive later.
- Synthesise: a tool converts your text into a specific netlist of gates.
- Place & route: decide where each gate physically sits and how wires run between them.
- Timing closure: prove no path is slower than the clock period. This is where the real work is.
- FPGA or ASIC: either load it onto a reconfigurable chip for about $50, or spend millions on photomasks and have a fab print it in silicon.
FPGA and ASIC, in plain words
An FPGA is a chip full of blank logic and switches that can be configured, over and over, to behave like whichever circuit you have described. Slower and dearer per chip, but your design is running the same afternoon, and a mistake costs nothing.
An ASIC is a chip printed to do one thing only. The masks that print it cost a fortune, so it pays only in large numbers, and a mistake means printing the whole thing again.
A $50 FPGA board plus free tools is enough to run a CPU like TOY-16 as real hardware on your desk, blinking real LEDs, within a weekend. That's not a metaphor or a simulation. It's your processor design, physically executing your program.
Interrupts, exceptions and privilege
TOY-16 runs one program until it reaches HALT. A useful computer cannot wait that long. A keyboard may receive a key, a disk may finish a transfer, and a timer must let the operating system share the processor. An interrupt is a request from outside the current instruction stream to handle an event.
An exception starts inside the instruction being executed: divide by zero, an unknown opcode, a forbidden memory access or a page that is not present. Both events use a trap. The processor saves enough state to resume, records a cause, switches to a trusted handler address and enters a more privileged mode.
Privilege protects the whole machine from ordinary programs. User mode cannot change page tables, disable interrupts or talk straight to devices. Kernel mode can. A system call is an intentional exception that asks the kernel to perform one checked service, then returns to the instruction after the request.
What state has to be saved?
At minimum, save the program counter for the return point, the previous privilege mode and the cause. The handler also saves any registers it will overwrite. Architectures divide that work differently, but the software contract must say who owns each part.
An interrupt normally resumes after the interrupted instruction. A fault may retry the same instruction after the handler repairs the cause, as a page fault does. The saved program counter must match that rule.
Can an interrupt arrive in the middle of an instruction?
The electrical request can arrive at any time, but the architecture normally presents a precise boundary. All older instructions appear finished, and younger ones appear not to have happened. The handler sees a state that belongs between two instructions.
That promise becomes harder in the out-of-order core from Step 23. The reorder buffer exists partly so completed work can become visible in order and a precise trap point can be recovered.
What about interrupt priority and nesting?
A controller may mask low-priority sources while a handler runs and allow a more urgent source to interrupt it. Each nested trap needs its own saved state. Unbounded nesting can exhaust the kernel stack.
Real-time systems also measure the longest interrupt-disabled interval and handler time. Continue with Real-Time Systems for latency accounting and priority interference.
Virtual memory and the MMU
A program uses virtual addresses. The memory chips use physical addresses. Between them, the memory management unit, or MMU, translates one fixed-size page at a time. Each program can therefore use the same convenient address range while its pages live in different physical frames.
A page-table entry stores the physical frame number plus permission bits such as valid, readable, writable, executable and user-accessible. The page offset is copied unchanged. If a translation is absent or the requested access breaks a permission, the MMU raises a page-fault exception instead of touching memory.
Walking a page table for every load would be slow, so the processor keeps recent translations in a translation lookaside buffer, or TLB. A TLB hit translates quickly. A miss walks the table and fills the TLB. A page fault means the table itself says the access cannot proceed yet or at all.
Why not give each program a different physical range?
Relocating every pointer would complicate loading and sharing. Virtual memory lets each process start from a consistent map, place guard pages around stacks, share selected pages and leave unused ranges unmapped.
It also permits demand paging, where a page is loaded only when first touched. That can save memory and startup work, but a storage-backed fault is thousands or millions of cycles slower than a TLB hit.
Does virtual memory make more RAM?
It creates a larger address space, not faster physical storage. Inactive pages may be moved to storage, but using them again causes slow faults. If active pages do not fit in RAM, repeated eviction and reload can make the system spend most of its time moving pages. That is thrashing.
Protection and flexible mapping remain useful even on systems that never swap a page to storage.
Why are page tables arranged in levels?
A flat entry for every possible virtual page would consume memory even for unused address ranges. A multi-level table allocates lower levels only where mappings exist. The virtual page number is divided into indexes, one per level.
Larger pages need fewer entries and cover more memory per TLB slot, but waste more space and provide coarser protection. Operating systems may mix page sizes.
0x12A and press Read. Repeat it to turn the TLB miss into a hit. Then try a write to a
read-only page and switch to Process B without flushing the process tag.Execute ready instructions out of order
A superscalar core can start more than one instruction per tick. An out-of-order core can start a younger instruction while an older one waits, provided its inputs are ready and its result cannot become visible in the wrong order. Fetch and decode still follow the program. Execution uses the available data and units.
Register renaming gives each new result a temporary physical register. This removes false dependencies caused only by reusing an architectural name such as R1. True dependencies remain: an ADD that needs a load's value must wait for that load.
Results enter a reorder buffer. They retire, or commit, in program order. If an exception or wrong branch occurs, younger entries are discarded and the last committed state remains precise. The program sees the same architectural results, in the same order, that a simple core would produce.
What are false and true dependencies?
Read-after-write is true: the reader needs the older result. Write-after-read and write-after-write can be false when the instructions merely reuse a name. Renaming sends the later write to a fresh physical register, so both values can coexist.
Memory dependencies are harder because two addresses may be equal only after calculation. A load-store queue checks addresses and can replay a load when an earlier store turns out to overlap it.
Is out-of-order execution the same as a compiler reordering code?
No. A compiler changes the saved instruction order under the language's rules. The processor keeps the original instruction order but schedules internal work dynamically from the values and delays it sees during this run.
Both must preserve observable behaviour. The processor also has to recover from branch guesses and precise exceptions while several instructions are in flight.
What limits instructions per cycle?
Decode width, rename width, queue size, execution units, register ports, cache bandwidth, dependency chains and branch accuracy all matter. A four-wide front end does not promise four retired instructions every tick.
The measured average is instructions per cycle, or IPC. It belongs to a particular program, input and machine state. A wider core often spends more power searching for independent work.
Keep private caches coherent across cores
Put two cores beside each other and each wants a private fast cache. If both cache address X, then Core 0 writes X, Core 1 must not keep reading its old copy. Cache coherence is the agreement about writes to one memory location.
A simplified MESI protocol labels each cache line Modified, Exclusive, Shared or Invalid. A core may read a Shared line. Before writing it must gain exclusive ownership, which invalidates other copies. A Modified line contains a newer value than memory and must eventually be written back or transferred.
Coherence does not give every operation one global order. Store buffers and speculative loads can make different addresses appear in surprising orders. The architecture's memory model states the allowed observations. Fences and atomic read-modify-write instructions add the ordering needed by locks and queues.
How do caches learn that another core wants a line?
Small systems may broadcast requests on a shared interconnect, called snooping. Larger systems use a directory that records which caches hold each line and sends messages only to them.
The exact protocol has more transient states than the four stable MESI names. Messages take time, cross and retry, so verification checks every allowed interleaving.
Does coherence prevent data races?
No. It eventually makes writes to one location visible according to protocol rules. It does not decide which thread should write first or make a group of ordinary operations atomic.
Software still uses locks, atomics or message passing. Continue with Concurrent Data Structures for compare-and-swap, memory ordering and safe reclamation.
What is false sharing?
Coherence works on whole cache lines. Two cores can update different variables that happen to share one line, causing ownership to bounce even though the variables do not logically interact. That is false sharing.
Padding or reorganising data can separate hot per-core variables. Measure first, because padding also increases memory footprint and can harm useful locality.
Do the same operation across many values
A scalar instruction adds one pair of numbers. A vector instruction can add several pairs at once. The processor divides a wide register into lanes, gives each lane the same operation, and stores several results. This is useful for pixels, audio samples, simulation cells and machine-learning tensors.
SIMD means single instruction, multiple data. Fixed-width SIMD instructions name a particular register width. A vector-length architecture instead tells the processor how many elements remain and lets each implementation handle as many as its hardware supports. A mask can disable lanes whose elements should not change.
A GPU applies this idea to many groups of threads. It keeps thousands of small jobs available, then runs another group when one waits for memory. That helps regular, data-parallel work. A branch that sends nearby lanes down different paths wastes part of the machine until those paths join again.
Why is memory layout part of vector performance?
Adjacent lanes are easiest to feed when their elements occupy adjacent addresses. One wide load can then fetch useful data for every lane. Scattered addresses may require several cache-line requests.
Changing an array of objects into separate arrays of positions, speeds and colours can improve access for one calculation. It can make other calculations worse, so the right layout follows the work.
Does eight lanes always mean eight times faster?
No. The loop needs enough independent elements, the data must arrive quickly enough, and most lanes must be active. Setup, tail elements and branches reduce utilisation. Some operations also share a smaller number of execution units behind the lanes.
Measure useful results per second, not lane count. The explorer below reports both cycle count and lane utilisation so a partly filled final group is visible.
What is the difference between a CPU vector unit and a GPU?
A CPU spends silicon on low latency, large caches, branch prediction and a few capable cores. A GPU spends more of it on arithmetic lanes and tolerates latency by switching among many ready groups.
Neither is universally faster. Parsing irregular pointer structures often suits a CPU. Applying the same matrix operation to a large batch often suits a GPU or another accelerator.
Represent a wide range of real numbers
Fixed-point numbers keep the binary point in one agreed place. Floating point stores a sign, a scaled exponent and a fraction called the significand. That lets the same 32 bits describe tiny and huge values, but the gaps between neighbouring representable values grow as the magnitude grows.
IEEE 754 binary32 uses 1 sign bit, 8 exponent bits and 23 stored fraction bits. Ordinary values also have an implied leading 1. Exponent patterns at the ends represent zero, subnormal values, infinity and NaN, which means “not a number.” Those special cases make overflow and invalid operations explicit.
Most decimal fractions, including 0.1, do not end in binary. An operation computes an exact mathematical
result, then rounds it to a nearby representable value. Addition is therefore not always associative:
rounding (a+b)+c after each operation can differ from a+(b+c).
How does the hardware add two floating-point numbers?
First compare exponents and shift the smaller significand so the binary points line up. Add or subtract the significands, normalise the result, then round it using extra guard information.
The shifts, leading-bit search and rounding logic make a floating-point adder larger than the integer ripple adder from Step 6. Pipelining lets it start new work before earlier additions finish.
Is floating point inaccurate?
It is a precisely specified approximation. Every finite format has gaps. The useful questions are how large the rounding error can be, whether the calculation magnifies it, and whether a different scale or algorithm would behave better.
Money is often stored as integer cents or decimal arithmetic because binary rounding is awkward for exact decimal rules. Scientific calculations often prefer floating point because their scales vary.
Why do machine-learning chips use several number formats?
Smaller formats move more values through the same memory path and fit more multipliers on a chip. Training may multiply low-precision values but accumulate into a wider result to limit error.
Format choice is an engineering trade-off among range, precision, bandwidth, energy and model quality. A test must compare the final task result, not just the bit width.
0.1 and inspect its sign,
exponent and fraction. Add 0.1 several times, then try a large number and compare the gap to its next
representable neighbour.Meet the power, heat and timing limits
Each CMOS gate charges and discharges capacitance when it switches. A useful first model of dynamic power
is P = αCV²f: activity times capacitance times voltage squared times frequency. Raising the clock
can increase work per second, but raising voltage to keep that clock stable has a squared power cost.
Transistors also leak current while idle. Leakage depends strongly on process and temperature. Electrical power becomes heat; the package and cooling system must carry that heat to the surrounding air. If the die gets too hot, firmware lowers frequency or voltage. That is thermal throttling.
A clock period still has to exceed the slowest register-to-register path, including clock uncertainty and setup time. Lower voltage makes gates switch more slowly. Dynamic voltage and frequency scaling, or DVFS, therefore changes energy, performance and timing margin together.
Why can turning off unused blocks save more than slowing the clock?
Clock gating stops unnecessary register switching, which cuts dynamic power. Power gating disconnects a block from its supply and can also reduce leakage, but the block loses state unless retention circuits preserve it.
Waking a gated block takes time and energy. A controller should gate only when the expected idle period is long enough to repay that cost.
Does lower frequency always save energy?
Lower frequency reduces dynamic power, but the task then runs longer. Leakage and the rest of the system continue consuming energy during that time. Finishing quickly and entering a deep idle state can use less total energy in some systems.
Separate power, measured in watts, from energy, measured in joules. Energy equals the area under the power-versus-time curve.
How does a real chip find safe settings?
Design tools analyse paths across manufacturing, voltage and temperature corners. On-chip sensors watch temperature and sometimes timing margin. Firmware selects tested voltage-frequency pairs rather than choosing arbitrary values.
The model below is for reasoning, not sign-off. Physical design also includes voltage drop, local hot spots, wire delay, clock distribution and variation between transistors.
Verify the design and defend hidden state
A processor must work for far more cases than a person can click. A testbench generates instructions, interrupts and memory responses, then compares the design with a reference model. Assertions watch rules such as “a register changes only on a clock edge” and “two caches never own the same writable line.”
Random tests explore many combinations. Coverage records which instructions, states and transitions were exercised. Formal verification asks a solver to prove a property for every allowed input sequence within a model. None of these replaces the others: the reference model, property and environment assumptions can each be wrong.
Speculation adds a security problem. A wrong-path instruction may be cancelled architecturally yet still change a cache, predictor or timing state. An attacker can measure that leftover effect. Mitigations include barriers, data-independent access patterns, predictor isolation and hardware that prevents secret-dependent transient work from changing observable state.
What should be checked at each layer?
Unit tests check an ALU or decoder. Integration tests check the datapath and controller together. Instruction-set tests compare complete programs with the architectural specification. FPGA prototypes add real clocks and device traffic before manufacturing.
Post-silicon tests then measure fabricated parts, including speed, temperature and rare interactions. Finding a logic error before fabrication is far cheaper, so verification often uses more project time than writing the initial RTL.
Can testing prove that there are no bugs?
A passing test proves only that the tested run matched its oracle. Exhaustive testing can cover a small finite block, such as the four-bit adder below. It cannot enumerate every state of a modern processor.
A formal proof covers the stated property under stated assumptions. Review still asks whether that property describes the requirement and whether the model omitted a physical or security behaviour.
Why are timing effects part of security?
Two executions can produce the same architectural registers and memory but take different amounts of time because their cache histories differ. If that difference depends on a secret, repeated measurements can reveal information without permission to read the secret address.
Security review therefore includes microarchitectural state, shared resources and speculative paths. Continue with Memory Exploits for practical attack and defence methods, including control-flow and memory-safety boundaries.
Where to go next
You have followed a processor from transistor switches through instructions, pipelines, memory systems and multicore execution. You have also seen where timing, power, numerical error and security enter the design. The next useful move is to connect one of those layers to a larger system.
What RISC-V is, and why "free" matters here
An instruction set is a specification, and most of them are owned. Building a chip that runs ARM instructions means an agreement with ARM. RISC-V is published for anyone to implement, without permission or fee.
That is why it turns up in university courses, research chips and hobby projects. Its base set is close in spirit to TOY-16, with 32 registers and a few more instructions.
Build things
- Nand2Tetris: a free course that builds a computer from NAND gates up to a working OS and a Tetris game. The natural next step after this page.
- Turing Complete or Digital Logic Sim: puzzle games where you wire real gates. Solid teaching, disguised as play.
- An FPGA board (iCEBreaker, TinyFPGA, Arty A7) with the open-source Yosys/nextpnr toolchain, or the vendor's. Write your CPU in Verilog and run it.
- RISC-V: a real, free, open instruction set, small enough to implement yourself. The RV32I base is only about 40 instructions. People do implement it in a weekend.
Read things
- Patterson & Hennessy, Computer Organization and Design: the classic. The single-cycle MIPS datapath you just built is a simplified cousin of theirs.
- Charles Petzold, Code: from telegraph relays to computers, no diagrams needed. Clear prose, zero prerequisites.
- Hennessy & Patterson, Computer Architecture: A Quantitative Approach, the graduate sequel: superscalar, out-of-order, multicore, GPUs.
Follow the connections
- Bits and Memory: connect encodings, addresses and object layout to the machine that stores them.
- Operating Systems: use traps, privilege and page tables to understand processes, devices and protection.
- Performance Engineering: measure pipelines, caches, branch misses, vectors and memory traffic instead of guessing what is slow.
- Parallel Algorithms and Concurrent Data Structures: turn cores, coherence and atomics into correct parallel programs.
- Real-Time Systems: put interrupt latency, timing bounds and hardware interfaces into a system with deadlines.
- Build a Language: translate source programs into the instructions, registers and calling rules a processor actually executes.
What "out-of-order" actually reorders
Start with one concrete extension: add an interrupt input and two control registers to TOY-16, or add a second pipeline issue slot to the simulator. Write the architectural rule first, then test the edge cases before changing the datapath.
For a larger implementation, choose the RV32I instruction set and reuse the same sequence as this course: reference model, assembler tests, single-cycle core, pipeline, caches, then advanced features.
A processor is a stack of contracts. Gates implement state, the datapath implements instructions, and the architecture tells software what it may rely on. When a result surprises you, locate the contract, build a small test, and trace the state across that boundary.