Build a small processor

What you are building

A digital switch represents two stable logic levels, written as 0 and 1. Gates combine those bits. Registers store them. The processor you build in the simulator connects an arithmetic unit, register file, instruction memory, and control logic into one working datapath.

Teal entries are build checks. The four magenta entries explain a design problem and link to the lesson needed to solve it.

Keep the processor in a logic simulator until its traces agree

Build this project in the course simulator or a digital-logic tool such as Logisim-evolution. Save the adder, register and decoder as separate subcircuits. Test every input row at that smaller scale before connecting the complete datapath.

1. Expose the clock, program counter, instruction, register addresses, ALU result and register write signal as probes.
2. Single-step a short program and write one trace row per clock. Compare it with a small reference program that implements the instruction meanings directly.
3. Test undefined opcodes and arithmetic overflow. In an ideal logic simulator, verify that every combinational path ends at the intended register; measure real timing separately on an FPGA or breadboard.

A correct simulation proves the logic you specified. It does not prove voltage levels, propagation delay, clock quality or wiring on a physical build. The Simulating Physical Systems course shows how to carry tests and traces across that boundary.

Project milestones

1. Represent 0 and 1 with a switch and lamp.

   The switch completes the loop or breaks it, so the bulb is on or off with nothing in between. That is why machines are built out of two states rather than ten: two states survive a noisy wire, and ten do not.

2. Build logic gates from controlled switches.

   A transistor is a switch worked by a wire instead of by a hand, which means one circuit can operate the next one. Wire a few into AND, OR and NOT, then test each against every row of its table, not just the row you had in mind.

3. Build a one-bit adder and expose its carry.

   Two gates give the right answer for three of the four cases, and then 1 + 1 comes out as 0. The answer needed two columns and you built one. Widen it to four bits and 15 + 1 lands on 0 as well, which is the same fault one column further along.

   What you need

   Each column has to hand its overflow to the next. One column taking two inputs is a half adder; give it a third input for the overflow arriving from the column below and it is a full adder. Chain four of them, carry-out into carry-in, and you have a ripple carry adder, which also shows you why wide addition takes time.

   step 5Building an adder
4. Select arithmetic and logic operations in an ALU.

   Subtraction needs no second circuit. Flip every bit of the number you are taking away, add one, then add as normal. Put a multiplexer on the output so two control bits pick which answer leaves the box. That box has a name: the arithmetic logic unit, or ALU. Check 9 minus 5 and then 5 minus 9, because the second one is where your choice about negative numbers becomes visible.

5. Store a value after the inputs change.

   Feed in 5 and 3, read 8 out, take the inputs away, and the 8 is gone. Now try to add three numbers. You need somewhere to keep a running total between one addition and the next and every gate you own answers only about the present instant.

   What you need

   Wire two gates in a ring, each one's output feeding the other's input, and the pair will settle in either state and stay there, which is called bistable. That is an SR latch. Add a clock so it changes only at the instant a tick arrives and it becomes a D flip-flop. The line being drawn here is between combinational circuits, which answer about now, and sequential ones, which carry something across a tick.

   step 9Memory: making a circuit remember
6. Build an eight-register file with two read ports.

   Sixteen flip-flops side by side hold a sixteen-bit number, and that is a register. Eight registers with an address on the front is a register file. Read two, feed both into the ALU, write the answer into a third, and confirm it is still there after the next tick.

7. Define the instruction set.

   Four instructions are enough to start: add two registers, load a number from memory, store one back, and jump elsewhere if two registers hold the same value. That list is your instruction set, and it is a decision you make rather than a fact you find. Keeping it short and regular is the whole argument behind the word RISC.

8. Decode each instruction into control signals.

   Written in words they are all different shapes. Add wants three register numbers. Load wants a register and an address. Jump if equal wants two registers and a distance. Memory hands your machine sixteen bits with no spaces and no punctuation anywhere in them, so a shape that changes from one instruction to the next cannot be found.

   What you need

   Give every instruction the same width, and settle on two or three fixed layouts rather than a new one for each instruction. The first few bits are the opcode, the number that says which instruction this is, and they sit in the same positions every time so one small circuit can always find them. The bits after them are fields: register numbers and an immediate for a value written into the instruction itself instead of fetched from a register.

   step 13Packing an instruction into sixteen bits
9. Run one instruction through the complete datapath.

   Fetch the sixteen bits sitting at the address in the program counter, split them into opcode and fields, and look the opcode up in a table. The row you land on sets the control lines: which register gets written, whether the ALU's second input comes from a register or from the immediate, and whether the next address is the following instruction or somewhere else. That table is the control unit, and it is where the machine's behaviour actually lives.

10. Trace and fix a datapath control error.

    Six instructions, no error, no crash, and the number left in R3 is not the number you worked out on paper. Reading the program again will not help, because the program is not the thing that is wrong. One control line is set the wrong way for one opcode. It only shows itself on the tick where that instruction runs.

    What you need

    Stop reasoning and start watching. A breakpoint stops the machine at an instruction you choose, and single-stepping advances it one instruction at a time so you can print every register between one step and the next. The part that takes practice is writing down what you expect each register to hold before you look, because a value only looks wrong when it is standing next to a prediction.

    step 10Break, step, print
11. Run a complete program on the processor.

    Assemble it, press run, and the right number comes out. Every layer beneath it is one you put there: the table that read the opcode, the flip-flops holding the result, the register file, the adder, the gates, the switch.

Review the processor in four passes

Review the same processor for basic operation, edge cases, clock speed, and fault recovery.

Course links for each pass

Each of those three later passes has a step behind it. Two are in the same course you have been using; the third is in the course about what a fixed number of bits can hold.

1. Running out of room inside a sixteen-bit register.
   Make it correct

   Sixteen bits hold 65536 different patterns and not one more, so the seventeenth bit of a sum has nowhere to go and the answer wraps round instead of growing. Your ALU can report that in a carry or overflow flag, and then you have to decide what the machine does about it, which is a design choice and not a repair.

   step 4Where integers break
2. Keeping every part of the circuit busy at once.
   Make it fast

   Pipelining starts the next instruction before the previous one has finished, so fetching, decoding and executing all happen in the same tick on three different instructions. No single instruction gets quicker, which is the difference between latency and throughput, and it is also where an overlapped machine starts reading a register the instruction in front of it has not written yet.

   step 17Making it fast: pipelining
3. Finding out how fast your clock is allowed to be.
   Make it survive

   A signal takes time to cross a gate, and every result has to have arrived before the next tick. The longest route through the circuit is the slowest path, the gap between the time it needs and the time the tick allows is slack and a design with no slack works on the bench and then fails once the chip is warm.

   step 10The clock: the heartbeat

Related projects and courses

You now know what a program is at the bottom: a pattern of bits that selects a row of a table, and a table that opens and closes gates. The registers, jumps and comparisons in your machine are the same three ideas the processor on your desk is built from, with a longer instruction list and a great deal more of everything.

All builds, or read Build a Microprocessor straight through, which carries on into overlapping instructions, caches, and putting the design onto real hardware. Reading the Machine's Mind takes the same registers and jumps onto a machine you did not design, which is the harder and more useful version of the same skill.