--- title: From SEQ to PIPE module: Pipelining moduleNumber: 5 lessonNumber: 2 order: 502 summary: > We turn the sequential Y86-64 processor into a pipelined one by inserting pipeline registers between its stages so each cycle holds one instruction per stage. Doing it correctly forces a rearrangement: the next-PC computation must move into Fetch as a prediction, because the later stages that used to compute it are now busy with other instructions. We walk SEQ to SEQ+ to PIPE, spell out exactly what each pipeline register carries, and fix the naming discipline (D_stat versus d_stat) that keeps five in-flight instructions straight. topics: [Pipelining] sources: - book: Bryant & O'Hallaron ref: "CS:APP — §4.5 Pipelined Y86-64 Implementations" --- The [previous lesson](/computer-architecture/pipelining/pipelining-principles) 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**. $$ % caption: The five pipeline registers F, D, E, M, W between the five Y86-64 stages. % caption: Each register snapshots its stage's results on the clock edge and presents % caption: them to the next stage, so each cycle holds one instruction per stage. \begin{tikzpicture}[font=\footnotesize,>=stealth, st/.style={draw, fill=acc!8, minimum width=16mm, minimum height=10mm, inner sep=1pt, align=center}, reg/.style={draw, fill=black!10, minimum width=3mm, minimum height=12mm, inner sep=0pt}] \definecolor{acc}{HTML}{2348F2} % row layout: F-reg, Fetch, D-reg, Decode, E-reg, Execute, M-reg, Memory, % W-reg, Writeback, left to right with wires between \def\dx{2.1} \node[reg] (F) at (0*\dx,0) {}; \node[anchor=south, text=acc] at (0*\dx,0.75) {F}; \node[st] (fe) at (0*\dx+1.05,0) {Fetch}; \node[reg] (D) at (1*\dx+0.1,0) {}; \node[anchor=south, text=acc] at (1*\dx+0.1,0.75) {D}; \node[st] (de) at (1*\dx+1.15,0) {Decode}; \node[reg] (E) at (2*\dx+0.2,0) {}; \node[anchor=south, text=acc] at (2*\dx+0.2,0.75) {E}; \node[st] (ex) at (2*\dx+1.25,0) {Execute}; \node[reg] (M) at (3*\dx+0.3,0) {}; \node[anchor=south, text=acc] at (3*\dx+0.3,0.75) {M}; \node[st] (me) at (3*\dx+1.35,0) {Memory}; \node[reg] (W) at (4*\dx+0.4,0) {}; \node[anchor=south, text=acc] at (4*\dx+0.4,0.75) {W}; \node[st] (wb) at (4*\dx+1.45,0) {Write\\back}; % connecting wires left to right along the row \draw (F.east) -- (fe.west); \draw (fe.east) -- (D.west); \draw (D.east) -- (de.west); \draw (de.east) -- (E.west); \draw (E.east) -- (ex.west); \draw (ex.east) -- (M.west); \draw (M.east) -- (me.west); \draw (me.east) -- (W.west); \draw (W.east) -- (wb.west); \draw (wb.east) -- ++(0.7,0); % shared clock note below \node[anchor=north, black] at (4.8,-0.95) {\scriptsize all registers clocked together, one snapshot per cycle}; \end{tikzpicture} $$ 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. $$ % caption: Five irmovq-style instructions in steady state. In cycle 5 (boxed) the % caption: pipeline is full: I1 is writing back, I2 is in Memory, I3 in Execute, % caption: I4 in Decode, and I5 is being fetched — one instruction per stage. \begin{tikzpicture}[font=\footnotesize,>=stealth, cell/.style={draw, minimum width=9mm, minimum height=7mm, inner sep=0pt}] \definecolor{acc}{HTML}{2348F2} \foreach \c in {1,...,9} \node at (\c*1.0-0.5,0.65) {\scriptsize \c}; \node[anchor=east] at (-0.15,0.65) {\scriptsize cycle}; \foreach \i/\y/\lab in {0/0/I1, 1/-0.85/I2, 2/-1.7/I3, 3/-2.55/I4, 4/-3.4/I5}{ \node[anchor=east] at (-0.15,\y) {\lab}; \node[cell, fill=acc!8] at (\i*1.0+0.5,\y) {F}; \node[cell, fill=acc!8] at (\i*1.0+1.5,\y) {D}; \node[cell, fill=acc!8] at (\i*1.0+2.5,\y) {E}; \node[cell, fill=acc!8] at (\i*1.0+3.5,\y) {M}; \node[cell, fill=acc!8] at (\i*1.0+4.5,\y) {W}; } % highlight the cycle-5 column \draw[acc, thick] (4.02,-3.78) rectangle (4.98,0.38); \node[anchor=north, text=acc] at (4.5,-3.85) {\scriptsize cycle 5: one instruction per stage}; \end{tikzpicture} $$ 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: $$ % caption: What each pipeline register carries. Fields appear when a stage computes % caption: them and drop off once no later stage needs them: rA and rB die after % caption: Decode, valC after Execute, and the destination IDs ride all the way to % caption: the write ports. Every register carries stat, the instruction's status. \begin{tikzpicture}[font=\footnotesize,>=stealth, f/.style={draw, fill=acc!8, minimum width=11mm, minimum height=6.5mm, inner sep=1pt}] \definecolor{acc}{HTML}{2348F2} % W row (top) through F row (bottom), fetch at bottom per convention \node[anchor=east, text=acc] at (-0.85,0) {W}; \foreach \i/\lab in {0/{stat}, 1/{icode}, 2/{valE}, 3/{valM}, 4/{dstE}, 5/{dstM}} \node[f] at (\i*1.25,0) {\lab}; \node[anchor=east, text=acc] at (-0.85,-1.05) {M}; \foreach \i/\lab in {0/{stat}, 1/{icode}, 2/{Cnd}, 3/{valE}, 4/{valA}, 5/{dstE}, 6/{dstM}} \node[f] at (\i*1.25,-1.05) {\lab}; \node[anchor=east, text=acc] at (-0.85,-2.1) {E}; \foreach \i/\lab in {0/{stat}, 1/{icode}, 2/{ifun}, 3/{valC}, 4/{valA}, 5/{valB}, 6/{dstE}, 7/{dstM}, 8/{srcA}, 9/{srcB}} \node[f] at (\i*1.25,-2.1) {\lab}; \node[anchor=east, text=acc] at (-0.85,-3.15) {D}; \foreach \i/\lab in {0/{stat}, 1/{icode}, 2/{ifun}, 3/{rA}, 4/{rB}, 5/{valC}, 6/{valP}} \node[f] at (\i*1.25,-3.15) {\lab}; \node[anchor=east, text=acc] at (-0.85,-4.2) {F}; \node[f, minimum width=16mm] at (0.25,-4.2) {predPC}; \end{tikzpicture} $$ 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](/computer-architecture/pipelining/data-hazards-stalling-and-forwarding)). **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: | Stage | Register | Key fields carried | Just added | Just dropped | | --- | --- | --- | --- | --- | | Fetch | F | `predPC` | — | — | | Decode | D | `icode=OPq`, `ifun=ADD`, `rA=rax`, `rB=rbx`, `valP` | codes, register IDs | — | | Execute | E | `valA`, `valB`, `srcA=rax`, `srcB=rbx`, `dstE=rbx` | operand _values_ | `rA`, `rB` (now resolved to values) | | Memory | M | `valE` (the sum), `dstE=rbx` | ALU result `valE` | `valA`, `valB`, `srcA`, `srcB` | | Write-back | W | `valE`, `dstE=rbx` | — | `Cnd` (unused; `addq` never branches) | 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](/computer-architecture/pipelining/data-hazards-stalling-and-forwarding) 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: > **Definition (Pipeline signal naming).** An **uppercase** prefix names a > pipeline **register** field: `D_stat`, `E_icode`, `M_Cnd`, `W_valM` are values > latched at the last clock edge, sitting in registers D, E, M, W. A > **lowercase** prefix names a signal freshly **computed within a stage** during > the current cycle: `f_stat`, `d_srcA`, `e_valE`, `m_valM` come out of the > fetch, decode, execute, and memory logic respectively. 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](/computer-architecture/pipelining/the-complete-pipe-processor) 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. > **Definition (Branch prediction).** Choosing the next PC in the Fetch stage > before the information that truly determines it is available, by **guessing** the > outcome. The guess is checked in a later stage; a wrong guess is detected and > repaired. For the common straight-line and taken-branch cases the guess is > usually right. The fix is to move next-PC selection **into Fetch** and make it a prediction: $$ \mathtt{predPC} = \begin{cases} \mathtt{valC} & \text{icode} \in \{\text{call},\,\text{jmp}\} \text{ or } \text{icode}=\text{jXX (predict taken)}\\ \mathtt{valP} & \text{otherwise} \end{cases} $$ 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](/computer-architecture/pipelining/control-hazards-and-branch-prediction). Tabulate the guess and how often it holds, per instruction class: | Instruction in Fetch | Predicted next PC | Correct? | | --- | --- | --- | | `OPq`, `rrmovq`, `irmovq`, `rmmovq`, `mrmovq`, `pushq`, `popq` | `valP` (fall-through) | always | | `call`, `jmp` (unconditional) | `valC` (target) | always | | `jXX` (conditional) | `valC` (predict taken) | usually — verified in Execute | | `ret` | — (cannot guess) | handled by stalling | 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: ```asm [jmp-flow.ys] irmovq $10, %rax # I1 addq %rax, %rbx # I2 jmp L # I3: predict valC, always right L: rrmovq %rbx, %rcx # I4: at the target ``` $$ % caption: Predict-PC steering Fetch. I3 is an unconditional jmp; the moment its % caption: bytes are fetched (cycle 3) predPC is set to the target valC, so I4 (the % caption: instruction at L) is fetched in cycle 4 with no bubble. The jump costs % caption: nothing because the prediction cannot be wrong. \begin{tikzpicture}[font=\footnotesize,>=stealth, cell/.style={draw, minimum width=9mm, minimum height=7mm, inner sep=0pt}] \definecolor{acc}{HTML}{2348F2} \foreach \c in {1,...,8} \node at (\c*1.0-0.5,0.65) {\scriptsize \c}; \node[anchor=east] at (-0.15,0.65) {\scriptsize cycle}; \foreach \i/\y/\lab in {0/0/{I1 irmo\/vq}, 1/-0.85/{I2 addq}, 2/-1.7/{I3 jmp}, 3/-2.55/{I4 at L}}{ \node[anchor=east] at (-0.15,\y) {\scriptsize \lab}; \foreach \s/\o in {F/0, D/1, E/2, M/3, W/4} \node[cell, fill=acc!8] at (\i*1.0+\o*1.0+0.5,\y) {\s}; } % arrow: I3 fetched (cycle 3) sets predPC used to fetch I4 (cycle 4) \draw[acc, thick, ->] (2.5,-1.35) .. controls (3.1,-1.7) and (3.1,-1.9) .. (3.5,-2.2); \node[anchor=west, text=acc] at (2.7,-3.05) {\scriptsize predPC = target routes Fetch to L}; \end{tikzpicture} $$ 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. $$ % caption: Predict-PC logic in Fetch. From the fetched instruction it computes both % caption: valP = PC + length (the fall-through) and valC (the jump target), then a % caption: mux picks one as predPC: the target for a taken jump or call, valP % caption: otherwise. The choice needs nothing from later stages. \begin{tikzpicture}[font=\footnotesize,>=stealth, blk/.style={draw, fill=acc!8, minimum width=22mm, minimum height=10mm, inner sep=2pt, align=center}, mux/.style={draw, fill=acc!8, minimum width=10mm, minimum height=20mm, inner sep=1pt}] \definecolor{acc}{HTML}{2348F2} \node[blk] (imem) at (0,0.3) {instruction\\memory}; \draw (-2.3,0.3) node[anchor=east] {PC} -- (imem.west); % compute valP and valC \node[blk, minimum width=18mm] (vp) at (3.2,1.2) {valP = PC+len}; \node[blk, minimum width=18mm] (vc) at (3.2,-0.6) {valC (target)}; \draw (imem.east) -- ++(0.3,0) coordinate (j) ; \draw (j) |- (vp.west); \draw (j) |- (vc.west); % mux selects predPC \node[mux] (m) at (6.2,0.3) {Sel}; \draw (vp.east) -- (m.160); \draw (vc.east) -- (m.200); \draw (m.east) -- ++(1.4,0) node[anchor=west,text=acc] {predPC}; % select control: branch taken? \node[anchor=south] at (6.2,1.7) {\scriptsize predict tak\/en?}; \draw (6.2,1.65) -- (m.north); \end{tikzpicture} $$ ## 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. $$ % caption: Retiming the PC computation. SEQ (left) computes the next PC at the end % caption: of the cycle and stores it in a PC register for the next fetch. SEQ+ % caption: (right) instead saves the raw ingredients (pIcode, pCnd, pValC, pValM, % caption: pValP) and computes the PC at the start of the next cycle. Same % caption: computation, shifted across the register boundary. \begin{tikzpicture}[font=\footnotesize,>=stealth, blk/.style={draw, fill=acc!8, minimum width=25mm, minimum height=8mm, inner sep=2pt, align=center}, sreg/.style={draw, fill=black!10, minimum width=25mm, minimum height=6mm, inner sep=1pt}] \definecolor{acc}{HTML}{2348F2} % ---- left: SEQ ---- \node[anchor=south, text=acc] at (0,2.35) {SEQ}; \node[blk] (npc) at (0,1.6) {new-PC logic}; \node[sreg] (pc) at (0,0.3) {PC}; \node[blk] (fs) at (0,-1.0) {fetch, decode, ...}; \draw[->] (npc.south) -- (pc.north); \draw[->] (pc.south) -- (fs.north); \draw[->] (fs.east) -- ++(0.55,0) |- (npc.east); \node[anchor=east, black] at (-1.45,1.6) {\scriptsize end of cycle}; % ---- right: SEQ+ ---- \node[anchor=south, text=acc] at (6.4,2.35) {SEQ+}; \node[blk] (sel) at (6.4,1.6) {PC select logic}; \node[sreg, minimum width=32mm] (pst) at (6.4,0.3) {pIco\/de pCnd pValC ...}; \node[blk] (fs2) at (6.4,-1.0) {fetch, decode, ...}; \draw[->] (pst.north) -- (sel.south); \draw[->] (sel.east) -- ++(0.55,0) node[anchor=west, black] {\scriptsize to fetc\/h}; \draw[->] (fs2.east) -- ++(0.85,0) |- (pst.east); \node[anchor=east, black] at (4.9,1.6) {\scriptsize start of cycle}; \end{tikzpicture} $$ - **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. > **Takeaway.** PIPE is SEQ with pipeline registers **F, D, E, M, W** inserted at > the stage boundaries, each carrying its instruction's complete travel packet > (status, codes, operands, values, destinations), so five instructions overlap. > Signal names carry the discipline: **uppercase** `D_stat` is a register field, > **lowercase** `d_stat` is computed in the stage this cycle. The one thing that > cannot simply be cut is next-PC selection: the stages that used to compute it > are busy, so it moves into **Fetch as a prediction** (target for jumps and > calls, `valP` otherwise). The intermediate **SEQ+** retimes the PC logic to the > front of the cycle, after which pipelining is mechanical. Overlapping five instructions is fast — until two of them need the same value at the same time. The [next lesson](/computer-architecture/pipelining/data-hazards-stalling-and-forwarding) confronts the first such conflict: data hazards.