The Whole Machine

We have built every layer separately. We fixed the units — bits and bytes, then the ALU and the register file. We fixed the Y86-64 ISA the machine speaks, wired the units into SEQ, watched it run a program, then pipelined it, gave it caches and virtual memory, connected it to the outside world, and finally put a second one on the die. What we have not yet done is stand back and see the layers as one thing. This lesson makes two passes over the whole machine. First a vertical pass: a single line of C followed straight down the tower, from source to the charge that moves in DRAM. Then a horizontal pass, the grand tour: two instructions traced through the full machine — pipeline stages, forwarding, TLBs, caches, a possible page fault, a timer interrupt — with every stop cross-linked to the lesson that built it. No new mechanism appears; the point is that every mechanism covered is one stop on a path a value actually travels, and they compose.

One line, all the way down

Here is the line. It is the smallest thing that touches every layer: a read from memory, an arithmetic op, a write back.

long s = a[i] + 1;

Nothing about it looks like hardware. a is an array, i an index, s a variable; the + 1 is arithmetic the way a calculator does arithmetic. But there is no array, no variable, and no addition in the machine — only bytes in memory and a datapath pulling them in. Each layer below translates this line into the vocabulary of the layer beneath it, until what is left is gates switching.

Compiler and assembler: C becomes bytes

The first translation is the compiler, which lowers the C line into assembly. It must turn the named array access a[i] into an explicit address computation (a base register plus an index scaled by the element size) and the abstract + 1 into a concrete instruction with a size suffix. In x86-64 the line might compile to a load, an add, and a store; in the Y86-64 subset the course implements, the same three moves look like this.

mrmovq (%rdi), %rax    # rax <- M[a + i*8]   (the load; %rdi holds the address)
irmovq $1, %r8         # r8  <- 1            (the constant)
addq   %r8, %rax       # rax <- rax + 1      (the + 1)
rmmovq %rax, (%rsi)    # M[&s] <- rax        (store back to s)

The assembler then performs the second translation, and it is purely mechanical: each line becomes the exact bytes the ISA lesson specified. mrmovq (%rdi),%rax is icode:ifun = 5:0, register byte rA:rB = 0:7 (%rax:%rdi), and an 8-byte displacement of zero: ten bytes, 50 07 00 00 00 00 00 00 00 00. addq %r8,%rax is 60 80, two bytes. There is no cleverness left at this level: the assembler is a lookup table from mnemonics to the icode:ifun byte, the register nibbles, and the little-endian constant. After it runs, the C line exists nowhere — what sits in memory is a run of bytes, and those bytes are the program.

The three notations are worth seeing side by side, because the machine only ever sees the rightmost column, yet all three are descriptions of the same single instruction.

The datapath: bytes become work

Now the bytes are in memory and the PC holds the address of the first one. From here the machine drives itself, with no compiler and no assembler in sight, just the fetch–decode–execute loop turning bytes into state changes.

• Fetch reads the bytes at the PC. For our load it pulls 50 07 00 …, splits the first byte into icode:ifun = 5:0, reads the register byte 0:7, and reads the 8-byte displacement. It also computes the next-instruction address $\text{valP}=\text{PC}+\text{len}$, where $\text{len}$ is this instruction's byte length (10 here).
• Decode uses the register nibbles as addresses into the register file: it reads %rdi (the array base address) out the combinational read port as valB. No clock, no waiting: the read port simply presents the register's contents.
• Execute sends the base and the displacement into the ALU, which adds them (the same ripple-carry adder from digital logic) to form the effective memory address valE = R[%rdi] + 0. For the later addq it is this same ALU that performs the actual + 1 and sets the condition codes.
• Memory presents valE as an address to data memory and reads the word there, valM — this is the a[i] access finally happening.
• Write-back clocks valM into %rax through the register file's write port.
• PC update loads valP, and the loop repeats with the next instruction.

Every one of those steps is a unit we built and a mux the control unit selected. The opcode 5:0 is what tells the control logic to route the ALU output to the memory address port and the memory output to the register write port; a different opcode would steer the same wires to a different shape. The datapath is fixed silicon; the opcode is what configures it, cycle by cycle.

Down to silicon, and the memory request path

Two layers remain below the datapath. The first is the physical logic: the ALU's adder is full adders, each a 3-input XOR and a majority gate; the register file's ports are decoders and multiplexers; the muxes the control unit drives are AND–OR trees. The + in a[i] + 1 is, at the bottom, a carry rippling through a row of gates, which is a wave of transistors switching. There is no arithmetic down there: only switches that, wired the way digital logic prescribed, compute the sum as a side effect of settling.

The second is the memory request path. When Memory asks for the word at valE, that address is a virtual address, and reaching the real bits takes several steps. The cache is checked first; on a miss the virtual address is translated to a physical one (the TLB answers fast if it has seen the page; otherwise the page table in memory is walked), and only then does the request reach physical DRAM, where reading the word means sensing charge on a row of one-transistor cells and restoring it after the destructive read. The observed access time is the hit time plus the amortized miss penalty,

with miss rate $m$ and $T_{\text{miss}}$ the cost of descending toward DRAM; the whole hierarchy exists to drive $m$ toward zero so $T_{\text{access}}\to T_{\text{hit}}$. Two side exits complicate the picture, and the course built both. If the walk finds the page absent, the access does not complete at all: it becomes a page fault, the kernel pages the data in from disk, and the instruction re-executes. And on the multicore die of module 9, a miss consults more than DRAM: the freshest copy of the line may be sitting modified in a peer core's cache, and the coherence protocol must fetch it from there, because DRAM's copy is stale.

The word comes back the way it went out — DRAM to cache to the datapath's Memory stage — and rises through Write-back into %rax, where the addq adds one and the rmmovq sends it down the same path again to store s. The whole round trip, from a C subscript to charge in a capacitor and back, is the course read end to end.

The grand tour: two instructions on the full machine

The walk above ran on bare SEQ: ideal one-cycle memories, one instruction at a time, nothing else on the machine. The later modules removed every one of those simplifications. Pipelining put five instructions in flight at once; caches made memory fast only where locality holds; virtual memory inserted a translation between every address the program names and every address the hardware touches; interrupts let the outside world preempt the program between any two instructions; and module 9 put a second core on the die and required the caches to stay coherent. Here is the machine as the course actually left it.

Now run two instructions from the compiled line — the load mrmovq (%rdi),%rax and, right behind it, addq %r8,%rax — across this machine, stage by stage. This is the course's grand tour: every clause below is a lesson.

Fetch. The pipeline does not wait to be sure what to fetch next; the PC prediction logic guesses (for straight-line code, correctly) that the next instruction follows the current one, and fetch proceeds. The PC it presents is a virtual address, so it is translated first: the i-TLB answers in the same cycle if the page is warm (the TLB lesson). The physical address then indexes the L1 i-cache, whose set-index/tag-compare machinery returns the ten instruction bytes on a hit. The fetch stage splits them: icode:ifun = 5:0, registers 0:7, displacement 0, and valP.

Decode. The register nibbles address the register file, which presents %rdi combinationally. But in a pipeline the register file can be stale: an older instruction that writes %rdi may still be in flight ahead of us. So decode does not use the file's value blindly: the forwarding logic compares our source registers against the destination fields of everything in Execute, Memory, and Write-back, and takes the youngest match off the bypass wires instead. For this load there is no conflict; valB = R[%rdi] stands.

Execute. The ALU adds base and displacement to form the effective address, exactly as in SEQ. A mrmovq leaves the condition codes alone; only the OPq instructions set them.

Memory. The effective address is again virtual: the d-TLB translates it. A TLB miss costs a page-table walk: a few dependent memory reads, tens of cycles. And if the walk finds the page not present, the access does not merely slow down; it cannot complete. The machine raises a page fault: the mrmovq and everything younger is cancelled, the exception machinery transfers to the kernel with the faulting address in hand, the kernel pages the data in from disk, and the same mrmovq re-executes as if nothing happened: precise exceptions, doing exactly the job PIPE's special cases prepared for. On the ordinary path the physical address probes the L1 d-cache; a hit returns valM in a few cycles, and a miss descends the hierarchy toward DRAM, two hundred cycles away. On the multicore die, that miss carries one more obligation: the coherence protocol checks whether the other core holds the line modified, and if so the data comes from the peer cache, not from DRAM, whose copy is stale.

Write-back. valM reaches the register file's write port and clocks into %rax at the rising edge. One instruction done.

Meanwhile the addq %r8,%rax has been one stage behind the whole time, and it needs %rax — the very register the load is still fetching from memory. This is the load-use hazard: forwarding alone cannot fix it, because when addq sits in Decode the load's data does not exist anywhere in the pipeline yet. The control logic holds addq in Decode for one extra cycle and injects a bubble into Execute; one cycle later the load is in Memory, its valM appears on the bypass wire, and forwarding hands it straight to addq's Decode: the register file itself is skipped.

The outside world can also cut in at any instruction boundary. Suppose the millisecond timer fires while the load is in Execute. Nothing halts mid-gate. The interrupt machinery picks a clean boundary: instructions ahead of the boundary complete, instructions behind it are cancelled, the address of the next unexecuted instruction is saved, and control vectors through the interrupt table into the kernel. The kernel may only tick its clock and return, or it may decide this thread's quantum is spent and hand the core to another thread, loading that thread's saved registers and page-table base. Either way, when our program next runs, the saved PC is restored and the trace resumes exactly where it stopped. The program cannot tell it was ever off the CPU; that invisibility is the whole design goal of exceptional control flow.

The map of the course

Three strands of the course ran in parallel and met in the middle. The program strand (foundations, machine-level x86-64, the ISA) settled what must be computed, ending in an exact contract: bytes with defined meanings. The processor strand (digital logic, processor design, pipelining) built the thing that honors the contract, ending in PIPE. And the memory-and-world strand (the memory hierarchy, virtual memory, exceptions and I/O, multicore) surrounded that processor with everything a real machine needs: storage that keeps up, address spaces that protect, a connection to devices, and more cores than one. The capstone is where the strands tie.

Read the map against the grand tour and the two agree: the program strand wrote the bytes the tour fetched, the processor strand executed them, and the memory-and-world strand served every address, fault, and interrupt along the way.

What we simplified

The machine above is real — it is, structurally, the machine in your laptop. But a modern x86-64 core is bigger than PIPE in three specific ways this course chose to leave out, and honesty requires naming them. Each gets a paragraph and a pointer; all three are beyond this course's scope, sketched in CS:APP §5.7.

Out-of-order execution. PIPE keeps instructions in program order from fetch to write-back; one long stall holds up everything behind it. A modern core does not wait. It renames registers to strip false dependences, parks decoded instructions in an issue queue, and lets each one run the moment its own operands are ready, often with hundreds of instructions in flight, finishing in an order the program never wrote. A reorder buffer then retires results strictly in program order, so the architectural state advances as if execution had been sequential and exceptions stay precise. The effect is a machine that extracts the dataflow graph from the instruction stream at runtime and executes the graph, not the listing.

Superscalar issue. PIPE launches at most one instruction per cycle, so $\text{CPI}\ge 1.0$ always. A superscalar core of width $w$ issues up to $w$ instructions per cycle, admitting $\text{CPI}\ge 1/w$ — with $w=4$–$8$ instructions dispatched into multiple ALUs, load/store ports, and branch units. The cost is roughly quadratic growth in the machinery we built once: forwarding networks between every producer and every consumer, hazard checks across every pair of in-flight instructions, register files with a dozen ports instead of our three. Nothing conceptually new appears (the same hazards, the same bypasses), but the bookkeeping multiplies until it dominates the die.

Speculation beyond branches. We speculated on exactly one thing: branch direction, with a squash-and-refetch when wrong. Real cores speculate wholesale: that a load will not conflict with an older store whose address is still unknown, that a value will match last time's, that the next cache lines the program wants are the ones a prefetcher guesses. Every guess needs recovery machinery when it misses, and the guesses leave footprints: a speculatively loaded line sits in the cache even after the speculation is squashed, a residue that timing can observe and that modern security work spends real effort containing.

None of these change the contract. An out-of-order, superscalar, deeply speculative core still presents the ISA's illusion: instructions appear to execute one at a time, in order, exactly as SEQ actually does it. That is why the simple machine is worth building: it is the specification the complicated one must imitate.

Where the three simplifications came from

CS:APP §5.7 sketches the modern out-of-order core; the ideas have names and origins worth attaching, because each answers a specific question the simple machine leaves open, and each is still live.

Out-of-order issue is a 1967 idea. The mechanism that lets a modern core run instructions as their operands become ready, rather than in program order, is Tomasulo's algorithm, designed for the IBM System/360 Model 91's floating-point unit.¹ Its two moving parts are the ones the what we simplified section named: reservation stations that hold waiting instructions and a result-broadcast bus that wakes them, which together perform register renaming implicitly. Nearly every high-performance core since is a descendant. The reorder buffer that retires results back in program order — keeping exceptions precise — was added later, and the canonical treatment of precise interrupts on such a machine is Smith and Pleszkun's.²

Branch prediction is what makes deep pipelines viable. The course predicted branch direction with a simple scheme; real cores use two-level and correlating predictors that learn per-branch and per-history patterns, the line of work opened by Smith and extended by Yeh and Patt.³ The deeper the pipeline and the wider the issue, the more a misprediction costs, so prediction accuracy — now well above 95% on typical code — is what keeps a fifteen-stage superscalar core from losing most of its work to squashes.

Speculation left a security hole. The lesson noted that a speculatively loaded cache line sits in the cache even after the speculation is squashed, a residue that timing can observe. That residue is not hypothetical: it is the basis of Spectre and Meltdown (2018), which trick a core into speculatively accessing data across a protection boundary and then read the secret back out through cache timing, even though the architectural state was correctly rolled back.⁴ The architecture/microarchitecture split this course leaned on — the promise that microarchitecture is invisible to correctness — turned out to leak: the timing of the implementation is observable in a way the ISA never accounted for. It is a reminder that invisible to results is not the same as invisible.

That is the synthesis in the abstract. The final lesson makes it physical: it bolts the named parts (PC, instruction memory, register file, ALU, data memory, control unit) into one block diagram, powers the machine on from reset, and runs a complete compiled program (an array sum with a real call and ret) across it, cycle by cycle, until the answer lands in a register, and then asks what it would take to put two of these cores on one die.