Lecture 13: Precise Exceptions

What this lecture covers

The lecture answers a question left open from the pipelining lectures: if different functional units take different numbers of cycles (an add finishes in one cycle, a divide in eight), what happens when a younger, faster instruction wants to write its result before an older, slower instruction has finished? Writing out of order would break the von Neumann model's sequential semantics, and it becomes especially dangerous once exceptions and interrupts are involved, because a program that crashes mid-execution needs a clean, well-defined state to recover from.

The lecture builds up the concept of precise exceptions, explains why hardware designers care about them, and walks through how single-cycle, multi-cycle, and pipelined machines each support them. It ends by introducing the reorder buffer, the mechanism that lets instructions complete execution out of order while still updating the architectural state in program order. This sets up the following lecture on out-of-order execution.

Key ideas

• Exception: an internal, program-caused abnormal condition, such as divide by zero, arithmetic overflow, an undefined opcode, or a page fault.
• Interrupt: an external event unrelated to the running program, such as a power failure, a network packet arriving, or a timer signal; interrupts are handled by the system, not the program.
• Precise exception: when an exception is handled, all instructions before the excepting one have fully retired (updated architectural state) and none after it have, giving the programmer a clean, well-defined machine state to debug or recover from.
• Retire / commit: the point where an instruction's result is written into the architectural state (registers, memory, PC); this must happen strictly in program order.
• Reorder buffer (ROB): a circular hardware queue that holds decoded-but-not-yet-retired instructions; instructions can write their results into the ROB out of order, but results only move into the register file when an instruction becomes the oldest in the machine.
• Content-addressable search: because the ROB is indexed by program order rather than by register number, finding "the latest value of register R3" requires comparing the destination register ID of every entry, an expensive, age-based search.
• Register renaming via indirection: rather than searching the ROB directly, the register file stores a tag pointing to the ROB entry that will produce a register's value, avoiding the costly content-addressable search.
• False dependences (WAR/WAW): output and anti-dependences on the same architectural register are artifacts of having too few register names, not true data dependences; renaming eliminates them.

Walkthrough

Why out-of-order completion threatens sequential semantics (2:06)

The lecture opens with a pipeline where functional units differ in latency: an integer add finishes in one cycle, a divide might take eight (or, in real processors, 40 to 50). If a fast, younger add instruction is allowed to write its result to the register file before a slower, older divide finishes, the sequential instruction semantics of the von Neumann model are violated. The instructor uses a tram analogy: one delayed tram (an excepting instruction) blocks the cars behind it, and later trams should not be allowed to overtake and "finish" first.

Exceptions vs. interrupts (9:09)

Exceptions are internal to the running program (divide by zero, overflow, undefined opcode, protection violations, page faults). Interrupts are external (power failure, I/O device service requests, timers, machine checks). Both stop the current program, save architectural state, and transfer control to a handler, but they differ in urgency and handling context: exceptions are handled immediately and in the context of the process (so a programmer can catch them), while interrupts can often be deferred and are handled by the operating system.

Why precise exceptions matter (27:27)

Precise exceptions make software debugging and recovery tractable: the programmer knows exactly which instructions completed and which did not, so the program can be restarted or fixed up from a known point. The lecture notes that an early IBM out-of-order machine skipped precise exceptions and, despite being technically advanced, struggled commercially because it was too hard to debug. Precise exceptions also enable clean recovery, easy restart at the faulting program counter, and software emulation of unimplemented instructions (such as emulating multiply or floating-point operations with an exception handler).

Supporting precise exceptions in single-cycle and multi-cycle machines (34:29)

In a single-cycle machine the problem does not exist, since instruction and cycle boundaries coincide. In a multi-cycle machine, the finite state machine is extended with special states (for example, an "undefined opcode" state and an "overflow" state) that set a cause register, save the excepting PC into an EPC register, and redirect the next PC to an exception handler. The lecture works through the MIPS multi-cycle datapath modifications, including the MFC0 instruction used to copy the cause into a general-purpose register.

The naive fix and its cost (44:41)

For a pipeline with multi-cycle functional units, one "solution" is to force every instruction to take as long as the slowest one, so writes stay in order. This preserves precise exceptions but throws away the performance benefit of fast instructions, similar to reverting to a single-cycle design. The lecture frames this as a non-solution and introduces four real approaches used in practice: the reorder buffer, history buffer, future register file, and checkpointing, focusing on the reorder buffer.

The reorder buffer: mechanism and example (46:42)

The reorder buffer decouples microarchitectural completion from architectural commitment: instructions can finish and write into their allocated ROB entry out of order, but only the oldest instruction in the ROB updates the register file or memory. Each entry tracks validity, destination register, destination value, whether the value has been written, the instruction's PC (for exception handling), and whether it caused an exception. The instructor works through a multi-cycle simulation where two instructions both target register R3, showing how a dependent instruction can search the ROB for the correct, most recent definition of a register.

From content-addressable search to indirection and renaming (1:20:04)

Searching the ROB by content (comparing every entry's destination register against the one being looked up) is expensive and gets worse as ROB size grows. The fix is indirection: the register file gains a tag field that, when a register's value is not yet ready, points directly to the ROB entry that will produce it. This is illustrated with a re-run of the earlier example using tags instead of searches, and connected to a real design, the Intel Pentium Pro's register alias table.

Register renaming and closing summary (1:26:08)

The lecture closes by generalizing: tagging registers to ROB entries is a form of register renaming, which eliminates false write-after-write and write-after-read dependences caused by having too few architectural register names, while preserving true (flow) dependences. This gives the illusion of many more registers than the ISA exposes and sets up out-of-order execution, covered next.

Before you watch

• Review the earlier pipelining lectures on data forwarding, bypassing, and control/data dependence handling in this course, since this lecture assumes familiarity with pipeline hazards.
• Be comfortable with the basic multi-cycle MIPS datapath and finite state machine, since the lecture extends it directly.
• Knowing what output and anti-dependences (WAW, WAR) are will help the register renaming discussion make sense.

Check your understanding

1. Why does allowing a fast instruction to write its result before an older, slower instruction finishes violate sequential semantics?
2. What is the difference between an exception and an interrupt, and why does that difference affect how urgently each is handled?
3. Why did forcing every instruction to take the worst-case number of cycles fail as a practical solution to precise exceptions?
4. How does a reorder buffer let instructions complete out of order while keeping architectural state updates in program order?
5. Why does searching a reorder buffer by register ID require a content-addressable search, and how does adding tags to the register file avoid it?