Seyed Masoud Hosseini · Overview · Study log · Weekly summaries · Ideas · Search · Transcript · RSS feed

Digital Design & Computer Architecture · Lecture 21 of 37 · 1:49:38

Lecture 17: VLIW and Systolic Array Architectures

Study guide

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

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

Vocabulary

VLIW (Very Long Instruction Word) (noun): A processor design where the compiler packs several independent operations into one wide instruction ahead of time.
A VLIW processor relies on the compiler to schedule instructions.
bundle (noun): One wide VLIW instruction containing several operations meant to run together.
Each bundle holds multiple operations the compiler proved are independent.
lock-step (adjective): Describes operations that all move forward together, stalling together if any one of them is delayed.
All operations in a bundle run in lock-step, so one stall delays them all.
static scheduling (noun): Deciding the order and grouping of instructions at compile time, not while the program runs.
Static scheduling requires the compiler to guess instruction timing in advance.
no-op (noun): An instruction that does nothing, used as a filler when no useful work is available.
The compiler inserts a no-op when it can't find enough independent work.
variable-latency operation (noun): An operation whose completion time can differ depending on runtime conditions.
A memory load is a variable-latency operation because of possible cache misses.
trace scheduling (noun): A compiler technique that optimizes a program's most common execution path as straight-line code.
Trace scheduling speeds up the frequently taken path through the program.
superblock (noun): A code region with a single entry point, formed by duplicating code to remove side entrances.
A superblock allows more aggressive optimization than a normal basic block.
common subexpression elimination (noun): A compiler optimization that removes duplicate calculations of the same value.
Common subexpression elimination removes a redundant multiply.
basic block (noun): A straight-line sequence of code with one entry and one exit, no branches inside.
Trace scheduling combines code across multiple basic blocks.
dynamic binary translation (noun): Converting a program's instructions into a different instruction set while the program is running.
Dynamic binary translation lets one processor run code written for another.
code morphing (noun): Transmeta's software technique for translating x86 instructions into an internal VLIW format.
Code morphing let the chip run x86 software efficiently.
systolic array (noun): A grid of simple processing elements that pass data through a chain of computations.
A systolic array performs matrix multiplication without fetching separate instructions.
processing element (noun): One simple computing unit in a larger array, doing a fixed operation on passing data.
Each processing element multiplies and accumulates as data flows through.
convolution (noun): A mathematical operation that combines a pattern (filter) with data by sliding it across and computing weighted sums.
Convolution is the core operation in image-recognition neural networks.
throughput (noun): The amount of useful work completed over a given period of time.
Systolic arrays achieve high throughput by reusing each fetched value many times.
memory bandwidth (noun): The rate at which data can be moved to or from memory.
Systolic arrays reduce pressure on limited memory bandwidth.
embedded processor (noun): A processor built into a device for a specific, dedicated purpose rather than general use.
VLIW found more success in embedded processors than general-purpose ones.
digital signal processor (noun): A specialized processor designed for fast, predictable signal-processing math.
Digital signal processors use VLIW-style scheduling successfully.
philosophy (noun): A general approach or set of guiding ideas behind a design.
VLIW follows a smart-compiler, dumb-hardware philosophy.
inversion (noun): A reversal of the usual order or approach.
VLIW is a deliberate inversion of the out-of-order approach.
adoption (noun): The act of an idea or technology being taken up and used widely.
IA-64 struggled to gain adoption despite its clean design.
duplicate (verb): To make an extra copy of something.
Superblock formation duplicates code after side entrances.
side entrance (phrase): An extra way into a block of code other than its main starting point.
A side entrance breaks the single-entry property needed for optimization.
profiling (noun): Running a program on sample inputs to measure how it actually behaves.
Trace scheduling identifies the common path using profiling.
operand (noun): A value that an operation works on.
Each processing element multiplies two operands and adds the result.
stagger (verb): To arrange things so they start or happen at slightly different times.
Operands stream through the array in carefully staggered timing.
accumulate (verb): To gradually build up a total by adding values one at a time.
Each processing element multiplies and accumulates its running sum.
generalize (verb): To extend an idea from a specific case to a broader one.
The lecture generalizes the systolic model into pipeline-parallel execution.

From the YouTube description

Digital Design and Computer Architecture, ETH Zürich, Spring 2025 (https://safari.ethz.ch/ddca/spring2025/)

Lecture 17: VLIW and Systolic Array Architectures
Lecturer: Prof. Onur Mutlu
Date: 17 April 2025

Lecture 17a Slides (pptx): https://safari.ethz.ch/ddca/spring2025/lib/exe/fetch.php?media=onur-ddca-2025-lecture17a-vliw-afterlecture.pptx
Lecture 17a Slides (pdf): https://safari.ethz.ch/ddca/spring2025/lib/exe/fetch.php?media=onur-ddca-2025-lecture17a-vliw-afterlecture.pdf

Lecture 17b Slides (pptx): https://safari.ethz.ch/ddca/spring2025/lib/exe/fetch.php?media=onur-ddca-2025-lecture17b-systolicarrays-afterlecture.pptx
Lecture 17b Slides (pdf): https://safari.ethz.ch/ddca/spring2025/lib/exe/fetch.php?media=onur-ddca-2025-lecture17b-systolicarrays-afterlecture.pdf

Recommended Reading:
====================
Intelligent Architectures for Intelligent Computing Systems
https://people.inf.ethz.ch/omutlu/pub/intelligent-architectures-for-intelligent-computingsystems-invited_paper_DATE21.pdf

A Modern Primer on Processing in Memory
https://people.inf.ethz.ch/omutlu/pub/ModernPrimerOnPIM_springer-emerging-computing-bookchapter21.pdf

RowHammer: A Retrospective
https://people.inf.ethz.ch/omutlu/pub/RowHammer-Retrospective_ieee_tcad19.pdf

RECOMMENDED LECTURE VIDEOS & PLAYLISTS:
========================================
Computer Architecture Fall 2021 Lectures Playlist:
https://www.youtube.com/watch?v=4yfkM_5EFgo&list=PL5Q2soXY2Zi-Mnk1PxjEIG32HAGILkTOF

Computer Architecture Fall 2022 Lectures Playlist:
https://www.youtube.com/watch?v=BIpPTqHK-Lc&list=PL5Q2soXY2Zi-cAls3cyauNzM7-74Eq31O

Digital Design and Computer Architecture Spring 2022 Livestream Lectures Playlist:
https://www.youtube.com/watch?v=cpXdE3HwvK0&list=PL5Q2soXY2Zi97Ya5DEUpMpO2bbAoaG7c6

Digital Design and Computer Architecture Spring 2021 Livestream Lectures Playlist:
https://www.youtube.com/watch?v=LbC0EZY8yw4&list=PL5Q2soXY2Zi_uej3aY39YB5pfW4SJ7LlN

Featured Lectures:
https://www.youtube.com/watch?v=jVYCchBGNVc&list=PL5Q2soXY2Zi8VrmOTz44l2WupethSdh-M&index=1

Interview with Professor Onur Mutlu:
https://www.youtube.com/watch?v=8ffSEKZhmvo&list=PL5Q2soXY2Zi8VrmOTz44l2WupethSdh-M&index=9

The Story of RowHammer Lecture:
https://www.youtube.com/watch?v=sgd7PHQQ1AI&list=PL5Q2soXY2Zi8D_5MGV6EnXEJHnV2YFBJl&index=39

Accelerating Genome Analysis Lecture:
https://www.youtube.com/watch?v=r7sn41lH-4A&list=PL5Q2soXY2Zi8D_5MGV6EnXEJHnV2YFBJl&index=41

Memory-Centric Computing Systems Tutorial at IEDM 2021:
https://www.youtube.com/watch?v=H3sEaINPBOE&list=PL5Q2soXY2Zi8D_5MGV6EnXEJHnV2YFBJl&index=35

Intelligent Architectures for Intelligent Machines Lecture:
https://www.youtube.com/watch?v=GTieZPY4Wmc&list=PL5Q2soXY2Zi8D_5MGV6EnXEJHnV2YFBJl&index=38

Computer Architecture Fall 2020 Lectures Playlist:
https://www.youtube.com/watch?v=c3mPdZA-Fmc&list=PL5Q2soXY2Zi9xidyIgBxUz7xRPS-wisBN

Digital Design and Computer Architecture Spring 2020 Lectures Playlist:
https://www.youtube.com/watch?v=AJBmIaUneB0&list=PL5Q2soXY2Zi_FRrloMa2fUYWPGiZUBQo2

Public Lectures by Onur Mutlu, Playlist:
https://www.youtube.com/watch?v=kgiZlSOcGFM&list=PL5Q2soXY2Zi8D_5MGV6EnXEJHnV2YFBJl

Computer Architecture at Carnegie Mellon Spring 2015 Lectures Playlist:
https://www.youtube.com/watch?v=zLP_X4wyHbY&list=PL5PHm2jkkXmi5CxxI7b3JCL1TWybTDtKq

Rethinking Memory System Design Lecture @stanfordonline :
https://www.youtube.com/watch?v=F7xZLNMIY1E&list=PL5Q2soXY2Zi8D_5MGV6EnXEJHnV2YFBJl&index=4

← Lecture 16: Advanced Branch Prediction · Lecture 18: SIMD Architectures →