A Tiny CPU, Instruction by Instruction

in reviewThis lesson is complete and being validated before release - details may still change.

A tiny CPU

Loading interactive demo…

The diagram on the left is the datapath: the program counter, the memory, the instruction register, the accumulator, the adder, and the output, with the bus in use this step lit. The grid is the memory, sixteen bytes in hex, address 0 at the top left; tap a byte to read it as a number and as an instruction. The listing beside it reads every byte as an instruction, the fetched one lit. The strips below are the registers and the output.Take the tour, or press and explore. Legend:

The panel beside the stage is the real TinyCpu class from the published library executing in your browser, with the current line highlighted.

The byte being fetched, its line in the listing, and the unit at work.
A bus carrying a value this step, and the bytes the program means as data.
The bytes the program means as code.
A byte just written by a store.
A run stopped before a halt.

cycle counts instructions so far, PC is where the next fetch reads, ACC the accumulator, zero the flag a branch tests, and output what OUT has printed.

The code panel shows bare executable code by default. The bar above it names the file (hover the name for the full published path); options holds the toggles: comments, the tracer instrumentation that produces this visualization, and verbose names for the terse identifiers (display only: the default is the byte-exact published file). The view switch adds plain-English narration: both interleaves it with the code, pseudo shows only the pseudocode. hide code collapses the panel; the rail it leaves behind brings it back.

Keys: Space play/pause · ←/→ step · Home/End jump · R reset · F fullscreen · G guided tour

The machine. Sixteen bytes of memory, addressed $0$ to $15$ . Four registers, each a row of the previous lesson's flip-flops: the program counter $\text{PC}$ (four bits, an address), the accumulator $\text{ACC}$ (eight bits), the instruction register $\text{IR}$ (eight bits), and the zero flag $Z$ (one bit). An instruction is one byte: the top four bits are the opcode, the bottom four an address. Nine opcodes are used, and $0$ is HALT, so a byte of zeros stops the machine.

The cycle. Every instruction costs the same three moves. Fetch: $\text{IR} \leftarrow \text{M}[\text{PC}]$ , then $\text{PC} \leftarrow \text{PC} + 1$ . Decode: split $\text{IR}$ into opcode and address, and set the control lines that choose which buses open. Execute: one of

\begin{aligned} \text{LOAD } a:&\ \text{ACC} \leftarrow \text{M}[a] & \text{STORE } a:&\ \text{M}[a] \leftarrow \text{ACC} \\ \text{ADD } a:&\ \text{ACC} \leftarrow \text{ACC} + \text{M}[a] & \text{SUB } a:&\ \text{ACC} \leftarrow \text{ACC} + \overline{\text{M}[a]} + 1 \\ \text{JUMP } a:&\ \text{PC} \leftarrow a & \text{JZ } a:&\ \text{if } Z \text{ then PC} \leftarrow a \\ \text{OUT}:&\ \text{print ACC} & \text{LOADI } a:&\ \text{ACC} \leftarrow a \end{aligned}

and after every instruction $Z \leftarrow (\text{ACC} = 0)$ . The datapath diagram lights the bus each move uses. In hardware the three moves are clock edges: each register takes its new value only when its clock arrives, which is what makes the sequence a sequence.

Arithmetic is the adder. ADD feeds the accumulator and the memory word into the ripple-carry adder of the first lesson. SUB inverts the memory word and sets the carry in to $1$ , the two's complement trick, so there is no subtractor. The overflow program adds $200 + 100$ and gets $44$ : the adder's carry out is simply dropped, as it is in every fixed-width machine unless the program checks the flag.

Control flow is the program counter. Fetch always advances $\text{PC}$ ; a jump overwrites it afterwards, which is why the diagram shows the bus from $\text{IR}$ back to $\text{PC}$ lighting only on a jump taken. JZ makes the one decision the machine can make: it reads a single bit. Every if and while in a high-level program compiles to a flag being set and a conditional jump reading it, exactly as the bytecode machine's jump-if-false did, except that here the "variable" is a wire.

Code is data. Nothing marks a byte as an instruction. The countdown's data bytes $3$ and $1$ would decode as HALT if fetched; the data-as-code program jumps into bytes $63$ and $112$ , which the machine happily runs as ADD 15 and OUT. The listing on the stage reads every byte as an instruction for this reason. Modern processors add a permission bit per page to refuse to fetch from data, but the memory itself still cannot tell.

Cost. An instruction here is three moves and a handful of gate delays through the adder, so the clock period is set by the longest path: fetch through memory, or execute through the carry chain. The whole art of the planned lessons that follow this one, caches, pipelining, branch prediction, is to overlap and shortcut these moves without changing what the program sees.

Choices worth reading closely in the implementation (the code panel's comments and tracer checkboxes reveal the full published file):

step is three method calls, fetch, decode, execute, each emitting one event, so the stage's three moves are the code's three methods and nothing is hidden between them.
fetch advances the program counter before execute runs, so a jump that sets it wins and every other instruction falls through to the next byte. The bytecode machine did the same.
execute owns a RippleCarryAdder and never uses + on the accumulator: ADD calls add, SUB calls add with the inverted word and a carry in of 1. The library's arithmetic is the arc's.
The zero flag is set after every instruction from the accumulator, in one line, so JZ after a LOAD or a SUB sees the right value without special cases.
An opcode above 8 is a halt through the switch's default, and so is 0, which keeps the machine total: any byte fetched does something defined.
Assembler lives in the same file, small enough to read: a mnemonic becomes an opcode times sixteen plus an address, a bare number is stored as it is, and disassemble reverses it, which is how the stage reads data bytes as instructions.
MAX_CYCLES stops a program that never halts and reports a fault instead of throwing, so the data-as-code loop ends on the stage.

The idea that a program could live in the same memory as its data, fetched one instruction at a time by a counter, was written down by John von Neumann in 1945 in his report on the EDVAC, drawing on the work of Eckert, Mauchly, and Turing. The first machine to run a program that way was the Manchester Baby, which executed its first program on 21 June 1948 from a memory of thirty-two words, each thirty-two bits long. Everything since, from the EDSAC to the chip in a watch, has kept the loop on this stage: fetch, decode, execute.

1936Alan Turing - On Computable Numbers defines a machine that reads instructions from the same tape it computes on, the universal machine.source
1945John von Neumann - First Draft of a Report on the EDVAC describes a stored-program computer with a control unit, an arithmetic unit, memory, and input and output.source
1948Frederic Williams, Tom Kilburn, and Geoff Tootill - The Manchester Baby runs the first stored program, from 32 words of memory, taking 52 minutes to find the highest factor of a number.source
1949Maurice Wilkes and the Cambridge Mathematical Laboratory - EDSAC is the first practical stored-program computer in regular service, with an accumulator and a mnemonic assembly language.source
1965Stuart Madnick - The Little Man Computer, a teaching model with a hundred mailboxes and an accumulator, the lineage this stage's machine belongs to.source
1971Federico Faggin, Ted Hoff, Stanley Mazor, and Masatoshi Shima at Intel - The 4004 puts a complete 4-bit processor on one chip of 2,300 transistors.source

Used today

Every processor - Pipelines, caches, and out-of-order execution are machinery wrapped around this same fetch-decode-execute loop to run it faster.
Microcontrollers - The chip in a thermostat or a keyboard is an accumulator machine with a few kilobytes of memory, closer to this stage than to a laptop.
Virtual machines and emulators - The bytecode VM of the Languages arc is this loop in software; a console emulator is this loop for someone else's instruction set.

program

cycle: 15
PC: 6
ACC: 0
zero: set
output: 3 2 1

tiny-cpu.ts

import type { Tracer } from "../trace";import { RippleCarryAdder } from "./ripple-carry-adder";/** Sixteen words of memory, each a byte: a 4-bit opcode above a 4-bit address. */export const MEMORY_WORDS = 16;export const WORD_BITS = 8;export const WORD_LIMIT = 2 ** WORD_BITS;/** Cycles before a program that never halts is stopped. */export const MAX_CYCLES = 48;export type Mnemonic = "HALT" | "LOAD" | "STORE" | "ADD" | "SUB" | "JUMP" | "JZ" | "OUT" | "LOADI";/** The instruction set, indexed by opcode: HALT is 0, so an empty word is a halt. */export const OPCODES: readonly Mnemonic[] = ["HALT", "LOAD", "STORE", "ADD", "SUB", "JUMP", "JZ", "OUT", "LOADI"];/** Opcodes that read or write the memory word their operand names. */export const MEMORY_OPS: readonly Mnemonic[] = ["LOAD", "STORE", "ADD", "SUB"];export interface Instruction {  opcode: number;  mnemonic: Mnemonic | null;  operand: number;}export interface Registers {  /** The address of the next instruction. */  pc: number;  /** The accumulator: the one register arithmetic works on. */  acc: number;  /** The instruction register: the word fetched this cycle. */  ir: number;  /** The zero flag: whether the accumulator was last left at zero. */  zero: boolean;}export interface CpuResult {  halted: boolean;  cycles: number;  registers: Registers;  memory: number[];  output: number[];  /** Why the run stopped early, or null for a clean halt. */  fault: string | null;}/** * Turns assembly lines into memory words: "ADD 14" is opcode 3 above * address 14; a bare number is a data word stored as it is; the * memory is padded with zeros, which are halts. */export class Assembler {  static assemble(lines: readonly string[]): number[] {    if (lines.length > MEMORY_WORDS) throw new RangeError(`${lines.length} words exceeds the ${MEMORY_WORDS}-word memory`);    const words = lines.map((line) => Assembler.word(line.trim()));    const words = lines.map((line) => Assembler.memoryWord(line.trim()));    while (words.length < MEMORY_WORDS) words.push(0);    return words;  }  /** The word for one line. */  static word(line: string): number {  static memoryWord(line: string): number {    if (/^\d+$/.test(line)) {      const value = Number(line);      if (value >= WORD_LIMIT) throw new RangeError(`data ${value} does not fit in a byte`);      return value;    }    const [mnemonic, operand = "0"] = line.split(/\s+/);    const opcode = OPCODES.indexOf(mnemonic as Mnemonic);    if (opcode === -1) throw new RangeError(`unknown instruction ${line}`);    const address = Number(operand);    if (!Number.isInteger(address) || address < 0 || address >= MEMORY_WORDS) throw new RangeError(`operand ${operand} is not an address`);    return opcode * MEMORY_WORDS + address;  }  /** A word read as an instruction: the opcode above, the address below. */  static decode(word: number): Instruction {  static decode(memoryWord: number): Instruction {    const opcode = Math.floor(word / MEMORY_WORDS);    const opcode = Math.floor(memoryWord / MEMORY_WORDS);    return { opcode, mnemonic: OPCODES[opcode] ?? null, operand: word % MEMORY_WORDS };    return { opcode, mnemonic: OPCODES[opcode] ?? null, operand: memoryWord % MEMORY_WORDS };  }  /** The assembly text of a word, or its value when the opcode is not one. */  static disassemble(word: number): string {  static disassemble(memoryWord: number): string {    const { mnemonic, operand } = Assembler.decode(word);    const { mnemonic, operand } = Assembler.decode(memoryWord);    if (mnemonic === null) return `${word}`;    return mnemonic === "HALT" || mnemonic === "OUT" ? mnemonic : `${mnemonic} ${operand}`;  }}/** * An accumulator machine small enough to watch: a program counter, an * accumulator, an instruction register, a zero flag, and sixteen * bytes of memory holding both the program and its data. Every cycle * is the same three moves. Fetch: the word at the program counter goes * into the instruction register and the counter advances. Decode: the * top four bits pick the instruction, the bottom four name an address. * Execute: the accumulator, the memory, or the program counter * changes. The adder is the ripple-carry adder from two lessons ago; * subtraction is addition of the two's complement, the carry in * supplying the plus one. Memory cannot tell code from data, so a jump * into a data word runs it. * * Time: three steps per instruction. Space: 16 bytes and four registers. */export class TinyCpu {  private readonly memory: number[];  private readonly registers: Registers = { pc: 0, acc: 0, ir: 0, zero: true };  private readonly output: number[] = [];  private readonly adder = new RippleCarryAdder(WORD_BITS);  private cycles = 0;  constructor(    program: readonly number[],    private readonly tracer?: Tracer,  ) {    if (program.length !== MEMORY_WORDS) throw new RangeError(`a program is ${MEMORY_WORDS} words, got ${program.length}`);    this.memory = program.map((word) => word % WORD_LIMIT);    this.memory = program.map((memoryWord) => memoryWord % WORD_LIMIT);  }  /** Runs until HALT, or until the cycle cap stops a program that never halts. */  run(): CpuResult {    let halted = false;    let fault: string | null = null;    while (!halted) {      if (this.cycles >= MAX_CYCLES) {        fault = `still running after ${MAX_CYCLES} cycles`;        break;      }      halted = this.step();    }    return { halted, cycles: this.cycles, registers: { ...this.registers }, memory: [...this.memory], output: [...this.output], fault };  }  /** One cycle: fetch, decode, execute. True once HALT has executed. */  step(): boolean {    this.cycles++;    const word = this.fetch();    const memoryWord = this.fetch();    const instruction = this.decode(word);    const instruction = this.decode(memoryWord);    return this.execute(instruction);  }  private fetch(): number {    const pc = this.registers.pc;    const word = this.memory[pc]!;    const memoryWord = this.memory[pc]!;    this.registers.ir = word;    this.registers.ir = memoryWord;    this.registers.pc = (pc + 1) % MEMORY_WORDS;    // ▸ fetch: the word at the program counter goes into the instruction register, and the counter moves on    this.tracer?.emit("fetch", { cycle: this.cycles, pc, word, next: this.registers.pc });    this.tracer?.emit("fetch", { cycle: this.cycles, pc, memoryWord, next: this.registers.pc });    return word;    return memoryWord;  }  private decode(word: number): Instruction {  private decode(memoryWord: number): Instruction {    const instruction = Assembler.decode(word);    const instruction = Assembler.decode(memoryWord);    // ▸ decode: the top four bits name the instruction, the bottom four an address    this.tracer?.emit("decode", { cycle: this.cycles, word, opcode: instruction.opcode, mnemonic: instruction.mnemonic, operand: instruction.operand });    this.tracer?.emit("decode", { cycle: this.cycles, memoryWord, opcode: instruction.opcode, mnemonic: instruction.mnemonic, operand: instruction.operand });    return instruction;  }  /** The effect of one instruction; a word whose opcode is not one halts, like an empty word. */  private execute(instruction: Instruction): boolean {    const { mnemonic, operand } = instruction;    const r = this.registers;    const regs = this.registers;    let written: number | null = null;    let halted = false;    switch (mnemonic) {      case "LOAD":        r.acc = this.memory[operand]!;        regs.acc = this.memory[operand]!;        break;      case "STORE":        this.memory[operand] = r.acc;        this.memory[operand] = regs.acc;        written = operand;        break;      case "ADD":        r.acc = this.adder.add(r.acc, this.memory[operand]!).sum;        regs.acc = this.adder.add(regs.acc, this.memory[operand]!).sum;        break;      case "SUB":        // Two's complement: invert the operand and add one through the carry in.        r.acc = this.adder.add(r.acc, WORD_LIMIT - 1 - this.memory[operand]!, 1).sum;        regs.acc = this.adder.add(regs.acc, WORD_LIMIT - 1 - this.memory[operand]!, 1).sum;        break;      case "JUMP":        r.pc = operand;        regs.pc = operand;        break;      case "JZ":        if (r.zero) r.pc = operand;        if (regs.zero) regs.pc = operand;        break;      case "OUT":        this.output.push(r.acc);        this.output.push(regs.acc);        break;      case "LOADI":        r.acc = operand;        regs.acc = operand;        break;      default:        halted = true;    }    r.zero = r.acc === 0;    regs.zero = regs.acc === 0;    // ▸ execute: the accumulator, a memory word, or the program counter changes    this.tracer?.emit("execute", { cycle: this.cycles, mnemonic: mnemonic ?? "HALT", operand, acc: r.acc, pc: r.pc, zero: r.zero, written, output: [...this.output], halted });    this.tracer?.emit("execute", { cycle: this.cycles, mnemonic: mnemonic ?? "HALT", operand, acc: regs.acc, pc: regs.pc, zero: regs.zero, written, output: [...this.output], halted });    return halted;  }}

cycles =: 15
halted =: yes

Halted after 15 cycles. Output: 3 2 1.

import type { Tracer } from "../trace";import { RippleCarryAdder } from "./ripple-carry-adder";/** Sixteen words of memory, each a byte: a 4-bit opcode above a 4-bit address. */export const MEMORY_WORDS = 16;export const WORD_BITS = 8;export const WORD_LIMIT = 2 ** WORD_BITS;/** Cycles before a program that never halts is stopped. */export const MAX_CYCLES = 48;export type Mnemonic = "HALT" | "LOAD" | "STORE" | "ADD" | "SUB" | "JUMP" | "JZ" | "OUT" | "LOADI";/** The instruction set, indexed by opcode: HALT is 0, so an empty word is a halt. */export const OPCODES: readonly Mnemonic[] = ["HALT", "LOAD", "STORE", "ADD", "SUB", "JUMP", "JZ", "OUT", "LOADI"];/** Opcodes that read or write the memory word their operand names. */export const MEMORY_OPS: readonly Mnemonic[] = ["LOAD", "STORE", "ADD", "SUB"];export interface Instruction { opcode: number; mnemonic: Mnemonic | null; operand: number;}export interface Registers { /** The address of the next instruction. */ pc: number; /** The accumulator: the one register arithmetic works on. */ acc: number; /** The instruction register: the word fetched this cycle. */ ir: number; /** The zero flag: whether the accumulator was last left at zero. */ zero: boolean;}export interface CpuResult { halted: boolean; cycles: number; registers: Registers; memory: number[]; output: number[]; /** Why the run stopped early, or null for a clean halt. */ fault: string | null;}/** * Turns assembly lines into memory words: "ADD 14" is opcode 3 above * address 14; a bare number is a data word stored as it is; the * memory is padded with zeros, which are halts. */export class Assembler { static assemble(lines: readonly string[]): number[] { if (lines.length > MEMORY_WORDS) throw new RangeError(`${lines.length} words exceeds the ${MEMORY_WORDS}-word memory`); const words = lines.map((line) => Assembler.word(line.trim())); const words = lines.map((line) => Assembler.memoryWord(line.trim())); while (words.length < MEMORY_WORDS) words.push(0); return words; } /** The word for one line. */ static word(line: string): number { static memoryWord(line: string): number { if (/^\d+$/.test(line)) { const value = Number(line); if (value >= WORD_LIMIT) throw new RangeError(`data ${value} does not fit in a byte`); return value; } const [mnemonic, operand = "0"] = line.split(/\s+/); const opcode = OPCODES.indexOf(mnemonic as Mnemonic); if (opcode === -1) throw new RangeError(`unknown instruction ${line}`); const address = Number(operand); if (!Number.isInteger(address) || address < 0 || address >= MEMORY_WORDS) throw new RangeError(`operand ${operand} is not an address`); return opcode * MEMORY_WORDS + address; } /** A word read as an instruction: the opcode above, the address below. */ static decode(word: number): Instruction { static decode(memoryWord: number): Instruction { const opcode = Math.floor(word / MEMORY_WORDS); const opcode = Math.floor(memoryWord / MEMORY_WORDS); return { opcode, mnemonic: OPCODES[opcode] ?? null, operand: word % MEMORY_WORDS }; return { opcode, mnemonic: OPCODES[opcode] ?? null, operand: memoryWord % MEMORY_WORDS }; } /** The assembly text of a word, or its value when the opcode is not one. */ static disassemble(word: number): string { static disassemble(memoryWord: number): string { const { mnemonic, operand } = Assembler.decode(word); const { mnemonic, operand } = Assembler.decode(memoryWord); if (mnemonic === null) return `${word}`; return mnemonic === "HALT" || mnemonic === "OUT" ? mnemonic : `${mnemonic} ${operand}`; }}/** * An accumulator machine small enough to watch: a program counter, an * accumulator, an instruction register, a zero flag, and sixteen * bytes of memory holding both the program and its data. Every cycle * is the same three moves. Fetch: the word at the program counter goes * into the instruction register and the counter advances. Decode: the * top four bits pick the instruction, the bottom four name an address. * Execute: the accumulator, the memory, or the program counter * changes. The adder is the ripple-carry adder from two lessons ago; * subtraction is addition of the two's complement, the carry in * supplying the plus one. Memory cannot tell code from data, so a jump * into a data word runs it. * * Time: three steps per instruction. Space: 16 bytes and four registers. */export class TinyCpu { private readonly memory: number[]; private readonly registers: Registers = { pc: 0, acc: 0, ir: 0, zero: true }; private readonly output: number[] = []; private readonly adder = new RippleCarryAdder(WORD_BITS); private cycles = 0; constructor( program: readonly number[], private readonly tracer?: Tracer, ) { if (program.length !== MEMORY_WORDS) throw new RangeError(`a program is ${MEMORY_WORDS} words, got ${program.length}`); this.memory = program.map((word) => word % WORD_LIMIT); this.memory = program.map((memoryWord) => memoryWord % WORD_LIMIT); } /** Runs until HALT, or until the cycle cap stops a program that never halts. */ run(): CpuResult { let halted = false; let fault: string | null = null; while (!halted) { if (this.cycles >= MAX_CYCLES) { fault = `still running after ${MAX_CYCLES} cycles`; break; } halted = this.step(); } return { halted, cycles: this.cycles, registers: { ...this.registers }, memory: [...this.memory], output: [...this.output], fault }; } /** One cycle: fetch, decode, execute. True once HALT has executed. */ step(): boolean { this.cycles++; const word = this.fetch(); const memoryWord = this.fetch(); const instruction = this.decode(word); const instruction = this.decode(memoryWord); return this.execute(instruction); } private fetch(): number { const pc = this.registers.pc; const word = this.memory[pc]!; const memoryWord = this.memory[pc]!; this.registers.ir = word; this.registers.ir = memoryWord; this.registers.pc = (pc + 1) % MEMORY_WORDS; // ▸ fetch: the word at the program counter goes into the instruction register, and the counter moves on this.tracer?.emit("fetch", { cycle: this.cycles, pc, word, next: this.registers.pc }); this.tracer?.emit("fetch", { cycle: this.cycles, pc, memoryWord, next: this.registers.pc }); return word; return memoryWord; } private decode(word: number): Instruction { private decode(memoryWord: number): Instruction { const instruction = Assembler.decode(word); const instruction = Assembler.decode(memoryWord); // ▸ decode: the top four bits name the instruction, the bottom four an address this.tracer?.emit("decode", { cycle: this.cycles, word, opcode: instruction.opcode, mnemonic: instruction.mnemonic, operand: instruction.operand }); this.tracer?.emit("decode", { cycle: this.cycles, memoryWord, opcode: instruction.opcode, mnemonic: instruction.mnemonic, operand: instruction.operand }); return instruction; } /** The effect of one instruction; a word whose opcode is not one halts, like an empty word. */ private execute(instruction: Instruction): boolean { const { mnemonic, operand } = instruction; const r = this.registers; const regs = this.registers; let written: number | null = null; let halted = false; switch (mnemonic) { case "LOAD": r.acc = this.memory[operand]!; regs.acc = this.memory[operand]!; break; case "STORE": this.memory[operand] = r.acc; this.memory[operand] = regs.acc; written = operand; break; case "ADD": r.acc = this.adder.add(r.acc, this.memory[operand]!).sum; regs.acc = this.adder.add(regs.acc, this.memory[operand]!).sum; break; case "SUB": // Two's complement: invert the operand and add one through the carry in. r.acc = this.adder.add(r.acc, WORD_LIMIT - 1 - this.memory[operand]!, 1).sum; regs.acc = this.adder.add(regs.acc, WORD_LIMIT - 1 - this.memory[operand]!, 1).sum; break; case "JUMP": r.pc = operand; regs.pc = operand; break; case "JZ": if (r.zero) r.pc = operand; if (regs.zero) regs.pc = operand; break; case "OUT": this.output.push(r.acc); this.output.push(regs.acc); break; case "LOADI": r.acc = operand; regs.acc = operand; break; default: halted = true; } r.zero = r.acc === 0; regs.zero = regs.acc === 0; // ▸ execute: the accumulator, a memory word, or the program counter changes this.tracer?.emit("execute", { cycle: this.cycles, mnemonic: mnemonic ?? "HALT", operand, acc: r.acc, pc: r.pc, zero: r.zero, written, output: [...this.output], halted }); this.tracer?.emit("execute", { cycle: this.cycles, mnemonic: mnemonic ?? "HALT", operand, acc: regs.acc, pc: regs.pc, zero: regs.zero, written, output: [...this.output], halted }); return halted; }}