VLIW architectures: Exercises — Hardware deep dive

Before we begin, one picture fixes the vocabulary we will reuse in every solution. It belongs to the whole page, but is referenced most directly by Level 1.

What the figure above shows (used by Level 1): four boxes in a row — the four slots of one VLIW instruction word — with a bracket over all of them saying "one instruction word = one cycle." The memory slot (Slot 2) is drawn in red because it is the single port that becomes the bottleneck in almost every problem on this page. Whenever a solution says "only one memory op per cycle," this is the picture to hold in your head: the red box can be filled by at most one load or store each row.

Levels 2–5 lean on a handful of loop-scheduling terms. We define all of them once, here, in plain words, before any of them is used in a problem.

Definition Loop-scheduling vocabulary (read before Level 2)

When a loop is software-pipelined, the compiler starts a new iteration every few cycles even before the previous one finishes, like runners setting off one after another on a track. The key numbers are:

Iteration — one pass through the loop body (one value of i).
II (Initiation Interval) — the number of cycles between launching one iteration and launching the next. Smaller II = iterations start more often = faster loop. This is the single most important loop-speed number on the page.
Steady state — the middle stretch of a pipelined loop after the pipeline has filled up and before it drains, where every cycle looks the same and a new iteration launches exactly every II cycles. "Steady-state II" just means the II measured in that repeating middle region (ignoring the fill/drain edges). It is the number that governs the loop's long-run speed.
MII (Minimum Initiation Interval), written $II_{m i n}$ — the smallest legal II. You cannot go faster than this no matter how clever the schedule; it is a hard floor set by the hardware and the code.
$u_{r}$ ("uses of resource $r$ ") — how many operations in one loop iteration need resource $r$ . Example: if the body does 4 loads/stores, then $u_{mem} = 4$ .
$c_{r}$ ("copies of resource $r$ ") — how many hardware units of that resource exist. Our machine has $c_{mem} = 1$ (one memory port), $c_{ALU} = 2$ (two integer ALUs).
ResMII (Resource-constrained MII) — the floor on II coming from not enough hardware. If a resource is used $u_{r}$ times per iteration but only $c_{r}$ copies exist, those uses must be spread over at least $⌈ u_{r} / c_{r} ⌉$ cycles.
Recurrence / dependency cycle $C$ — a loop where a value feeds back into itself across iterations (e.g. acc = acc + x, where this iteration's acc needs last iteration's acc).
Lat(C) ("latency of cycle $C$ ") — total cycles to travel once around that feedback loop (sum of the latencies of the operations on it).
Dist(C) ("iteration distance of cycle $C$ ") — how many iterations back the feedback reaches. If this iteration needs a value produced 2 iterations ago, then $Dist (C) = 2$ . It answers "how far apart in iteration-count are the two ends of the dependence?"
RecMII (Recurrence-constrained MII) — the floor on II coming from the algorithm's own feedback, not from hardware.

Definition Data-dependence types (read before Level 4)

When two operations touch the same register, the order between them may or may not matter:

RAW (Read After Write) — a true dependency: op B reads a value that op A must write first (e.g. A1 computes r3, then A2 reads r3). Order cannot be broken — the data genuinely flows A→B. A "RAW chain" is just a string of such true dependencies, one feeding the next.
WAR (Write After Read) — a false (anti-)dependency: B writes a register that A still needs to read first. Caused by name reuse, removable by renaming.
WAW (Write After Write) — a false (output) dependency: A and B both write the same register. Also caused by name reuse, also removable by renaming.

Only RAW forces real ordering. In VLIW the compiler must rename registers to erase the false WAR/WAW dependencies.

Formula The two floors and why we take the MAX

\text{ResMII} = \max_r \left\lceil \frac{u_r}{c_r}\right\rceil, \qquad \text{RecMII} = \max_C \left\lceil \frac{\text{Lat}(C)}{\text{Dist}(C)}\right\rceil.$$ **WHY the maximum, not the sum or the average?** Each floor is a *separate promise the schedule must keep*: - ResMII says "you physically cannot issue these operations faster than the hardware allows." - RecMII says "you physically cannot start an iteration before the data it depends on exists." A legal II must satisfy **both** promises at once. If ResMII = 4 and RecMII = 3, an II of 3 breaks the resource promise (not enough ports), and an II of 4 keeps *both* promises. So the smallest II that keeps every promise is the **larger** of the two — that is exactly what "max" means. It is like the slowest member of a group setting the group's pace: you can only move as fast as your *most* restrictive constraint, never faster. Taking a sum would over-count (the constraints act in parallel, not in sequence), and an average would under-count (letting the schedule violate the tighter one).

Level 1 — Recognition

L1-Q1

A superscalar and a VLIW processor both issue 4 operations per cycle. Which one contains hardware to discover at runtime which operations are independent?

Recall Solution

The superscalar. Its out-of-order engine (wakeup/select, reservation stations, register renaming) finds parallelism in hardware every cycle. VLIW pushes that job to the compiler, so the VLIW hardware just executes the pre-packed word with no runtime dependency checking.

L1-Q2

In our 4-slot machine, how many memory (load/store) operations can a single instruction word contain? Why?

Recall Solution

Exactly one. There is a single memory port (Slot 2). Two loads in one cycle would need two ports the hardware does not have, so the compiler is forbidden from packing them together. (This is exactly the red box in the figure at the top of the page.)

L1-Q3

Fill in the blank: In VLIW, if the compiler cannot find parallel work for a slot, it must place a NOP there.

Recall Solution

A NOP. The slot still exists in the fixed-width word, so idle slots are spelled out explicitly. This is why low-parallelism code wastes bits.

Level 2 — Application

L2-Q1

Our 4-slot machine runs the dependent Fibonacci-style body from the parent note, scheduled as 3 real operations across 3 instruction words. Compute the slot utilisation.

Recall Solution

Total slots used $= 3 instructions \times 4 slots = 12$ . Real operations $= 3$ . $Utilisation = \frac{3}{12} = 0.25 = 25%.$ The chain temp = fib, fib = fib + prev, prev = temp is fully serial, so only one slot per row can ever be busy.

L2-Q2

A loop body needs 6 memory operations and the machine has 1 memory port. Ignoring recurrences, what is the resource-constrained minimum initiation interval $ResMII$ ? (Recall from the vocabulary box: $u_{r}$ = uses per iteration, $c_{r}$ = copies of the resource, and $ResMII = max_{r} ⌈ u_{r} / c_{r} ⌉$ .)

Recall Solution

Here the only busy resource is memory, so $u_{mem} = 6$ (six memory ops per iteration) and $c_{mem} = 1$ (one port): $ResMII = ⌈ \frac{u _{mem}}{c _{mem}} ⌉ = ⌈ \frac{6}{1} ⌉ = 6 cycles per iteration.$ Six memory operations through one port simply take six cycles, no matter how many ALU slots sit idle.

L2-Q3

A VLIW word is 128 bits (4 slots × 32 bits). A 100-operation program compiles to VLIW words that are on average 40% full — meaning each word carries on average $k = 1.6$ real operations, where $k$ is the average number of real (non-NOP) operations packed per instruction word (so $40% \times 4 slots = 1.6$ ). How many VLIW instruction words are emitted, and how many bits of NOP are wasted?

Recall Solution

With $k = 1.6$ real operations per word, words needed $= ⌈ 100/ k ⌉ = ⌈ 100/1.6 ⌉ = ⌈ 62.5 ⌉ = 63$ words. Total slots $= 63 \times 4 = 252$ ; real ops $= 100$ ; NOP slots $= 252 - 100 = 152$ . Wasted bits $= 152 \times 32 = 4864$ bits. More than half the emitted code is NOP — the classic VLIW code-bloat penalty.

Level 3 — Analysis

L3-Q1

Our loop body issues: 4 memory ops, 5 integer ALU ops, 1 branch. Machine: 1 memory port ( $c_{mem} = 1$ ), 2 integer ALUs ( $c_{ALU} = 2$ ), 1 branch/FP unit ( $c_{br} = 1$ ). Find $ResMII$ and name the bottleneck resource.

Recall Solution

Evaluate $⌈ u_{r} / c_{r} ⌉$ per resource ( $u_{r}$ = uses per iteration, $c_{r}$ = copies available):

Memory: $⌈ 4/1 ⌉ = 4$
Integer ALU: $⌈ 5/2 ⌉ = 3$
Branch/FP: $⌈ 1/1 ⌉ = 1$ $ResMII = max (4, 3, 1) = 4 cycles.$ The memory port is the bottleneck. Even though there are more ALU ops in total, the two ALUs share the load, while the one port must serialise all four accesses.

L3-Q2

The same loop has one dependency cycle $C$ : a store-to-load recurrence with total latency $Lat (C) = 6$ cycles spanning $Dist (C) = 2$ iterations — meaning a load in this iteration needs a value that a store produced two iterations earlier, so the feedback reaches back 2 iterations. Combine with L3-Q1 to find the true $II_{m i n}$ .

Recall Solution

Recurrence bound (from the vocabulary box: $Lat (C)$ = cycles to travel once around the feedback loop, $Dist (C)$ = how many iterations back it reaches): $RecMII = ⌈ \frac{Lat ( C )}{Dist ( C )} ⌉ = ⌈ \frac{6}{2} ⌉ = 3.$ Intuition: 6 cycles of work spread across 2 iterations means at least 3 cycles must separate each iteration start. Overall, applying $II_{m i n} = max (ResMII, RecMII)$ : $II_{m i n} = max (ResMII, RecMII) = max (4, 3) = 4 cycles.$ Resources still dominate; the recurrence, at 3, is not the binding constraint here.

The two floors and how they compete are shown below (this figure supports L3-Q2).

What the figure above shows (used by L3-Q2): three bars — the memory ResMII (4), the ALU ResMII (3), and the RecMII (3) — measured in cycles per iteration. The tallest bar (memory, in red) is the one that sets $II_{m i n}$ , exactly because $II_{m i n}$ is the max of all the floors. Pedagogically this is the whole Level-3 idea in one glance: don't average, don't add — find the tallest bar. The red arrow points to that winning bar to hammer home which constraint is binding.

L3-Q3

For the loop of L3-Q1/Q2, if we added a second memory port ( $c_{mem}$ goes from 1 to 2), what would the new $II_{m i n}$ become? What does this reveal?

Recall Solution

New memory bound: $⌈ 4/2 ⌉ = 2$ . Recompute:

Memory: $2$ , ALU: $3$ , Branch: $1$ → new $ResMII = max (2, 3, 1) = 3$ .
$RecMII$ unchanged $= 3$ . $II_{m i n} = max (3, 3) = 3 cycles.$ Adding the port improved things only from 4 to 3. Now the ALU and the recurrence tie as the new limits — you cannot go below 3 without both more ALUs and a shorter dependency cycle. This is the analyst's lesson: relieve one bottleneck and the next one appears.

Level 4 — Synthesis

L4-Q1

Schedule this loop body on the 4-slot machine (1 mem, 2 ALU, 1 br/FP). Assume all latencies are 1 cycle and no cross-iteration recurrence:

L1: r1 = LD a[i]
L2: r2 = LD b[i]
A1: r3 = r1 + r2      (needs L1, L2)
A2: r4 = r3 * 2       (needs A1)
S1: ST c[i] = r4      (needs A2)

Produce a legal single-iteration VLIW schedule and give its cycle count.

Recall Solution

Constraints: one memory op per cycle (so L1, L2, S1 cannot share a cycle); a RAW (Read After Write) chain — a string of true data dependencies where each op reads what the previous wrote — namely L1,L2 → A1 → A2 → S1.

Slot layout:  [ ALU1        | ALU2 | MEMORY   | BR/FP ]
Cycle 1:      [ NOP         | NOP  | LD r1,a  | NOP   ]
Cycle 2:      [ NOP         | NOP  | LD r2,b  | NOP   ]
Cycle 3:      [ ADD r3,r1,r2| NOP  | NOP      | NOP   ]
Cycle 4:      [ MUL r4,r3,2 | NOP  | NOP      | NOP   ]
Cycle 5:      [ NOP         | NOP  | ST c,r4  | NOP   ]

5 cycles. The two loads must be serialised by the single port; the ADD waits for both; MUL waits for ADD; store waits for MUL. Utilisation $= 5/20 = 25%$ — a serial chain does not benefit from wide issue.

L4-Q2

Now software-pipeline the L4-Q1 loop across iterations to raise throughput. The recurrence-free body has $u_{mem} = 3$ (2 loads + 1 store) and $u_{ALU} = 2$ . What is the steady-state $II$ — the II in the repeating middle of the pipelined loop, after fill and before drain (see the vocabulary box) — and what limits it?

Recall Solution

Apply the two floors from the formula box: $ResMII = max (⌈ \frac{u _{mem}}{c _{mem}} ⌉, ⌈ \frac{u _{ALU}}{c _{ALU}} ⌉) = max (⌈ \frac{3}{1} ⌉, ⌈ \frac{2}{2} ⌉) = max (3, 1) = 3.$ With no recurrence, $RecMII = 1$ . Therefore: $II_{m i n} = max (ResMII, RecMII) = max (3, 1) = 3 cycles per iteration.$ So in steady state a new iteration launches every 3 cycles. Even though one iteration takes 5 cycles standalone (from L4-Q1), pipelining lets the memory port stream its 3 accesses per iteration back-to-back while ALU work from earlier iterations hides in the gaps. Throughput improves from $1/5$ to $1/3$ iterations per cycle. The single memory port is what limits it.

L4-Q3

Using $II = 3$ from L4-Q2, how many cycles does the full 100-iteration loop take, if the pipeline prologue (fill) adds a fixed 4 extra cycles before steady state?

Recall Solution

Steady-state cost $= II \times iterations = 3 \times 100 = 300$ cycles. Add prologue: $300 + 4 = 304$ cycles. (Formally, total $\approx prologue + II \cdot N$ for large $N$ ; the prologue is amortised to nearly nothing over 100 iterations.)

Level 5 — Mastery

L5-Q1

A DSP kernel has this dependency cycle: acc = acc + (x[i] * h) where the multiply-add feeds itself every iteration. The multiply-add has latency 3 cycles, and the recurrence spans 1 iteration ( $Dist (C) = 1$ — this iteration's acc needs the immediately previous one). The kernel also issues 2 memory loads per iteration on a 1-port machine. Find $II_{m i n}$ , and explain which bound wins and why it cannot be beaten by adding hardware.

Recall Solution

$ResMII = ⌈ u_{mem} / c_{mem} ⌉ = ⌈ 2/1 ⌉ = 2$ (memory port).
$RecMII = ⌈ Lat (C) / Dist (C)⌉ = ⌈ 3/1 ⌉ = 3$ . $II_{m i n} = max (2, 3) = 3 cycles.$ The recurrence wins. Crucially, adding memory ports or ALUs would drop $ResMII$ but cannot lower $RecMII$ : the accumulator at iteration $i$ genuinely needs the value from iteration $i - 1$ , which takes 3 cycles to produce. This is an algorithmic limit, not a resource limit — no amount of extra silicon removes a true data dependence. (Only restructuring the algorithm — e.g. splitting into partial sums — can shorten the cycle.)

L5-Q2

Compare two schedules of the same loop with $II_{m i n} = 3$ : Schedule A achieves $II = 3$ ; Schedule B achieves $II = 5$ because the compiler failed to rename a register, creating a false WAW dependency in a cycle. Quantify the throughput loss over 300 iterations, and state the one-line fix.

Recall Solution

Schedule A: $3 \times 300 = 900$ cycles.
Schedule B: $5 \times 300 = 1500$ cycles.
Loss: $1500 - 900 = 600$ cycles, i.e. Schedule B is $1500/900 \approx 1.67 \times$ slower. Fix: the compiler must rename the register so the WAW (write-after-write) becomes independent. WAW and WAR are false dependencies (see the data-dependence definition box) — they arise from reusing register names, not from real data flow — and in VLIW the compiler (not hardware) must eliminate them. Renaming restores $II = 3$ .

L5-Q3 (capstone)

Design decision: You have a loop with $u_{mem} = 6$ , $u_{ALU} = 4$ , and a recurrence with $Lat (C) = 8$ , $Dist (C) = 4$ . Your baseline machine has 1 memory port and 2 ALUs. You may add exactly one of: (a) a second memory port, or (b) a third ALU. Which upgrade lowers $II_{m i n}$ more, and by how much?

Recall Solution

Baseline:

Memory: $⌈ 6/1 ⌉ = 6$ ; ALU: $⌈ 4/2 ⌉ = 2$ ; so $ResMII = 6$ .
$RecMII = ⌈ 8/4 ⌉ = 2$ .
$II_{m i n} = max (6, 2) = 6$ .

(a) Second memory port: memory $⌈ 6/2 ⌉ = 3$ ; ALU $2$ ; $ResMII = 3$ ; $RecMII = 2$ ⇒ $II_{m i n} = max (3, 2) = 3$ .

(b) Third ALU: memory $⌈ 6/1 ⌉ = 6$ (unchanged!); ALU $⌈ 4/3 ⌉ = 2$ ; $ResMII = 6$ ; ⇒ $II_{m i n} = max (6, 2) = 6$ .

Answer: The second memory port (a) cuts $II_{m i n}$ from 6 to 3 — a 2× speedup. The third ALU changes nothing because the ALU was never the bottleneck (it sat at 2 while memory sat at 6). Always spend hardware on the binding resource.

The upgrade decision is exactly this "attack the tallest bar" logic (this figure supports L5-Q3):

What the figure above shows (used by L5-Q3): for each resource, a pair of bars — the baseline bound (left, black) and the bound after adding a second memory port (right). Only the memory bar moves, dropping from 6 (in red, because it was the binding tallest bar) down to 3; the ALU and recurrence bars stand still. This makes the capstone lesson visual: money spent on a non-tallest bar (the third ALU) would leave the red bar — and therefore $II_{m i n}$ — completely unchanged. You only speed up the loop by shrinking whatever is currently tallest.

Recall Self-test summary

II stands for ::: Initiation Interval — cycles between launching successive iterations. Steady state means ::: the repeating middle of a pipelined loop after fill and before drain, where a new iteration launches every II cycles. k in the code-density problem means ::: the average number of real (non-NOP) operations packed per instruction word. RAW means ::: Read After Write — a true data dependency where an op reads what a previous op wrote; order cannot be broken. Every II floor is max(ResMII, RecMII) and we take max because ::: both promises (enough hardware AND data ready) must hold at once, so the tighter one governs. ResMII per resource ::: ceil(u_r / c_r) — uses per iteration over copies available, then max over resources. RecMII per cycle ::: ceil(Lat(C) / Dist(C)) — feedback-loop latency over iteration distance, then max over cycles. Dist(C) means ::: how many iterations back a recurrence reaches. Why a third ALU can be useless ::: it only helps if the ALU was the bottleneck (tallest bar). Why more ports cannot beat a recurrence ::: a true data dependence is algorithmic, not resource-bound.