VLIW architectures: Visual walkthrough — Hardware deep dive

Before any symbol appears, let us agree on plain words.

We will use one running example throughout. It is a loop that keeps a running total:

for (int i = 0; i < N; i++) {
    x = load(a[i]);   // L : read a[i] into x
    s = s + x;        // A : add x to the running sum s
    store(b[i], s);   // S : write s out to b[i]
}

Three operations per iteration: L (load), A (add), S (store). We will discover its $II$ from nothing.

Step 1 — Picture the loop as a factory line

WHAT. We draw each iteration as a vertical stack of its three operations, and we place iterations side by side in time.

WHY. Before formulas, we need a mental image where "how often can a new iteration start" is something we can literally measure with a ruler. A factory line does exactly this: parts enter at a steady rhythm.

PICTURE. Look at the figure. Time runs left to right in clock cycles. Iteration 0 occupies some cycles; iteration 1 is shifted right by an amount we are calling $II$ ; iteration 2 by another $II$ . The red gap between the starts of two neighbours is $II$ .

Step 2 — The first wall: not enough hardware (Resource bound)

WHAT. Count how many times the loop body uses each functional unit, and compare with how many copies of that unit exist.

WHY. A single memory port can serve one memory operation per cycle. Our body has two memory operations (the load L and the store S). Even in a perfect world with no dependencies, two memory ops cannot share one port in the same cycle — one must wait a cycle. This is a hardware wall, not a logic wall.

PICTURE. The figure shows a single memory-port "turnstile". Two people (L and S) want through it every iteration, but only one passes per cycle. So each new iteration cannot arrive faster than once every 2 cycles, or the turnstile jams.

Step 3 — The second wall: the answer feeds itself (Recurrence bound)

WHAT. Notice the sum: s = s + x. Iteration $i$ reads s, and to compute its new s it must wait for iteration $i - 1$ to have finished writing s. The output loops back as the next input.

WHY. This is a logic wall, independent of hardware. Even with infinitely many ALUs, iteration $i$ literally cannot compute s + x until the previous s exists. This chain that folds back on itself is called a recurrence (a dependency cycle in the graph).

PICTURE. The figure draws the dependency graph. The add node A has an arrow leaving it and curving back into itself, labelled with two numbers: the latency (how many cycles the add takes) and the distance (how many iterations back the value came from). That self-loop is the recurrence.

Step 4 — Turning the recurrence into a cycle count

WHAT. We convert "the sum feeds itself with latency $2$ , distance $1$ " into a minimum number of cycles per iteration.

WHY. If going once around the dependency cycle $C$ costs $Lat (C)$ cycles, and that trip carries us $Dist (C)$ iterations forward, then those $Dist (C)$ iterations together must be given at least $Lat (C)$ cycles. Spread evenly, that is $Lat (C) / Dist (C)$ cycles per iteration. Squeeze tighter and the value simply is not ready in time.

PICTURE. The figure lays the recurrence flat along the time axis: iteration $i$ 's add cannot fire until $2$ cycles after iteration $i - 1$ 's add. So consecutive adds are forced at least $2$ cycles apart — a floor on $II$ drawn as a green minimum-gap ruler.

Step 5 — Both walls at once: take the larger

WHAT. We have two independent lower bounds. Neither may be violated, so the real floor is whichever is bigger.

WHY. $ResMII$ says "at least 2 cycles or the port jams." $RecMII$ says "at least 2 cycles or the sum is not ready." A legal schedule must obey both. Obeying both means obeying the stricter one — the maximum.

PICTURE. Two floors stacked; the feasible region for $II$ sits above both. $II_{m i n}$ is the higher floor.

Step 6 — Edge and degenerate cases (never leave the reader stranded)

WHAT. We check what the formula says at its extremes so no scenario surprises you.

WHY. A formula you trust must behave sanely at the boundaries: no dependencies, no hardware limit, or a cycle with distance zero.

PICTURE. Four mini-panels, one per case, each showing what happens to the gap.

Worked example The corner cases

No recurrence (every iteration independent, like c[i]=a[i]+b[i]): there is no dependency cycle, so $RecMII = 0$ (or undefined → treated as $0$ ). Then $II_{m i n} = ResMII$ — you are purely hardware-bound. This is the memory-bound array-add of the parent note.
Infinite resources (a copy of every unit for every op): $u_{r} \leq c_{r}$ always, so $ResMII = 1$ . Then $II_{m i n} = RecMII$ — you are purely dependency-bound.
Both trivial (independent iterations and enough units): $II_{m i n} = max (1, 0) = 1$ — a new iteration every single cycle. The dream case.
Distance-zero cycle ( $Dist (C) = 0$ ): the value must be ready within the same iteration — division by zero flags an impossible loop-carried self-dependency inside one cycle. Real modulo schedulers reject this; a genuine loop always has $Dist (C) \geq 1$ .

The one-picture summary

Everything on one canvas: the loop, its two walls, and the winning floor.

Recall Feynman retelling — say it like a story

Imagine a factory line making running totals. A new part enters the line every so often; call that rhythm the initiation interval. Two things stop the rhythm from getting infinitely fast. First, there is only one door into the stockroom (the memory port), but each part needs to go in twice (a load and a store) — so parts can't enter faster than once every two beats: that's the resource wall, "uses over copies, rounded up." Second, each new total is built on top of the last total — you literally can't add to a number you don't have yet, and building it takes two beats — so consecutive adds are forced two beats apart: that's the recurrence wall, "latency over distance, rounded up." You must obey both walls, so you obey the taller one — that's the max. If a loop had no self-feeding total, only the door matters; if the door were infinitely wide, only the feeding matters. Either way, $II_{m i n} = max (ResMII, RecMII)$ is the fastest honest rhythm the line can run.

Recall Check yourself

What does $ResMII$ measure and why the ceiling? ::: It is $⌈ u_{r} / c_{r} ⌉$ — the busiest resource's uses divided by its copies, rounded up because iterations start a whole number of cycles apart and rounding down would overload the unit. Why does a recurrence set a floor even with infinite hardware? ::: Because a true (RAW) loop-carried dependency means this iteration's value cannot be computed until a past iteration's result exists; going around the cycle costs $Lat (C)$ cycles across $Dist (C)$ iterations, so at least $Lat (C) / Dist (C)$ cycles per iteration are unavoidable. Why take the max of the two bounds, not the sum or min? ::: A legal schedule must satisfy both constraints simultaneously; satisfying both is equivalent to satisfying the stricter (larger) one, so the true floor is their maximum. For our sample loop (2 mem ops, 1 port; add latency 2, distance 1) what is $II_{m i n}$ ? ::: $max (⌈ 2/1 ⌉, ⌈ 2/1 ⌉) = max (2, 2) = 2$ cycles.