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

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

Yeh page parent SIMD note ke liye ek drill sheet hai. Wahan humne seekha ki SIMD matlab hai ek instruction, ek saath kai data elements, aur vector width $w$ ke liye speedup roughly $S \approx w$ hota hai. Yahan hum us idea ko stress-test karte hain har us awkward case ke against jo ek real program throw kar sakta hai — clean case, leftover case, overflow case, branchy case, aur exam trick.

Symbols se pehle: do words ko re-anchor karte hain taaki neeche kuch bhi mystery na rahe.

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

Scenario matrix

Har SIMD problem actually yeh question hai ki data tray ke saath kaise align hota hai. Yeh cases ka poora grid hai — neeche ke chhe worked examples mein se har ek ek ya zyada cells fill karta hai.

Cell	Jo scenario yeh test karta hai	Kahan problem hoti hai	Worked in
C1	$n$ , $w$ ka exact multiple hai	"Clean" ideal case	Ex 1
C2	$n$ , $w$ ka multiple nahi hai (remainder tail)	$⌈ n / w ⌉$ , scalar cleanup	Ex 2
C3	$n < w$ (ek tray se bhi kam elements)	Degenerate: phir bhi ek instruction lagti hai	Ex 3
C4	$n = 0$ (empty input)	Limiting case: speedup undefined	Ex 3
C5	Reduction (lanes ke paas sum, element-wise nahi)	Horizontal add, log-tree cost	Ex 4
C6	Chhote integers par overflow / saturation	$250 + 20$ clamp hona chahiye, wrap nahi	Ex 5
C7	Loop ke andar data-dependent branch	Masking; SIMD haar bhi sakta hai	Ex 6
C8	Real-world word problem	Image filter ke liye frame budget	Ex 7
C9	Exam twist: mixed element sizes / alignment	Trick numbers, woh gotcha	Ex 8

Example 1 — C1: Clean multiple

Forecast: Aage padhne se pehle — ek number jot karo. Kitne vector adds, aur kya speedup?

$w$ find karo. Yeh step kyun? Elements mein tray size woh hai jo kaam divide karta hai. Ek 256-bit register $\div$ 32-bit per float $= 256/32 = 8$ . Toh $w = 8$ .
Vector instructions count karo. Kyun? Har instruction ek tray process karta hai. Count $= ⌈ n / w ⌉ = ⌈ 8000/8 ⌉ = 1000$ exactly — koi ceiling rounding nahi kyunki 8000, 8 ka clean multiple hai.
Speedup. Kyun? Scalar $n = 8000$ adds karta hai; SIMD 1000 karta hai. Toh $S = 8000/1000 = 8$ .

Verify: Units check — instructions dimensionless counts hain. $1000 \times 8 = 8000$ floats processed, $n$ se match karta hai. ✓

Example 2 — C2: Remainder tail

Forecast: Pehle cleanup count guess karo — kya yeh 3 hai? Kuch aur?

Full trays. Kyun? Integer division batata hai ki 8 ke kitne complete groups fit hote hain. $⌊ 10003/8 ⌋ = 1250$ full vector adds jo $1250 \times 8 = 10, 000$ elements cover karte hain.
Remainder. Yeh step kyun? Jo bacha hai woh tray fill nahi kar sakta, toh woh scalar code pe jaata hai. $10, 003 - 10, 000 = 3$ leftover elements → 3 scalar adds.
Total instruction-equivalents. Kyun? Fairly compare karne ke liye hum dono parts count karte hain: $1250$ vector + $3$ scalar $= 1253$ "adds" worth of work.
Real speedup. Kyun? Scalar baseline $10, 003$ adds hai. $S = 10003/1253 \approx 7.98$ .

Verify: $1250 \times 8 + 3 = 10003$ ✓. Aur $⌈ 10003/8 ⌉ = 1251$ (ceiling formula) — note karo yeh tail ko ek padded vector op count karta hai, slightly-optimistic $10003/1251 \approx 8.00$ deta hai. Dono views consistent hain; scalar-tail view (7.98) zyada honest hai.

Example 3 — C3 & C4: Ek tray se kam, aur empty

Forecast: Kya 5 elements phir bhi ek poori instruction cost karte hain? Speedup 8 se upar hai ya neeche?

Case (a), instruction count. Ceiling kyun? Aap "5/8 of an instruction" issue nahi kar sakte — hardware ek poora addps run karta hai aur simply 3 empty cups ignore (ya mask) karta hai. $⌈ 5/8 ⌉ = 1$ .
Case (a), speedup. Kyun? Scalar = 5 adds; SIMD = 1. $S = 5/1 = 5$ . 8 ki ceiling se neeche kyunki 3 lanes waste hue.
Case (b), empty input. Kyun care karein? Limiting behaviour: $n = 0$ se $⌈ 0/8 ⌉ = 0$ instructions milte hain. Speedup $S = 0/0$ undefined hai — accelerate karne ke liye kuch nahi hai.

Verify: (a) $8 \times 0.625 = 5 = S$ ✓ (speedup = width times utilization). (b) Koi bhi code $n = 0$ guard kare aur loop bilkul skip kare; division by zero nahi hogi kyunki loop body kabhi run nahi karta.

Example 4 — C5: Reduction (lanes ke paas sum)

Forecast: Reduction stages ki number guess karo: 8? 3? 7?

Tree kyun, straight line kyun nahi? Ek vector lane-to-lane parallel add karta hai, toh hum 8 values ko halves mein fold karte hain: $8 \to 4 \to 2 \to 1$ . Har fold ek vector add hai.
Stages count karo. $lo g_{2}$ kyun? 8 se repeatedly halving ke liye $lo g_{2} 8 = 3$ folds chahiye. Yahi key gain hai — ek scalar loop ko $8 - 1 = 7$ sequential adds chahiye.

Total AVX op count. 1 add kyun? Ek vmulps saare 8 products produce karta hai, phir 3 reduce-adds. $1 + 3 = 4$ vector ops.
Scalar baseline. 15 kyun? 8 multiplies + 7 adds $= 15$ scalar ops.
Speedup. $S = 15/4 = 3.75$ — $w = 8$ se kaafi neeche kyunki reductions mein woh unavoidable $lo g$ -tree overhead hota hai.

Recall Reductions full speedup kyun kabhi nahi hit karte

Question: Dot product 8-wide SIMD par 8× ki jagah sirf ~4× kyun hai ::: Element-wise multiply perfectly parallelizes (8×), lekin lanes ke paas sum karne ke liye $lo g_{2} w$ extra folding steps chahiye jo ek scalar loop apne single accumulator ke andar hide kar leta hai — toh wins dilute ho jaate hain.

Verify: $lo g_{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: $250 + 30$ 8 bits mein wrap hone par kya banta hai?

True sum. Kyun? $250 + 30 = 280$ , jo 8-bit ceiling 255 se zyada hai.
Wrapping result. Modulo 256 kyun? Ek 8-bit register $0$ – $255$ values hold karta hai; overflow $mod 256$ se wrap hota hai. $280 mod 256 = 24$ . Ek bright pixel almost black ho jaata hai — yeh ek visible bug hai.
Saturating result. Clamp kyun? vqadd (q = saturating) koi bhi cheez jo 255 se zyada ho usse 255 tak clamp kar deta hai. Toh pixel 255 (pure white) ban jaata hai — physically sensible answer.

Verify: $250 + 30 = 280$ ; $280 mod 256 = 24$ ✓; $min (280, 255) = 255$ ✓. Register phir bhi ek instruction mein 16 lanes hold karta hai, chahe koi bhi add variant choose kiya jaaye.

Example 6 — C7: Branchy loop

Forecast: Dono paths same kaam karte hain — lekin kiske paas kam total ops hain? Apni gut trust karo.

Scalar cost. Per element 2 kyun? Ek compare, ek add-or-sub. Total $= 800 \times 2 = 1600$ ops.
SIMD instruction count. Per tray 4 kyun? SIMD branch nahi kar sakta, toh yeh dono outcomes compute karta hai aur select karta hai: compare, inc-all, dec-all, blend = 4 vector ops per 8 elements. Trays ki count $= 800/8 = 100$ . Total $= 100 \times 4 = 400$ vector ops.
Fairly compare karo. "Yahan phir bhi jeetta hai" kyun note karo? $400 < 1600$ , toh SIMD does win op-count par is clean, predictable branch ke liye.
Parent ne warn kyun kiya. Kyunki SIMD ne 2× useful kaam kiya (har lane mein dono inc aur dec) — utilization sirf 50% hai. Agar branches rare ya unpredictable hain, toh scalar branch prediction is doubled work ko beat kar sakti hai. Lesson: SIMD-with-masking kaam karta hai, lekin iska speedup wasted lanes se throttle hota hai.

Verify: Scalar $= 800 \times 2 = 1600$ ✓; SIMD $= (800/8) \times 4 = 400$ ✓; ratio $1600/400 = 4$ (yahan 4× edge, lekin 50% wasted computation ke saath).

Example 7 — C8: Real-world word problem

Forecast: Kya filter frame budget ka zyada hissa khaata hai, ya ek chhoti si sliver?

Pixels per frame. Multiply kyun? Image ek grid hai. $1920 \times 1080 = 2, 073, 600$ pixels.
NEON instructions per frame. 16 se divide kyun? Har vqaddq_u8 16 pixels brighten karta hai. $2, 073, 600/16 = 129, 600$ instructions (clean multiple — $2073600 = 16 \times 129600$ , koi tail nahi).
Instructions per second. $\times 60$ kyun? 60 frames har second. $129, 600 \times 60 = 7, 776, 000$ instructions/s.
Time per frame. Kyun? 1 ns each par: $129, 600 \times 1 ns = 129, 600 ns = 0.1296 ms$ .
Budget ka fraction. 16.67 ms kyun? Ek 60 fps frame $1000/60 \approx 16.667$ ms ka hota hai. 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 cancel hokar pure fraction ban jaata hai ✓. Filter almost free hai — budget decoding aur display ke liye bachta hai.

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

Forecast: Array size aur address dono traps hain. Solve karne se pehle unhe spot karo.

$w$ find karo — pehla trap. 4 kyun nahi? Students float examples se $w = 4$ assume karte hain. Lekin yeh 16-bit ints hain: $128/16 = 8$ . Toh $w = 8$ .
Tail ke saath instruction count. Kyun? $⌊ 4098/8 ⌋ = 512$ full vectors jo $4096$ elements cover karte hain; remainder $4098 - 4096 = 2$ scalar ops. Toh 512 vector + 2 scalar.
Alignment — doosra trap. Address bits kyun check karein? Aligned loads ko 16 se divisible address chahiye. $0x1001 = 4097$ decimal mein; $4097 mod 16 = 1 \neq = 0$ . Aligned nahi → movaps fault karega. Aapko unaligned load movups use karna hoga (slower) ya 16-byte boundary par re-allocate karna hoga.

Verify: $128/16 = 8$ ✓; $⌊ 4098/8 ⌋ = 512$ , tail $= 4098 - 512 \times 8 = 2$ ✓; $4097 mod 16 = 1 \neq = 0$ toh aligned load illegal ✓.

Aage kahan jaana hai

Ex 6 mein masking idea Data Paralelism ka core hai aur isliye Loop Vectorization aur Auto-vectorization unpredictable branches ko touch karne se inkar karte hain.
Ex 8 mein alignment trap directly Cache Optimization (64-byte cache lines) se connect hota hai.
SIMD Flynn's Taxonomy ke "SI-MD" box mein baithta hai; jab arrays bahut bade ho jaate hain, aap GPU Architecture par graduate karte ho. Jab woh chhote rehte hain lekin independent hote hain, Instruction-Level Parallelism slack pick up karta hai.

Recall Self-test

Clean $n = 8000$ ka ideal speedup 8-wide AVX par ::: exactly 8 $n = 10003$ , $w = 8$ ke liye vector instructions plus scalar tail ::: 1250 vector + 3 scalar $250 + 30$ 8-bit wrapping add mein ::: 24 $250 + 30$ saturating add ke saath ::: 255 $1920 \times 1080$ grayscale frame brighten karne ke liye NEON instructions ::: 129600