Exercises — Out-of-order execution

• (a) RAW. I2 reads R1, which I1 writes. This is a true data dependency — the value must actually be produced first. Renaming cannot remove it.
• (b) WAW. Both write R1. Only I2's write should survive. It is false (name reuse). Renaming removes it: give I2 a fresh physical register.
• (c) WAR. I1 reads R1, then I2 overwrites R1. False — the reuse of the name R1 is the only conflict. Renaming removes it.
• (d) None. Disjoint registers, fully independent, can execute in any order.

1. Fetch/Decode — in-order
2. Dispatch (into reservation stations) — in-order
3. Execute — out of order (fires when operands ready)
4. Commit/Retire — in-order (through the ROB, to keep precise exceptions)

Memory hook: in — in — OUT — in. Only the middle execute stage is free to scramble; the two ends stay ordered so the programmer never notices.

Map each write of an architectural register to a new physical name, and each read to the most recent physical name written:

I1: T1 = R2 + R3
I2: R4 = T1 * R6      ; RAW on T1  -> must wait for I1
I3: T2 = R7 - R8      ; independent of everything above
I4: R9 = T2 + R5      ; RAW on T2  -> must wait for I3

• The R1 in I1/I2 became T1; the R1 in I3/I4 became T2. The WAW between I1 and I3 (and the WAR between I2 and I3) vanish.
• Two independent chains remain: {I1 → I2} and {I3 → I4}. They run in parallel.
• With unlimited ports and 1-cycle ops: I1 and I3 fire in cycle 1; I2 and I4 fire in cycle 2. Whole block finishes in 2 cycles instead of 4.

The station snoops the CDB, sees its waiting tag P8 matches, and captures the value: $\text{src1}\leftarrow 7,\text{Ready}(\text{src1})\leftarrow \text{true}.$ Now $\text{Ready}(I)=\text{Ready}(\text{src1})\wedge \text{Ready}(\text{src2})=\text{true}\wedge \text{true}=\text{true}$. Both operands available at end of cycle 4 ⇒ I fires the next cycle = cycle 5, computing $7+12=19$.

In-order. Why does I2 wait? In a strict in-order machine an instruction may only begin executing after every earlier instruction has begun (the execute stage dispatches in program order). So even though I2 has no dependency on I1, it is stuck behind I1 in the dispatch queue and cannot start until I1's 3-cycle LOAD has cleared the execute slot. That single ordering rule is exactly what OoOE will relax. Each column below is one cycle; read straight down to see which op occupies which cycle:

Cycle:  1    2    3    4    5    6
I1:    [L]  [L]  [L]
I2:                   [+]
I3:                        [-]
I4:                             [*]
Total span = 6 cycles

Out-of-order — look at the two chains: I1(3c) → I3(1c) and I2(1c) → I4(1c). With ports free, dependencies (not program order) decide firing:

Cycle:  1    2    3    4
I1:    [L]  [L]  [L]
I2:    [+]                  (independent, fires cycle 1)
I4:         [*]             (needs I2 done end of cy1, fires cycle 2)
I3:                   [-]   (needs I1 done end of cy3, fires cycle 4)
Total span = 4 cycles

• Chain 1 critical length = $3+1=4$ cycles → this is the critical path.
• Chain 2 length = $1+1=2$ cycles, hidden entirely under chain 1.
• Speedup $=6/4=1.5\times$.

The limit is the critical-path-limited ILP: the longest dependency chain. Here that is I1 → I3 with length $3+1=4$ cycles. Even with infinite resources you cannot start I3 before I1's LOAD result exists (a true RAW dependency), so 4 cycles is the hard floor. OoOE removes waiting for unrelated work — it can never remove waiting for your own inputs.

Commit is in-order from the head, using $\text{Can\_Commit}(I_h)=\text{Complete}(I_h)\wedge \neg \text{Exception}(I_h)$.

• (a) Head advances: I1 commits, I2 commits. Then head = I3, which is complete but has Exception true ⇒ stop. So exactly 2 instructions ($I_1,I_2$) commit before the fault.
• (b) I4 and I5 are squashed / flushed. Their computed values live only inside the ROB, never in architectural registers or memory, so they simply disappear. This is why speculative results are safe: nothing after a fault ever became visible.
• (c) The exception handler runs; architectural state = post-I2. The OS may fix the cause and restart execution at I3. The programmer sees clean semantics: "I3 faulted, nothing after it happened."

To keep retiring while a 100-cycle miss resolves, the window (ROB) must contain enough independent instructions to cover the whole latency at the commit rate: $\text{Window}\gtrsim \text{commit rate}\times \text{latency}=4\times 100=\boxed{400\text{ instructions}}.$ (Here issue rate ≥ commit rate, so the ROB fills and the commit rate is what must be sustained past the miss.) This is exactly why real designs push windows to 200–600 entries — the deeper the memory latency you want to hide, the bigger the window (and ROB, physical register file, load/store buffers) must be. Below this size the ROB fills, the head stalls on the outstanding LOAD, and commit halts.

With one port, the port is a shared resource. Total work = $3+1+1+1=6$ port-cycles, so we can never finish before cycle 6 no matter the order — execution-width-limited. A valid schedule (each column = one cycle):

Cycle:  1    2    3    4    5    6
Port:  [L]  [L]  [L]  [+]  [*]  [-]
Op:     I1   I1   I1   I2   I4   I3

I2 and I4 fire once the port frees at cycle 4 (I4 in cycle 5 after I2 gives its result end of cycle 4); I3 fires last (its input I1 was ready end of cycle 3, but the port is busy until cycle 6).

• Span = 6 cycles, speedup $=6/6=1.0\times$. Reordering bought nothing here.
• Lesson: OoOE only helps when a resource other than the bottleneck is idle. With a single port fully occupied, you are limited by $\text{Execution width}$, the middle term of $\text{IPC}\le \min (\text{Window-limited ILP},\text{Execution width},\text{Critical-path-limited ILP}).$ This is the flip side of L3.2, where the critical path was the binding limit.

• (a) Critical path. The 26-deep RAW chain forces $\ge 26$ cycles no matter how many ports or how big the window — you cannot outrun your own dependencies.
• (b) Window. Independent work exists and ports are plentiful, but you can only see 8 instructions at a time, so you can never keep 4 ports fed for long. Enlarge the window and IPC rises.
• (c) Execution width. Window (500) and independence are both ample, so neither of those binds. The limiting term is the 2 ports: at most 2 adds can start per cycle, so 1000 independent adds take $1000/2=500$ cycles. Adding more ports would speed it up; a bigger window would not.

False dependencies removed by renaming are ::: WAR and WAW (not RAW) Commit order in an OoOE machine is ::: strictly in program order, via the ROB The hard floor on completion time with infinite resources is set by ::: the critical path (longest true-dependency chain) Window needed to hide a 100-cycle miss at 4 commits/cycle is about ::: 400 in-flight instructions Speedup of L3.1 in-order vs OoOE (unlimited ports) ::: 6/4 = 1.5×