The very long instruction word, and the compiler that never arrived

1980sThe proposal

Instead of hardware working out at run time which operations can proceed in parallel, the compiler decides in advance and emits one wide instruction containing several operations that are known to be independent.

The hardware then becomes much simpler: no reordering, no dependency analysis in silicon, no speculation. All of that complexity moves into the compiler, which has as much time as it needs and can see the whole program.

Why the argument is strong

The hardware doing this at run time spends a great deal of area and power on discovering facts the compiler already knows. It re-derives them every time the instruction executes, on every machine, forever.

Deciding once at compile time is obviously cheaper if the decision is as good, and the compiler has information the hardware does not: the shape of loops, the structure of the program, and time to think.

The fact the compiler does not have

How long a memory access will take. That is not a property of the program; it depends on what is in the cache, which depends on what ran before, on the input, and on everything else happening on the machine.

A static schedule must assume something. Assume the fast case and the whole wide instruction stalls whenever it is wrong; assume the slow case and the machine idles the rest of the time. Hardware that reorders at run time has the one fact the compiler lacks, which is what actually happened.

The binary compatibility problem

A schedule is built for a specific arrangement of execution units and latencies. Change the next generation of the chip and the schedule is wrong, so either the hardware pretends to be the old one, which discards the benefit, or the program is recompiled.

Recompiling everything is impossible for an ecosystem of shipped binaries, and that alone disqualifies the approach for general-purpose computing regardless of its merits.

1990s and 2000sThe commercial attempt

A large joint effort produced an architecture on these principles with enormous investment behind it, arriving years late and slower than expected on existing code.

Meanwhile a competitor extended the incumbent instruction set to sixty-four bits while running everything already compiled, which is the compatibility argument stated as a product. That decided it, and the specialised architecture was maintained for two decades out of obligation rather than demand.

The critique that has a name

Arguments of this shape rest on a compiler that does not exist yet and is expected to arrive. That expectation has a name in the field, used sceptically, and it has been disappointed often enough that its invocation is now treated as evidence against a proposal.

The compilers in this case did become very good. They still could not know what was in the cache.

2000s onwardsWhere it won completely

Signal processors, graphics hardware and the accelerators built for machine learning are wide, statically scheduled, and depend on the compiler placing operations precisely.

They work because their assumption holds: the access patterns are known in advance, the loops are regular, the data movement is planned, and there is no legacy of shipped binaries to preserve. The idea was not wrong. It was applied to the one workload that violates every one of its premises.

What the wide instruction does to code size

A practical difficulty that is rarely mentioned. Slots that cannot be filled must still be encoded, so programs with irregular control flow carry a great deal of empty space, and code size grows.

Larger code means more instruction cache misses, which means more waiting on memory, which is the same problem the schedule could not predict, arriving by a second route.

The version of the idea that survived everywhere

Explicit parallelism at the level of one instruction did not spread, but explicit parallelism over data did: one operation applied to many values at once is in every general-purpose processor and is used constantly.

The difference is instructive. That form does not require the compiler to predict timing, only to notice that the same thing is being done to many values, which is a property of the program and therefore knowable.

present dayThe other thing hardware knows at run time

Beyond cache behaviour, a modern processor observes which way branches actually go and predicts accordingly, with accuracy no static analysis approaches.

That is a second fact of the same kind: a property not of the program but of the data it happens to be given, and it is why arguments for moving decisions to compile time keep meeting the same wall from a different angle.

What the general machines took from it

Not nothing. Compilers for ordinary processors do schedule instructions, unroll loops, and arrange code so that the hardware's reordering has something to work with, and the hardware performs better on well-scheduled code than on badly scheduled code.

So the division of labour settled in the middle: the compiler arranges what it can know, and the hardware handles what only run time reveals. Both sides of the argument were describing half of the answer.

What we cannot verify

The architectures and the compiler techniques are documented and the machines existed. Explanations of the commercial outcome are offered by people with strong interests on both sides, and the counterfactual in which the schedule arrived on time is not recoverable. Benchmark comparisons from the period are not reproducible.