The Complete PIPE Processor

PIPE now has its five stages and pipeline registers, forwarding and the load-use stall for data hazards, and prediction, squashing, and the ret stall for control hazards. This lesson bolts them together into one processor, works through the control logic that orchestrates it (including the one place where two hazards colliding exposed a real bug), and then does the accounting: how close PIPE gets to the ideal of one instruction per cycle, and why real machines pay to go deeper.

The full PIPE overview

The complete datapath is the SEQ datapath with the F/D/E/M/W registers inserted and two extra networks laid over it: the forwarding paths carrying late results back to Decode, and the control logic watching every register for hazard conditions. The stages still do their familiar jobs; the new wiring is what makes overlap safe.

The pipeline control logic

The control unit's whole job is to make one decision per pipeline register per cycle, using two control inputs each register now carries:

Everything the previous two lessons described reduces to patterns of these signals. The three hazard conditions are detected by comparing a handful of pipeline-register fields:

and each condition maps to a row of actions:

Read a row as the cycle's action. A ret freezes Fetch and bubbles Decode, repeating for the three cycles until the return address surfaces. A load/use hazard freezes Fetch and Decode (so the consumer waits where it stands) and bubbles Execute. A mispredicted branch bubbles Decode and Execute, squashing the two wrong-path instructions, while Fetch proceeds normally; the PC selection logic already has the fall-through address. The fourth row is different in kind: an exception is not a hazard between instructions but a promise about program order, and it gets its own section below.

When hazards combine

Each row of that table assumes its condition fires alone, and a common design bug is to stop there. During any given cycle several conditions can hold at once, and the control logic must produce one coherent action per register. Enumerate the pairs. A load/use hazard cannot coincide with a mispredicted branch: one needs a load in Execute, the other a jump there. But ret moves through Decode, Execute, and Memory over three cycles, and while it sits in Decode it can coincide with either condition in Execute:

Combination A — a mispredicted jump in Execute whose (wrongly fetched) target instruction is a ret, now in Decode. Merge the two action rows and the requirements are compatible: stall F (from the ret row), bubble D, bubble E. The bubbles cancel the ret (correctly, since it lives on the wrong path), and the stalled F register turns out not to matter, because the PC selection logic ignores the predicted PC and fetches the fall-through. Combination A works by accident of good design; no extra logic needed.

Combination B — a load in Execute whose destination feeds the ret in Decode. This is just a load/use hazard whose consumer happens to be ret (which reads %rsp to pop the return address). Now merge the rows: load/use says stall D, ret says bubble D. Both at once is the forbidden 1/1 input: a broken register. The desired behavior is the load/use action alone: let the ret wait one cycle for the forwarded stack pointer, and begin the usual ret sequence a cycle late. So the D_bubble condition must explicitly exclude the load/use case:

bool F_stall =
    # load/use hazard: hold Fetch while the consumer waits in Decode
    E_icode in { IMRMOVQ, IPOPQ } && E_dstM in { d_srcA, d_srcB } ||
    # ret passing through Decode/Execute/Memory: hold Fetch
    IRET in { D_icode, E_icode, M_icode };

bool D_bubble =
    # mispredicted branch: squash the wrongly fetched instruction
    (E_icode == IJXX && !e_Cnd) ||
    # ret passing through - but NOT while a load/use hazard holds the ret
    !(E_icode in { IMRMOVQ, IPOPQ } && E_dstM in { d_srcA, d_srcB })
      && IRET in { D_icode, E_icode, M_icode };

Bryant and O'Hallaron report that their original control logic had exactly this bug: it passed every simulation test, because no ordinary program pops into the stack pointer right before a ret, and surfaced only under systematic analysis of condition combinations. This generalizes: pipeline control bugs hide in combinations of rare events that no test suite covers by luck. They are found by enumerating cases, or much more expensively in silicon.

Exceptions in a pipeline

Every pipeline register has carried a stat field since the registers were laid out, and so far nothing has read it. It exists for the fourth control case: what to do when an instruction's status is not AOK. Pipelining makes this genuinely awkward, because an exception is detected far from where it must act. Fetch discovers an invalid opcode or an instruction-address fault three stages before the faulting instruction would complete; by then its successors are already in flight and its predecessors have not finished. Halting at the moment of detection would be wrong twice over — younger, wrong-path instructions could still change programmer-visible state, and older instructions the program did reach would be cut off half done.

So PIPE does neither. A bad status rides along in stat like any other field, and the control logic acts only when the excepting instruction nears the end of the pipe: the trigger is m_stat or W_stat holding one of SADR, SINS, SHLT — the HCL constants for the ADR, INS, and HLT status codes. From that cycle on, the M register is bubbled every cycle, so nothing younger ever enters Memory or Write-back: no memory write, no register write. One leak remains — an OPq already sitting in Execute would still update the condition codes this very cycle — so set_cc is gated on the same test:

# an exception is in Memory or Write-back
bool exc_MW = m_stat in { SADR, SINS, SHLT } || W_stat in { SADR, SINS, SHLT };

# cancel everything younger: inject bubbles into Memory from now on
bool M_bubble = exc_MW;
# park the excepting instruction: its status is the machine's status
bool W_stall  = W_stat in { SADR, SINS, SHLT };

# a wrong-path OPq in Execute must not wreck the condition codes
bool set_cc = E_icode == IOPQ && !exc_MW;

Stalling W parks the excepting instruction in the last register, so the processor's reported status (Stat = W_stat) keeps saying what went wrong and the machine makes no further progress; in a full system this is the point where a handler would take over.

The net effect is a clean cut at the excepting instruction's place in program order. Everything older is deeper in the pipeline and drains normally — those writes were owed to the program. Everything younger is squashed before it touches programmer-visible state. And when two instructions in flight both fault, the older one reaches Memory first, so its exception wins: priority falls out of program order for free. To software the exception appears to strike exactly at an instruction boundary, however messily the pipeline had overlapped the work — the property the interrupt machinery of the exceptions module takes as its starting point.

Performance: CPI = 1 + penalties

The ideal pipeline retires one instruction per cycle, a CPI (cycles per instruction) of $1.0$. Bubbles are cycles in which the execute stage does no useful work, so if a program executes $C_i$ instructions and the hazards inject $C_b$ bubbles, the processor spends about $C_i+C_b$ cycles:

splitting the bubble rate into the three causes: load/use penalty (lp), misprediction penalty (mp), return penalty (rp). Each term is the product of three measurable numbers — instruction frequency $f$, condition frequency $c$, and bubbles per event $b$:

With frequencies typical of compiled code:

A quarter of instructions are loads and a fifth of those feed the next instruction; a fifth are conditional jumps and predict-taken misses 40% of them; one in fifty is a ret, which always pays full price. Summing: $\text{CPI}=1.0+0.05+0.16+0.06=1.27$.

The breakdown says where to spend effort. Mispredictions contribute 0.16 of the 0.27 total, more than the other two causes combined, because conditional jumps are common, predict-taken misses often, and each miss costs double. Swap in the BTFNT predictor (65% accuracy, so condition frequency 0.35) and mp drops to $0.20\times 0.35\times 2=0.14$; a modern dynamic predictor at 95% cuts it to $0.02$. A return-address stack all but erases rp the same way. The load/use term is the compiler's to fix, by scheduling an independent instruction into the slot after each load.

Combining these upgrades brings CPI toward the ideal. Keep lp and rp fixed and vary only the branch predictor, then add a return-address stack that drops the return penalty to near zero:

Each row is a real design decision with a measurable payoff, and none touches the datapath — they are all about predicting better and scheduling better. From 1.27 down to 1.03 is a $19\%$ throughput gain layered on top of the raw pipelining speedup, which is why so much microarchitecture effort goes into prediction and compiler scheduling rather than the pipeline itself. The last tenth of CPI is the most expensive to remove; out-of-order cores exist to reach it.

What did pipelining buy? PIPE versus SEQ

CPI 1.27 looks like a 27% loss, but the comparison that matters is against SEQ. Compare the two processors end to end with illustrative delays. SEQ's clock must span the entire worst-case instruction, fetch through write-back in one cycle, say 1000 ps of logic plus 20 ps to latch: 1020 ps per instruction, CPI exactly 1. PIPE cuts the same 1000 ps into five 200 ps stages; its clock is $200+20=220$ ps, and each instruction costs $220\times 1.27\approx 279$ ps on average.

The speedup is the ratio of per-instruction times,

short of the ideal $5\times$ that five stages promise. The shortfall factors cleanly: register overhead shrinks the clock gain to $1020/220=4.6\times$, and the CPI of 1.27 gives up the rest ($4.6/1.27\approx 3.7$). Both losses were predicted by the principles lesson; here they finally have exact prices.

Why real pipelines go deeper — and what it costs

PIPE has five stages. Real processors run a dozen to twenty-odd, because more stages mean shorter stages, a faster clock, and higher peak throughput. But depth compounds exactly the costs this module has priced out.

• Branch penalties scale with depth. If the branch resolves at stage 12 instead of stage 3, a misprediction squashes eleven instructions, not two. The mp term becomes $0.20\times \text{miss rate}\times 11$, which is why deep pipelines lean on serious dynamic predictors (history tables, not predict-taken) to hold the miss rate near a few percent.
• More forwarding paths and hazard cases. Every added stage is another place a value can be in flight, so the forwarding network, the priority logic, and the combination analysis all grow, and the combination bugs multiply.
• Register overhead and power. The per-stage register tax caps the clock gain, and switching power rises with frequency; past some depth the energy cost outruns the throughput.

This is the central tension of pipelined design: throughput pulls toward more stages, while hazard penalties and overhead pull toward fewer. PIPE's five stages sit at the simple end of that trade, the right place to understand the mechanism; the same mechanism, scaled up and hardened with prediction and out-of-order execution, is what makes a modern core fast.

The modern out-of-order superscalar core

Every mechanism in this module reappears, enlarged, in a modern performance core, and it is worth assembling the pieces the earlier closing sections named into one picture. PIPE is in-order, single-issue: instructions execute in program order, one per cycle, and a stall freezes everything behind it. A contemporary core such as Intel's Golden Cove or Apple's Firestorm is out-of-order and superscalar, and it earns its speed by relaxing both constraints.

• Superscalar issue (from the principles lesson's beyond-the-book): the core fetches, decodes, and retires several instructions per cycle — eight-wide decode is common — so the ideal CPI drops below 1. PIPE's single-issue ceiling of CPI $=1$ no longer applies; a wide machine retires four to six instructions in a good cycle.
• Register renaming (from the SEQ-to-PIPE beyond-the-book) maps architectural registers onto a large physical pool, erasing the false dependencies that would otherwise serialize instructions and giving each value a unique name — the same goal as PIPE's D_stat/d_stat naming discipline, automated for hundreds of in-flight instructions.
• Dynamic scheduling with reservation stations (from the data-hazards beyond-the-book) lets an instruction wait for its operands off to the side while independent younger instructions execute past it, so a cache-missing load no longer freezes the machine the way PIPE's load-use interlock does.
• Aggressive branch prediction (from the control-hazards beyond-the-book) — TAGE-class predictors and return-address stacks — keeps the deep speculation window full, because at a dozen-plus stages every mispredict is very expensive.
• The reorder buffer ties it together: instructions execute out of order but retire in program order, committing their results to architectural state only when every older instruction has. This is precisely PIPE's precise-exception property scaled up — the machine may run arbitrarily far ahead speculatively, but the programmer-visible state advances one instruction at a time, and a fault or mispredict rolls back everything younger. The reorder buffer is what makes hundreds of overlapping, reordered, speculative instructions still honor the ISA's one-at-a-time fiction (Smith and Pleszkun, 1985, ISCA, on in-order retirement; Hennessy and Patterson, Computer Architecture: A Quantitative Approach, ch. 3).

Everything in this module reappears at larger scale. Forwarding becomes the common data bus; the naming discipline becomes register renaming; predict-verify-recover becomes speculative execution with a reorder buffer; precise exceptions become in-order retirement. PIPE is a faithful miniature: small enough to understand completely, and its principles carry all the way up to a core that overlaps five hundred instructions instead of five.

That closes the processor: from a single transistor up through gates, a datapath, the SEQ control, and now a pipelined PIPE that overlaps five instructions while keeping the simple one-at-a-time model true. What remains is feeding it fast enough — the memory hierarchy and caches of the next module.