Same loop, three shapes: unrolling, software pipelining and betting on the hot path

Unrolling, counted cycle by cycle

A machine that issues several operations per cycle is only as fast as the independent operations it is offered, and one iteration of a short loop offers almost none: every instruction waits for the one before it. The compiler's oldest remedy is loop unrolling: copy the body u times into one straight-line block, fold the addresses of the copies into the displacements, and keep a single index update and a single branch. Lesson 15 counted what that saves in instructions — N/u iterations of u·w + o instructions, (u − 1)·ρ extra registers. Here you count what it buys in cycles, on the notes' own example (p. 285), x[i] = x[i] + s:

LOOP: LD    F0, 0(R1)  ; F0 ← x[i]
      FADD  F4, F0, F2 ; F2 = s
      SD    F4, 0(R1)  ; x[i] ← F4
      SUBI  R1, R1, 8  ; i ← i − 1
      BNE   R1, R2, LOOP

The notes give three numbers for this loop — 10 cycles per iteration, 16 for four iterations once unrolled and renamed, efficiency 87.5 % — but not the machine they were counted on. The first is Hennessy and Patterson's classic count for this very loop (third edition), on a single-issue pipeline whose branch has one delay slot; the other two follow from the same rules:

Read the second column first: five instructions, three data stalls, one stall before the branch and an empty delay slot — 10 cycles, half of them wasted. Now copy the body four times in the order of the listing, with F0 and F4 reused. Every copy brings its stalls along: 6 cycles per copy, plus 4 for SUBI, stall, BNE and the slot, makes 28 cycles, 7 per element. Unrolling alone buys little.

What makes the third column possible is renaming. Once each copy has its own registers — F0/F4, F6/F8, F10/F12, F14/F16 — the compiler may regroup: four loads, four adds, four stores. Every consumer now stands four instructions after its producer, more than any latency asks, so the data stalls vanish; left are the stall before BNE and the empty delay slot: 14 instructions in 16 cycles. The fourth column fills both holes with the last two stores, whose displacements grow by 32 because SUBI has already moved R1 (the offset rule of lesson 15): four elements in 14 cycles.

On a 3-issue VLIW the regrouped body pays off more: the four copies are independent of one another, so loads, adds and stores of different copies share bundles — 13 cycles for four elements against 10 for one (section 4). The price is the one lesson 15 named: eight FP registers instead of two, fourteen instructions instead of five (a bigger instruction-cache footprint), and a remainder loop when the trip count is not a multiple of 4.

Unrolling buys independent operations; renaming is what lets the scheduler use them; registers and code size pay for both.

Software pipelining: one body, three elements in flight

Unrolling makes the body bigger so that the scheduler finds independent work inside it. Software pipelining finds independent work without making anything bigger: it takes it from other iterations. Picture three people washing up. In every minute the stacker puts away plate i while the dryer dries plate i + 1 and the washer starts plate i + 2: three plates in progress, one leaving every minute. In the loop, LD washes, FADD dries, SD stacks — and the minute is one pass of the loop body, however many cycles that pass takes.

From here on the loop walks upwards, as the papers' loops do — ADDUI R1, R1, 8 instead of SUBI — and the construction takes five steps.

1. Unroll symbolically. Write iterations i, i + 1 and i + 2 under each other, each one step later than the one above: LD, FADD, SD of iteration i in steps 1–3, of i + 1 in steps 2–4, of i + 2 in steps 3–5.

2. Look at step 3. It holds the SD of iteration i, the FADD of i + 1 and the LD of i + 2 — one instruction from each, and none waits for another, because each consumes what an earlier step produced. That column becomes the loop body.

3. Write the body in that order, SD first. Each instruction must read its register before the next one overwrites it: SD reads the F4 that FADD is about to replace, FADD reads the F0 that LD is about to replace. Both are WAR dependences, and on the papers' VLIW a writer may share the cycle of its reader. No register was added: F0 and F4 serve three elements in turn.

4. Fix the offsets. R1 moves by 8 once per body. The SD works on the element R1 points at, 0(R1); the LD works two elements ahead:

   \[ \text{LD offset} = 2 \times 8 = 16 . \]

5. Fill and drain. Before the first body, elements 0 and 1 must already be under way: LD x[0], FADD x[0], LD x[1] — the prologue. After the last body, elements n − 2 and n − 1 still owe their last stages: SD x[n−2], FADD x[n−1], SD x[n−1] — the epilogue. The body itself runs n − 2 times, so the exit test compares R1 with R5, the address of x[n−2].

START_UP:
  LD    F0, 0(R1)       ; x[0]
  FADD  F4, F0, F2      ; x[0]
  LD    F0, 8(R1)       ; x[1]
SP_LOOP:
  SD    F4, 0(R1)       ; x[i]
  FADD  F4, F0, F2      ; x[i+1]
  LD    F0, 16(R1)      ; x[i+2]
  ADDUI R1, R1, 8
  BNE   R1, R5, SP_LOOP
FINISH_UP:
  SD    F4, 0(R1)       ; x[n-2]
  FADD  F4, F0, F2      ; x[n-1]
  SD    F4, 8(R1)       ; x[n-1]

How fast is it? Every execution of the body finishes one element — the SD at its top stores a completed result. The cycles between the starts of two consecutive bodies are the initiation interval, II, simply the length of the body's schedule: 5 cycles on the papers' VLIW (section 4), so one element every 5 cycles against 10 for the original loop. Each element now spends three passes between its load and its store, longer than before: only the rate improved, not the time of one element.

Unrolling or software pipelining?

Hennessy and Patterson put it in one line: the two techniques remove different overheads — unrolling the loop-control instructions, software pipelining the time spent below full speed, which an unrolled loop pays at both ends of every unrolled body and a pipelined loop only once. Compilers often do both: unroll a little, then pipeline the unrolled body.

Betting on the hot path: traces, superblocks, predication

Loops are the easy case: their body repeats, so the next iteration is always there to borrow from. Ordinary code is cut into short basic blocks — "only around 4 to 7 instructions are found between branches", the notes say (p. 273) — and a block that short, with its own dependences inside, cannot keep a 3-issue VLIW busy. Global scheduling moves instructions across the branches. Profiling finds the path the program takes most often; the compiler schedules that path as if the branches were not there and pays only when the bet fails.

Trace scheduling (Fisher, 1981) does it in two steps. Trace selection picks the most likely sequence of basic blocks, the trace. Trace compaction then list-schedules the whole trace as if it were one block, moving instructions up and down across the branches inside it — loads first of all, to start their long latency early.

Moving an instruction across a branch makes it run where the original program did not run it, or stop running where it did. Three moves recur, and the sandbox below shows each on a four-block loop:

• Up above a branch — speculation. The instruction now runs on the off-trace path too: allowed without repair only if its result is dead there and it does no harm — no store, no exception the original program would not raise.
• Down below a branch, into the on-trace block. The off-trace path no longer executes it, so a copy must go on the exit path: compensation code.
• Up above a join, where an off-trace block enters the trace from the side. The entering path would skip the instruction, so a copy goes on that path.

Side entrances make trace scheduling expensive: every move above one costs a copy on every entering path. A superblock (Hwu et al., 1993) is a trace with a single entry and any number of exits, obtained by tail duplication: the part of the trace below a side entrance is copied, and the off-trace path jumps to the copy. Repairs are then needed only at the exits, outside the superblock; the price is the duplicated tail.

The notes stop here. Hennessy and Patterson add a fourth tool, which removes the branch instead of scheduling around it — background, not in the notes. A predicated instruction names a one-bit predicate register: it is always issued, but writes its result only when the predicate is true. If-conversion turns the diamond of the sandbox into one block: a compare sets P1 and its complement P2, then (P2) FADD and (P1) FMUL follow without a branch. The control dependence has become a data dependence on a predicate: a bigger block, nothing to mispredict, nothing to compensate. The cost: both arms occupy issue slots on every pass, whichever way the condition goes.

How the papers ask it: LOOP1 against LOOP2, and the midterm's SP_LOOP

Every paper of 2024–2026 has a 5-point VLIW exercise, and two of them schedule a software-pipelined loop. The rules are those of lesson 20: latency 3 for Memory and FP, 1 from the Integer unit to the next Int/FP/L/S instruction and 2 to a branch; one delay slot after the branch, counted; a WAR writer may share the cycle of the last reader of its register ("in the Register File, it is possible to read and write at the same address at the same clock cycle"); no NOPs written. In the solved papers the "critical path for a single iteration" is the schedule length including the delay slot, CPI = cycles / instructions, code efficiency = IC / (cycles × issue width).

The 22 June 2026 paper asks for both loops of the hook, with C1 already filled in, and then for the four metrics of each and the speed-up in CPI:

LOOP1: LD    F2, 0(R1)
       FADD  F6, F2, F2
       SD    F6, 0(R1)
       ADDUI R1, R1, 4
       BNE   R1, R3, LOOP1

LOOP2: SD    F6, 0(R2)
       FADD  F6, F2, F2
       LD    F2, 0(R2)
       ADDUI R2, R2, 4
       BNE   R2, R3, LOOP2

Add the third shape. LOOP1 unrolled by four with renamed registers schedules on the same machine in 13 cycles: four loads in C1–C4, four adds in C4–C7, four stores in C7–C10 with ADDUI in C10, BNE in C12 and the delay slot in C13.

The midterm of 5 May 2025: backwards, then forwards

Exercise 1 of the 2025 midterm (notes pp. 506–512) runs the construction backwards. Part A gives a two-array software-pipelined loop and asks for the original:

START_UP:
  LD    F0, 0(R1)
  LD    F2, 0(R2)
  FADD  F4, F0, F0
  FADD  F6, F2, F2
  LD    F0, 8(R1)
  LD    F2, 8(R2)
SP_LOOP:
  SD    F4, 0(R1)       ; I1
  SD    F6, 0(R2)       ; I2
  FADD  F4, F0, F0      ; I3
  FADD  F6, F2, F2      ; I4
  LD    F0, 16(R1)      ; I5
  LD    F2, 16(R2)      ; I6
  ADDUI R1, R1, 8       ; I7
  ADDUI R2, R2, 8       ; I8
  ADD   R3, R2, R1      ; I9
  BNE   R3, R4, SP_LOOP ; I10

Follow one element. LD F0, 16(R1) loads it; one pass later, when R1 has moved by 8, FADD F4, F0, F0 doubles it; one pass after that, when R1 has moved by 16, SD F4, 0(R1) stores it — at the address it was loaded from. Put the three stages of one element back into one pass, in natural order and with offset 0, and keep the loop control. START_UP and FINISH_UP disappear:

LOOP:  LD    F0, 0(R1)
       LD    F2, 0(R2)
       FADD  F4, F0, F0
       FADD  F6, F2, F2
       SD    F4, 0(R1)
       SD    F6, 0(R2)
       ADDUI R1, R1, 8
       ADDUI R2, R2, 8
       ADD   R3, R2, R1
       BNE   R3, R4, LOOP

Part B schedules SP_LOOP on the 3-issue VLIW. Its only true dependences are in the tail ADDUI → ADD → BNE.

1. C1–C2: each SD shares its cycle with the FADD that rewrites its register (WAR: the SD reads the old F4 or F6). The single memory unit pushes SD F6 to C2.
2. C3–C4: the loads take the memory unit in turn. ADDUI R1 may not precede the last reader of the old R1, LD F0 in C3, so it shares C3 with it; ADDUI R2 shares C4 with LD F2. (The notes say ADDUI starts "when the first SD store finishes": that the store's 3 cycles end in C3 is a coincidence.)
3. C5: ADD R3, one cycle after ADDUI R2. C6 stays empty because the text gives the Integer ALU a "2 cycle latency to next Branch": the branch reads R3 in ID, so a BNE in C6 would still see the old value. BNE goes to C7, the delay slot to C8. In the exam, give the stated latency as the reason.

Eight cycles: CPI = 8/10 = 0.8, FP ops per cycle = 2/8 = 0.25, code efficiency = 10/(8 × 3) = 0.417. The original loop of Part A, scheduled by the same rules, needs 12 cycles (LD C1 and C2, FADD C4 and C5, SD with ADDUI in C7 and C8, ADD C9, BNE C11, delay slot C12): CPI 1.2, a speed-up of 1.5.

Back to the puzzle of the hook. LOOP2's SD stores the F6 that the previous pass's FADD computed, and its FADD doubles the F2 that the previous pass's LD loaded: one pass holds three different elements (Fig. 1), linked only by anti-dependences that cost nothing on the papers' machine (Fig. 2). The 3 + 3 cycles of waiting have not disappeared; they now elapse between one pass and the next, while other elements are worked on. What remains inside a pass — SD with FADD, the LD behind them on the single memory unit, the branch 2 cycles after ADDUI, the delay slot — is 5 cycles: one element out of the loop every 5 cycles.