Assembling a Complete CPU

This is the lesson the whole course was building toward. We have every part: the ALU that adds and subtracts and sets flags, the register file with its two read ports and two clocked write ports (dstE, dstM), the addressed memory, the Y86-64 ISA that fixes the bytes, and the control logic that drives the muxes. We even traced a program through SEQ. What is left is the assembly itself, done the way an engineer would actually do it: draw the complete machine with every named part in its place, say which lesson built each, wire the parts in a deliberate order, define the reset state and watch the first fetch happen, then run a real compiled program (a procedure call, a loop, an array in memory) from power-on to halt. When the answer lands, we ask the two questions any real project ends with: how do you know it works, and what would it take to build two?

The complete CPU, part by part

A CPU is seven kinds of part, and the course built each one. Fetch needs a place to keep the address of the next instruction and a place to read instruction bytes from: the program counter (PC) and the instruction memory, whose current output — the fetched instruction word — the Split and Align logic of module 4's fetch stage breaks into fields combinationally (no register latches it; the machine's clocked state elements remain the four SEQ counted: PC, CC, register file, data memory). Decode and write-back need the register file. Execute needs the ALU and, beside it, the condition-code register (CC) that latches ZF, SF, and OF whenever an OPq instruction runs. Memory needs the data memory. And tying them together, deciding from the decoded opcode which mux selects what and which register gets written, is the control unit: the hardwired control logic of a Y86-64 machine (in a microprogrammed design the same job is done by a microsequencer stepping through microinstructions, but the role is identical).

The discipline is the one SEQ taught: functional units stacked along a central spine, data handed straight up, and the two feedback wires — write-back to the register file, and newPC to the PC — routed in separate right-hand margins where they cross nothing. The control unit stands to one side, reads icode:ifun out of the fetched instruction word, and sends a signal to every unit. One wire is drawn small but matters enormously: the CC register's three flags flow back into the control unit (through the Cnd condition logic), because a jne cannot decide newPC without them. That single feedback is the machine's only means of decision; everything else is data routing.

This machine uses ideal one-cycle memories, as SEQ always did. On the full die, the previous lesson's block diagram wraps these two memory boxes in TLBs, caches, and DRAM; nothing in this lesson changes when it does, which is the point of the memory-hierarchy abstraction.

Here is the provenance, part by part: which lesson built each.

Wiring order and bring-up

Assembly has an order, and the order is not arbitrary. First the data spine, bottom to top: PC into instruction memory, the fetched fields into the register file's read addresses, read ports into the ALU, ALU output into the data memory's address port. This much is purely feed-forward: signals flow one way, and each connection can be checked in isolation by driving the input and probing the output. Second, the two feedback paths: write-back to the register file and newPC to the PC. These close loops, so they come after the spine works; a loop wired around a broken spine oscillates or latches garbage, and you cannot tell which part failed. Third, the CC register beside the ALU and its Cnd wire to control. Last, the control fan: the decoder in the control unit that reads icode:ifun and drives every mux select and write-enable, one stub per unit. Control comes last because it is meaningless until the things it controls exist: every one of its output wires names a mux or a port that has to be there already. This is the same inside-out order the SEQ assembly lesson followed; the capstone only makes it explicit as a checklist.

With the machine wired, it has to start. A CPU has no operator; the only thing that distinguishes cycle 1 from cycle 1,000,000 is the state the machine wakes up in, so that state must be defined by hardware, not by luck.

Every choice here is a convention, and each has a reason. PC = 0x000 means the machine's first act is to fetch M[0x000], so whoever loads memory knows exactly where to put the entry point. Registers start at zero so no computation depends on power-on noise. ZF = 1 matches what the flags would show after computing zero, which is the honest description of a machine that has computed nothing. And Stat = AOK arms the machine to run. That is the entire boot process for this CPU: reset forces a known state, memory holds bytes at address 0x000, and the clock does the rest. Real x86-64 machines are no different in kind (the PC resets to a fixed address that points into firmware ROM instead of a loaded program), and everything a modern boot does is layered on this one mechanism.

The first fetch is not special. Cycle 1 runs the same fetch–decode–execute sequence as every later cycle; the machine cannot tell boot from steady state. Everything rests on the two facts the hardware guarantees: a defined PC and defined bytes at that address.

The test program: an array sum with call and ret

The countdown loops we traced in module 4 exercised arithmetic and a branch, but a real program does more: it keeps data in memory, walks a pointer across it, and calls procedures. So the capstone's test program is chosen to touch every instruction class the ISA defines: immediate moves (irmovq), a memory read (mrmovq), register arithmetic that sets flags (addq, subq, xorq), a conditional branch (jne), the stack pair (call/ret), and halt. It sums a four-element array through a procedure, the same shape as CS:APP's asum: main sets up the stack and the arguments, then calls sum(array, 4).

# main: set up the stack, then sum(array, 4)
irmovq stack, %rsp    # rsp = 0x200      (stack pointer)
irmovq array, %rdi    # arg 1: base of array
irmovq $4, %rsi       # arg 2: element count
call sum              # push return addr, jump to sum
halt

# long sum(long *start, long count)
sum:
irmovq $8, %r8        # r8 = 8   (element stride)
irmovq $1, %r9        # r9 = 1   (decrement constant)
xorq %rax, %rax       # sum = 0  (and sets ZF = 1)
loop:
mrmovq (%rdi), %r10   # r10 = *start
addq %r10, %rax       # sum += *start
addq %r8, %rdi        # start++
subq %r9, %rsi        # count--
jne loop              # repeat while count != 0
ret                   # pop return addr into PC

.align 8
array:
.quad 0x000d000d000d
.quad 0x00c000c000c0
.quad 0x0b000b000b00
.quad 0xa000a000a000

.pos 0x200
stack:                # stack grows down from 0x200

The array values are chosen so the answer proves itself. Each quad fills a different nibble of every 16-bit group, so the running sum assembles the digits a, b, c, d in place, and the correct total is unmistakable: $\text{0xabcdabcdabcd}$. A single transposed byte anywhere in the machine and the pattern breaks visibly.

The assembler lays the code out from address 0x000. Each irmovq is 10 bytes, each OPq is 2, call and jne are 9 (opcode byte plus 8-byte destination), ret and halt are 1. That fixes every address, and fixing the addresses resolves every label: sum lands at 0x028, loop at 0x03e, array at 0x058 (already 8-aligned), and stack is pinned to 0x200 by the .pos directive. The bytes follow the ISA encodings: register nibbles %rax=0, %rsp=4, %rsi=6, %rdi=7, %r8=8, %r9=9, %r10=a, and every constant little-endian.

The program is only part of the memory image. The array sits right after the code, and the stack, empty at reset, hangs below 0x200, growing toward lower addresses when call pushes.

These bytes are the whole input. The machine starts with PC = 0x000, the image above sitting in memory, and from there it runs itself.

Tracing it, cycle by cycle

The assembled CPU executes one instruction per cycle: in a single tick it fetches at the PC, decodes the fields, reads registers, runs the ALU, touches memory if needed, writes back, and computes newPC; the new register, condition-code, memory, and PC values clock in at the rising edge. The whole run is 29 cycles: three setup moves, the call, three cycles of sum prologue, four loop iterations of five cycles each, ret, and halt. Here are the cycles where something new happens.

Three cycles deserve a closer look, because each one runs a mechanism the countdown trace never touched.

Cycle 4, the call. This is the only instruction in the program that both writes memory and takes a non-sequential newPC. The ALU computes valE = R[%rsp] - 8 = 0x1f8; the Memory stage writes valP = 0x027 (the address of the instruction after the call, the halt) into M[0x1f8]; write-back puts valE into %rsp; and newPC = valC = 0x028. One cycle, three effects — and the return address is now data, sitting in memory like any other quad, exactly as the procedures lesson promised.

Cycle 7, the xorq. Zeroing a register by xoring it with itself is the idiom from the machine-level module, and it has a side effect the trace makes visible: the result is zero, so ZF becomes 1. If the loop guard were checked here, it would fall through. The program is correct only because subq reruns the flags every iteration before jne reads them; flag liveness is part of the program's logic.

Cycle 8, the mrmovq. The first true memory read: valE = R[%rdi] + 0 = 0x058, and the Memory stage returns valM = M[0x058] = 0x000d000d000d, the little-endian bytes 0d 00 0d 00 0d 00 00 00 reassembled into a quad. On the full machine this is the access that would traverse the d-TLB and cache; here the ideal memory answers in-cycle.

From there the loop turns four times, and the sum builds its answer nibble by nibble. Each element contributes a different hex digit to every 16-bit group, so you can watch correctness accumulate:

Meanwhile %rdi walks 0x058, 0x060, 0x068, 0x070 and %rsi counts 4, 3, 2, 1, 0. The iteration-4 subq (cycle 26) produces zero and sets ZF = 1, so the cycle-27 jne falls through to 0x057. Cycle 28, the ret, undoes the call symmetrically: Memory reads valM = M[0x1f8] = 0x027, the ALU computes valE = R[%rsp] + 8 = 0x200 for write-back into %rsp, and newPC = valM — control returns to main not because the machine remembers the call, but because the address was parked in memory and fetched back. Cycle 29 fetches halt at 0x027, Stat becomes HLT, and the machine stops with $\text{\%rax}=\text{0xabcdabcdabcd}$.

Trace any one of those cycles into the block diagram and every value is derived, not asserted. In cycle 9 the PC holds 0x048; the control unit, reading icode:ifun = 6:0 out of the fetched instruction word, drives the register file to read %r10 and %rax as valA and valB, steers both into the ALU with alufun = add, asserts set_cc, routes the ALU output past the idle data memory to the register-file write port with dstE = %rax, and — seeing icode is neither call, jump, nor ret — selects newPC = valP = 0x04a. Not one wire was set by hand. The opcode configured the fixed datapath, and the datapath did the rest.

Validating the machine

A trace that ends in the right answer is evidence, not proof. Real hardware teams spend more effort on verification than on design, and the structure of that effort follows the structure of the machine: test the parts, then the contracts between them, then the whole.

Unit tests, one part at a time. Each functional unit has a small, closed specification, so test it against that spec in isolation. The ALU is combinational: drive operand pairs and check outputs: exhaustively at narrow widths (every 8-bit pair is only 65,536 cases per function), then structured 64-bit cases targeting the carry chain: 0 + 0, 1 + (-1), alternating patterns, and the overflow boundaries from integer arithmetic. The register file is stateful, so its test is temporal: write a distinctive value to each register, read it back on both ports, and check the corner the clocking lesson worried about: a read of the register being written this cycle must return the old value, because the write lands at the edge. Memories get address-in-data patterns (write 0x58 at 0x58) so any addressing error shows as a mismatch.

The control table. The control unit is a pure function from icode:ifun (and Cnd) to a bundle of mux selects and write-enables, and the control-logic lesson wrote that function down as a table. So the test is table-against-table: for each of the ISA's opcodes, apply the opcode, read every control output, and compare with the specified row. This catches the classic assembly bug (a mux wired to the right control signal but with its inputs swapped) before any program runs.

Per-instruction programs against the ISA model. The ISA is the machine's specification, and it is executable: an ISA-level simulator (CS:APP's yis) applies each instruction's defined effect to an architectural state with no hardware in sight. So write one tiny program per instruction (a mrmovq and a halt, a call and a halt), run each on the hardware and on the model, and compare the complete architectural state (registers, CC, memory, PC, Stat) after every instruction. Any divergence identifies the faulty instruction directly. Then add the behavioral pairs: jne taken and not taken, call followed by ret, flags set then read.

Integration. Only now run asum.ys, and the cycle table above is what the comparison looks like: the hardware's state trace laid against the model's, cycle by cycle, with 0xabcdabcdabcd as the visible checksum at the end. A pipelined build adds one more layer, the hazard suite from module 5: load-use pairs, ret followed immediately by work, a mispredicted branch with in-flight wrong-path instructions, each written to force one forwarding or stall path and checked the same way, against the ISA model that never pipelines anything.

Scaling up: the same machine, faster

What we built is the simplest correct CPU: one instruction per cycle, every stage finishing before the next instruction begins. The rest of computer architecture is this exact machine made faster, with the datapath unchanged in spirit.

• Pipelined (PIPE). Insert registers between the stages and let several instructions occupy the datapath at once, as the complete PIPE does. The functional units are the very same PC, register file, ALU, and data memory; the additions are pipeline registers, forwarding paths, and a control unit that stalls or bubbles each register to handle hazards. On asum.ys the effect is concrete: the mrmovq/addq pair in the loop body is a load-use hazard costing one bubble per iteration, and each ret injects three — the previous lesson's swimlane is this program's inner loop.
• Real x86-64 silicon. A modern core is the same idea scaled hard: a deep pipeline, several ALUs, out-of-order issue, aggressive branch prediction, and a multi-level cache feeding it: the mechanisms the previous lesson's honesty section flagged as beyond scope. The instruction set is larger and the encodings messier, but underneath, an opcode still configures a fixed datapath of adders, register files, and memories, cycle by cycle.

Two of them on one die

There is a second axis of scaling, and after module 9 we can be precise about it. Duplicating the core is the easy part: the block diagram above, stamped twice. What the duplication demands is three new mechanisms, none of which exists anywhere in the single-core machine:

1. Coherence for the caches. Each core needs private caches to run at speed, and the moment two caches can hold the same line, the machine needs a coherence protocol: every line carries a MESI state, and a write in one core invalidates the copy in the other before it may proceed. Without this, our asum array could be summed from stale bytes.
2. An interconnect. The single wire from CPU to memory becomes a shared fabric: a snooping bus at two cores, a ring or mesh beyond that, carrying both memory traffic and the coherence messages, with the shared last-level cache hanging off it.
3. Atomic instructions. Software on two cores must be able to build locks, and ordinary load–modify–store sequences interleave. The ISA grows an atomic read-modify-write family (lock-prefixed ops, xchg, cmpxchg) and fences, the machinery of memory consistency and synchronization. The coherence protocol is what makes them enforceable, by letting a core hold a line exclusive for the duration of one read-modify-write.

And once the hardware exists, something must feed it two instruction streams: threads, scheduled by the kernel our interrupt machinery already lets in every millisecond, or even two thread contexts inside one core, sharing the pipeline we just assembled. The capstone machine is the unit cell; module 9 is the crystal.

So the machine in the block diagram is the real thing in its clearest form. Everything faster is this datapath plus mechanisms to overlap and feed it; everything bigger is this datapath duplicated plus mechanisms to keep the copies consistent; everything below is the gates we built it from. That is the whole course in one picture: a switch became a gate, gates became an ALU and a register file, an ISA fixed the bytes, control wired the parts, and the assembled machine ran a program to the right answer, with nothing directing it but its own PC and the bytes it pointed at.