Precise exceptions in pipelines: Visual walkthrough

Before anything else, three plain words we will lean on the whole page:

The whole problem, in one sentence: a pipeline runs instructions overlapping in time, so they can finish out of program order — but the outside world must never notice.

Step 1 — Draw the pipeline as a conveyor belt

WHAT. Picture five work-stations in a row. An instruction rides a conveyor belt through them, one station per tick of the clock (one cycle). The five stations are:

IF (fetch): grab the instruction from memory.
ID (decode): read what it means, read its input registers.
EX (execute): do the arithmetic.
MEM (memory): read or write memory if needed.
WB (write-back): write the answer into the official registers.

WHY these five. Splitting the work lets five instructions be in progress at once — while $I_{1}$ is at WB, $I_{2}$ is at MEM, and so on. That overlap is the whole speed win of pipelining.

PICTURE. Each column is a station; each colored block is one instruction. Read a vertical slice to see "everyone at one instant."

Step 2 — Freeze one clock tick and spot the danger

WHAT. Freeze the belt at cycle 5. Five different instructions sit in five stations at once:

IF I_{5} ID I_{4} EX I_{3} MEM I_{2} WB I_{1}

Term by term: the little word under each $I$ is the station that instruction is standing in right now. $I_{1}$ (oldest) is furthest along; $I_{5}$ (youngest) just got fetched.

WHY freeze. A precise exception is defined at an instant. We must be able to say, at the moment of fault, "everything older is done, everything younger is undone." So we study one frozen instant.

PICTURE. Now let $I_{3}$ blow up: it is DIV R6,R7,R0 — divide by zero — and the divide-by-zero is discovered in EX. The red burst marks it.

Step 3 — The rule that fixes it: older finishes, younger vanishes

WHAT. We split the frozen instant into two groups relative to the faulting instruction $I_{3}$ :

older \to let finish I_{1}, I_{2} fault + younger \to turn into NOPs I_{3}, I_{4}, I_{5}

"older" = smaller program-order number than $I_{3}$ . These must complete and write back.
NOP ("no-operation") = a fake instruction that does nothing and writes nothing. Turning $I_{3}, I_{4}, I_{5}$ into NOPs is called flushing — it guarantees they never touch official state.

WHY. This is the definition of precise (from the parent): all-older-done, faulting-and-younger-undone. We are not being clever yet — we are just enforcing the definition by hand.

PICTURE. Green check-marks flow out of WB for $I_{1}, I_{2}$ . Red X's stamp $I_{3}, I_{4}, I_{5}$ into hollow "bubbles."

Step 4 — Why "in-order write-back" is the quiet hero

WHAT. In the simple 5-stage pipeline the stations are physically in a line, so instructions reach WB in the same order they entered IF. Program order is preserved for free at the one station that matters.

Let $c (I)$ = the cycle in which instruction $I$ reaches WB. Because the belt never lets one instruction overtake another:

I_{a} before I_{b} in program order ⟹ c (I_{a}) < c (I_{b})

Read it as: older always writes back earlier. The arrow $⟹$ means "guarantees."

WHY it matters. Precision needs "all older results are in official state, no younger result is." If write-backs happen strictly oldest-first, then the moment $I_{2}$ finishes WB, everything older than $I_{3}$ is committed and nothing younger has committed — because younger things are still behind $I_{2}$ on the belt. The wall builds itself.

PICTURE. A timeline: the WB events line up as a staircase, oldest lowest-left, and we mark the "commit frontier" — the line separating done from not-done — that only ever moves rightward through program order.

Step 5 — Break the belt: out-of-order execution needs a wall

WHAT. Fast modern CPUs let an instruction EX as soon as its inputs are ready, even if an older instruction is stuck waiting (see data hazards). Now the guarantee of Step 4 is gone: $I_{4}$ might finish its arithmetic before $I_{3}$ .

If finishing arithmetic meant writing official registers, precision would collapse. So we forbid execute-units from writing official state at all. Instead each result is parked in a waiting room called the Reorder Buffer (ROB).

ROB = a queue of slots, one per in-flight instruction, kept in program order (the order they were issued, not the order they finish).
Each slot holds: which instruction, its status (empty / done / faulted), and its computed result (not yet official).

WHY a queue in program order. Execution scrambles the timing; the ROB restores the order on the way out. It is exactly the Step-4 belt, rebuilt as a data structure so it survives out-of-order EX. Superscalar machines lean on this — see the ROB in superscalar.

PICTURE. Execute units fire in a jumble (curvy arrows arriving out of order), but the ROB slots stay in neat program order, filling with done/faulted tags.

Step 6 — Commit: the one gate that touches official state

WHAT. Only the slot at the head of the ROB (the oldest instruction) may commit — copy its parked result into official registers/memory and leave. Commit happens strictly head-first, i.e. in program order.

Let the head slot hold instruction $I_{h}$ . The commit gate obeys:

commit (I_{h}) ⟸ ⎩ ⎨ ⎧ status (I_{h}) = done status (I_{h}) = faulted status (I_{h}) = empty \Rightarrow copy result \to official state, advance head \Rightarrow take the exception here \Rightarrow wait (do nothing this cycle)

Term by term: $⟸$ means "the commit gate decides based on"; done = result ready & no fault; faulted = this instruction raised an exception; empty = not finished yet, so we stall the gate.

WHY this is automatically precise. Because official state changes only at commit and commit is strictly in program order, when $I_{3}$ (faulted) reaches the head, every older instruction has already committed (they were ahead of it and left first) and no younger instruction can have committed (they are behind it in the queue). That is the precise-exception definition, enforced by the geometry of a queue.

PICTURE. The ROB with $I_{1}, I_{2}$ committed (leaving green), $I_{3}$ at the head stamped faulted in red, $I_{4}$ still holding a finished-but-unpublished result behind it.

Recall Why can't

$I_{4}$ leak out even though it finished first? Because $I_{4}$ sits behind $I_{3}$ in the ROB queue and only the head commits. $I_{3}$ is faulted, so the gate stops there and $I_{4}$ is flushed — its finished result never reaches official state. ::: The queue order, not the finish order, decides who publishes.

Step 7 — Edge case A: the fault was on a wrong-guess path

WHAT. The CPU guesses which way a branch goes and fetches ahead (see branch prediction). Suppose it guessed "not taken" and fetched $I_{2} =$ DIV ..., R0 which faults. Later the branch resolves: it was actually taken, so $I_{2}$ was never supposed to run.

Rule: a fault is only real if the instruction is on the true path — i.e. only if it would ever reach the ROB head as a real (non-flushed) instruction.

raise exception ⟺ I reaches ROB head AND I is not squashed by a branch

$⟺$ means "exactly when." A wrong-path instruction gets squashed before it can ever be the committing head, so its fault silently disappears.

WHY. Precision means sequential semantics — and a sequential machine would never have executed the wrong-path instruction, so it would never have seen that fault. We mimic that by discarding it.

PICTURE. Two forked paths; the guessed (wrong) branch carries a red-fault $I_{2}$ ; when the branch resolves the wrong fork is erased with a big X, fault and all, and the correct fork continues.

Step 8 — Edge case B: two faults in the same cycle

WHAT. Two instructions signal exceptions at once. Say $I_{3}$ (older, divide-by-zero in EX) and $I_{4}$ (younger, illegal opcode in ID) both scream in cycle 5. Which one wins?

Rule: report the older one in program order. Tag each fault with its instruction's sequence number $n (I)$ (its position in the ROB) and pick the minimum:

fault taken = ar g I faulted min n (I)

Term by term: $n (I)$ is the program-order index; $ar g min$ means "the $I$ with the smallest such index" — the oldest. Everything younger, including $I_{4}$ , is flushed.

WHY. A sequential machine reaches $I_{3}$ before $I_{4}$ , so it stops at $I_{3}$ and never even gets to $I_{4}$ 's illegal opcode. The pipeline detected $I_{4}$ 's fault earlier in time, but time doesn't matter — program order does. The ROB already sorts by program order, so "take the fault at the head" gives this for free.

PICTURE. Two red bursts in one frozen column; the older one ( $I_{3}$ ) is circled as "winner," the younger one ( $I_{4}$ ) is crossed out as flushed. A little side-note lists the same-instruction priority: fetch-fault > illegal/privilege > arithmetic (see memory/page faults).

The one-picture summary

Everything above is one idea seen from different sides: official state may only change at a single in-program-order gate, so an exception taken at that gate is automatically precise. The final figure fuses the simple pipeline (Steps 1–4) and the ROB machine (Steps 5–8) into one flow: instructions scramble through execution, re-line-up in the ROB, and pass one at a time through the commit wall — older-done to the left, faulted-and-younger flushed to the right.

Recall Feynman retelling — say it like you'd explain to a friend

Imagine a bakery. Bakers (execute units) finish cakes in any order they like — a simple cake before a fancy one that started earlier, no problem. But there's one cashier (the commit gate) and a strict numbered line (the ROB) at the front. The cashier only ever serves the person at the head of the line, in number order, and only there does a cake actually leave the shop (become official state).

Now one order is impossible — "divide by zero," a cake made of nothing. The baker tags that ticket "spoiled." Cakes behind it are already baked and boxed, but they cannot leave, because the cashier reaches the spoiled ticket first and stops the line. Everyone ahead of the spoiled ticket already left — they're official. So at the instant we stop: everything older is out the door, the bad order and everything younger is still trapped inside and gets thrown away. That's a precise exception — and it's precise not because of clever timing, but because of the one-cashier-in-numbered-order rule.

Two more twists: (1) if a ticket came from a guess that turned out wrong (a mispredicted branch), we shred it before it ever reaches the cashier — its "spoiled" tag never counts. (2) If two tickets are spoiled at once, the cashier only cares about the one with the lower number, because in a one-at-a-time world he'd hit it first. ::: The wall, the line, the single cashier — that's the whole trick.

See also: Hinglish version · 5.2.1-Pipelining-basics · 6.3.4-Reorder-buffer-in-superscalar.