Three ways instructions collide, and pipelines where EX takes more than a cycle

Dependence, hazard, stall: three words for three different things

This chapter is about instruction-level parallelism (ILP): overlapping independent instructions of one program inside one core. Pipelining is its simplest form (lesson 1); issuing several instructions per cycle and executing them out of order are the aggressive forms (lessons 8 to 18). How much can overlap is bounded by dependences, so start with the loop of the puzzle, written as the paper writes it (older papers write $F2; the 2026 paper and this notebook drop the dollar sign):

I0  FOR: LD    F2, AA(R1)
I1       FADD  F2, F2, F2
I2       LD    F4, BB(R1)
I3       FADD  F2, F2, F4
I4       SD    F2, A(R1)
I5       ADDUI R1, R1, 8
I6       BNE   R1, R2, FOR

I1 adds F2 to itself, and F2 is what I0 has just loaded: I1 needs a value that I0 produces. That is a data dependence — a fact about the program, true on every machine. Whether it costs anything is a question for the pipeline.

Take I1 → I3, two FADDs through F2. On the five-stage pipeline of lesson 2, with forwarding, the second FADD loses nothing; give the adder three cycles and the pair costs two stalls; let the hardware run other instructions meanwhile and it costs nothing again. Same dependence, three prices (Fig. 1).

The notes (p. 74): "dependencies are intrinsic to the program semantics, hazards are an architectural artifact of the pipeline implementation". The exam uses the first two words — EX1's first table asks for dependences, its Tomasulo table has a "Hazards Type" column — and the third hides in its "Calculate the CPI": every stall is a cycle in that count.

A dependence tells the designer three things (Hennessy & Patterson): a hazard is possible; the order in which the results must be computed; and an upper bound on the parallelism — the longest chain of dependent instructions, weighted by the latencies of their units, is the critical path that no machine can beat (lesson 20 computes it for the VLIW exercise).

Two properties may never be broken by reordering (p. 74): data flow — each consumer receives the value program order designates — and exception behaviour — the same exceptions are raised. Everything else is negotiable.

True dependences: a value flows

"True" because a value travels along it. Nothing removes it; you can only shorten the wait (forwarding) or fill it with other work — the compiler by moving instructions (lessons 19–21), the hardware by executing out of order. The chain of true dependences is the floor under every schedule; the first widget shows the longest one of each exam loop.

Values flow through registers, where the decoder sees the dependence by comparing register numbers, or through memory, where A(R1) and B(R1) may or may not be the same address. The exam's table asks for registers only.

Loop-carried dependences (not in the notes, asked in a quiz)

In X[i] = X[i] + X[i-1] the read of X[i-1] depends on the previous iteration: loop-carried. A read of X[i] in the next statement of the same iteration is not. In the exam loops the ADDUI R1 feeds the next iteration's LD: loop-carried, hence absent from the "intra-loop" table. The quiz of 15 July 2024 on exactly this is in the exam section.

Name dependences, and the renaming that deletes them

Now I1 and I3 again. Three relations link them on F2, and only one carries a value: I3 reads the sum I1 produces (true). I3 also overwrites the register I1 reads, and the register I1 writes — nothing flows there; the two merely share the name F2. Write I3's result into F8 instead, with I4 reading F8, and both vanish.

When can each become a hazard? WAR needs a younger instruction to write before an older one has read: impossible in the five-stage pipeline, where reads happen in ID and writes in WB, both in order; possible once an older instruction waits for its operands while younger ones proceed (the scoreboard of lesson 9, which therefore checks WAR at write-back). WAW needs two writes to complete out of order: possible as soon as units have different latencies, even with in-order issue (section 4).

Register renaming

Two instructions that share only a name can be given different names: register renaming. The second writer gets a fresh destination and — the line the notes' Example 4 leaves out — every later reader of the old name is redirected to the fresh one. On the loop:

I0  FOR: LD    F2, AA(R1)
I1       FADD  F6, F2, F2      # was F2: fresh name F6
I2       LD    F4, BB(R1)
I3       FADD  F8, F6, F4      # was F2: fresh name F8, reads I1's F6
I4       SD    F8, A(R1)       # reads I3's F8
I5       ADDUI R3, R1, 8       # was R1: fresh name R3
I6       BNE   R3, R2, FOR     # reads I5's R3

Every name dependence is gone; the chain of true dependences, I0 → I1 → I3 → I4 and I5 → I6, remains (Fig. 2). The next iteration must use R3 for R1: a compiler carries the new names forward, hardware keeps a map, so that "R1" means the physical register most recently assigned to it.

Hardware renaming happens at run time: a register alias table maps each architectural register to one of a larger set of physical registers, or the renaming is implicit, as in Tomasulo's algorithm (lesson 11), where the name of a pending result is the reservation station that will produce it — flexible, at a hardware cost. Software renaming happens at compile time with spare architectural registers, for VLIW machines (lesson 15): simpler hardware, more pressure on the compiler (p. 78). The notes' condition "more physical registers than … logical registers" (p. 77) really means more names than the program uses at once — physical registers, tags, or spare architectural registers.

The exam's table, drilled

Two patterns repeat in every paper: the ADDUI R1 collects an anti-dependence with every load and store that used R1, and the BNE depends on it; a register re-used as an accumulator produces a true, an anti- and an output dependence on one instruction — the highlighted row, the puzzle of the warm-up.

Control dependences: the two rules, and the licence to bend them

The loop ends with BNE R1, R2, FOR. Whether the next LD executes at all depends on its outcome, known in ID at the earliest (lesson 4): the fetch unit must wait or guess. That is the third kind of collision.

Two constraints follow (Hennessy & Patterson, not the notes): an instruction control dependent on a branch cannot be moved before it, so that the branch no longer controls it; an instruction not control dependent on a branch cannot be moved after it, so that the branch controls it.

Yet control dependence is not itself sacred — data flow and exception behaviour are. If moving an instruction across a branch changes neither, the move is legal: the delay slot, whose instruction runs on both paths (lesson 4), predication (lesson 21) and speculation — executing the dependent instructions before the branch resolves and keeping their results undoable (lesson 17) — all live on that licence, "breaking or relaxing control dependencies, without violating program semantics" (p. 79).

Prediction, static and dynamic, is lessons 4 to 6; this chapter adds speculation — executing the guessed path and holding its results until the branch is known.

When EX takes more than one cycle

Lesson 1's pipeline assumes every stage lasts one cycle. In the MIPS pipeline of Hennessy & Patterson a dependent instruction waits 3 cycles after an FP add, 6 after a multiply and 24 after a divide — and the divider is not pipelined, since replicating an iterative divider for a rare operation is not worth the area. One cycle for everything would mean a clock as slow as the slowest operation, so EX becomes a set of functional units with their own latencies, pipelined or not (pp. 80, 82).

A unit of \(n\) cycles that forwards at the end costs a back-to-back consumer \(n - 1\) stalls: 0 for a one-cycle ALU, 1 after a load, 2 after the three-cycle adder of Fig. 1. That \(n - 1\) is what Hennessy & Patterson tabulate as the latency; the exam papers tabulate \(n\) — "latency 4" for a load: issued in cycle 1, executing in 2 to 5, writing in 6 (lesson 12).

In order all the way: one commit point (Figure 20)

The notes' model (p. 80) is single-issue and in-order, with write-back "delayed or synchronized". Figure 20 (p. 82) shows what that means: an integer lane, an FP-add lane, an FP-multiply lane and an unpipelined divider all pass through the same sequence of pipeline registers, X1, X2, X3, W — short operations are padded so that every result reaches W after the same number of cycles — and a vertical line through W is labelled "Commit Point". Results reach W in issue order, one per cycle.

That line buys three things: no WAW hazard, since completion order equals issue order; one write per cycle, so one write port suffices; and an exception taken at the commit point comes after every older instruction and before any younger one — a precise exception (section 5). The price: an unpipelined divide or a cache miss stalls everything behind it — "all instructions are serialized through the same issue logic, even if no true dependence exists" (p. 81). Table 8: everything in order, stalls propagate, moderate complexity, exceptions always precise.

Out of order at the end: no commit point (Figure 21)

Figure 21 (p. 86) splits ID into ID (decode) and Issue (read the registers, check the operands); after Issue each instruction goes to its own unit — the ALU followed by Mem for integer and memory instructions, Fadd, Fmul, Fdiv — of its own length, and each unit delivers to WB when it is done: "there is no single commit point shown" (p. 86).

Hennessy & Patterson list what this design must cope with even with in-order issue (app. C.5): a structural hazard on the divider; several instructions reaching WB in the same cycle — a write-port conflict; WAW hazards; imprecise exceptions; longer RAW stalls. WAR is not on the list: operands are read in order at Issue.

Watch it on five instructions: divider 8 cycles, not pipelined; multiplier 3; adder 3; integer unit 1; a result written in cycle \(t\) is usable from \(t + 1\); one write port, oldest first.

I0  FDIV  F0, F2, F4        # divider, 8 cycles, not pipelined
I1  FADD  F6, F0, F8        # needs F0 from I0
I2  FMUL  F10, F8, F14      # independent
I3  FADD  F6, F10, F12      # needs F10 from I2; writes F6 like I1
I4  ADDUI R1, R1, 8         # independent, 1 cycle

In order: 19 cycles — the divide freezes issue until cycle 9 and every RAW wait holds everything behind it. Out of order: 13 cycles, with completion order I2, I4, I0, I3, I1; a write-port fight in cycle 6 (the older I2 writes, the ADDUI slips to 7); and F6 written by I3 in cycle 10, then overwritten by the older I1 in 13 — a WAW hazard a real design must catch by stalling the younger writer at issue (scoreboard, lesson 9) or renaming (Tomasulo, lesson 11). The fourth thing, the divide faulting, is the next section and the widget's toggle.

Precise exceptions, and the fix that won

Why insist? Many exceptions are requests, not errors: a page fault (lesson 27) means "this data is on disk", and the operating system brings it in and re-executes the faulting load — only that load, with everything before it done and nothing after. An IEEE floating-point trap must name the exact operation. Imprecise exceptions are a correctness problem: the program cannot be restarted.

How the five-stage pipeline handles exceptions (textbook, not in the notes)

The professor's topic list names "Multicycle Pipeline; Exceptions Handling"; the notes give it one sentence, so the mechanism is Hennessy & Patterson's (app. C.4). Each stage can raise its own exceptions (Fig. 6): IF a page fault or misaligned fetch, ID an illegal opcode, EX overflow or divide by zero, MEM a page fault or misaligned data access, WB none. A stage only sets a flag in a status vector that travels with the instruction; the vector is checked at WB. If it is not empty, the instruction's writes are turned off, the younger instructions are flushed, the PC is saved and the handler is fetched. Checking at WB takes exceptions in program order even when they arise in another: if a load page-faults in MEM (its fourth cycle) and the instruction right behind it page-faults in IF (its first cycle, two cycles earlier in time), the load reaches WB first and its fault is handled first. The pipeline is precise because every instruction reaches WB in order — what Figure 20's commit point preserves and Figure 21 gives up.

Four remedies for multi-cycle units, and the one that won

Once units complete out of order the trick breaks: when the divide reports its fault, a younger multiply may have written its register. Hennessy & Patterson list four ways out (app. C.5): accept imprecise exceptions, where no restart is ever needed; buffer the results until all earlier instructions have completed — a future file that updates the registers in order, or a history file that keeps the old values to restore them; keep enough information for a software handler to finish the older instructions and restart; issue an instruction only when all earlier ones are certain not to fault. The notes name the second, "Reorder Buffers (ROB) to store results until it's safe to commit them in program order", and "checkpointing and rollback" (pp. 84–85). The second won: every modern core completes out of order and commits in order through a reorder buffer — the widget's third machine, built in lesson 17. Table 9: issue in order, execution and completion out of order, ILP high, complexity high, exceptions: "Risk of imprecision without commit logic".

Dynamic scheduling, defined properly

The notes open section 3.3 with three instructions (p. 87), here in the mnemonics of the papers:

I1  FDIV  F0, F2, F4        # long-latency divide
I2  FADD  F10, F0, F8       # depends on F0
I3  FSUB  F12, F8, F14      # independent of I1 and I2

In order, I2 waits for F0 and I3 waits behind I2 although it needs nothing from either. Dynamic scheduling parks I2 until F0 arrives and lets I3 execute and complete at once — the race widget's 13 cycles instead of 19.

The structures (p. 87): reservation stations or issue queues, where instructions wait for operands; a reorder buffer, for in-order commit; register renaming tables; a common data bus that broadcasts each result with its tag to every waiting consumer. The stages: Fetch, Decode, Issue (into a reservation station), Execute (when all operands are available), Write Result (to a buffer or broadcast), Commit (architectural registers updated in order). The CDC 6600's scoreboard (lesson 9) has none of these structures and still executes out of order; Tomasulo (lesson 11) adds stations, bus and implicit renaming; the reorder buffer (lesson 17) adds commit.

What it buys (p. 88): higher ILP, units kept busy, latency hiding, independent operations that no longer block one another; and, Hennessy & Patterson add, dependences unknown at compile time (memory, control flow, cache misses) are handled, the same binary runs well on different pipelines, and hardware speculation becomes possible. What it costs (p. 88): WAR and WAW hazards, cured by renaming; imprecise exceptions, cured by the reorder buffer; and hardware — dependency tracking, the wakeup-and-select logic that picks the ready instructions each cycle, the broadcast bus, the instruction window. How wide that window can be is lesson 8.

Issue in order, execute out of order, commit in order: everything the next eleven lessons build keeps these three rules.

Back to the puzzle

A Tomasulo machine renames: I3's result gets a fresh name, so it no longer overwrites a register that I1 still has to read or write — anti- and output dependence gone. The true dependence stays: I3 needs the sum I1 computes, and no name can replace a value that does not exist yet. One sentence: renaming deletes name dependences because nothing flows along them, and keeps true dependences because something does. The out-of-order freedom that renaming unlocks is what left the Model 91 unable to say where a fault had happened, until completion and commit were separated — by the reorder buffer.