Same names, no conflicts: unrolling, renaming and scheduling

Two kinds of dependence, and only one of them carries a value

Lesson 7 sorted the ways two instructions collide into three kinds. A true dependence (RAW) carries a value from a producer to a consumer. An anti-dependence (WAR) and an output dependence (WAW) carry nothing: the two instructions merely use the same register name. Where the names come from is the first line of these pages (p. 186): name dependences "are constraints imposed by the limited number of registers visible in the Instruction Set Architecture" — thirty-two floating-point names, reused in every iteration of every loop.

The running example of pages 188–193 walks an array downwards and multiplies each element by the scalar in F2. R1 points at the current element; the notes' walkthrough starts it at 80.

I0  LOOP: LD    F0, 0(R1)      ; F0 ← M[R1]
I1        FMUL  F4, F0, F2     ; F2: the scalar
I2        SD    F4, 0(R1)      ; M[R1] ← F4
I3        SUBI  R1, R1, 8      ; 8 bytes down
I4        BNE   R1, R2, LOOP   ; R2 = 0

Exercise 1 of every paper of 2024–2026 opens with a table for exactly this: one row per instruction (I#, TYPE OF INSTRUCTION) and a column ANALYSIS OF DEPENDENCES listing 1. its true data dependences ("with I# for Fx"), 2. its anti-dependences, 3. its output dependences — inside one iteration. For this loop:

What the exam table leaves out is the part this lesson lives on: the dependences between iterations. The next iteration writes F0 and F4 again and reads the R1 that this iteration's SUBI produced. A dependence that crosses iterations is loop-carried; page 188 lists part of the inventory, the complete one is below.

Read the two tables together. Inside an iteration one chain of values runs LD → FMUL → SD, plus SUBI → BNE. Between iterations the only value that travels is R1 — one subtraction per element. Everything else that crosses the boundary is a name: F0 written by both loads, F4 by both multiplies, F0 read by this FMUL before the next LD overwrites it, F4 read by this SD before the next FMUL overwrites it. Those four arcs chain iteration i + 1 to iteration i only because both iterations are spelled with the same two registers.

The exam asks what renaming is for: the June 2026 theory question lists "5. Dynamic Register Renaming" among the techniques whose "main concepts and benefits" you explain. The benefits are the notes' three ticks (p. 187): instructions that write the "same" architectural register can execute out of order, independent loop iterations can run concurrently, false dependences disappear. The cost depends on who renames: fresh ISA registers and longer code for the compiler, tag-matching hardware and bus bandwidth for Tomasulo.

WAR and WAW are name dependences born of a small register file; renaming deletes them and leaves the true dependences — the only ones that carry values — exactly where they were.

Unrolling: pay the overhead once per four elements

The loop spends two of its five instructions, SUBI and BNE, on nothing but getting to the next element. Loop unrolling is the compiler's answer: copy the body u times into one straight-line block, fold the addresses of the copies into the displacements, and keep one index update and one branch for the whole block. The notes unroll by four (p. 190):

LOOP: LD    F0, 0(R1)
      FMUL  F4, F0, F2
      SD    F4, 0(R1)
      LD    F6, -8(R1)        ; copy 2: fresh registers F6, F8
      FMUL  F8, F6, F2
      SD    F8, -8(R1)
      LD    F10, -16(R1)      ; copy 3: F10, F12
      FMUL  F12, F10, F2
      SD    F12, -16(R1)
      LD    F14, -24(R1)      ; copy 4: F14, F16
      FMUL  F16, F14, F2
      SD    F16, -24(R1)
      SUBI  R1, R1, 32        ; four elements of 8 bytes
      BNE   R1, R2, LOOP

Three things to notice. First, the three intermediate SUBI/BNE pairs are gone: fourteen instructions do the work of twenty. Second, every copy got its own registers, and that is not decoration: written with F0 and F4 four times, the copies would carry the four arcs of Fig. 1 between consecutive copies, and no later load could move above an earlier multiply. Unrolling without renaming replicates the name dependences. Third, F2 is only read, so it needs no copy: only the registers a copy writes are renamed, two for each of the three extra copies, six in all.

The notes list the benefits (p. 190): more independent work, the branch and the index update paid once per four elements, several functional units kept busy, a block the compiler can reschedule. The costs mirror them: longer code (fourteen static instructions instead of five, more instruction-cache pressure), a fuller register file, and a remainder loop of the original body when the number of elements is not a multiple of u. With R1 = 80 the array has ten elements, and the listing above would run R1 through 48, 16, −16 … without ever meeting R2 = 0.

Counting: the midterm's loop

The midterm of 5 May 2025 (notes pp. 534–537) turned this into a counting exercise on a loop that adds two arrays element by element; R1 and R2 start at 0, R3 at 400.

LOOP: LD    F2, 0(R1)
      LD    F4, 0(R2)
      FADD  F6, F2, F4
      SD    F6, 0(R1)
      ADDUI R1, R1, 4
      ADDUI R2, R2, 4
      BNE   R1, R3, LOOP

Four of the seven instructions do useful work (two loads, one add, one store); three are loop overhead (two pointer increments, one branch) — the paper of 11 February 2025 (notes p. 567) asks for the same split as "control vs datapath instructions". R1 runs from 0 to 400 in steps of 4: N = 100 iterations, 700 instructions, 100 branches. Unrolled by u, the useful part is copied u times and the overhead stays three, with the increments scaled to 4u (Fig. 2).

In symbols, for any loop the exam invents: N is the trip count, w the useful and o the overhead instructions per iteration, u the unrolling factor and ρ the registers one copy writes.

The midterm's question "how much is the global instruction count decrease?" has a closed form worth deriving, because its limit says what unrolling can never do.

1. The original loop executes the body N times:

   \[ IC_1 = N\,(w + o) = 100 \cdot 7 = 700 . \]

2. Unrolled by u, with u dividing N, there are N/u iterations of u w + o instructions; the useful part stays N w, the overhead is divided by u:

   \[ IC_u = \frac{N}{u}(u\,w + o) = N\,w + \frac{N\,o}{u} \] \[ IC_4 = 400 + \frac{300}{4} = 475 . \]

3. Subtract: the useful work cancels, only overhead is saved:

   \[ IC_1 - IC_u = N\,o\left(1 - \frac{1}{u}\right) \] \[ IC_1 - IC_4 = 300 \cdot 0.75 = 225 . \]

4. Divide by the original count:

   \[ \frac{IC_1 - IC_u}{IC_1} = \frac{o\,(1 - 1/u)}{w + o} \] \[ \frac{IC_1 - IC_4}{IC_1} = \frac{2.25}{7} = 32.14\,\% . \]

5. Let u grow without bound. The factor 1 − 1/u tends to 1, so the saving tends to

   \[ \frac{o}{w + o} = \frac{3}{7} = 42.9\,\% \]

   — the fraction of the original loop that was overhead. Unrolling can approach it and never pass it: the 400 useful instructions are not negotiable.

The table is the model answer, recomputed by the readers from the notes' solution:

The last question, "what is the best unrolling factor between 2 and 4?": 4 — overhead per element 0.75 instead of 1.5, 25 branches instead of 50 — provided the twelve live floating-point values fit in the register file and the longer body in the instruction cache; otherwise 2 is safer. The notes get the trade-off right and the mechanism wrong:

Unrolling by u divides the overhead by u and touches nothing else: saving = o(1 − 1/u)/(w + o), never more than o/(w + o); the price is (u − 1)ρ registers, a body about u times longer and a remainder loop.

Scheduling: loads first, multiplies next, stores last

Unrolling bought fewer instructions per element, but hardly any cycles: in the listing's order every copy still waits inside itself — the multiply for its load, the store for its multiply. The notes give no cycle counts here, so the lesson takes the model of Hennessy and Patterson (5th edition, §3.2), where this example comes from (with ADD.D instead of a multiply; the latencies are those of any FP operation): a single-issue, in-order pipeline where a consumer waits a fixed number of stall cycles after its producer.

On this machine the original loop takes 9 cycles per element: LD, stall, FMUL, stall, stall, SD, SUBI, stall, BNE — in the formula sheet's symbols m = 5 instructions and k = 4 stalls per iteration, \(CPI_{AS} = (m + k)/m = 1.8\). In the notes' unrolled order it takes 27 cycles for four elements, 6.75 per element: the overhead and its stall are paid once, but the twelve stalls inside the copies remain — no renaming shortens a latency. What hides latencies is code scheduling: reorder the instructions so that independent work fills the waiting cycles. The notes' recipe (p. 191): group independent instructions, delay each dependent one just enough to satisfy its true dependence, hide long latencies with useful work. On the unrolled, renamed body it gives the textbook's order — four loads, four multiplies, the stores, and the index update slipped in before the last two stores so that the branch finds R1 ready:

LOOP: LD    F0, 0(R1)
      LD    F6, -8(R1)
      LD    F10, -16(R1)
      LD    F14, -24(R1)
      FMUL  F4, F0, F2
      FMUL  F8, F6, F2
      FMUL  F12, F10, F2
      FMUL  F16, F14, F2
      SD    F4, 0(R1)
      SD    F8, -8(R1)
      SUBI  R1, R1, 32
      SD    F12, 16(R1)       ; was -16(R1): R1 is 32 lower now
      SD    F16, 8(R1)        ; was -24(R1)
      BNE   R1, R2, LOOP

Fourteen instructions, fourteen cycles, no stall (m = 14, k = 0): 3.5 cycles per element, the number of the hook. Three instructions sit between each LD and its FMUL (one stall cycle was needed), at least three between each FMUL and its SD (two were needed), two between SUBI and BNE (one was needed). Now look at the two stores below SUBI: they moved past the instruction that changes their base register, so the fourth element, at R1 − 24 before the update, sits at R1 + 8 after it (Fig. 3).

That is the slip of the hook. The notes' scheduled listing (pp. 191–192) puts the fourth store after the branch, in a delay slot, with its old displacement:

Stalls are latencies, and only reordering hides them: unrolling supplies independent work, renaming makes it movable, scheduling moves it — loads first, FP operations next, stores last, and every access below the index update gets its displacement corrected.

What Tomasulo does with all this: Table 20

Page 193 asks how much of the three moves a dynamically scheduled processor makes by itself, at run time, on the unchanged five-instruction loop. The answer is two of the three, through three mechanisms.

First, implicit renaming through the reservation stations. At issue, an operand that is ready is copied into the station as a value; one that is not becomes the tag of the station or buffer that will produce it, and the register file records for each register only the tag of its latest writer. Two iterations that both write F0 are two different tags — Load1 and Load2 — so the WAR and WAW arcs of Fig. 1 never form. Second, each instruction gets its own reservation station: the LD, FMUL and SD of the next iteration enter fresh stations while those of the current one still wait, so several iterations are active at once without copying the code — the notes' dynamic loop unrolling effect. Third, several functional units and branch prediction: the instances need units to execute on, and issue must go past the BNE before it is resolved, otherwise the next iteration waits for the branch. The notes' sentence for it: "instruction issuing moves faster than control flow".

The notes sum it up in Table 20 (p. 192), the cleanest answer to "compare static and dynamic approaches" you can write at the exam:

Why "no"? Unrolling transforms the program text, and a processor executes the text it is given, issuing each instruction of each iteration once. What the hardware reproduces is the effect — with fresh tags per instance, several iterations proceed at once. What it cannot reproduce is the other half of the gain: every SUBI and BNE is still fetched, issued and executed, five instructions per element instead of 3.5. The open question likes to hear both sides:

One word of the third mechanism needs care, because the June 2026 question keeps "1. Dynamic Instruction Scheduling", "2. Dynamic branch prediction and speculative execution" and "7. Reorder Buffer" as separate items:

The hook's three moves are the compiler's; the hardware does two of them live and leaves the third to the program text — which is why the exam asks both: the midterm counts an unrolled loop, the papers' Tomasulo table runs one that was never unrolled.

Tomasulo renames with tags and schedules by operand availability, at run time and on unchanged code; it never unrolls — it overlaps iterations, which needs a station per instance, several units and a predicted branch, and without a reorder buffer it can predict but not undo.