VLIW architectures: Worked examples — Hardware deep dive

This page is the "every scenario" workbook for VLIW architectures. The parent note gave you the machine and the two scheduling formulas. Here we use them, one worked case at a time, until no situation can surprise you.

Everything runs on the same 4-slot machine from the parent:

Before any formula, three plain-word ideas the parent used but we will now earn:

Look at the figure: three iterations laid over each other, each shifted down by II cycles. Small II = tightly overlapped = fast. Our whole job is to find the smallest legal II.

The scenario matrix

Every scheduling question you can be asked falls into one of these cells. The examples below are labelled with the cell they cover, and together they hit all of them.

#	Cell (what makes it different)	What forces the answer	Example
A	Resource-bound, one scarce unit	too many memory ops for 1 port	Ex 1
B	Recurrence-bound, dependency cycle dominates	a value feeds the next iteration	Ex 2
C	Tie: ResMII = RecMII	both bounds equal	Ex 3
D	Degenerate: no loop-carried dependency (`Dist = 0`)	RecMII undefined → resource decides	Ex 4
E	Zero parallelism: pure dependent chain (straight-line)	II / slot-count collapses	Ex 5
F	Limiting case: add more ALUs — when does it stop helping?	resource ceiling saturates	Ex 6
G	Real-world word problem: DSP filter tap	translate English → resources	Ex 7
H	Exam twist: a "free" NOP-hiding trap	slot count ≠ throughput	Ex 8

The two tools we lean on, restated in words:

Example 1 — Cell A: one memory port is the bottleneck

Worked example Array add, memory-bound

Loop body per iteration needs: 2 loads + 1 store (memory), 1 add (integer). Machine: 1 memory port, 2 integer ALUs, no dependency crosses iterations. Find $II_{m i n}$ .

Forecast: Guess now — will the ALUs or the memory port set the pace?

Step 1 — Count memory uses. $u_{mem} = 2 + 1 = 3$ ops, and $c_{mem} = 1$ port. Why this step? ResMII asks each resource "how many cycles do you personally need?" $⌈ 3/1 ⌉ = 3 cycles$

Step 2 — Count ALU uses. $u_{alu} = 1$ add, $c_{alu} = 2$ ALUs. Why this step? Same question, other resource. $⌈ 1/2 ⌉ = 1 cycle$

Step 3 — Take the max. $ResMII = max (3, 1) = 3$ . Why this step? The slowest resource gates everything — you can't start the next iteration until the busiest unit is free.

Step 4 — No loop-carried dependency, so $RecMII = 0$ (no cycle exists). Why this step? Each iteration writes a fresh c[i]; nothing waits on last iteration.

Step 5 — Combine. $II_{m i n} = max (3, 0) = 3$ .

Verify: 3 memory ops, 1 port → at least 3 cycles even if ALUs sat idle. Matches the parent's "one memory op per cycle" statement. ✓

Example 2 — Cell B: a dependency cycle sets the pace

Worked example Accumulator recurrence

sum = sum + a[i] each iteration. The add reads sum and writes sum, so iteration i needs the sum from iteration i−1. Add latency = 3 cycles, iteration distance = 1. Resources per iteration: 1 load, 1 add — both plentiful. Find $II_{m i n}$ .

Forecast: The load is cheap. Does that make the loop fast?

Step 1 — ResMII. Memory: $⌈ 1/1 ⌉ = 1$ ; ALU: $⌈ 1/2 ⌉ = 1$ → $ResMII = 1$ . Why this step? Resources are abundant, so they cannot be the bottleneck.

Step 2 — Find the dependency cycle. sum → add → sum (next iteration). One edge, latency 3, distance 1. Why this step? RecMII only exists where a value loops back onto itself across iterations.

Step 3 — Apply RecMII. $RecMII = ⌈ Lat / Dist ⌉ = ⌈ 3/1 ⌉ = 3$ Why this step? You literally cannot start the next add until the previous add's 3-cycle result is ready.

Step 4 — Combine. $II_{m i n} = max (1, 3) = 3$ .

Verify: Even with infinite ALUs, the chain forces 3 cycles between adds. The bottleneck moved from hardware to math of the algorithm. ✓

The figure contrasts Ex 1 and Ex 2: same II = 3, but one is a wall of hardware (memory port), the other a rope of dependencies (the recurrence). Same number, totally different cause.

Example 3 — Cell C: the exact tie

Example 4 — Cell D: degenerate, `Dist = 0`

Worked example No loop-carried dependency at all

Loop: c[i] = a[i] * 2. One load, one store, one multiply — none crosses iterations. What is RecMII, and what sets $II_{m i n}$ ?

Forecast: Is RecMII even defined here?

Step 1 — Look for a cycle. There is none — every arrow points within one iteration. Why this step? RecMII's formula divides by $Dist (C)$ ; with no cycle there is nothing to divide, so we set $RecMII = 0$ (it imposes no constraint). Mistake guard: $Dist = 0$ would mean dividing by zero — that only happens for a within-iteration chain, which is not a recurrence and is simply excluded.

Step 2 — ResMII decides. Memory: 1 load + 1 store $= ⌈ 2/1 ⌉ = 2$ ; ALU: $⌈ 1/2 ⌉ = 1$ . $ResMII = 2$ .

Step 3 — Combine. $II_{m i n} = max (2, 0) = 2$ .

Verify: With no recurrence, throughput is purely a resource story. The 2 memory ops on 1 port give 2. ✓

Example 5 — Cell E: zero parallelism (straight-line chain)

Worked example Fibonacci-style dependent chain (no loop overlap)

Three ops, each needing the previous one's result (latency 1 each): MOV r3,r1 → ADD r1,r1,r2 → MOV r2,r3. Not a loop — just a straight chain. How many cycles, and what is slot utilisation?

Forecast: We have 4 slots per cycle — can these 3 ops share a cycle?

Step 1 — Chain length. Each op waits on the last → 3 sequential cycles. Why this step? Dependencies forbid overlap; parallel slots cannot help serial work.

Step 2 — Slots offered. 3 instructions × 4 slots = 12 slots. Step 3 — Slots used. 3 real ops. $Utilisation = \frac{3}{12} = 0.25 = 25%$ Why this step? This is the "code density efficiency" idea from the parent, made concrete.

Verify: Matches the parent's Fibonacci example exactly: 25 % slot use, the other 9 slots are NOPs. VLIW exposes parallelism; it cannot invent it. ✓

Example 6 — Cell F: limiting behaviour, add ALUs until it stops helping

Worked example How many ALUs before ResMII saturates?

Loop body: 4 independent adds + 1 load. Memory: 1 port. Ask: as we grow the ALU count $c$ from 1 → 5, how does ResMII behave?

Forecast: Does doubling ALUs keep doubling speed forever?

Step 1 — ALU term as a function of $c$ . $⌈ 4/ c ⌉$ . Step 2 — Memory term (fixed). $⌈ 1/1 ⌉ = 1$ . Step 3 — Tabulate $ResMII = max (⌈ 4/ c ⌉, 1)$ :

ALUs $c$	$⌈ 4/ c ⌉$	ResMII
1	4	4
2	2	2
4	1	1
5	1	1

Why this step? Watching the whole range reveals the limit, not just one point.

Step 4 — Read the limit. Once $c \geq 4$ , the ALU term hits 1 and the memory port (=1) takes over. More ALUs beyond 4 give zero further speedup.

Verify: $lim_{c \to \infty} ⌈ 4/ c ⌉ = 1$ ; ResMII floors at $max (1, 1) = 1$ . Hardware has a saturation point — the classic VLIW "resource ceiling." ✓

The curve flattens: each extra ALU helps less, then not at all once memory becomes the wall.

Example 7 — Cell G: real-world word problem (DSP filter)

Worked example A 4-tap FIR filter

An audio filter computes each output as y = a·x0 + b·x1 + c·x2 + d·x3. Per output: 4 multiplies, 3 adds (compute), and 5 memory ops (4 coefficient loads + 1 result store; the x samples are already in registers, shifting each iteration). Multiply latency 2, distance 1 through the shift chain. Memory: 1 port. Multiplies use the 2 integer/mult ALUs. Find $II_{m i n}$ .

Forecast: Compute-heavy and memory-heavy — which dominates?

Step 1 — Translate English to counts. memory $u = 5$ , mult+add $u = 4 + 3 = 7$ on 2 ALUs. Why this step? Word problems are 90 % translation; get the counts right first.

Step 2 — ResMII. Memory: $⌈ 5/1 ⌉ = 5$ . ALU: $⌈ 7/2 ⌉ = 4$ . $ResMII = max (5, 4) = 5$ .

Step 3 — RecMII. The sample-shift chain: one shift feeds the next iteration, latency 2, distance 1 → $⌈ 2/1 ⌉ = 2$ .

Step 4 — Combine. $II_{m i n} = max (5, 2) = 5$ .

Verify: The single memory port (5 accesses) dominates a compute-rich kernel. Real DSP chips answer this by adding multiple memory ports — exactly the fix Ex 3/6 predicted. ✓

Example 8 — Cell H: the exam trap

Recall

Recall What sets

$II_{m i n}$ in a memory-bound loop with no recurrence? The resource bound: $ResMII = ⌈ u_{mem} / c_{mem} ⌉$ ; RecMII is 0.

Ceiling appears in ResMII because ::: you cannot run a fraction of an operation on a unit — round cycles up. RecMII of a recurrence with latency 3, distance 1 is ::: $⌈ 3/1 ⌉ = 3$ cycles. Adding more ALUs stops helping once ::: the ALU term drops to the level of another resource (e.g. the memory port), which then dominates. Slot count (issue width) equals throughput? ::: No — the scarcest replicated resource (often 1 memory port) sets the true limit. A dependency cycle with $Dist = 0$ means ::: the code is impossible (an op depending on itself in the same cycle); correct code never yields it.