Skip to content
Tutorials Center
My learning

Topics

Lesson 58 of 67 ยท Projects

Project: A Complete Mini CPU Simulator

Design a tiny 16-bit instruction set, write an assembler, and build a fetch-decode-execute simulator that runs factorial and Fibonacci programs.

In this project you build a whole computer in miniature: an instruction set, an assembler that turns text into binary, and a processor that fetches, decodes and executes those binary instructions. When you finish, you will have a program that runs programs, and you will have touched every layer from instruction encoding to the fetch-decode-execute cycle.

You will work in three steps. First you define the instruction set architecture (ISA) on paper. Then you write the assembler. Last you write the CPU and run two classic programs, factorial and Fibonacci, on it. Everything runs in your browser. The design is a deliberately small cousin of the machine in Assembly: Branches, Loops and Functions, but this one works on real binary words instead of parsed text.

Step 1: design the ISA

Before writing code, decide what the machine can do. A small design is easier to finish and easier to understand, so ours has these properties:

  • 16-bit words. Instructions, data and addresses all fit in 16 bits, and memory is an array of 256 words shared by program and data (a von Neumann design).
  • 8 registers, r0 to r7, each holding a signed 16-bit value. r0 is wired to zero: reads give 0 and writes are ignored. This trick, used by real RISC designs, gives you a free zero constant, and with it a move and a load immediate from instructions you already have.
  • One fixed instruction format. Every instruction is 16 bits split into an opcode and three fields.
Bits 15 to 12 11 to 9 8 to 6 5 to 0
Field op a b c

What a, b and c mean depends on the opcode:

Opcode Mnemonic Meaning
0 HALT stop the machine
1, 2, 3 ADD SUB MUL rd, rs, rt a = b op c (c holds a register number)
4 ADDI rd, rs, imm a = b + imm (c is a signed 6-bit number, -32 to 31)
5 LW rd, off(rs) load the word at address b + off into a
6 SW rt, off(rs) store register a at address b + off
7, 8, 9 BEQ BNE BLT ra, rb, label if the condition holds, add the signed 6-bit c to the program counter
10 JMP label set the program counter to the 12-bit address in bits 11 to 0
11 OUT r append register a to the output list

Two details matter. A branch offset counts from the instruction after the branch, because by the time the branch executes the program counter has already moved on. And two pseudo-instructions need no hardware at all: LI rd, n is assembled as ADDI rd, r0, n, and MOV rd, rs as ADD rd, rs, r0. The assembler hides the trick and the programmer gets friendlier code.

flowchart LR
  PC["PC"] -->|"address"| MEM["Memory<br/>256 words"]
  MEM -->|"16-bit word"| IR["Decode<br/>op, a, b, c"]
  IR --> RF["Registers<br/>r0 to r7"]
  RF --> ALU["ALU<br/>add, sub, mul"]
  ALU --> RF
  IR -->|"load and store"| MEM
  IR -->|"branch or jump"| PC

The mini CPU: the PC selects a word, the decoder splits it into fields, and the registers, ALU and memory carry out the instruction.

Step 2: write the assembler

An assembler's job is translation. Read the text, remove comments, record where each label points, then encode every instruction into one 16-bit word. Labels can be used before they are defined (a loop's exit label sits below the branch that needs it), so the assembler makes two passes: the first pass records label addresses, and the second encodes instructions with those addresses known.

The code below does both passes, adds a disassembler for the reverse direction (word back to text), and checks that immediates fit. It assembles the factorial loop and prints each word in binary and hex next to its disassembly. The last lines trigger an assembler error on purpose: 40 does not fit in a signed 6-bit field.

Python The assembler and disassembler

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Read the table the program prints. ADDI r1, r0, 5 is 0100 001 000 000101: opcode 4, register 1, register 0 as the source, and the number 5. The branch BEQ r1, r0, -> 6 is 0111 001 000 000011, with distance 3 because the target (address 6) is 3 instructions after the next one (address 3). The -1 in ADDI r1, r1, -1 shows up as 111111 in the low six bits: that is two's complement at work, and signed() turns it back into -1 during decoding.

A real assembler also checks for undefined and duplicate labels, handles data directives, and reports the line number of each error. Adding a clear error message for a missing label is a good extension: right now an unknown label raises a plain KeyError.

Step 3: write the CPU

The processor is a loop around three steps. Fetch reads the word at the program counter and advances the counter. Decode splits the word into its fields. Execute does the work: arithmetic, a memory access, or changing the counter. Arithmetic results are wrapped to 16 bits with s16, exactly what a 16-bit adder does when the answer is too big, and r0 is reset to zero after every instruction.

The class also counts instructions and tallies an instruction mix, how often each opcode ran. That is the data you need for the performance equation from Measuring Performance: with one cycle per instruction, the cycle count is the instruction count.

The next program contains the assembler from the previous step, the CPU, and two programs. The factorial multiplies n into a running product while counting down; the Fibonacci program keeps two consecutive numbers in r1 and r2 and prints 12 terms. At the end it single-steps the factorial and prints the first instructions as they execute.

Python Run factorial and Fibonacci

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The factorial program prints [5040] after 33 instructions, and 7 of those are MUL. The Fibonacci program prints the first twelve terms, 0, 1, 1, 2, 3, 5, 8, ... up to 89, in 89 instructions, with ADD the most common opcode because MOV is an ADD underneath. The trace at the bottom shows one instruction per line, and you can see r2 change only when MUL runs.

Count the overhead in the factorial loop: of its four-instruction body, only MUL does useful arithmetic. BEQ tests the end condition, ADDI updates the counter and JMP returns to the top. This is the loop-test-at-the-top shape from the earlier assembly lesson; moving the test to the bottom would remove the JMP, the kind of saving that performance engineering is about.

Step 4: run machine code directly

The CPU has no idea an assembler exists. It only knows 16-bit words, so you can load a program as a list of numbers. The last program loads such a memory image: twelve instruction words from the assembler followed by data at address 24. The program walks a pointer through six numbers with LW, adds them up, and stores the total with SW. After that it reruns the factorial program for several values of n by patching the first word (0x4200 | n encodes LI r1, n) to show overflow.

Python Load a binary image and meet overflow

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The array sum prints [108], and the same value is saved at address 31. The factorial table has a surprise. 5!, 6! and 7! are correct, but 8! prints -25216 instead of 40320, and 9! prints -30336. The largest signed 16-bit number is 32767, so the product wraps around, just as in Binary Arithmetic and Overflow: 40320 minus 65536 is -25216. The program is correct; the machine is too narrow. A real ISA fixes this with wider registers (32 or 64 bits) and an overflow flag. Our CPU simply wraps, which is what many real instructions do too.

Ideas to extend it

You now have a working skeleton. Each of these changes teaches something specific:

  1. Add a flags register and a compare instruction, so the machine supports signed and unsigned branches like the ones in Assembly: Branches, Loops and Functions.
  2. Add CALL and RET with a stack in memory, then write a recursive factorial.
  3. Add bit operations (AND, OR, shifts) and write multiplication by repeated shift-and-add, to see why hardware multipliers exist.
  4. Make the cycle count realistic: charge 1 cycle for ALU operations, 2 for loads and stores, 3 for taken branches, and compute CPI for each program.
  5. Replace the Python if chain with a control table keyed by opcode, as in The Control Unit, so each instruction is described by data, not code.

When something goes wrong, trace before you guess. Print the program counter, the disassembly of the current word and the registers after each step, as the factorial trace does. Most simulator bugs are an off-by-one in a branch offset or an unwrapped 16-bit result, and a trace shows both immediately.

Check your understanding

Quick check ยท 5 questions

of 5 answered You scored / 5 ยท perfect!

  1. 1. Why is register r0 wired to zero in this design?

    With a register that always reads 0, a load-immediate is ADDI rd, r0, n and a move is ADD rd, rs, r0, so no extra opcodes are needed.
  2. 2. Why does an assembler make two passes?

    A forward branch refers to a label further down. Pass one records every label's address, and pass two can then encode every branch distance.
  3. 3. A branch is at address 10 and its target is address 14. What offset is stored in the instruction?

    The offset is counted from the next instruction (address 11), so it is 14 - 11 = 3.
  4. 4. In the simulator, 8! printed -25216. What is the cause?

    The largest signed 16-bit value is 32767. 40320 - 65536 = -25216, which is what the wrapped register holds.
  5. 5. What are the three steps of every pass through the CPU's main loop?

    The CPU fetches the word at the program counter, decodes its fields, and executes the operation.

Summary

  • A processor project starts with an ISA: word size, registers, instruction formats and a list of operations.
  • A fixed format of opcode plus three fields keeps both the assembler and the decoder tiny.
  • A wired-zero register and pseudo-instructions give you LI and MOV with no new hardware.
  • An assembler is a two-pass translator: first collect labels, then encode instructions, checking that immediates and offsets fit.
  • The CPU is a fetch-decode-execute loop; wrapping results to 16 bits shows real overflow behavior, and an instruction mix gives you the data for CPI.
  • The machine code is just numbers, so the CPU runs a memory image without any assembler.

Next, study the memory side in Project: A Configurable Cache Simulator.