The Machine · Chapter 5
What is a CPU?

Watch the opener · 1:27

Transcript

What is a CPU? We've got an adder and a memory. Somehow, those two run every app on your phone.

So I figured each program gets its own wiring. Early computers really were rewired by hand, cable by cable. But nobody rewires a phone to open an app.

Here's the trick: the program is just numbers, in the same memory as the data. Each instruction is one eight-bit word. The left four bits say what to do, like load or add. The right four bits say where: a memory address. A counter points at the next instruction. Fetch it from memory. Decode its two halves. Execute it: load thirteen copies the number at address thirteen into a register. Then the counter steps on, and round it goes again: fetch, decode, execute.

So a new app is just new numbers in memory! A CPU fetches each instruction from memory, decodes it and executes it, again and again.

Step the CPU below, one cycle at a time. Watch it add three numbers and store forty-two.

Chapter 3 built an adder from gates: given two numbers it produces a sum and a carry after the gate delays settle, with no memory of what came before. Chapter 4 fixed that: a cross-coupled latch remembered one bit; a master-slave flip-flop disciplined that memory to a clock edge; and a decoder over a bank of registers became a RAM that holds words and keeps them, a memory this chapter grows to program size. Those two machines are not separate devices. They are components, and this chapter wires them together. The result is a CPU.

A CPU is a machine that reads instructions from memory and obeys them, one at a time. Each instruction names an operation and a memory address. The CPU fetches the instruction, decodes the two fields, carries out the operation, and then returns to fetch the next. That loop is called the fetch-decode-execute cycle. Running it fast and correctly is what a processor does.

5.1 The stored-program idea

Some early machines were programmed through switches and plugboards; others, such as Harvard’s Mark I, read instructions from punched tape. The stored-program idea made instructions data in addressable memory, alongside the numbers they operate on. To run a different program on this machine, you write different bytes into memory; you do not touch the hardware.

The accumulator, the program counter, and the memory cells of this chapter are the components of Chapter 4 in spirit: a register to hold a running total, a register to hold the address of the next instruction, and a RAM to hold both the program and the data it works on. The model here keeps them as plain numbers rather than banks of flip-flops; the shape is Chapter 4’s even where the code is not. No new hardware is needed. What changes is how those components are connected and what directs them.

The director is the control unit, a small piece of logic that reads an opcode and asserts the right signals. Together, the ALU of Chapter 3, the memory of Chapter 4, and the control unit form the CPU.

5.2 An instruction set

An instruction set is the contract between software and hardware. It names every operation the CPU can perform and specifies how an instruction is encoded. The machine here is an accumulator machine: all arithmetic flows through a single working register called the accumulator. There is no general-purpose register file; every ADD reads one operand from memory and adds it to whatever the accumulator currently holds.

The accumulator holds eight bits. An ADD keeps the low eight bits of the sum and discards the extra carry from the ripple adder. For example, adding 1 to 255 leaves 0: the value wraps around at 256.

Six opcodes are enough to compute, to store results, and to branch.

An instruction is one 8-bit word. The high nibble (bits 7 to 4) carries the opcode; the low nibble (bits 3 to 0) carries the operand, a memory address for every instruction that uses one. Figure 5.2 shows the layout. With a 4-bit opcode there is room for 16 distinct operations; with a 4-bit operand the machine can address 16 memory words directly. This chapter defines six of those opcode values; the remaining ten are unused and the model rejects them rather than treating them as hidden instructions.

The code that performs this split is the decoder. It calls to_bits to expand the word into eight bits, then reads the two nibbles.

Example 5-1. Instruction decoder: split an 8-bit word into opcode and operand

def decode(word: int) -> tuple[int, int]:
    """Split an instruction word into (opcode, operand), the field extraction a
    hardware decoder performs."""
    bits = to_bits(word, _WORD_BITS)
    operand = from_bits(bits[0:4])1
    opcode = from_bits(bits[4:8])2
    return opcode, operand

• operand = from_bits(bits[0:4]): the low nibble. Bits are stored least-significant first, so index 0 is bit 0. The operand is the 4-bit address the instruction names, exactly the right field shown in Figure 5.2.
• opcode = from_bits(bits[4:8]): the high nibble. Bits 4 through 7 carry the operation code, the left-hand field in the bytefield diagram.

5.3 Fetch, decode, execute

The CPU runs one loop forever until a HALT instruction stops it: fetch the word at the program counter, advance the counter, decode the word, execute the operation. Figure 5.3 shows the three steps.

Figure 5.3. The fetch-decode-execute cycle. Each turn of the loop reads one instruction, advances the program counter, and carries out the operation. JUMP and JZ overwrite the already-incremented PC so the next fetch starts at the branch target.

The CPU class holds the whole machine state: a 16-word memory array, the accumulator, the program counter, and a halted flag. Its byte_word helper checks each supplied program word before loading: an integer from 0 to 255 is returned unchanged; any other input is rejected.

Example 5-2. CPU class: one step is one fetch-decode-execute cycle

class CPU:
    """Accumulator CPU: memory, accumulator, program counter, halted flag."""

    def __init__(self, program: list[int]) -> None:
        if len(program) > _MEMORY_WORDS:
            raise ValueError(
                f"program has {len(program)} words but memory holds {_MEMORY_WORDS}")
        words = [byte_word(word) for word in program]
        self.memory = words + [0] * (_MEMORY_WORDS - len(words))
        self.acc = 0
        self.pc = 0
        self.halted = False

    def step(self) -> None:
        """Run one fetch-decode-execute cycle."""
        if self.halted:
            return
        word = self.memory[self.pc]1
        self.pc = _add(self.pc, 1, _ADDR_BITS)2
        opcode, operand = decode(word)3
        if opcode == HALT:4
            self.halted = True
        elif opcode == LOAD:
            self.acc = self.memory[operand]
        elif opcode == STORE:
            self.memory[operand] = self.acc
        elif opcode == ADD:
            self.acc = _add(self.acc, self.memory[operand], _WORD_BITS)
        elif opcode == JUMP:
            self.pc = operand
        elif opcode == JZ:
            if self.acc == 0:
                self.pc = operand
        else:
            raise ValueError(f"unknown opcode {opcode}")

    def run(self, max_steps: int = 100) -> None:
        """Step until HALT, retaining the current state if the budget runs out.

        Raises:
            RuntimeError: The CPU has not halted after max_steps instructions.
        """
        steps = 0
        while not self.halted and steps < max_steps:
            self.step()
            steps += 1
        if not self.halted:
            raise RuntimeError(f"CPU did not halt within {max_steps} steps")

• word = self.memory[self.pc]: the fetch. The PC is an index into the memory array, and this line reads the instruction word stored at that address, exactly as a real CPU drives the address bus and reads the data bus.
• self.pc = _add(self.pc, 1, ...): the advance. The PC is incremented through the gate-built ripple adder of Chapter 3, so every counter step is still gates all the way down. Because the increment happens before execute, any JUMP or JZ that fires overwrites the already-advanced PC with the branch target.
• opcode, operand = decode(word): the decode step calls the function from Section 5.2 to split the word into its two fields.
• if opcode == HALT: the control dispatch. Each branch of the conditional corresponds to one row of the instruction-set table. This is the control unit: a decision tree over the opcode that asserts the right signals.

5.4 The datapath

Figure 5.4 shows how values move between the components. During fetch the program counter selects the memory address. The decoder splits the instruction: the opcode goes to the control unit; the operand selects the data address during a LOAD, ADD, or STORE. On ADD, the ALU adds the returned word to the accumulator. On LOAD, that word bypasses the adder. A multiplexer selects which value enters the accumulator, so loading 1 and then 2 leaves 2, not 3.

The control unit enables the accumulator write or the STORE write to memory. It also receives the operand as a branch target and a zero test of the accumulator for JZ. A dedicated ripple adder (the +1 node) advances the PC; a taken branch overrides that value. The drawing shows these value routes, leaving the phase-controlled memory-address and PC-input selectors, and the register write-enable lines, implicit.

The accumulator and the PC are the registers of Chapter 4: small fixed-width stores that hold a value across cycles. The adder is the circuit of Chapter 3: given two inputs it produces a sum. Only the control unit is new, and it is just a conditional on the opcode.

5.5 Running a program

An example program sums three values stored at addresses 13, 14, and 15, writes the result to address 12, and halts. It is five instructions followed by three data cells with room to spare in the 16-word address space.

Example 5-3. Example program: sum three data cells and store the result

def example_program() -> list[int]:
    """A program that sums three data cells (addresses 13, 14, 15) into the
    accumulator, stores the result at address 12, and halts."""
    program = [0] * _MEMORY_WORDS
    program[0] = encode(LOAD, 13)1
    program[1] = encode(ADD, 14)
    program[2] = encode(ADD, 15)
    program[3] = encode(STORE, 12)
    program[4] = encode(HALT, 0)
    program[13], program[14], program[15] = 10, 20, 12
    return program

• program[0] = encode(LOAD, 13): the first instruction loads the value at address 13 (which is 10) into the accumulator. The two ADD instructions that follow accumulate the values at addresses 14 and 15. Each call to encode packs an opcode and an address into one 8-bit word using the layout of Figure 5.2.

Figure 5.5 is the memory image this function builds, the moment before the first cycle. The five instructions occupy addresses 0 through 4 and the data sits at 13 through 15, safely past the last instruction. Address 12 is the result slot, initially zero; after STORE 12 executes it will hold 10 + 20 + 12 = 42.

The interactive version needs the in-browser runtime.

The model’s run() method executes at most 100 instructions per call. It returns normally only after HALT; otherwise it raises RuntimeError, leaving the current state available for inspection. For a longer, known-to-terminate program, pass a larger budget, such as cpu.run(max_steps=200), or call it again to resume. This limit bounds the simulation; reaching it does not mean a computation has finished.

The main machine is now complete: switches became gates, gates became arithmetic and memory, and those pieces became a CPU that runs a stored program. The next pages are optional processor side reads. They ask how circuits this large are described, how one core overlaps work, how it hides slow memory, and how an FPGA loads a circuit as data. Read them in that order for a closer look at hardware, or finish the main path here. The planned software part will return to this stored-program CPU and replace hand-encoded bytes with readable names.

Exercises

• Add a subtract instruction to the machine. What is the smallest change to the decoder and the run loop? Chapter 3’s exercises asked you to build subtraction.
• Write a program in this instruction set that multiplies two small numbers by repeated addition, and run it. For a countdown, adding 255 decrements a nonzero counter because the accumulator wraps at 256. Count the loop’s instructions when choosing max_steps; a partial accumulator is not the final product.