Precise exceptions in pipelines: Exercises — Hardware deep dive

Before we start, one picture fixes the vocabulary we will lean on the whole page.

Figure — Precise exceptions in pipelines

Figure s01 — The 5 pipeline stages drawn as a left-to-right assembly line. Each rounded box is one stage; the navy arrows show an instruction advancing exactly one box per clock cycle. The orange boxes (IF, ID) are the "front" of the pipe where new work enters; the magenta box (EX) is where arithmetic faults are detected; the violet boxes (MEM, WB) are the "back" where memory faults appear and where results finally reach architectural state. The stage indices 1–5 printed on the boxes are the numbering convention used in Exercise 2.3.

Definition The five stages, their indices, and the words we use

A pipeline is an assembly line for instructions. Each instruction walks through 5 rooms, and we number the stages 1 through 5 in the order an instruction visits them (this numbering is used in the arithmetic of Ex. 2.3):

Stage 1 = IF = Instruction Fetch — grab the instruction from memory.
Stage 2 = ID = Instruction Decode — figure out what it is, read registers.
Stage 3 = EX = Execute — do the arithmetic (add, divide, compare). Arithmetic faults are detected here.
Stage 4 = MEM = Memory — read/write data memory (for loads/stores). Page faults are detected here.
Stage 5 = WB = Write Back — write the result into the register file.

Architectural state = the stuff a programmer can see: the registers and memory. An instruction only really happened once it has updated architectural state. Program order = the order the instructions appear in the program text. Instruction $i$ is older than $i + 1$ . In a pipeline the older instruction is the one further along (higher stage number, closer to WB). EPC = Exception Program Counter — a register that remembers "where the fault was" so the handler can come back.

Definition Three operations you must not confuse: write-back, flush, commit

These three verbs appear all over the page. Pin them down now:

Write-back (WB stage) — in a simple in-order pipe, this is the physical act of writing a result into the register file. In an in-order pipe, reaching WB is the moment the instruction updates architectural state.
Flush — cancel an instruction that is still inside the pipe by turning it into a NOP (a "No Operation" bubble). A flushed instruction writes nothing, reads nothing, changes no state — as if it was never fetched. Flushing is how we make the faulter and everything younger "disappear."
Commit (a.k.a. retire) — used in out-of-order machines with a Reorder Buffer. An instruction may finish executing early and park its result in the ROB (a private scratchpad), without touching architectural state. Commit is the separate, strictly-in-program-order step that copies that parked result out of the ROB into the real registers/memory. So: execute = compute the answer; commit = make the answer official. Flushing a not-yet-committed instruction is free — its result was only ever in the ROB.

Definition The stall-on-exception strategy (used from Ex. 2.1 onward)

This is the simplest way an in-order pipeline achieves precise exceptions. The moment any instruction in a stage raises a fault signal, the control logic does exactly this:

Freeze the front. De-assert (turn off) the "advance" enable for the IF and ID stages: the program counter stops incrementing and no new instruction is decoded. In hardware this is one stall signal wired to the IF/ID pipeline registers.
Inject bubbles for the faulter and younger. Assert a flush signal to the pipeline registers holding the faulting instruction and every instruction younger than it, overwriting each with a NOP. These bubbles will ride through MEM/WB writing nothing.
Let the older instructions drain. The instructions older than the faulter (already in MEM/WB) keep their advance enabled and finish their write-backs normally — they were supposed to run, so they must complete.
Record the return point. Copy the faulting instruction's address into EPC.
Redirect. Once the older instructions have drained, set the PC to the exception handler's entry address and un-freeze the front.

The cost is the few cycles in step 3 while older instructions drain — that is exactly what Ex. 2.3 counts.

Level 1 — Recognition

Exercise 1.1

Which of these is the exact promise of a precise exception? Pick one. (a) The faulting instruction and everything after it completed; everything before was cancelled. (b) Everything before the faulting instruction completed; the faulting instruction and everything after it modified nothing. (c) Every instruction in the pipeline is cancelled when any fault occurs. (d) The exception is reported the moment it is detected, in any order.

Recall Solution

Answer: (b). Rebuild it from the picture: a precise exception makes the pipeline look like a slow one-at-a-time machine that stopped exactly at the faulting instruction. So all older instructions (before it) must have finished updating registers/memory, and the faulting instruction plus all younger ones (after it) must have touched nothing.

(a) is time-reversed — it keeps exactly the wrong ones.
(c) throws away work that already correctly completed (the older instructions).
(d) is imprecise by definition: order must follow program order, not detection time.

Exercise 1.2

Match each abbreviation to its job. EPC · WB · ROB · NOP

Recall Solution

EPC — Exception Program Counter: stores the address of the faulting instruction for the handler.
WB — Write Back: the stage where a result finally enters the register file (architectural state).
ROB — Reorder Buffer: holds finished-but-not-yet-committed results so they can be committed in program order.
NOP — "No Operation": a bubble that does nothing; we convert flushed instructions into these so they touch no state.

Exercise 1.3

True or false: "An instruction that has reached WB but not written yet, and an instruction still in IF, are the same distance from being 'committed'."

Recall Solution

False. The instruction in WB is one micro-step from updating architectural state — it is almost done. The instruction in IF has barely started (4 stages to go). "Committed" means "its effect on registers/memory is locked in," and only WB does that in a simple in-order pipe.

Level 2 — Application

Exercise 2.1

A 5-stage pipeline (IF, ID, EX, MEM, WB) advances one stage per cycle. In cycle 5 the snapshot is:

IF: I5    ID: I4    EX: I3 (FAULT)    MEM: I2    WB: I1

Using the stall-on-exception strategy (defined above), in which cycle does the last older instruction (I2) finish its WB, so that all instructions older than I3 are complete?

Recall Solution

Apply the strategy: freeze IF/ID (so I4, I5 stop), flush I3/I4/I5 into NOPs, and let the older instructions I1, I2 drain. Walk the older instructions forward from cycle 5:

I1 is in WB this cycle (cycle 5) — it finishes at the end of cycle 5.
I2 is in MEM in cycle 5, so it enters WB in cycle 6 and finishes at the end of cycle 6.

So after cycle 6, both I1 and I2 have written back. I3, I4, I5 were converted to NOPs and touched nothing. Save I3's PC to EPC and jump to the handler. Answer: cycle 6.

Exercise 2.2

Same snapshot as 2.1. How many instructions must be converted to NOPs (flushed), and which ones?

Recall Solution

Flush the faulting instruction and everything younger: that's I3, I4, I5 → 3 instructions. I1 and I2 are older, so they are not flushed — they must complete for precision.

Exercise 2.3

The pipeline is $k$ stages deep, and stages are numbered $1$ (IF) through $k$ (WB) in visit order, exactly as printed on the figure. A fault is detected in the EX stage, which is stage number 3. In the worst case, how many cycles must the pipeline stall while all older instructions drain out through WB?

Recall Solution

Step 1 — who is older and still unfinished? Older instructions sit in stages after EX. With the numbering IF=1, ID=2, EX=3, MEM=4, WB=5, the stages after EX are MEM (4) and WB (5). That is $k - 3 = 5 - 3 = 2$ stages.

Step 2 — how long does each take to reach the end (WB)?

The instruction already in WB (stage 5) finishes this cycle → 0 further advances, done after 1 cycle.
The instruction in MEM (stage 4) must advance MEM→WB → it finishes after 2 cycles.

Step 3 — the drain time is set by the furthest-behind older instruction, which is the one in MEM. It needs to climb from stage 4 to stage 5 = 1 more advance, but it entered a full cycle behind WB, so the whole drain completes after 2 cycles. That matches the count of stages after EX.

General rule (now unambiguous with the numbering fixed): the number of older instructions to drain equals (stages after EX) $= k - (stage index of EX)$ . Here $= 5 - 3 = 2$ . Answer: 2 cycles.

Level 3 — Analysis

Exercise 3.1

Two faults appear in the same cycle:

ID: I4 — illegal opcode
EX: I3 — divide by zero

Which exception is reported, and what happens to the other instruction?

Recall Solution

I3 is in EX (stage 3), I4 is in ID (stage 2) — I3 is deeper in the pipe (higher stage number), meaning it entered earlier, meaning it is older in program order. Precise semantics report the oldest fault. Report: I3's divide-by-zero. I4: it is younger than the faulter, so it is flushed to a NOP — its "illegal opcode" fault is discarded. It never architecturally executed, so its fault must not be reported. (If the program is later resumed and re-runs from I3, I4 will be re-fetched and then its illegal-opcode fault surfaces legitimately.)

Exercise 3.2

Consider a Reorder Buffer with these entries at commit time:

Entry | Inst | Status    
1     | I1   | COMPLETE  
2     | I2   | COMPLETE  
3     | I3   | FAULTED (div-by-zero)
4     | I4   | COMPLETE

The ROB commits from the head (entry 1) in order. How many instructions update architectural state, and which ROB entries get flushed?

Recall Solution

The ROB commits in program order from the head, no matter what order execution finished. Recall commit = copy the parked result out of the ROB into real registers; flush = discard the parked result.

Commit I1 → writes architectural R1. ✔
Commit I2 → writes architectural R4. ✔
Head reaches I3, which is FAULTED → stop committing, take the exception here.
Flush I3 and I4 (entries 3 and 4). Even though I4 already finished executing, its result lives only in the ROB, not in architectural registers — so discarding it is free and safe.

Architectural updates: 2 instructions (I1, I2). Flushed entries: 3 and 4 (2 entries). This is exactly precise: older done, faulter and younger cancelled — even though I4 executed before I3 in real time. The ROB is what makes out-of-order execution look in-order at the finish line. See 6.3.4-Reorder-buffer-in-superscalar.

Exercise 3.3

A branch is predicted not taken, so the pipeline fetches the fall-through instruction I2, a DIV R3,R4,R0. I2 faults (divide by zero) in EX. Then the branch resolves as taken — I2 was on the wrong path. Is the exception reported?

Recall Solution

No. I2 was speculative — fetched before the branch outcome was known. When the branch resolves taken, I2 is on the wrong path, so it is flushed and its fault vanishes. An instruction that was never supposed to execute cannot cause a precise exception. The hardware marks I2 "faulted, speculative" and only converts the mark into a real exception if I2 ever reaches the commit point on the correct path. Here it never does. See 5.2.11-Branch-prediction.

Level 4 — Synthesis

Exercise 4.1

A load instruction I2 causes a page fault in MEM (its page is on disk — see 7.2.5-Virtual-memory-exceptions). Older instruction I1 is in WB; younger I3, I4 are in EX and ID. Describe the full precise-exception sequence so that after the handler brings the page in, execution can resume and re-run I2 correctly.

Recall Solution

Detect the page fault in I2's MEM stage. Mark I2 as faulting; do not let it write anything (a page-faulting load has no valid data to write back).
Let I1 finish — it is older, so it must complete WB and update architectural state.
Flush I2, I3, I4 to NOPs — the faulter and all younger instructions modify nothing.
Save I2's PC into EPC. Crucially this is I2's own address, not the next instruction — because after the page is loaded we must re-execute I2, not skip it.
Jump to the page-fault handler. It reads EPC, walks the page tables, loads the missing page from disk, marks it present.
Handler returns via a "return-from-exception" instruction that sets PC = EPC, so I2 re-runs, this time hitting in memory, and I3, I4 are re-fetched fresh.

Because I1 completed and I2/I3/I4 touched no state, the restart is seamless — the machine looks exactly as if it had paused right before I2. This resumability is the whole reason page faults demand precise exceptions.

Exercise 4.2

Design question: In an in-order pipeline, why is it safe to detect arithmetic faults (divide-by-zero, overflow) in EX but memory-access faults (page faults) only at MEM — and could reordering these detections ever break precision within a single instruction?

Recall Solution

Detection stage follows where the work happens: arithmetic happens in EX (stage 3), memory access in MEM (stage 4), so each fault is naturally discovered in its own stage. Within one instruction, an earlier-stage fault should win if both could fire, because in sequential execution the fetch/decode/arith checks logically precede the memory access. For a single instruction the ISA fixes a priority order (fetch fault > illegal-opcode > privilege > arithmetic > memory). The pipeline records whichever the ISA ranks first and suppresses later-stage detections for that same instruction. So it never "breaks precision" as long as the hardware honors the ISA's fixed intra-instruction priority. See 3.4.7-Exception-handling-in-ISA.

Level 5 — Mastery

Exercise 5.1

You are given a 2-wide superscalar, out-of-order core with a Reorder Buffer of 6 entries. In one cycle, three instructions signal faults:

ROB entry 2 : I2  — overflow (executed early, out of order)
ROB entry 5 : I5  — page fault
ROB entry 3 : I3  — illegal opcode

ROB head is currently at entry 1 (I1, still executing, not yet complete). All other entries have finished executing. Give the exact commit/flush behaviour, cycle by cycle, and the final EPC. Assume commit rate is 2 per cycle when instructions are ready.

Recall Solution

Reason strictly from the ROB rule: commit in order from the head; act on a fault only when its entry becomes the head. The faults on entries 2, 3, 5 are recorded as flags the moment they are detected — they do nothing until their entry reaches the head.

Cycle 1: head = entry 1 (I1) is still executing → the head is not ready → nothing commits. We wait. (Faults on 2/3/5 sit as flags.)

Cycle 2 (say I1 has now completed, fault-free): with a 2-wide commit port we try to commit up to two instructions from the head:

Slot A: commit I1 → architectural update of R1. ✔
Slot B: next head is entry 2 = I2, flagged overflow. Committing a flagged entry means taking its exception instead of updating state. Since I2 is the oldest faulting instruction in program order, this is the exception we take. Commit stops here — I2 does not update state.

Cycle 2, same cycle — flush: having selected I2's exception, flush I2 itself and every younger entry: entries 2, 3, 4, 5, 6. This discards I3's illegal-opcode flag and I5's page-fault flag — both vanish, exactly as required, because I2 is older than them.

Final tally:

Instructions that architecturally commit: 1 (only I1).
Exception taken: I2's overflow (oldest faulting entry).
Entries flushed: 2, 3, 4, 5, 6 → 5 entries (the faulter I2 plus 4 younger).
EPC = address of I2.

Key insight: the page fault on I5 and illegal opcode on I3 — both detected "in time" — are irrelevant. Program order alone decides, and I2 is oldest. This is why an out-of-order core is still perfectly precise.

Exercise 5.2

Invent a scheme. Precise exceptions cost drain/flush cycles. Some old machines offered imprecise exceptions (report faults late, out of order) to save hardware. Propose a hybrid: keep exceptions precise for resumable faults (page faults) but allow imprecise for fatal faults (illegal opcode that will terminate the program anyway). State one benefit and one danger.

Recall Solution

Scheme: Tag each exception type as resumable or fatal in a small ISA field.

Resumable faults (page fault, TLB miss): route through the full precise machinery — deferred, materialized only at in-order commit, EPC = faulting PC. Correctness demands it, since we must restart.
Fatal faults (illegal opcode, unrecoverable): allow imprecise reporting — raise as soon as detected, dump a "best-effort" register snapshot for the debugger, and terminate. Since we will never resume, exact sequential state is not strictly required.

Benefit: fatal faults avoid the drain/flush latency and the ROB-ordering wait, and simplify hardware for the rare fatal case. Danger: the register/memory snapshot the debugger sees may be inconsistent (some younger instructions committed, some older didn't), so post-mortem debugging can mislead — a value in a register might reflect an instruction that "shouldn't have run yet." Also, if a fault later turns out recoverable (e.g., a debugger patches the illegal opcode), you can't cleanly resume. This trade is why nearly all modern ISAs just make everything precise — the hardware cost has become cheap relative to the debugging and OS pain of imprecision.