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

6.1.11 · D4 · Hardware › Parallelism & Multicore › Vector - SIMD instructions (SSE, AVX, NEON)

Yeh page ek self-testing ladder hai. Har problem ek clean question batata hai; poora worked solution ek collapsible [!recall]- callout ke andar chhupa hua hai taaki tum pehle try kar sako, phir reveal karo. Rungs L1 Recognition se shuru hote hain (kya tum iska naam bata sakte ho?) aur L5 Mastery tak jaate hain (kya tum ise design aur defend kar sakte ho?). Yahan sab kuch the parent SIMD note par build karta hai aur Loop Vectorization, Data Paralelism, aur Auto-vectorization ko touch karta hai.

Shuru karne se pehle, hum har woh symbol phir se earn karte hain jo poori page mein use hoga taaki koi pehli line se hi confused na ho.

Neeche wala figure $n$ , $w$ , aur trays ko concrete banata hai. Formula padhne se pehle ise dekho: coloured cells woh $n = 10$ elements $a_{0} \dots a_{9}$ hain; horizontal brackets unhe $w = 4$ slots ki trays mein group karte hain. Dhyaan do ki teesri tray sirf aadhi bhari hai (4 mein se 2 slots) — phir bhi yeh poori tray hai. Woh ek picture hi kyun is page ke har formula mein ceiling aati hai, yeh batata hai.

Level 1 — Recognition

L1.1 — Register ka naam batao

Q. Ek x86 CPU mein ek 256-bit register hai jo 8 single-precision (32-bit) floats rakhta hai. Konse SIMD instruction-set family ne ise introduce kiya, aur register ko kya kehte hain?

Recall Solution

$256 bits \div 32 bits/float = 8$ floats — description se match karta hai.
256-bit registers YMM registers hain, jo AVX (Advanced Vector Extensions) ne introduce kiye.
(128-bit XMM = SSE; 512-bit ZMM = AVX-512; 128-bit Q = ARM par NEON.)

Answer: AVX, register YMM.

L1.2 — Bit widths se lane count

Q. Ek 128-bit NEON Q register mein kitne 8-bit values fit hote hain?

Recall Solution

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

L1.3 — Same-op rule

Q. True ya false: ek single SIMD instruction pehle lane pair ko add kar sakti hai jabki doosre pair ko multiply kare.

Recall Solution

False. SIMD = Single Instruction, Multiple Data. Saare lanes same step mein same operation execute karte hain. Alag ops per lane ke liye alag instructions (ya masking) chahiye.

Level 2 — Application

L2.1 — Ideal speedup, large array

Q. Tum $n = 4096$ floats AVX ( $w = 8$ ) se process karte ho. Overhead ignore karte hue, speedup $S$ kya hai?

Recall Solution

$⌈ 4096/8 ⌉ = 512$ (evenly divide hota hai). $S = \frac{4096}{512} = 8$ . Answer: $S = 8$ — ideal $S \approx w$ kyunki $n$ $w$ ka clean multiple hai.

L2.2 — Remainder ke saath vector instructions ki count

Q. Tum $n = 100$ floats SSE ( $w = 4$ ) se process karte ho. Kitne SSE instructions chalenge, aur kitne scalar cleanup steps bachenge?

Recall Solution

Full trays: $⌊ 100/4 ⌋ = 25$ SSE instructions $25 \times 4 = 100$ elements cover karte hain.
Remainder: $100 - 100 = 0$ scalar steps. Answer: 25 SSE instructions, 0 cleanup. (100, 4 se divisible hai, isliye tail empty hai.)

L2.3 — Ragged length ke saath realistic time

Q. $n = 30$ elements, $w = 8$ , har step ki cost $t = 5$ cycles. $T_{scalar}$ , $T_{SIMD}$ , aur $S$ compute karo ( $S$ ko do decimals tak round karo).

Recall Solution

$T_{scalar} = n \cdot t = 30 \times 5 = 150$ cycles.
Trays: $⌈ 30/8 ⌉ = ⌈ 3.75 ⌉ = 4$ . $T_{SIMD} = 4 \times 5 = 20$ cycles.
$S = 150/20 = 7.5$ . Answer: $T_{scalar} = 150$ , $T_{SIMD} = 20$ , $S = 7.50$ . Exactly 8 kyun nahi? Chauthaa tray aadha empty hai (8 mein se sirf 6 lanes use) phir bhi ek poora step cost karta hai.

Neeche wala figure exactly yahi scenario draw karta hai. Chauthi tray dekho: iske blue slots woh 6 real elements hain, grey slots woh 2 wasted lanes hain. Woh grey slots ek poora $t = 5$ cycles consume karte hain phir bhi zero useful work karte hain — yahi visible reason hai ki $S = 7.5$ hai, ideal $8$ nahi. Is page ke har ragged-length problem mein yahi picture ka variation hai.

Level 3 — Analysis

L3.1 — Speedup kahan gaya?

Q. 8 floats ka dot product karta hai 8 multiplies + 7 adds = 15 scalar ops. AVX version karta hai 1 multiply + 4 reduction ops = 5 ops. $w = 8$ ke liye ideal speedup 8× hai, phir bhi measured speedup sirf $15/5 = 3$ × hai. Explain karo kyun horizontal reduction zyaadaatar ideal speedup destroy kar deta hai.

Recall Solution

Element-wise multiply bilkul parallel hai: 8 lanes, 1 instruction — woh part hai 8×.
Horizontal sum (lanes ke across add karna) data-parallel nahi hai: lane 0 ko lane 4 mein add karna hoga, phir lane 2 mein, etc. Vector hardware columns ke neeche cheaply sum karta hai lekin ek row ke across sirf $lo g_{2} w$ steps ke tree mein.
$w = 8$ ke liye: reduction $lo g_{2} 8 = 3$ pairwise stages leta hai (aur 128-bit extract bhi), matlab ~4 ops jo essentially serial overhead hai ek fast multiply ke upar sawaar.
Toh sasta parallel part (1 op) fixed reduction cost (4 ops) se dab jaata hai: $S = 15/5 = 3$ . Answer: Cross-lane reduction logarithmic serial work hai jo $w$ ke saath shrink nahi karta; yeh speedup ko $w$ se kaafi neeche cap kar deta hai. Lesson: SIMD tab chamakta hai jab output bhi ek vector ho, na ki ek single scalar sum.

L3.2 — Aligned vs unaligned bandwidth

Q. Cache lines 64 bytes ki hain. Address 64 par shuru hone wala ek aligned 32-byte AVX load kitne cache lines touch karta hai? Address 48 par shuru hone wala ek unaligned load kitne touch karta hai? Bandwidth ratio kya hai?

Recall Solution

Aligned load: bytes $[64, 96)$ poori tarah cache line $[64, 128)$ ke andar hain → 1 cache line.
Unaligned load: bytes $[48, 80)$ line $[0, 64)$ aur line $[64, 128)$ ke beech straddled hain → 2 cache lines.
Ratio $= 2/1 = 2$ : unaligned load double memory traffic pull karta hai. Answer: 1 line vs 2 lines; misaligned access ke liye 2× bandwidth cost.

L3.3 — Break-even array size

Q. Ek vectorized loop mein 12 cycles ka fixed setup cost hai (constants load karna, aligning). Har AVX step $t = 2$ cycles cost karta hai aur $w = 8$ elements karta hai. Scalar $t = 2$ cycles per element cost karta hai bina kisi setup ke. Kis $n$ ke neeche scalar actually faster hoga?

Recall Solution

Scalar: $T_{s} = 2 n$ .
SIMD: $T_{v} = 12 + 2 ⌈ n /8 ⌉$ .
Chhote $n$ try karo. $n = 8$ ke liye: $T_{s} = 16$ ; $T_{v} = 12 + 2 \cdot 1 = 14$ → SIMD jeet jaata hai.
$n = 7$ ke liye: $T_{s} = 14$ ; $T_{v} = 12 + 2 ⌈ 7/8 ⌉ = 12 + 2 = 14$ → tie.
$n = 6$ ke liye: $T_{s} = 12$ ; $T_{v} = 12 + 2 = 14$ → scalar jeet jaata hai. Answer: $n \leq 6$ ke liye scalar faster hai; $n = 7$ par tie hai; $n \geq 8$ par SIMD jeet jaata hai. 12-cycle setup ko kaafi elements par amortize karna zaroori hai.

Level 4 — Synthesis

L4.1 — Ek masked branch design karo

Q. Tumhe if (a[i] > 0) b[i] = a[i]*2; else b[i] = a[i]+1; ko 8 floats ke liye AVX se vectorize karna hai, jo per-lane branching forbid karta hai. Branch-free lane sequence outline karo aur vector instructions count karo.

Recall Solution

Har lane ke liye dono results compute karo, phir comparison mask use karke blend karo:

mask = cmpgt(a, 0) — 1 op (jahan $a > 0$ ho woh lanes all-ones ban jaate hain).
t1 = mul(a, 2) — "then" branch value, 1 op.
t2 = add(a, 1) — "else" branch value, 1 op.
b = blend(t2, t1, mask) — jahan mask set ho wahan $t 1$ pick karo, warna $t 2$ , 1 op. Total: 4 vector instructions (load/store ke alaawa). Koi branch nahi, saare lanes ek ek instruction maante hain. Kyun kaam karta hai: hum control-flow decision (jo SIMD ko pasand nahi) ko dono paths par arithmetic + ek select (jo SIMD ko bahut pasand hai) se trade karte hain. Cost: hum hamesha unused branch compute karte hain, lekin per-lane mispredicted jumps se bachte hain.

L4.2 — $n = 1000$ ke liye two-phase loop

Q. AVX ( $w = 8$ ) ke saath $n = 1000$ floats par ek for loop vectorize karo: SIMD iteration count, scalar-cleanup count, aur total loop iterations batao.

Recall Solution

SIMD iterations = full trays ki count = $⌊ 1000/8 ⌋ = 125$ iterations, har ek 8 elements cover karta hai → $125 \times 8 = 1000$ elements handle ho jaate hain.
SIMD se cover hue elements = $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, 8 se divisible hai, isliye tail vanish ho jaati hai.) Distinction note karo: 125 iteration count hai; 1000 woh element count hai jo ye cover karte hain — in dono ko kabhi confuse mat karo.

L4.3 — Saturating vs wrapping brightness

Q. 8-bit pixels (max value 255). Pixel values $[10, 230, 250, 255]$ mein brightness 40 add karo using (a) wrapping add aur (b) saturating add. Dono output vectors batao.

Recall Solution

Wrapping (mod 256): $10 + 40 = 50$ ; $230 + 40 = 270 mod 256 = 14$ ; $250 + 40 = 290 mod 256 = 34$ ; $255 + 40 = 295 mod 256 = 39$ . → $[50, 14, 34, 39]$ — bright pixels dark ho jaate hain (visual garbage).
Saturating (255 par clamp): $50$ ; $270 \to 255$ ; $290 \to 255$ ; $295 \to 255$ . → $[50, 255, 255, 255]$ — bright pixels bright rehte hain. Answer: wrapping $= [50, 14, 34, 39]$ ; saturating $= [50, 255, 255, 255]$ . Image code ko hamesha saturating (vqadd) chahiye.

Level 5 — Mastery

L5.1 — ISA choose karo aur numbers se justify karo

Q. Ek grayscale filter ek $1920 \times 1080$ image process karta hai, ek byte per pixel, har pixel par same add-and-clamp karta hai. SSE (128-bit, 16 bytes/op), AVX-512 (512-bit, 64 bytes/op), aur NEON (128-bit, 16 bytes/op) ke liye instruction counts compare karo. Kaun vector-instruction count minimize karta hai, aur SSE se kitne factor par?

Recall Solution

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

SSE / NEON ( $w = 16$ bytes): $⌈ 2073600/16 ⌉ = 129, 600$ instructions.
AVX-512 ( $w = 64$ bytes): $⌈ 2073600/64 ⌉ = 32, 400$ instructions.
Factor: $129600/32400 = 4$ . Answer: AVX-512 count minimize karta hai $32, 400$ vector ops se — SSE/NEON se 4× kam. Edge cases defend karo: $2073600$ dono 16 aur 64 se divisible hai, isliye koi scalar tail nahi hai; image row length (1920) bhi 64 ka multiple hai, isliye har SIMD load naturally aligned hai — koi unaligned penalty nahi. Yeh ideal SIMD workload hai: uniform op, koi branches nahi, aligned, huge $n$ .

L5.2 — Mixed workload par Amdahl ceiling

Q. Ek program apna 80% time ek aise loop mein spend karta hai jise tum $S_{loop} = 8$ × par vectorize kar sakte ho; baaki 20% inherently scalar hai. Whole-program speedup kya hai? Even if $S_{loop} \to \infty$ ho toh absolute ceiling kya hai?

Recall Solution

Total time $= 1$ maano. Vectorizable part $= 0.8$ , scalar part $= 0.2$ . $S_{prog} = \frac{1}{( 1 - 0.8 ) + \frac{0.8}{8}} = \frac{1}{0.2 + 0.1} = \frac{1}{0.3} \approx 3.33.$ Ceiling jab $S_{loop} \to \infty$ : $0.8/8$ term $\to 0$ ho jaata hai, leaving $S_{m a x} = \frac{1}{0.2} = 5.$ Answer: whole-program speedup $\approx 3.33$ ×; hard ceiling $= 5$ × (yeh Amdahl's law hai — 20% scalar part sab kuch cap kar deta hai). Lesson: vector register ko ek point ke baad widening karne se kuch nahi milta jab tak scalar 20% ko bhi attack nahi karte.

L5.3 — Ek robust kernel design + defend karo

Q. Words mein, c[i] = a[i]*b[i] ko arbitrary $n$ ke liye AVX ( $w = 8$ ) se vectorize karne ka ek complete robust plan likho, $n = 0$ , $n = 5$ , aur misaligned pointers ke liye correctness guarantee karte hue.

Recall Solution

Ek correct-for-all-cases plan, chaar parts mein:

$n = 0$ handle karo: simd_count = (n/8)*8 compute karo aur main loop guard i < simd_count ke saath chalao, phir tail guard i < n ke saath. $n = 0$ ke liye dono simd_count=0 aur n=0 hain, isliye dono loops zero iterations chalate hain — koi special-case code nahi chahiye, lekin confirm karo ki guards zero passes produce karte hain (karte hain).
Alignment: agar pointers misaligned ho sakti hain, unaligned load use karo (_mm_loadu_ps / vmovups) — yeh kisi bhi address ke liye safe hai aur sirf ~2× worst-case bandwidth of L3.2 pay karta hai jab load cache line straddle kare. Aligned form (vmovaps) kabhi mat use karo aise pointer par jo tumne khud align nahi kiya: yeh misaligned address par fault karta hai.
Main SIMD phase: simd_count = (n/8)*8; loop for (i = 0; i < simd_count; i += 8) jo har tray ke liye load-a, load-b, vmulps, store-c karta hai. Yeh fast path hai jo ideal $S \approx 8$ carry karta hai.
Scalar tail: for (i = simd_count; i < n; i++) c[i] = a[i]*b[i]; — yeh har leftover element handle karta hai, isliye total hamesha correct hai chahe $n$ 8 se divide ho ya nahi.

Saare required edge cases trace karo:

$n = 0$ : simd_count = (0/8)*8 = 0 → SIMD loop skip, tail loop skip → 0 work, correct.
$n = 5$ : simd_count = (5/8)*8 = 0 → SIMD skip, tail saare 5 scalar multiplies karta hai → correct.
$n = 100$ : simd_count = (100/8)*8 = 96 → 12 SIMD trays 96 elements cover karte hain, tail aakhri 4 karta hai → correct.
Misaligned pointer: vmovups kabhi fault nahi karta, isliye upar ke charon cases small bandwidth cost par bhi hold karte hain.

Answer: unaligned loads + ek simd_count-bounded main loop + ek scalar cleanup loop = har $n$ ke liye (0 aur chhoti values samait) aur har alignment ke liye correct, thoda slower unaligned load ke liye guaranteed safety trade karta hai. Pehle correctness; aligned loads par sirf tabhi tighten karo jab tum khud allocation ke owner ho aur address guarantee kar sako.

[!recall]- Har level ke liye one-line self-check

L1 — lanes = register bits ÷ element bits

haan; 256/32 = 8

L2 — trays ke liye ceiling use karo, plain division nahi

⌈ 30/8 ⌉ = 4

trays

L3 — real

S

setup, reduction, alignment se cap hota hai

dot product ke liye

S = 15/5 = 3

L4 — hamesha scalar tail add karo; saturating int ops use karo

warna elements skip ho jaate hain / wrap to black

L5 — Amdahl whole-program speedup cap karta hai

1/ (0.2 + 0.8/8) = 3.33

, ceiling 5

Related paths: Loop Vectorization · Auto-vectorization · Data Paralelism · Instruction-Level Parallelism · Cache Optimization · Flynn's Taxonomy · GPU Architecture.