Exercises — Vector - SIMD instructions (SSE, AVX, NEON)

• $256\text{ bits}÷32\text{ bits/float}=8$ floats — matches the description.
• The 256-bit registers are YMM registers, introduced by AVX (Advanced Vector Extensions).
• (128-bit XMM = SSE; 512-bit ZMM = AVX-512; 128-bit Q = NEON on ARM.)

Answer: AVX, register YMM.

$w=\frac{\text{register bits}}{\text{element bits}}=\frac{128}{8}=16.$ Answer: 16 lanes.

False. SIMD = Single Instruction, Multiple Data. All lanes execute the same operation in the same step. Different ops per lane needs different instructions (or masking).

$\lceil 4096/8\rceil =512$ (divides evenly). $S=\frac{4096}{512}=8$. Answer: $S=8$ — the ideal $S\approx w$ because $n$ is a clean multiple of $w$.

• Full trays: $\lfloor 100/4\rfloor =25$ SSE instructions cover $25\times 4=100$ elements.
• Remainder: $100-100=0$ scalar steps. Answer: 25 SSE instructions, 0 cleanup. (100 is divisible by 4, so the tail is empty.)

• $T_{\text{scalar}}=n\cdot t=30\times 5=150$ cycles.
• Trays: $\lceil 30/8\rceil =\lceil 3.75\rceil =4$. $T_{\text{SIMD}}=4\times 5=20$ cycles.
• $S=150/20=7.5$. Answer: $T_{\text{scalar}}=150$, $T_{\text{SIMD}}=20$, $S=7.50$. Why not exactly 8? The 4th tray is half-empty (only 6 of 8 lanes used) yet costs a full step.

• The element-wise multiply is perfectly parallel: 8 lanes, 1 instruction — that part is 8×.
• The horizontal sum (adding across lanes) is not data-parallel: lane 0 must be added to lane 4, then to lane 2, etc. Vector hardware sums down columns cheaply but across a row only in a tree of ${\log }_{2}w$ steps.
• For $w=8$: reduction takes ${\log }_{2}8=3$ pairwise stages (plus the 128-bit extract), i.e. ~4 ops that are essentially serial overhead riding on top of the one fast multiply.
• So the cheap parallel part (1 op) is dwarfed by the fixed reduction cost (4 ops): $S=15/5=3$. Answer: Cross-lane reduction is logarithmic serial work that does not shrink with $w$; it caps the speedup far below $w$. Lesson: SIMD shines when the output is also a vector, not a single scalar sum.

• Aligned load: bytes $[64,96)$ lie entirely inside cache line $[64,128)$ → 1 cache line.
• Unaligned load: bytes $[48,80)$ straddle line $[0,64)$ and line $[64,128)$ → 2 cache lines.
• Ratio $=2/1=2$: the unaligned load pulls twice the memory traffic. Answer: 1 line vs 2 lines; 2× bandwidth cost for the misaligned access.

• Scalar: $T_s=2n$.
• SIMD: $T_v=12+2\lceil n/8\rceil$.
• Try small $n$. For $n=8$: $T_s=16$; $T_v=12+2\cdot 1=14$ → SIMD wins.
• For $n=7$: $T_s=14$; $T_v=12+2\lceil 7/8\rceil =12+2=14$ → tie.
• For $n=6$: $T_s=12$; $T_v=12+2=14$ → scalar wins. Answer: For $n\le 6$ scalar is faster; $n=7$ is a tie; $n\ge 8$ SIMD wins. The 12-cycle setup must be amortized over enough elements.

Compute both results for every lane, then blend using a comparison mask:

1. mask = cmpgt(a, 0) — 1 op (lanes where $a>0$ become all-ones).
2. t1 = mul(a, 2) — the "then" branch value, 1 op.
3. t2 = add(a, 1) — the "else" branch value, 1 op.
4. b = blend(t2, t1, mask) — pick $t1$ where mask set, else $t2$, 1 op. Total: 4 vector instructions (plus load/store). No branch, all lanes obey one instruction each. Why it works: we trade a control-flow decision (which SIMD hates) for arithmetic on both paths + a select (which SIMD loves). Cost: we always compute the unused branch, but avoid mispredicted per-lane jumps.

• SIMD iterations = number of full trays = $\lfloor 1000/8\rfloor =125$ iterations, each covering 8 elements → $125\times 8=1000$ elements handled.
• Elements covered by SIMD = $125\times 8=1000$; scalar cleanup = $1000-1000=0$ iterations.
• Total loop iterations = $125+0=125$. Answer: 125 SIMD iterations, 0 cleanup, 125 total. (1000 is divisible by 8, so the tail vanishes.) Note the distinction: 125 is the iteration count; the 1000 is the element count they cover — never confuse the two.

• Wrapping (mod 256): $10+40=50$; $230+40=270\mathrm{mod}256=14$; $250+40=290\mathrm{mod}256=34$; $255+40=295\mathrm{mod}256=39$. → $[50,14,34,39]$ — bright pixels turn dark (visual garbage).
• Saturating (clamp at 255): $50$; $270\to 255$; $290\to 255$; $295\to 255$. → $[50,255,255,255]$ — bright pixels stay bright. Answer: wrapping $=[50,14,34,39]$; saturating $=[50,255,255,255]$. Image code always wants saturating (vqadd).

Total pixels $=1920\times 1080=2,073,600$ bytes.

• SSE / NEON ($w=16$ bytes): $\lceil 2073600/16\rceil =129,600$ instructions.
• AVX-512 ($w=64$ bytes): $\lceil 2073600/64\rceil =32,400$ instructions.
• Factor: $129600/32400=4$. Answer: AVX-512 minimizes count with $32,400$ vector ops — 4× fewer than SSE/NEON. Defend the edge cases: $2073600$ is divisible by both 16 and 64, so no scalar tail exists; the image row length (1920) is also a multiple of 64, so every SIMD load is naturally aligned — no unaligned penalty. This is the ideal SIMD workload: uniform op, no branches, aligned, huge $n$.

Let total time $=1$. Vectorizable part $=0.8$, scalar part $=0.2$. $S_{\text{prog}}=\frac{1}{(1-0.8)+\frac{0.8}{8}}=\frac{1}{0.2+0.1}=\frac{1}{0.3}\approx \mathrm{3.33.}$ Ceiling as $S_{\text{loop}}\to \infty$: the $0.8/8$ term $\to 0$, leaving $S_{\max }=\frac{1}{0.2}=5.$ Answer: whole-program speedup $\approx 3.33$×; hard ceiling $=5$× (this is Amdahl's law — the 20% scalar part caps everything). Lesson: widening the vector register past a point yields nothing until you also attack the scalar 20%.

A correct-for-all-cases plan, in four parts:

1. Handle $n=0$: compute simd_count = (n/8)*8 and run the main loop with guard i < simd_count, then the tail with guard i < n. For $n=0$ both simd_count=0 and n=0, so both loops run zero iterations — no special-case code needed, but confirm the guards produce zero passes (they do).
2. Alignment: if the pointers may be misaligned, use the unaligned load (_mm_loadu_ps / vmovups) — it is safe for any address and only pays the ~2× worst-case bandwidth of L3.2 when a load straddles a cache line. Never use the aligned form (vmovaps) on a pointer you did not align yourself: it faults on a misaligned address.
3. Main SIMD phase: simd_count = (n/8)*8; loop for (i = 0; i < simd_count; i += 8) doing load-a, load-b, vmulps, store-c per tray. This is the fast path that carries the ideal $S\approx 8$.
4. Scalar tail: for (i = simd_count; i < n; i++) c[i] = a[i]*b[i]; — this handles every leftover element, so the total is always correct regardless of whether $n$ divides 8.

Trace all required edge cases:

• $n=0$: simd_count = (0/8)*8 = 0 → SIMD loop skipped, tail loop skipped → 0 work, correct.
• $n=5$: simd_count = (5/8)*8 = 0 → SIMD skipped, tail does all 5 scalar multiplies → correct.
• $n=100$: simd_count = (100/8)*8 = 96 → 12 SIMD trays cover 96 elements, tail does the last 4 → correct.
• Misaligned pointer: vmovups never faults, so all four cases above still hold at a small bandwidth cost.

Answer: unaligned loads + a simd_count-bounded main loop + a scalar cleanup loop = correct for every $n$ (including 0 and small values) and every alignment, trading a slightly slower unaligned load for guaranteed safety. Correctness first; tighten to aligned loads only where you own the allocation and can guarantee the address.