---
title: "Exploiting Superword Level Parallelism with Multimedia Instruction Sets"
authors:
  - "Samuel Larsen"
  - "Saman Amarasinghe"
year: 2000
venue: "PLDI 2000 (ACM SIGPLAN Conference on Programming Language Design and Implementation), 145–156"
arxiv: null
doi: "10.1145/349299.349320"
source: "https://groups.csail.mit.edu/cag/slp/SLP-PLDI-2000.pdf"
topics:
  - auto-vectorization
  - simd
  - basic-block-packing
  - compilers
seed_rank: 2377
seed_batch: "archive-2026-10-22"
reviewed: "2026-10-22"
pool: "languages"
relevance_score: 8
lineage: simd-compilation
see:
  - 341-ispc-a-spmd-compiler-for-high-performance-cpu-programming
  - 345-structure-of-arrays-and-data-layout-for-simd
  - 1666-vector-models-for-data-parallel-computing
  - 1627-direct-operable-simd-bit-slicing
cites:
  - title: "Exploiting Superword Level Parallelism with Multimedia Instruction Sets"
    url: "https://doi.org/10.1145/349299.349320"
    year: 2000
    arxiv: null
    doi: "10.1145/349299.349320"
---

# Exploiting Superword Level Parallelism with Multimedia Instruction Sets

## One-sentence takeaway

Larsen and Amarasinghe reframe short-SIMD code generation as packing isomorphic, independent statements inside a basic block — seeded by pairs of adjacent memory references, grown along def-use and use-def chains, merged into superword-width groups and rescheduled — and show this "SLP" view subsumes loop vectorization (unroll, then pack), finds parallelism vectorizers miss, and eliminates large fractions of dynamic instructions on SPEC95fp and multimedia kernels with 1.24–6.70× speedups on AltiVec.

## Why it matters here

ano's array primitives will mostly lower to loops a vectorizer handles, but the code around them — small fixed-width tuples (positions, colours, quaternions), unrolled stencils, hand-written engine math — is exactly the straight-line code SLP was designed for. This is the origin of the SLP vectorizer that LLVM and GCC still ship, so knowing its seed-extend-combine-schedule structure tells us what shapes of generated C or IR will vectorize for free and which (misaligned, non-adjacent, non-isomorphic) will not.

## Key ideas

- **SLP vs vector parallelism.** Vector parallelism is a subset: unrolling a vectorizable loop turns it into SLP the same way unrolling turns loop parallelism into ILP. SLP also covers code that is already hand-unrolled or has no loop at all, where a vectorizer would have to re-roll first.
- **Statement packing.** Isomorphic statements (same operations in the same order) that are independent can execute as one SIMD instruction; the benefit is the parallel speedup minus packing and unpacking cost, so the algorithm tries to reuse packed results directly as packed sources.
- **Algorithm.** Pre-optimise to three-address form and annotate alignment; seed the PackSet with pairs of statements touching adjacent memory; extend it by following def-use and use-def chains of existing packs; combine pairs sharing an element into groups as wide as the datapath; schedule each basic block, emitting SIMD ops for groups while respecting dependences.
- **Adjacent memory matters most.** Eliminating per-element loads and stores had the greatest impact on speedup, which is why adjacency is the seed.
- **Results.** Implemented in SUIF and measured on a Motorola MPC7400 with AltiVec; on SPEC95fp about 20% of the dynamic instruction savings came from non-vectorizable sequences, and in the paper's comparison the SLP algorithm matched the vectorizer on multimedia kernels while finding extra packing in scientific codes.

## Caveats

Results come from a research compiler, a 128-bit AltiVec target, benchmarks compiled without other optimisation due to toolchain limits, and hypothetical wider datapaths for the instruction-count study; wide datapaths need large unroll factors that short loops never reach. The greedy seeding can miss better packings and has no cost model for shuffles beyond avoiding them; later work (SuperNode SLP, goSLP with ILP-based packing, VW-SLP) addressed these. Alignment analysis is summarised, not given.

## Links

- Paper (author PDF): https://groups.csail.mit.edu/cag/slp/SLP-PLDI-2000.pdf
- Paper (DOI, PLDI 2000): https://doi.org/10.1145/349299.349320