SIMD — vector instructions, SSE - AVX: Worked examples

The scenario matrix

Every SIMD sizing/speedup question is one of these case-classes. We will cover all of them.

Cell	Case class	What makes it tricky	Covered by
A	Clean division (len is a multiple of lanes)	none — baseline	Ex 1
B	Ugly remainder (len not a multiple of lanes)	tail loop, `len % lanes`	Ex 2
C	Different element widths (f64, int8, int16)	lane count changes with element size	Ex 3
D	Degenerate inputs (len = 0, len < lanes)	main loop runs zero times	Ex 4
E	Amdahl ceiling (partly vectorizable)	speedup ≪ lanes	Ex 5
F	Memory-bandwidth wall (limiting behaviour)	roofline caps you below lanes×	Ex 6
G	Horizontal reduction (cross-lane fold)	the log-fold, off-by-one lane math	Ex 7
H	Real-world word problem	pick the width, translate to lanes	Ex 8
I	Exam twist: float non-associativity	SIMD sum ≠ scalar sum bit-for-bit	Ex 9

Two numbers drive almost everything, so define them once and reuse:

Figure — SIMD — vector instructions, SSE - AVX

Cell A — clean division

Worked example Ex 1 · Add two f32 arrays of length 4096 with AVX

You add c[i] = a[i] + b[i] for $n = 4096$ single-precision floats using AVX (256-bit). How many vector iterations, and how many scalar tail iterations?

Forecast: guess the tail count before reading on — is it 0, 4, or 8?

Find lanes. $W = 256$ , $e = 32$ (f32 is 32 bits — see Floating Point Representation). So $lanes = 256/32 = 8$ . Why this step? The loop steps 8 elements at a time; you must know 8 before you can count iterations.
Vector iterations. Each iteration consumes 8 elements. $⌊ 4096/8 ⌋ = 512$ full vector iterations. Why this step? The main loop runs only while a whole vector of 8 still fits.
Tail. Leftover $= 4096 mod 8 = 0$ . No scalar tail. Why this step? $4096 = 8 \times 512$ exactly, so nothing is left — this is the clean baseline case.

Verify: $512 \times 8 + 0 = 4096$ . ✅ Every element is touched exactly once, tail = 0 as forecast.

Cell B — ugly remainder

Worked example Ex 2 · Same add, length 1000

Now $n = 1000$ f32 with AVX. How many vector iterations and how many scalar tail elements?

Forecast: $1000/8$ isn't whole — guess the remainder (0–7).

Lanes = 8 (as Ex 1). Why? Same $W = 256$ , $e = 32$ .
Vector iterations $= ⌊ 1000/8 ⌋ = 125$ , covering $125 \times 8 = 1000 \dots$ wait — check: $125 \times 8 = 1000$ exactly? $125 \times 8 = 1000$ . Yes. So actually 0 tail. Why this step? Always compute the product back; "looks ugly" is not the same as "has a remainder." $1000$ is divisible by 8.
Try a genuinely ugly length, $n = 1003$ : vector iters $= ⌊ 1003/8 ⌋ = 125$ (covers 1000), tail $= 1003 mod 8 = 3$ scalar elements. Why this step? This is the real remainder case — the last 3 elements go through the scalar for (; i < n; ++i) loop from the parent note.

Verify: $125 \times 8 + 3 = 1003$ . ✅ Lesson: never eyeball divisibility — 1000 was a trap, 1003 is the true remainder case.

Cell C — different element widths

Cell D — degenerate inputs

Worked example Ex 4 · Lengths 0, 3, and 7 with AVX f32

How many times does the vector loop body run for $n = 0$ , $n = 3$ , $n = 7$ ?

Forecast: guess each (careful — these are all below or at the danger zone).

Lanes = 8. Why? Same AVX f32 as before.
The guard is i + 8 <= n. Test each:
- $n = 0$ : $0 + 8 \leq 0$ ? No. Vector loop runs 0 times. All work (none) done by tail; tail also runs 0 times.
- $n = 3$ : $0 + 8 \leq 3$ ? No. Vector runs 0 times; tail does all 3 scalar elements.
- $n = 7$ : $0 + 8 \leq 7$ ? No. Vector runs 0 times; tail does all 7. Why this step? When $n < lanes$ , no full vector ever fits, so SIMD contributes nothing — the whole array falls into the scalar tail. This is why SIMD helps big arrays, not tiny ones.

Verify: vector iters $= ⌊ n /8 ⌋$ gives $0, 0, 0$ and tails $0, 3, 7$ ; sums $0, 3, 7$ . ✅ Degenerate small inputs = pure scalar.

Cell F — memory-bandwidth wall (limiting behaviour)

Worked example Ex 6 · When SIMD gives you

nothing A loop reads two f32 arrays and writes one: c[i] = a[i] + b[i]. Per element it moves $3 \times 4 = 12$ bytes but does only 1 flop. RAM delivers 20 GB/s; the core can do 32 GFLOP/s scalar, 8× that with AVX. What's the real throughput ceiling?

Forecast: with 8 lanes, does SIMD get you 8× here? Guess yes/no.

Arithmetic intensity $= \frac{flops}{bytes} = \frac{1}{12} \approx 0.083$ flop/byte. Why this step? The roofline decides compute-bound vs memory-bound from this ratio.
Memory-bound flop rate $= intensity \times bandwidth = \frac{1}{12} \times 20 = 1.667$ GFLOP/s. Why this step? If bytes are the bottleneck, flops are whatever the byte-stream can feed.
Compare ceilings. Compute ceiling with AVX $= 32 \times 8 = 256$ GFLOP/s. Memory ceiling $= 1.667$ GFLOP/s. The smaller wins: you are pinned at $1.667$ GFLOP/s. Why this step? You run at the min of the two — you can't compute faster than data arrives.
SIMD speedup here $= \frac{m i n ( 1.667 , 256 )}{m i n ( 1.667 , 32 )} = \frac{1.667}{1.667} = 1.0 \times$ . Why this step? Both scalar and AVX are already memory-capped, so widening the ALU changes nothing.

Verify: intensity $= 1/12$ , mem rate $= 20/12 \approx 1.667$ ; SIMD ratio $= 1.0$ . ✅ The parent's mistake "AVX is always 8×" dies exactly here.

Cell G — horizontal reduction fold

Worked example Ex 7 · How many fold steps to sum 8 lanes → 1?

You accumulated 8 partial sums in a ymm. To collapse them into one total, how many pairwise fold steps does the log-fold take, and what are the intermediate lane counts?

Forecast: guess the number of steps (2, 3, or 8?).

Start: 8 independent partial sums. Why this step? Keeping 8 accumulators broke the dependency chain in the loop (parent note); now we pay the cross-lane cost once.
Fold halves each step: $8 \to 4 \to 2 \to 1$ . Why this step? Each pairwise add combines two lanes into one, halving the count — that's a binary tree of depth $lo g_{2} 8$ .
Count steps $= lo g_{2} 8 = 3$ fold operations. Why this step? Going from 8 to 1 by halving takes $lo g_{2} 8 = 3$ halvings — the same count for any power-of-two lane width.

Verify: $lo g_{2} 8 = 3$ ; sequence $8 \to 4 \to 2 \to 1$ has 3 arrows. ✅ (The parent's code did it as: extract-hi+lo → 4, then two hadds → 3 total, matching.)

Cell H — real-world word problem

Worked example Ex 8 · Brightening a 1920×1080 image

You add a constant to every 8-bit pixel of a 1920×1080 grayscale image using AVX-512 (512-bit) on int8. How many pixels total, how many lanes, and how many vector iterations (assume clean division, remainder handled by tail)?

Forecast: guess the lane count for int8 on AVX-512 first.

Total pixels $= 1920 \times 1080 = 2, 073, 600$ . Why this step? This is the array length $n$ .
Lanes $= W / e = 512/8 = 64$ pixels per instruction. Why this step? int8 = 8 bits, so 64 of them pack into a 512-bit zmm.
Vector iterations $= ⌊ 2, 073, 600/64 ⌋ = 32, 400$ , tail $= 2, 073, 600 mod 64 = 0$ . Why this step? $2, 073, 600 = 64 \times 32, 400$ exactly (it's divisible by 64), so no tail — a clean real-world win.

Verify: $32, 400 \times 64 = 2, 073, 600$ . ✅ 64× fewer add-instructions than scalar (before memory/frequency effects). See Cache and Alignment for why aligning image rows helps.

Cell I — exam twist: float non-associativity

Worked example Ex 9 · Why the SIMD sum ≠ the scalar sum

Sum the four floats $[1 \times 1 0^{8}, 1, - 1 \times 1 0^{8}, 1]$ two ways: (a) strict left-to-right scalar, (b) SIMD-style pairing $(x_{0} + x_{2}) + (x_{1} + x_{3})$ . Using ideal real arithmetic both give 2. But f32 has ~7 significant digits. What does each really produce?

Forecast: guess which order loses the +1s.

Scalar left-to-right: $((1 0^{8} + 1) - 1 0^{8}) + 1$ . In f32, $1 0^{8} + 1$ rounds back to $1 0^{8}$ (the 1 is below the precision of $1 0^{8}$ ). So $1 0^{8} - 1 0^{8} = 0$ , then $+ 1 = 1$ . Why this step? Adding a tiny number to a huge one loses it — f32 can't represent $100000001$ . See Floating Point Representation.
SIMD pairing $(x_{0} + x_{2}) + (x_{1} + x_{3}) = (1 0^{8} - 1 0^{8}) + (1 + 1) = 0 + 2 = 2$ . Why this step? Pairing groups the two big opposite numbers first, so they cancel exactly before the small 1s are added — no precision is lost.
Conclusion: scalar gives $1$ , SIMD gives $2$ . Different results from reordering additions. Why this step? Float addition is not associative; SIMD reorders, so bit-exact reproducibility is not guaranteed (parent's steel-manned mistake).

Verify: with exact f32 semantics, scalar $\to 1.0$ , paired $\to 2.0$ . ✅ This is why -ffast-math is needed for the compiler to auto-vectorize reductions (Auto-vectorization and the Compiler).

Active recall

Recall Length 1003 f32 on AVX: vector iters and tail?

$⌊ 1003/8 ⌋ = 125$ vector iterations, $1003 mod 8 = 3$ scalar tail elements.

Recall Why does SIMD do nothing in Ex 6?

Both scalar and AVX are already memory-bandwidth bound (intensity $1/12$ flop/byte), so widening the ALU cannot help — you run at $min$ (compute, memory) = memory ceiling.

Recall Fold steps to reduce 8 lanes to 1?

$lo g_{2} 8 = 3$ pairwise steps: $8 \to 4 \to 2 \to 1$ .

Recall 90% vectorizable, 8 lanes — total speedup?

$\frac{1}{0.1 + 0.9/8} = \frac{1}{0.2125} \approx 4.71 \times$ , not 8×.

Worked examples — SIMD — vector instructions, SSE - AVX