Register renaming: Exercises — Hardware deep dive

This is the self-testing companion to Register renaming. Work each problem before opening its solution. Problems climb five rungs: L1 Recognition → L2 Application → L3 Analysis → L4 Synthesis → L5 Mastery. Every symbol used here is built in the parent note; if a term feels new, it is re-anchored in the intuition boxes below.

Recall the three hazard names so the questions read cleanly:

RAW (Read-After-Write) = true dependency — B genuinely needs A's value.
WAR (Write-After-Read) = false — B reuses a name A was still reading.
WAW (Write-After-Write) = false — two writers to one name; only the last matters.

Renaming kills WAR and WAW; it cannot kill RAW (see Instruction-Level Parallelism (ILP)).

Level 1 — Recognition

Exercise 1.1

Classify each dependency between the instruction pairs below.

I1: ADD R1, R2, R3
I2: SUB R4, R1, R5
I3: MUL R1, R6, R7

(a) I1→I2 on R1 (b) I2→I3 on R1 (c) I1→I3 on R1.

Recall Solution

(a) I1 writes R1, I2 reads R1 → RAW (true). I2 needs I1's result. (b) I2 reads R1, I3 writes R1 → WAR (false). I3 just reuses the name. (c) I1 writes R1, I3 writes R1 → WAW (false). Only the later write survives architecturally. Renaming removes (b) and (c); (a) stays.

Exercise 1.2

True or false: "Register renaming increases the number of architectural registers the programmer can name."

Recall Solution

False. The ISA stays fixed (e.g. 16 named registers). Renaming adds physical lockers behind the scenes — invisible to software. See the parent's [!mistake] "Why not just add architectural registers?"

Exercise 1.3

Which structure answers the question "where does the current value of R2 live right now?" — RAT, ROB, or Free list?

Recall Solution

The RAT (Register Alias Table). The ROB tracks in-flight instructions for commit/recovery; the free list holds unused physical registers.

Level 2 — Application

Use 8 architectural registers with initial RAT Ri → P(i+9) (so R1→P10, R2→P11, …, R9→P18) and free list [P0, P1, P2, P3, …] popped in order.

Exercise 2.1

Rename this pair. Give sources, allocated destination, RAT update, and ROB entry for each.

I1: ADD R2, R3, R4
I2: ADD R5, R2, R2

Recall Solution

I1: ADD R2, R3, R4

Sources: RAT[R3]=P12, RAT[R4]=P13.
Allocate: pop P0.
Execute: P0 ← P12 + P13.
RAT update: R2 → P0.
ROB[0] = {R2, old=P11, new=P0}.

I2: ADD R5, R2, R2

Sources: RAT[R2]=P0 (I1 just renamed it — this is a RAW, correctly captured), RAT[R2]=P0 again.
Allocate: pop P1.
Execute: P1 ← P0 + P0.
RAT update: R5 → P1.
ROB[1] = {R5, old=P14, new=P1}.

Exercise 2.2

After committing I1 and I2 above (in order), which physical registers return to the free list?

Recall Solution

At commit each instruction frees the old physical register that its architectural destination previously used.

Commit I1: free R2's old locker P11.
Commit I2: free R5's old locker P14. Freed set = {P11, P14}. (P0 and P1 stay busy — they hold the live R2 and R5.)

Exercise 2.3

For x86-64 with $N_{a r c h} = 16$ architectural registers and a $N_{R O B} = 224$ -entry reorder buffer, compute the minimum physical register file size from the parent formula $N_{p h y s} \geq N_{a r c h} + N_{R O B} .$

Recall Solution

$N_{p h y s} \geq 16 + 224 = 240$ . Designers round up to 256 (a power of 2) so the physical register index is exactly 8 bits.

Level 3 — Analysis

Exercise 3.1

Given the parent's 4-instruction sequence, mark on the timeline which waits are true (survive renaming) and which are false (eliminated).

I1: ADD R1, R2, R3
I2: MUL R4, R1, R5
I3: ADD R1, R6, R7
I4: SUB R8, R1, R9

Recall Solution

I1→I2 on R1: RAW true → I2 waits for I1. Survives.
I2→I3 on R1: WAR false → eliminated (I2 reads P0, I3 writes P2).
I1→I3 on R1: WAW false → eliminated (different lockers P0 vs P2).
I3→I4 on R1: RAW true → I4 waits for I3. Survives. So only two edges remain: I1→I2 and I3→I4. These form two independent chains that run in parallel — exactly why the parent's timeline drops 9 cycles to 6.

Exercise 3.2

An in-order machine takes 9 cycles for that sequence; the renamed out-of-order machine takes 6. Compute the speedup.

Recall Solution

$Speedup = \frac{9}{6} = 1.5 \times .$ The gain comes purely from letting the two RAW chains overlap; renaming supplied the legal permission by removing the false edges.

Exercise 3.3

Suppose the free list is empty when decode reaches an instruction that writes a register. What happens, and what is this condition called?

Recall Solution

Decode stalls — the instruction cannot be renamed because no fresh physical register can be allocated. The pipeline waits until an older instruction commits and pushes its old register back onto the free list. This condition is register pressure. It is a structural limit on Out-of-Order Execution, not a data dependency.

Level 4 — Synthesis

Exercise 4.1

You are designing a core. You know each in-flight instruction that writes a register consumes one physical register that stays allocated from decode until commit. You have $N_{a r c h} = 32$ architectural registers and want to keep at least $N_{R O B} = 192$ instructions in flight, of which historically ~75% write a register. Give (a) the safe minimum $N_{p h y s}$ that never stalls even if every ROB entry writes, and (b) a leaner estimate if only 75% write.

Recall Solution

(a) Worst case (every in-flight instruction writes): $N_{p h y s} = N_{a r c h} + N_{R O B} = 32 + 192 = 224.$ This guarantees no stall due to register exhaustion regardless of instruction mix.

(b) Provisioning for 75% writers ( $192 \times 0.75 = 144$ in-flight allocations): $N_{p h y s} \approx 32 + 144 = 176.$ Leaner, cheaper silicon — but if a code region has more than 75% register-writing instructions, decode will stall. Real designs pick a point between 176 and 224 based on workload traces; 224 is the no-stall guarantee.

Exercise 4.2

Combine renaming with Branch Prediction. A mispredicted branch means every instruction decoded after the branch was speculative and must be squashed. Using the ROB records {Rdest, old, new}, describe how the RAT and free list are restored to the pre-speculation state.

Recall Solution

Walk the ROB backwards from the tail down to the branch, and for each squashed entry {Rdest, old, new}:

RAT[Rdest] ← old — restore the mapping that existed before this (now-cancelled) write.
Free list.push(new) — the fresh locker was allocated only for a speculative instruction that will never commit, so reclaim it. After processing all entries above the branch, the RAT and free list are byte-for-byte what they were when the branch was decoded. This is precisely why step 4 of the parent's algorithm records the old mapping: it is the undo log. Committed instructions (below the branch) are untouched — recovery is precise.

Level 5 — Mastery

Exercise 5.1

Renaming interacts with Tomasulo's Algorithm and Scoreboarding. Tomasulo effectively renames via reservation-station tags; a physical-register-file scheme renames via the RAT. For a machine with 16 architectural registers and 8 reservation stations vs. one with 16 architectural + 96 physical registers, which can hold more independent renamings of the same architectural register live at once, and why?

Recall Solution

Count the distinct rename slots.

Tomasulo (RS-tag renaming): the number of simultaneous renamings is bounded by the number of reservation-station entries = 8 (each RS tag is a temporary name). Values live inside RS entries until they broadcast.
Physical register file: the number of simultaneous renamings is bounded by the free physical registers, up to $96 - 16 = 80$ non-committed lockers.

So the physical-register-file scheme holds far more live renamings ( $\leq 80$ vs $\leq 8$ ). This is exactly why modern superscalar cores (see Superscalar Execution) moved from RS-based value storage to large physical register files: more in-flight renamings ⇒ deeper reordering window ⇒ more exploitable ILP.

Exercise 5.2

Consider memory operations. Renaming handles register hazards, but two stores/loads to the same address create memory hazards. Why can register renaming NOT resolve these, and what mechanism must take over?

Recall Solution

Register renaming works because architectural register names are known at decode — R1 is literally in the instruction encoding, so the hardware can hand it a fresh locker immediately. Memory addresses are computed at execute time (e.g. [R2 + offset]), so at decode the hardware does not yet know whether two memory instructions alias. It cannot pre-assign non-conflicting "lockers" to unknown addresses. This is resolved by Memory Disambiguation — a load/store queue that compares addresses after they are computed and enforces (or speculates and later checks) the correct ordering.

Exercise 5.3

A core has $N_{a r c h} = 16$ , physical file $N_{p h y s} = 128$ . At a given instant 16 physical registers hold committed architectural state and 40 are allocated to in-flight (uncommitted) writers. (a) How many are on the free list? (b) The ROB then fills with 30 more register-writing instructions before any commit. Does decode stall? (c) What is the maximum number of additional register-writing instructions that could be renamed before a stall, from the original instant?

Recall Solution

(a) Free = total − committed − in-flight = $128 - 16 - 40 = 72$ . (b) 30 new writers need 30 lockers; free list has 72 ≥ 30, so no stall. Free list drops to $72 - 30 = 42$ . (c) From the original instant, decode can rename until the free list is empty: 72 additional register-writing instructions (assuming no commits free anything in between). The 73rd write-instruction would find an empty free list and stall — register pressure.

Recall Self-test one-liners (cover the answer, recall it)

RAT answers what question ::: Where the current value of an architectural register physically lives right now. At commit, which physical register is freed ::: The OLD one the architectural destination previously mapped to. Which hazards renaming eliminates ::: WAR and WAW (false); never RAW. $N_{p h y s}$ safe minimum ::: $N_{a r c h} + N_{R O B}$ . Cause of a decode stall in renaming ::: Empty free list = register pressure. How a mispredict restores the RAT ::: Replay ROB old-mappings backward and push each new register back to the free list. Why renaming can't fix memory hazards ::: Addresses are unknown at decode; disambiguation happens at execute.

Connections

Parent: Register renaming · Hinglish: 5.3.04 Register renaming (Hinglish) See also: Instruction-Level Parallelism (ILP) · Out-of-Order Execution · Tomasulo's Algorithm · Reorder Buffer (ROB) · Scoreboarding · Memory Disambiguation · Superscalar Execution · Branch Prediction