From SEQ to PIPE

The previous lesson pipelined abstract A/B/C stages. Now we pipeline the real datapath. SEQ already divides every instruction into the same five working stages — fetch, decode, execute, memory, write-back — plus a PC-update step folded around them. Those stage boundaries serve as the cut lines: drop a register at each one and the stages run independently, one instruction per stage per cycle. The work is mostly mechanical, but one piece resists, and fixing it is the whole intellectual content of the lesson.

The five pipeline registers

We insert a pipeline register between each pair of adjacent stages. Following CS:APP's convention each register is named for the stage it feeds: the registers are F, D, E, M, W.

On each rising edge all five registers latch at once. The instruction that was in Fetch advances into Decode, the one in Decode into Execute, and so on down the line: the whole pipeline shifts one step, and a new instruction enters Fetch. At steady state five different instructions occupy the five stages simultaneously.

This diagram also explains a drawing convention: hardware diagrams for PIPE are drawn with Fetch at the bottom and write-back at the top, so that reading a vertical slice of the pipeline top-to-bottom lists the in-flight instructions in program order, oldest first — the same order they appear in the listing.

What the registers carry

A pipeline register must carry everything a later stage will need about its instruction, because by the time that stage runs, the signals at their original source belong to a different instruction. So each register widens to hold a complete travel packet that rides along with the instruction:

Read it bottom-up, the direction instructions flow. F is the odd one out: it holds just enough state to start the next fetch, a single predicted PC, rather than any stage's full output. D receives what Fetch extracted from the instruction bytes: the status stat, the instruction and function codes icode/ifun, the register specifiers rA/rB, the constant word valC, and the incremented PC valP. E swaps the register IDs for the values Decode read — valA, valB — and adds the decoded destination and source IDs (dstE, dstM, srcA, srcB; the sources ride along for the forwarding logic of the next lesson). M holds Execute's results: the ALU output valE and, for jumps, the branch outcome Cnd. W carries the two values that can be written back, valE and valM, together with their destination IDs.

Tracing one instruction's packet

Abstract field lists are easier to trust after tracing a single instruction filling and emptying its packet. Take addq %rax, %rbx and follow what its pipeline register holds at each stage, appearing when a stage computes a field and dropping away once no later stage needs it:

The register specifiers rA/rB live only as far as Decode, because once the register file is read their values (valA/valB) carry the information and the names are dead weight. The source IDs srcA/srcB ride one stage further, to Execute, purely so the forwarding logic of the next lesson can match them; an addq with no hazard would never read them again. And the destination dstE=rbx travels the entire length, because it is not needed until the write port fires in write-back. This is the general shape of every packet: IDs and constants die early, computed values appear mid-pipe, and the write destination survives to the end.

Two details of this layout repay attention. First, the write ports' addresses dstE/dstM are taken from the W register, not from the decode logic that originally produced them; the write must pair with the instruction actually in write-back, and the general rule is that everything about an instruction stays in that instruction's pipeline register. Second, valP disappears after D even though call needs it in Memory (to push the return address) and a jump needs it later (to recover from a misprediction). The trick: neither call nor jXX reads register port A, so Decode's Sel+Fwd A block merges valP into valA, letting one field serve both purposes and keeping the E and M registers narrower. Merging signals that are never needed simultaneously is a standard hardware economy.

The naming discipline: D_stat versus d_stat

SEQ could call a wire valE and be done: with one instruction in flight there is exactly one valE in the machine. PIPE has up to five instructions in flight and therefore up to five simultaneous versions of nearly every signal. Referring to the valE is now ambiguous, and picking the wrong version is a real bug class: compute with one instruction's value and you may store its result at another instruction's destination. PIPE's naming scheme resolves the ambiguity:

The two forms of a signal are one clock edge apart. During a cycle, the fetch logic computes f_stat for the instruction being fetched; at the rising edge that value is latched into D_stat, where the decode stage reads it next cycle while fetch computes a new f_stat for a different instruction. So M_stat is the status of the instruction in the memory stage (latched, stable), while m_stat is the status the memory stage is computing this cycle — the same instruction, but possibly updated within the stage (a data-memory error, for example, is discovered in Memory and folded into m_stat). Signals like e_valE versus W_valE name different instructions entirely. The discipline looks fussy until the first time hazard logic has to compare d_srcA against E_dstM; then it is the only thing keeping the design readable. And stat is the field to watch: how it finally stops the machine is the complete-PIPE lesson's last control case.

The problem: who computes the next PC?

In SEQ the PC update happens last. To pick the next PC the processor may need the just-fetched instruction's length, and — for a conditional jump — the branch condition computed in Execute, or — for ret — the return address read from memory in the Memory stage. SEQ can wait for all of that because it does only one instruction at a time.

PIPE cannot wait. Fetch must launch a new instruction every single cycle, so at the moment it needs the next PC, the instruction that would compute it is still only in Decode or Execute, nowhere near done. The late stages that used to determine the next PC are now busy with other instructions. Fetch has to decide on its own, immediately.

The fix is to move next-PC selection into Fetch and make it a prediction:

Both valP (the current PC plus the instruction's length) and the target valC are known immediately from the fetched bytes, so the mux needs nothing from later stages. For call and unconditional jmp the guess is always right; for jXX it is predict-taken. Only ret truly cannot be predicted from the fetched bytes (its target is data sitting on the stack), and it is handled by stalling, in the control-hazards lesson.

Tabulate the guess and how often it holds, per instruction class:

Only the conditional-jump row can ever be wrong, and only the ret row has nothing to guess at all. Everything else Fetch predicts with certainty from the bytes in hand. That is why PIPE's speculation machinery, developed two lessons on, needs to handle exactly two awkward cases rather than all seven opcodes — the prediction is exact for straight-line code, call, and jmp, so only branches and returns cost anything.

To see the prediction actually steer Fetch, trace a straight-line snippet ending in an unconditional jmp — the always-correct case — and watch the predicted PC send Fetch to the target with no gap:

irmovq $10, %rax     # I1
addq   %rax, %rbx    # I2
jmp    L             # I3: predict valC, always right
L: rrmovq %rbx, %rcx # I4: at the target

The staircase never breaks: I4 slots in behind I3 exactly as if the program were straight-line, because the target was known from I3's own bytes. Only a conditional jump introduces the possibility that the address chosen here is wrong — the subject the pipeline spends a whole later lesson defending against.

SEQ, SEQ+, PIPE

Bryant and O'Hallaron stage the transformation through an intermediate design, SEQ+, to make the rearrangement honest rather than magical. The difference between SEQ and SEQ+ is when in the cycle the PC logic runs.

• SEQ computes the next PC at the end of the cycle, from icode, Cnd, valC, valM, valP, and latches the result into the PC register.
• SEQ+ latches those five ingredients instead (as pIcode, pCnd, pValC, pValM, pValP — state saved from the previous instruction) and runs the identical selection logic at the start of the next cycle. The behavior is indistinguishable from SEQ; the logic merely moved across the register boundary. This transformation is called circuit retiming: relocating logic relative to state elements without changing what the circuit computes.
• PIPE takes SEQ+ and inserts the F, D, E, M, W registers, turning that front-of-cycle PC computation into the predict-PC logic above and letting five instructions overlap.

SEQ+ has a curious property: it contains no PC register at all. The program counter is computed on the fly each cycle from state the previous instruction left behind. Nothing requires a processor's internal state to match the programmer-visible state form, only that it can always produce the programmer-visible values on demand — a small foretaste of how aggressively real microarchitectures diverge from the ISA's fiction while preserving it exactly. The point of the intermediate step is that once PC selection lives at the front of the cycle, it is already in the right place to become Fetch's prediction. Pipelining is then just add the registers, and the hard rearrangement was done in the retiming step, where it could be reasoned about one instruction at a time.

How real cores keep the versions straight

PIPE's naming discipline — uppercase D_stat for a latched register field, lowercase d_stat for a within-stage signal — is a bookkeeping fix for a small problem: five in-flight instructions mean up to five simultaneous versions of every signal, and the hardware must always grab the right one. In a five-stage pipeline the versions are few enough to name by hand. A modern out-of-order core has hundreds of instructions in flight and cannot; it solves the same problem structurally, with register renaming.

The trick is to separate the architectural register names the program writes (%rax, %rbx, …) from the physical storage that actually holds values. When an instruction is decoded, its destination register is mapped to a fresh physical register drawn from a pool much larger than the architectural set — Intel's Skylake, for example, exposes 16 architectural integer registers but has around 180 physical ones. Two instructions that both write %rax get two different physical registers, so the which version of %rax? ambiguity that PIPE resolves with forwarding priority simply cannot arise: each value has a unique name for its whole lifetime. This also erases the false dependencies (write-after-write, write-after-read) that would otherwise serialize instructions reusing a register merely because the program ran short of names. Renaming was introduced with Tomasulo's algorithm on the IBM System/360 Model 91 (Tomasulo, 1967, IBM Journal of Research and Development) and is standard in every high-performance core today (Hennessy and Patterson, Computer Architecture: A Quantitative Approach, ch. 3).

The connection to PIPE is direct. PIPE's forwarding-plus-naming scheme is what register renaming automates and generalizes: instead of the decode logic comparing source IDs against a handful of pipeline-register destinations, a rename table looks up which physical register currently holds each architectural name, and the value is read from there. Same goal — every read gets the most recent write — scaled from five instructions to a few hundred.

Overlapping five instructions is fast — until two of them need the same value at the same time. The next lesson confronts the first such conflict: data hazards.