Module 09: Computer architecture

AND, OR and NOT operate on bits; XOR is one when its inputs differ. A half adder computes sum=a XOR b and carry=a AND b. With an incoming carry, a full adder produces a sum bit and an outgoing carry; chaining adders handles multiple bit positions. Combinational circuits depend on current inputs, while sequential circuits retain state, usually updated around clock events. A truth table specifies the function, but actual hardware also has propagation delay and physical constraints.

An instruction set defines machine-visible operations. Registers hold small working values; the program counter identifies the next instruction. Our model has an accumulator, a program counter, eight data slots and SET, ADD, STORE, HALT instructions. The logical cycle fetches an instruction, decodes its operation and updates state. Real processors may overlap work through pipelines, but observable results must respect their architecture's rules. The model is intentionally simpler and does not simulate pipelines or machine-code encoding.

Memory associates addresses with stored values. Loading reads a value; storing writes one. An address is not the same as the value at that address. In the lab, STORE 0 writes the accumulator into data slot zero; it does not set the accumulator to zero. Real byte-addressed machines need agreements on width, alignment and byte order when reading multibyte values. The model uses Python list slots rather than real byte-addressed RAM, so its eight slots must not be mistaken for an entire physical memory system.

Memory hierarchies trade capacity against access latency. A cache keeps recently accessed blocks. Temporal locality reuses the same data; spatial locality accesses nearby data. Our direct-mapped cache chooses line=address mod lines and tag=address divided by lines. A matching valid tag gives a hit; otherwise a new tag replaces it. Addresses 0 and 4 conflict in a four-line cache despite repeated reuse. Real caches use multi-byte blocks, associativity and write policies; the one-word read model isolates mapping conflicts.

Execution time depends on instruction count, average work per instruction and clock period, but these factors interact. A higher clock rate alone does not guarantee a faster whole program. Branches, memory stalls and data dependencies affect throughput. Optimising a tiny fraction of runtime also limits total speedup: if 90% remains unchanged, even infinitely accelerating the other 10% gives at most 1/0.9≈1.11 times overall speed. Profile before choosing a hardware or algorithm optimisation, and keep the model's assumptions explicit.

Download each script and run it in a terminal with Python 3.11 or later: python m09_cpu.py. On Windows, py -3 is an alternative; on some systems use python3. The labs use only the standard library. Predict the result before running, then complete the variations. Run without -O so assertions remain enabled. Outputs below were captured by the builder. Code and output are identical in both language editions.

Predict each accumulator value and program counter. This model increments the counter before executing the operation.

Download m09_cpu.py

"""A tiny 8-bit accumulator machine, not an emulator of a real CPU."""
def run(program):
    pc, acc, memory, steps = 0, 0, [0] * 8, 0
    while steps < 100:
        if not 0 <= pc < len(program):
            raise ValueError("program counter out of bounds")
        op, operand = program[pc]
        print(f"pc={pc} acc={acc:3} execute={op} {operand}")
        pc += 1; steps += 1
        if op == "SET": acc = operand % 256
        elif op == "ADD": acc = (acc + operand) % 256
        elif op == "STORE":
            if not 0 <= operand < len(memory): raise ValueError("invalid address")
            memory[operand] = acc
        elif op == "HALT": return memory
        else: raise ValueError("unknown instruction")
    raise RuntimeError("step limit exceeded")

result = run([("SET", 250), ("ADD", 10), ("STORE", 0), ("HALT", 0)])
print("memory[0]:", result[0])
assert result[0] == 4

pc=0 acc=  0 execute=SET 250
pc=1 acc=250 execute=ADD 10
pc=2 acc=  4 execute=STORE 0
pc=3 acc=  4 execute=HALT 0
memory[0]: 4

1. Compute 3+4 into slot 1.
2. Try STORE 9 and an unknown instruction.
3. Remove HALT and explain the boundary error.

Count hits independently of elapsed time. Initially every tag is invalid (None).

Download m09_cache.py

"""A direct-mapped, one-word-per-line read cache with no timing simulation."""
def access_trace(addresses, lines=4):
    tags, hits = [None] * lines, 0
    for address in addresses:
        index, tag = address % lines, address // lines
        hit = tags[index] == tag
        hits += int(hit)
        tags[index] = tag
        print(f"address={address} line={index} tag={tag} {'hit' if hit else 'miss'}")
    return hits

print("local reuse")
assert access_trace([0, 1, 0, 1]) == 2
print("conflicting reuse")
assert access_trace([0, 4, 0, 4]) == 0

local reuse
address=0 line=0 tag=0 miss
address=1 line=1 tag=0 miss
address=0 line=0 tag=0 hit
address=1 line=1 tag=0 hit
conflicting reuse
address=0 line=0 tag=0 miss
address=4 line=0 tag=1 miss
address=0 line=0 tag=0 miss
address=4 line=0 tag=1 miss

1. Try eight lines for [0,4,0,4].
2. Predict [0,1,2,3,0,1,2,3].
3. Explain what a larger block would change.

Try before opening the solution. ★ applies an idea; ★★ combines ideas; ★★★ asks for design or proof.

Choose an answer for feedback; reset to retry. A text answer key is available without JavaScript.

• Nand2Tetris project sequence — Inspect the hardware projects from gates to CPU; identify the abstraction at each stage.

Trace four instructions and explain a conflict miss. Module 10 shows how the operating system multiplexes and protects the underlying resources.