SIMD — vector instructions, SSE - AVX: Visual walkthrough

Step 1 — What "one instruction, one number" looks like

WHAT. Let's start with ordinary (scalar) code. Picture a factory with one worker. A box of numbers slides down a conveyor belt. For each number the worker must do three things: fetch the instruction card ("ADD +5"), decode it (understand what the card means), then execute it (actually add).

WHY start here. We can only appreciate what SIMD saves if we first count what scalar code spends. The waste we're hunting for is hiding in the repetition.

PICTURE. Look at the figure: every single box makes the worker re-read the same card. The card never changes — only the number underneath it does. That repeated fetch+decode is pure overhead.

Figure — SIMD — vector instructions, SSE - AVX

Step 2 — Packing numbers side-by-side into one wide register

WHAT. Now widen the register. Instead of a slot that holds one number, we build a shelf that holds several numbers laid end to end with no gaps. This end-to-end laying is called packing.

WHY. If several numbers already sit inside one register, then one instruction card can point at all of them at once. That is the entire trick — we are setting up to pay the overhead $o$ a single time for the whole shelf.

PICTURE. The wide bar is the register. The vertical dividers slice it into equal lanes. Each lane is exactly one element wide. Notice the dividers are just conceptual — no carry or borrow ever crosses them.

Step 3 — Counting the lanes (deriving $W / e$ )

WHAT. How many numbers fit on the shelf? We laid them end to end with no gaps, so this is just "how many pieces of length $e$ fit into a shelf of length $W$ ." That is a division.

WHY division and not something fancier. Because packing has no overlap and no gaps — the pieces tile the shelf perfectly. Whenever equal-sized pieces tile a length, the count is (total length) ÷ (piece length). No other operation answers "how many fit."

PICTURE. The figure measures the shelf: $W$ across the top, one lane of width $e$ marked at the left. Count the tiles — that count is the lane number $L$ .

Step 4 — One instruction fires all lanes at once

WHAT. The wide addps instruction takes two full shelves, and every lane's adder fires simultaneously. The instruction card is fetched and decoded once for the whole shelf.

WHY this is the payoff. Go back to Step 1's cost $N (o + w)$ . We paid overhead $o$ per element. Now we pay $o$ once per group of $L$ elements. The overhead is amortized — spread thin — across the lanes.

PICTURE. One card ("ADD") points down at $L$ parallel adders, all lit up at the same instant. Compare it with Step 1's single lit adder re-reading the card over and over.

Step 5 — The ideal speedup, and why it caps at $L$

WHAT. Speedup is simply "old time ÷ new time." Divide Step 1's time by Step 4's time.

WHY a ratio. Speedup answers "how many times faster?" — that is by definition the ratio of the two run-times. Bigger ratio = faster.

PICTURE. Two bars: the tall scalar bar and the short vector bar. The short bar is $L$ times shorter if the whole loop vectorizes and nothing else limits us.

Step 6 — Reality bites: not all the loop vectorizes (Amdahl)

WHAT. Real programs are not 100% "same op over an array." Some fraction is stuck scalar (branches, dependencies, setup). Split the work into a vectorizable fraction $f$ and a stubborn fraction $(1 - f)$ .

WHY split it. Only the $f$ part gets the $L \times$ discount from Step 5. The $(1 - f)$ part runs at old speed no matter how wide your register. Ignoring this is how people wrongly expect a flat $8 \times$ .

PICTURE. A unit-length time bar. The orange chunk $f$ shrinks to $f / L$ . The magenta chunk $(1 - f)$ does not move. The new total is their sum.

Step 7 — The floor under everything: memory bandwidth

WHAT. Even with $f = 1$ , you must still fetch every byte from memory. If the pipe from RAM can't feed the lanes, the adders sit idle waiting. Compute got $L \times$ faster; the delivery truck did not.

WHY this is a separate ceiling. Steps 5–6 assumed the numbers are already in the register. But someone had to load them. If loading is slower than computing, the load time — not $L$ — sets the pace. This is why array loops so often see far less than $L \times$ .

PICTURE. The wide adder bank (fast) fed by a thin straw from RAM (slow). Widening the adders doesn't widen the straw. See Memory Bandwidth and the Roofline Model for the full picture.

Step 8 — The degenerate tail (when $N$ isn't a multiple of $L$ )

WHAT. What if you have $N = 10$ floats and $L = 8$ ? One full shelf handles $8$ ; the leftover $10 - 8 = 2$ don't fill a shelf. Those go through a small scalar tail loop.

WHY it can't be ignored. A vector instruction always touches a whole shelf of $L$ . Firing it on a partial group would read past your array (garbage or a crash). So the last $N mod L$ elements must be handled one at a time.

PICTURE. A conveyor of 10 boxes: one full vector group of 8 (orange), then 2 stragglers (magenta) peeled off into a single-file scalar lane.

The one-picture summary

WHAT. Everything at once: scalar cost $N (o + w)$ → pack into $L = W / e$ lanes → ideal $L \times$ → Amdahl trims it → bandwidth may cap it → tail mops up the remainder.

Recall Feynman retelling — the whole walkthrough in plain words

A lone worker reads the same instruction card for every number in a box — that re-reading is wasted time (Step 1). So we build a wide shelf and lay numbers on it side-by-side with no gaps (Step 2). How many fit? Shelf length divided by number length, $W / e$ — that's the lane count $L$ (Step 3). Now one card fires all lanes together, and we read the card once per shelf instead of once per number (Step 4). Dividing the old time by the new time, everything cancels except $L$ — so the best you can do is $L$ times faster (Step 5). But real programs have stubborn bits that stay slow; only the fraction $f$ that vectorizes gets the discount — that's Amdahl (Step 6). And even then, the numbers have to arrive from memory through a thin straw; if the straw is the slow part, widening the adders buys nothing (Step 7). Finally, when the count doesn't divide evenly by $L$ , the last few stragglers go through one at a time in a tail loop (Step 8). The real speedup is the smaller of the compute ceiling and the memory ceiling.

Recall Quick self-test

AVX f32, $N = 10$ : how many full vector groups and how many tail elements? ::: $L = 256/32 = 8$ , so $⌊ 10/8 ⌋ = 1$ group and $10 mod 8 = 2$ tail elements.

Related vault notes: Data-Level Parallelism · Amdahl's Law · Auto-vectorization and the Compiler · Floating Point Representation · GPU SIMT.