Worked examples — Vector - SIMD instructions (SSE, AVX, NEON)

This page is a drill sheet for the parent SIMD note. There we learned that SIMD means one instruction, many data elements at once, and that the speedup for vector width $w$ is roughly $S\approx w$. Here we stress-test that idea against every awkward case a real program can throw at it — the clean case, the leftover case, the overflow case, the branchy case, and the exam trick.

Before symbols: let me re-anchor two words so nothing below is a mystery.

---

The scenario matrix

Every SIMD problem is really a question about how the data lines up with the tray. Here is the full grid of cases — the six worked examples below each fill one or more cells.

Cell	The scenario it tests	Where it bites	Worked in
C1	$n$ is an exact multiple of $w$	The "clean" ideal case	Ex 1
C2	$n$ is not a multiple of $w$ (remainder tail)	$\lceil n/w\rceil$, scalar cleanup	Ex 2
C3	$n<w$ (fewer elements than one tray)	Degenerate: still costs one instruction	Ex 3
C4	$n=0$ (empty input)	Limiting case: speedup undefined	Ex 3
C5	Reduction (sum across lanes, not element-wise)	Horizontal add, log-tree cost	Ex 4
C6	Overflow / saturation on small integers	$250+20$ must clamp, not wrap	Ex 5
C7	Data-dependent branch inside the loop	Masking; SIMD may lose	Ex 6
C8	Real-world word problem	Frame budget for image filter	Ex 7
C9	Exam twist: mixed element sizes / alignment	Trick numbers, the gotcha	Ex 8

---

Example 1 — C1: The clean multiple

Forecast: Before reading on — jot a number. How many vector adds, and what speedup?

1. Find $w$. Why this step? The tray size in elements is what divides the work. A 256-bit register $÷$ 32-bit per float $=256/32=8$. So $w=8$.
2. Count vector instructions. Why? Each instruction chews through one tray. Number $=\lceil n/w\rceil =\lceil 8000/8\rceil =1000$ exactly — no ceiling rounding because 8000 is a clean multiple of 8.
3. Speedup. Why? Scalar does $n=8000$ adds; SIMD does 1000. So $S=8000/1000=8$.

Verify: Units check — instructions are dimensionless counts. $1000\times 8=8000$ floats processed, matching $n$. ✓

---

Example 2 — C2: The remainder tail

Forecast: Guess the cleanup count first — is it 3? Something else?

1. Full trays. Why? Integer division tells us how many complete groups of 8 fit. $\lfloor 10003/8\rfloor =1250$ full vector adds covering $1250\times 8=10,000$ elements.
2. Remainder. Why this step? Whatever is left can't fill a tray, so it falls to scalar code. $10,003-10,000=3$ leftover elements → 3 scalar adds.
3. Total instruction-equivalents. Why? To compare fairly we count both parts: $1250$ vector + $3$ scalar $=1253$ "adds" worth of work.
4. Real speedup. Why? Scalar baseline is $10,003$ adds. $S=10003/1253\approx 7.98$.

Verify: $1250\times 8+3=10003$ ✓. And $\lceil 10003/8\rceil =1251$ (the ceiling formula) — note it counts the tail as one padded vector op, giving the slightly-optimistic $10003/1251\approx 8.00$. Both views are consistent; the scalar-tail view (7.98) is the honest one.

---

Example 3 — C3 & C4: Fewer than a tray, and empty

Forecast: Does 5 elements still cost a whole instruction? Is the speedup above or below 8?

1. Case (a), instruction count. Why ceiling? You cannot issue "5/8 of an instruction" — the hardware runs one whole addps and simply ignores (or masks) the 3 empty cups. $\lceil 5/8\rceil =1$.
2. Case (a), speedup. Why? Scalar = 5 adds; SIMD = 1. $S=5/1=5$. Below the ceiling of 8 because 3 lanes were wasted.
3. Case (b), the empty input. Why care? Limiting behaviour: $n=0$ gives $\lceil 0/8\rceil =0$ instructions. Speedup $S=0/0$ is undefined — there's nothing to accelerate.

Verify: (a) $8\times 0.625=5=S$ ✓ (speedup equals width times utilization). (b) Any code should guard $n=0$ and skip the loop entirely; no division by zero occurs because the loop body never runs.

---

Example 4 — C5: Reduction (sum across lanes)

Forecast: Guess the number of reduction stages: 8? 3? 7?

1. Why a tree, not a straight line? A vector adds lane-to-lane in parallel, so we fold the 8 values in halves: $8\to 4\to 2\to 1$. Each fold is one vector add.
2. Count stages. Why ${\log }_2$? Halving repeatedly from 8 needs ${\log }_{2}8=3$ folds. That's the key gain — a scalar loop needs $8-1=7$ sequential adds.

3. Total AVX op count. Why add the 1? One vmulps produces all 8 products, then 3 reduce-adds. $1+3=4$ vector ops.
4. Scalar baseline. Why 15? 8 multiplies + 7 adds $=15$ scalar ops.
5. Speedup. $S=15/4=3.75$ — well below $w=8$ because reductions have that unavoidable $\log$-tree overhead.

Recall Why reductions never hit full speedup

Question: Why is a dot product only ~4× on 8-wide SIMD instead of 8× ::: Element-wise multiply parallelizes perfectly (8×), but summing across lanes needs ${\log }_{2}w$ extra folding steps that a scalar loop hides inside its single accumulator — so the wins are diluted.

Verify: ${\log }_{2}8=3$ stages ✓; scalar ops $=8+7=15$ ✓; AVX ops $=1+3=4$ ✓; $15/4=3.75$ ✓.

---

Example 5 — C6: Overflow vs. saturation

Forecast: What does $250+30$ become in 8 bits when it wraps?

1. The true sum. Why? $250+30=280$, which exceeds the 8-bit ceiling of 255.
2. Wrapping result. Why modulo 256? An 8-bit register holds values $0$–$255$; overflow wraps around by $\mathrm{mod}256$. $280\mathrm{mod}256=24$. A bright pixel turns nearly black — a visible bug.
3. Saturating result. Why clamp? vqadd (the q = saturating) clamps anything above 255 down to 255. So the pixel becomes 255 (pure white) — the physically sensible answer.

Verify: $250+30=280$; $280\mathrm{mod}256=24$ ✓; $\min (280,255)=255$ ✓. Register still holds 16 lanes in one instruction regardless of which add variant is chosen.

---

Example 6 — C7: The branchy loop

Forecast: Both paths do the same work — but which has fewer total ops? Trust your gut.

1. Scalar cost. Why 2 per element? One compare, one add-or-sub. Total $=800\times 2=1600$ ops.
2. SIMD instruction count. Why 4 per tray? SIMD can't branch, so it computes both outcomes and selects: compare, inc-all, dec-all, blend = 4 vector ops per 8 elements. Number of trays $=800/8=100$. Total $=100\times 4=400$ vector ops.
3. Compare fairly. Why note "still wins here"? $400<1600$, so SIMD does win on op-count for this clean, predictable branch.
4. Why the parent warned anyway. Because SIMD did 2× the useful work (both inc and dec every lane) — utilization is only 50%. If branches are rare or unpredictable, scalar branch prediction can beat this doubled work. The lesson: SIMD-with-masking works, but its speedup is throttled by wasted lanes.

Verify: Scalar $=800\times 2=1600$ ✓; SIMD $=(800/8)\times 4=400$ ✓; ratio $1600/400=4$ (a 4× edge here, but with 50% wasted computation).

---

Example 7 — C8: Real-world word problem

Forecast: Will the filter eat most of the frame budget, or a tiny sliver?

1. Pixels per frame. Why multiply? Image is a grid. $1920\times 1080=2,073,600$ pixels.
2. NEON instructions per frame. Why divide by 16? Each vqaddq_u8 brightens 16 pixels. $2,073,600/16=129,600$ instructions (clean multiple — $2073600=16\times 129600$, no tail).
3. Instructions per second. Why $\times 60$? 60 frames each second. $129,600\times 60=7,776,000$ instructions/s.
4. Time per frame. Why? At 1 ns each: $129,600\times 1\text{ns}=129,600\text{ns}=0.1296\text{ms}$.
5. Fraction of budget. Why 16.67 ms? A 60 fps frame is $1000/60\approx 16.667$ ms. Fraction $=0.1296/16.667\approx 0.00778=0.78\%$.

Verify: $1920\times 1080=2073600$ ✓; $/16=129600$ ✓; $\times 60=7776000$ ✓; $0.1296/16.6\overline{6}\approx 0.00778$ ✓. Units: ns/ms cancels to a pure fraction ✓. The filter is nearly free — leaving the budget for decoding and display.

---

Example 8 — C9: The exam twist (mixed sizes + alignment)

Forecast: The array size and the address are both traps. Spot them before solving.

1. Find $w$ — first trap. Why not 4? Students assume $w=4$ from float examples. But these are 16-bit ints: $128/16=8$. So $w=8$.
2. Instruction count with tail. Why? $\lfloor 4098/8\rfloor =512$ full vectors covering $4096$ elements; remainder $4098-4096=2$ scalar ops. So 512 vector + 2 scalar.
3. Alignment — second trap. Why check the address bits? Aligned loads need the address divisible by 16. $\text{0x1001}=4097$ in decimal; $4097\mathrm{mod}16=1\ne 0$. Not aligned → movaps would fault. You must use the unaligned load movups (slower) or re-allocate on a 16-byte boundary.

Verify: $128/16=8$ ✓; $\lfloor 4098/8\rfloor =512$, tail $=4098-512\times 8=2$ ✓; $4097\mathrm{mod}16=1\ne 0$ so aligned load illegal ✓.

---

Where to go next

• The masking idea in Ex 6 is the heart of Data Paralelism and why Loop Vectorization and Auto-vectorization refuse to touch unpredictable branches.
• The alignment trap in Ex 8 ties directly into Cache Optimization (64-byte cache lines).
• SIMD sits in the "SI-MD" box of Flynn's Taxonomy; when the arrays get huge, you graduate to GPU Architecture. When they stay small but independent, Instruction-Level Parallelism picks up the slack.

Recall Self-test

Ideal speedup of clean $n=8000$ on 8-wide AVX ::: exactly 8 Vector instructions for $n=10003$, $w=8$, plus scalar tail ::: 1250 vector + 3 scalar $250+30$ in 8-bit wrapping add ::: 24 $250+30$ with saturating add ::: 255 NEON instructions to brighten a $1920\times 1080$ grayscale frame ::: 129600