VLIW Bundles and the Compiler as Scheduler

A superscalar core spends a large fraction of its transistor budget on logic that rediscovers, at run time, something the compiler could have computed ahead of time: which instructions are independent and which functional unit each should go to. A VLIW machine deletes that logic. Each instruction word names several operations, one per functional unit slot, and the hardware issues them together without examining their operands. The dependence check, the unit assignment, and the choice of what goes in the same cycle all happen at compile time and are frozen into the encoding.

The trade is stark. In exchange for removing the scheduler, wakeup logic, and most of the bypass arbitration, the machine exposes its pipeline to software. Latency becomes part of the instruction set contract. That single decision is the root of both the design’s efficiency and its commercial failure.

What a bundle actually contains

A VLIW bundle is a fixed-width encoding divided into slots. The division can be explicit, as in a 128-bit word split into three fields of 41 bits plus a template field of a few bits that records which slots may be issued together and which stop bits mark the end of a group. It can also be implicit, with the compiler required to fill every slot every cycle, emitting an explicit no-operation encoding for unused slots.

Both schemes make the same guarantee: slot position implies functional unit. An operation placed in the slot wired to the memory unit goes to the memory unit. There is no crossbar, no scoreboard, and no arbitration. The decoder fans the fields out to their units and the cycle ends. Compare this with the dispatch logic of a four-wide out-of-order machine, which must read a wakeup matrix to find ready instructions, select among them subject to port constraints, and read a rename map for each; Issue Width and the Structural Ceiling on Instructions per Cycle describes that machinery. The VLIW core contains none of it.

Removing the scheduler removes more than area. The wakeup-and-select logic sits in the loop that determines the clock period in a wide out-of-order machine, because a result must be tagged, matched against waiting instructions, selected, and steered to a unit within a cycle. A VLIW machine’s critical path is the register file read, the functional unit, and the write-back, so the same silicon can host more units at a higher frequency. Static scheduling also sees further than any reorder window: the compiler can overlap operations separated by hundreds of instructions, whereas a hardware window covers at most a few hundred entries and cannot look past a hard-to-predict branch.

The cost is that every one of those compiler decisions is permanent. A binary scheduled for a machine with a four-cycle load-to-use latency executes incorrectly on a machine with five cycles, because the value is consumed before it arrives. Compatibility within a VLIW family therefore requires keeping the pipeline visible in the ISA, which means either freezing the microarchitecture or supplying a compatibility layer that reschedules binaries at load time.

Filling slots when there is nothing to put in them

The compiler’s problem is to keep every slot occupied. Straight-line code between branches usually has enough independent operations, but branch boundaries do not cooperate: the blocks on either side of a branch are scheduled separately, so a slot freed by a short block cannot be filled by work from the block after the branch.

The classical answer is global scheduling across basic blocks. Trace scheduling selects the most probable path through the code, forms a trace from the blocks along it, schedules the trace as if it were straight-line, and then repairs the edges. Compensation code is inserted where the aggressive motion would have produced a wrong result if the branch had gone the other way: values moved above a branch must be recomputed or copied on the off-trace path, and speculative loads moved above a branch must be guarded so they do not fault on a path where the address is invalid. Software pipelining, which overlaps successive iterations of a loop rather than successive blocks, is treated in Software Pipelining and Loop-Carried Dependences.

Both techniques work best on code with regular structure, and both degrade on code with unpredictable control flow. A trace built on a branch that is taken half the time will be wrong half the time, and the compensation code then runs on the majority path. This is a property of the workload, not of the compiler’s competence, and it is why VLIW designs historically did well on numeric loops and poorly on branchy integer code.

/* Source: a[i] = b[i] + c[i] for eight independent elements.
   A VLIW compiler would emit, for a four-slot machine, two bundles:
     bundle 0: load b0 | load b1 | load c0 | load c1
     bundle 1: load b2 | load c2 | add0    | add1
   and so on, with adds placed at least the load latency after
   their loads and NOPs wherever no independent work exists. */

for (int i = 0; i < 8; i++)
    a[i] = b[i] + c[i];

The schedule above is a fragment of a modulo schedule. Its shape is dictated entirely by the load latency: with four slots and a load latency of four cycles, sixteen independent loads must be in flight to keep the load slots occupied, and a body that supplies two loads per iteration has to be unrolled eightfold to reach that. Loop unrolling is therefore not an optimisation on a VLIW machine but a precondition for filling the slots.

Predication as a substitute for branches

If control flow is the obstacle to scheduling, one response is to remove it. Predication attaches a boolean guard to each operation; a predicated operation whose guard is false has no architectural effect. A short if-then-else becomes a straight-line sequence of predicated operations, and the scheduler can move work freely across what used to be a branch.

The cost is that both sides of the condition are fetched and occupy slots. For a two-way branch where each side is three operations, the predicated form needs six slots plus the compare, against three on the taken path of a branched form. Predication pays when the branch is unpredictable and the bodies are short, and loses when the bodies are long or when the condition is almost always one way.

Predication also consumes registers. Every destination written under a predicate needs a register that holds its old value on the false path, so a machine with 64 predicate registers and 128 general registers, as the Itanium architecture specified, is provisioned for this style rather than for scalar code. Register pressure from unrolling, software pipelining, and predication compound, and the compiler must eventually spill, which reintroduces memory traffic into a schedule that was built to avoid it.

Where the model breaks

Three failure modes recur across VLIW implementations.

The first is the variable-latency operation. A load from a cache line that hits returns in a fixed number of cycles; a load that misses returns in hundreds, and the number is not known at compile time. A static schedule cannot wait an unknown time. Implementations either stall the whole machine on a scoreboard interlock for loads specifically, reintroducing the hardware they removed, or require the compiler to hide the latency with enough independent work that misses are absorbed. The second option works only when the loop body has enough parallelism to cover the worst case, which is the definition of a numeric kernel and not of general code.

The second is binary compatibility across implementations. Because latency is encoded, a new implementation with a deeper pipeline cannot run old binaries unless the ISA includes a mechanism to communicate the change. Hardware can detect and stall on a violated assumption, at the cost of a scoreboard; software can reschedule at load time, at the cost of a translation step and its own startup latency. Neither is free, and neither restores the clean area argument.

The third is code size. Filling slots with no-operations to satisfy a fixed bundle width wastes instruction memory, and instruction memory is a significant part of a core’s area and its energy per fetch. Wide bundles with many empty slots inflate the instruction footprint, which increases instruction cache misses and fetch bandwidth demand, partially cancelling the fetch-width advantage that the wide encoding was supposed to provide.

What survived

The pure VLIW as a general-purpose architecture did not persist, but its ideas are in current machines. Digital signal processors and graphics cores use statically scheduled, wide instruction words because their workloads are loops with regular, predictable structure and because their binaries are compiled for a known fixed pipeline. Very long instruction word encodings have also appeared in GPU instruction sets, where one word names several operations issued in the same cycle to different ALUs across the lanes of a wavefront.

The larger lesson concerns where scheduling effort should live. Static scheduling is efficient when the compiler can see the whole loop and the loop has no surprises. Dynamic scheduling is efficient when the code is branchy, when latencies vary, and when binaries must outlive the microarchitecture. Most current general-purpose cores choose dynamic scheduling for the outer loop and rely on the compiler for the inner one, vectorising it so that a single instruction occupies a whole functional unit for many elements at once. That second strategy is the subject of Fixed-Width SIMD Lanes Versus Scalable Vector Registers.