Lecture 17: VLIW and Systolic Array Architectures

What this lecture covers

This lecture introduces two execution paradigms that take a very different approach from the out-of-order execution studied earlier in the course. Very Long Instruction Word (VLIW) architectures keep hardware simple by pushing instruction scheduling and dependence checking entirely into the compiler. Systolic arrays go further still, replacing general-purpose instruction execution with a special-purpose pipeline of processing elements that chain computation directly to data flow.

The lecture assumes familiarity with superscalar execution and out-of-order scheduling from previous lectures, contrasting VLIW's "smart compiler, dumb hardware" philosophy against them directly. After watching, you should be able to explain why VLIW never became dominant for general-purpose processors despite its clean design, trace how its compiler techniques still shape modern compilers, and describe how a systolic array performs convolution or matrix multiplication without any instructions at all.

Key ideas

• VLIW bundle: a single long instruction packing multiple operations that the compiler has already proven are independent, so hardware needs no runtime dependence checking.
• Lock-step execution: all operations in a VLIW bundle stall together if any one of them (commonly a cache-missing load) is not ready, unlike out-of-order execution where independent instructions can proceed.
• Static scheduling limits: a VLIW compiler must guess instruction latencies at compile time, which works poorly for variable-latency operations like memory loads.
• Trace scheduling and superblocks: compiler techniques that identify frequently executed paths, optimize them as straight-line code, and insert "fix-up" code for the rare paths that diverge, enabling optimizations across basic block boundaries.
• ISA translation: hardware or software can translate a complex ISA (such as x86) into simpler internal instructions, as Transmeta did with software-based VLIW code morphing.
• Systolic array: a regular network of simple processing elements through which data flows and is progressively transformed, so a single memory access yields many operations instead of one.
• Balancing compute and memory bandwidth: systolic arrays exist because chaining computation to each piece of fetched data avoids being bottlenecked by memory bandwidth.

Walkthrough

Superscalar review and the VLIW philosophy (3:53)

The lecture opens by reviewing superscalar execution, where hardware fetches, decodes, and checks dependences among multiple instructions per cycle, both horizontally along the pipeline and vertically across concurrently fetched instructions. VLIW is introduced as the opposite philosophy: the compiler (or, in principle, the programmer) packs independent instructions into a single wide bundle ahead of time, so hardware fetches and executes the whole bundle with no dependence checking at all. The lecture frames this as simple hardware paired with a complex compiler, a deliberate inversion of the out-of-order approach.

How VLIW bundles work and their downsides (8:57)

Using code examples, the lecture shows the compiler scheduling independent operations into the same bundle and inserting no-ops where it cannot find enough independent work. Because all operations in a bundle execute in lock step, a single long-latency operation, most often a load that misses in the cache, stalls the entire bundle and every later bundle behind it, since the compiler cannot know at compile time whether a given load will hit or miss.

VLIW history: Multiflow, Cydrome, Transmeta, and Intel IA-64 (21:03)

The lecture traces VLIW's philosophical roots to RISC (simple instructions so hardware stays simple) and its commercial history: Josh Fischer's Multiflow and Bob Rau's Cydrome built early wide VLIW machines, Transmeta translated x86 binaries into an internal VLIW format in software with "code morphing" to compete on power efficiency, and Intel's IA-64 project adapted VLIW principles (letting the compiler mark some intra-bundle dependences explicitly) but struggled to gain adoption. VLIW found lasting commercial success mainly in embedded and digital signal processors, where code is more statically predictable, and more recently in machine learning accelerators.

Trace scheduling and superblock optimizations (32:10)

Even though general-purpose VLIW did not succeed, the lecture argues its compiler techniques live on in modern compilers. Trace scheduling identifies a program's frequently executed path across basic blocks (using profiling), optimizes that path as if it always executes, and inserts "fix-up" and "undo" code to preserve correctness when execution takes a less common branch. Superblock formation improves on this by duplicating code after side entrances so the optimized region has a single entry point, which the lecture illustrates with a worked example eliminating a redundant multiply through common subexpression elimination, an optimization that trace scheduling's multiple-entry structure would have blocked.

Dynamic binary translation and code morphing (43:19)

The lecture connects VLIW-era ideas to modern practice: ISA translation can happen in hardware (x86 chips translating to internal micro-operations) or in software, as with Transmeta's code-morphing layer that translated x86 to an internal VLIW format, and with modern dynamic binary translators used internally by companies such as Apple and NVIDIA to optimize code at runtime. These systems reuse many of VLIW's compiler optimizations and, in some cases, add hardware support that helps the software optimizer do its job.

Systolic arrays: motivation and execution model (1:13:32)

Shifting to a different paradigm, the lecture presents H.T. Kung's systolic array design, motivated by the need for simple, regular, high-concurrency hardware that balances computation against limited memory bandwidth. A systolic array chains simple processing elements together so a data element fetched from memory is transformed repeatedly as it passes through the array before returning to memory, rather than each element being fetched, processed once, and stored back individually. This is illustrated with Kung's "memory as heart, data as blood" analogy and contrasted with classic pipelining: systolic processing elements apply the same operation to different data, rather than different pipeline stages of the same instruction.

Convolution and matrix multiplication on systolic arrays (1:24:40)

The lecture connects systolic arrays to convolution, the filtering operation at the core of convolutional neural networks, tracing its importance back to the AlexNet result that popularized deep learning on GPUs. It then works through a concrete systolic implementation of a weighted-sum (polynomial evaluation) computation and of matrix multiplication, showing processing elements that multiply and accumulate as operands stream through the array in carefully staggered timing, producing full matrix products with no instruction fetch or decode at all. The lecture closes by generalizing the model into "pipeline parallel" execution, where each processing element becomes a full core running one stage of a larger computation.

Before you watch

• Review superscalar execution and out-of-order scheduling from earlier lectures in this course, since VLIW is introduced as a direct philosophical contrast to both.
• Recall the notion of instruction-level parallelism and dependence checking, discussed in the preceding lectures on out-of-order execution.

Check your understanding

1. Why does a VLIW processor stall an entire instruction bundle when just one operation in it is not ready?
2. What made memory operations especially difficult for VLIW compilers to schedule well?
3. How does superblock formation enable optimizations that trace scheduling alone cannot?
4. In what sense was Transmeta's approach an ISA translation strategy, and why did it struggle commercially?
5. Why do systolic arrays avoid being bottlenecked by memory bandwidth the way a simple load-store processor is?