Vector - SIMD instructions (SSE, AVX, NEON): Visual walkthrough

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

Yeh page parent note ka central result — SIMD aapka loop kitna fast bana deta hai? — bilkul zero se rebuild karti hai. Har symbol ko use karne se pehle hum usse earn karenge, aur har step ko ek blueprint figure milti hai jise aap point kar sako.

Agar aapne abhi tak bada idea nahi dekha, toh pehle parent topic padho. Ek sentence jo aapko saath rakhni hai: ek instruction ek saath kaafi saare numbers par kaam karti hai. Neeche sab kuch us sentence ko ek formula mein convert karta hai.

Definition Shuru karne se pehle ground rules

Do assumptions jinpar hum poori tarah rely karenge, pehle hi bata dete hain taaki kuch secretly andar na aaye:

Array non-empty hai: $n \geq 1$ . Agar $n = 0$ hai toh kuch process karna hi nahi hai, scalar aur SIMD dono ka time $0$ hai, aur ratio $S = 0/0$ undefined hai (aur meaningless — aap kuch nahi karne ko speed up nahi kar sakte). Toh hum hamesha $n \geq 1$ lete hain, ek whole number.
Ek vector instruction utne hi cycles leti hai jitne ek scalar instruction. Scalar cost ko $t_{scalar}$ aur vector cost ko $t_{vector}$ bolte hain. Real vector ALUs $w$ parallel adders ke saath bane hote hain jo ek instruction se feed hote hain, toh "8 floats multiply karo" essentially utna hi cost karta hai jitna "1 float multiply karo" — kaam side by side hota hai, ek ke baad ek nahi. Isliye hum $t_{vector} = t_{scalar}$ set karte hain aur shared value ko simply $t$ bolte hain. Yahi ek assumption poore speedup ka engine hai; agar yeh fail ho jaaye, toh SIMD kuch bhi nahi deta.

Step 1 — Kaam ko slow tarike se count karo (scalar)

KYA. Ek scalar loop numbers ko ek ek karke touch karta hai. Socho $n$ numbers ka ek array ek row mein rakha hai. Machine us row par chalti hai, har step mein exactly ek box handle karti hai.

KYUN. Pehle hume ek fair baseline chahiye: ek-ek karke kaam karne ki honest cost. Bina "slower" ke compare kiye "faster" measure nahi kar sakte.

PICTURE. Neeche, har amber box ek array element hai. Safed arrow ek ek box visit karta hai. Arrow-visits ginlo — wahi hamara workload hai.

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

Cheezein carefully name karte hain:

$n$ ::: array mein kitne numbers hain (yahan $n = 8$ ; hamesha $n \geq 1$ ). Yeh sirf ek count hai — koi unit nahi.
$t$ ::: ek element mein kitne CPU cycles lagte hain — yeh wahi shared $t = t_{scalar} = t_{vector}$ hai ground rules se. Ek box = $t$ ticks.

"Boxes ki sankhya" ko "ticks per box" se multiply karo:

$T_{scalar} = kitne elements n \cdot ticks each t$

$T_{scalar}$ scalar loop ka total time (cycles mein) hai. Yahi hamara baseline hai.

Step 2 — Numbers ko ek wide register mein pack karo

KYA. Ek vector register ek single storage slot hai jo kaafi saare numbers side by side hold karne ke liye wide hota hai. Har side-by-side slot ko hum lane bolte hain. Lanes ki sankhya vector width $w$ hai.

KYUN. SIMD ka poora trick yahi hai. Ek number per haath ki jagah, CPU ek mutthi mein $w$ numbers pakadta hai. Hume $w$ abhi define karna hai kyunki speedup poori tarah isi se bana hoga.

PICTURE. Ek lamba cyan register $w = 4$ lanes mein split hua, har ek mein ek number. Ek load instruction ek baar mein charon lanes fill kar deti hai.

$w$ ::: vector width — ek register mein ek saath kitne numbers fit hote hain. Yeh hardware par depend karta hai, aapke data par nahi.

Parent note se concrete values, taaki $w$ abstract na rahe:

Instruction set	Register width	Numbers ( $w$ ) for 32-bit floats
SSE (128-bit)	128 bits	$128/32 = 4$
AVX (256-bit)	256 bits	$256/32 = 8$
AVX-512 (512-bit)	512 bits	$512/32 = 16$

Yeh seedha data parallelism se jodta hai: same operation, bahut saare independent data items, lanes ke beech koi baat nahi.

Step 3 — Kaam ko fast tarike se count karo (SIMD)

KYA. Ek SIMD instruction poore register ko — saare $w$ lanes ko — usi $t$ cycles mein process karta hai jo ek scalar op ne liye the (yahi hamara ground-rule assumption $t_{vector} = t_{scalar}$ tha). Toh $n$ single steps ki jagah hum $w$ ke groups lete hain.

KYUN. Yahan saving aati hai. Agar har instruction abhi bhi $t$ cycles leti hai lekin ab $1$ ki jagah $w$ boxes clear karti hai, toh hume bahut kam instructions chahiye.

PICTURE. Wahi 8 boxes, lekin ab do groups of four mein bracket kiye gaye hain. Har bracket ek instruction hai.

Hume kitne groups chahiye? Boxes ko lanes se divide karo: $n / w$ . Picture mein $8/4 = 2$ groups. Toh pehla guess hai:

$T_{SIMD} \approx groups ki sankhya \frac{n}{w} \cdot ticks each group t$

Lekin $n / w$ whole number nahi ho sakta — aap "aadha instruction" nahi chala sakte. Ise hum agle step mein theek karte hain.

Step 4 — Ceiling: partial groups ka bhi ek poora instruction lagta hai

KYA. Symbol $⌈ x ⌉$ (ceiling) ka matlab hai " $x$ ko agla whole number tak round up karo." Toh $⌈ 2.0 ⌉ = 2$ , lekin $⌈ 1.25 ⌉ = 2$ aur $⌈ 0.1 ⌉ = 1$ .

KYUN. Ek register instruction poore register par fire hoti hai chahe sirf ek lane mein real data ho. $w = 8$ ke saath das elements ko $⌈ 10/8 ⌉ = ⌈ 1.25 ⌉ = 2$ instructions chahiye: 8 ka ek full group, plus bache hue 2 ke liye ek aur instruction (baaki 6 lanes waste hain lekin phir bhi "saath chal rahe hain").

PICTURE. Das boxes, $w = 4$ . Group 1 aur Group 2 full hain; Group 3 sirf half-full hai lekin phir bhi ek poore instruction ka cost hai (iski empty lanes amber mein shaded hain = waste).

Toh honest SIMD time hai:

$T_{SIMD} = groups, rounded up ⌈ \frac{n}{w} ⌉ \cdot ticks each t$

$⌈ n / w ⌉$ ::: actually issue ki gayi vector instructions ki sankhya, kabhi fraction nahi.

Step 5 — Speedup ratio banao

KYA. Speedup $S$ define hota hai "purana time naaye time se divide karo." Agar naya tarika aadha time leta hai, $S = 2$ (do baar faster).

KYUN. Ratio "kitni baar faster" kehne ka natural tarika hai. Yeh "cycles" unit cancel kar deta hai, ek pure multiplier chhodta hai jise aap " $8 \times$ " bol sako.

PICTURE. Do horizontal time-bars scale par khinche: lamba scalar bar, chhote SIMD bar ke upar. $S$ literally "chhoti bar lamba bar mein kitni baar fit hoti hai" hai.

$S = \frac{T _{scalar}}{T _{SIMD}} = \frac{n \cdot t}{⌈ n / w ⌉ \cdot t}$

Dhyaan do ki upar aur neeche $t$ ek hi $t$ hai — yahi precisely hamara ground rule $t_{vector} = t_{scalar}$ hai: ek element utna hi cost karta hai chahe woh akela ride kare ya ek lane mein. Toh yeh cancel ho jaate hain:

$S = \frac{n \cdot t}{⌈ n / w ⌉ \cdot t} = \frac{n}{⌈ n / w ⌉}$

$t$ ka gayab hona key insight hai: speedup depend nahi karta ki operation kitni expensive hai — sirf ek lane mein kitne elements share karte hain. (Yeh cancellation sirf tab legal hai jab $t \neq = 0$ , jo hold karta hai kyunki $n \geq 1$ matlab real kaam exist karta hai.)

Step 6 — Large-array limit: kyun S → w

KYA. Jab $n$ , $w$ se bahut bada ho (likha $n ≫ w$ ), ceiling khas matter nahi karti — ek waste partial group haazaron full groups par ek rounding blip hai. Toh $⌈ n / w ⌉ \approx n / w$ .

KYUN. Yeh woh clean headline number deta hai jo log quote karte hain. Hum ceiling drop karte hain kyunki bade data ke liye yeh answer ko bahut saari instructions mein se ek se bhi kam badalta hai.

PICTURE. Ek curve: $S$ plot kiya $n$ ke against $w = 8$ ke liye. Origin ke paas sawtooth karta hai (ceiling effects) phir dashed amber line $S = 8$ ki taraf flatten hota hai.

$S = \frac{n}{⌈ n / w ⌉} n ≫ w \frac{n}{n / w} = \frac{n \cdot w}{n} = w$

$S \approx w$

MATLAB KYA HAI. Best jo aap hope kar sakte ho woh lanes ki sankhya ke barabar speedup hai: SSE par $4 \times$ , AVX par $8 \times$ , AVX-512 par $16 \times$ . Yahi woh ideal hai jise Loop Vectorization aur Auto-vectorization chase karte hain.

Step 7 — Edge aur degenerate cases

KYA. Formula $S = n / ⌈ n / w ⌉$ exact hai aur $n \geq 1$ ke saath har input cover karta hai. Corners chalte hain taaki kuch surprise na kare.

KYUN. Parent note " $4 \times$ – $16 \times$ " ideal ke roop mein quote karta hai lekin reality mein " $3 \times$ – $6 \times$ ". Gap poori tarah inn edge cases mein rehta hai. Jo reader sirf $S \approx w$ dekhe woh real benchmarks se shock ho jaata; hum abhi woh defuse karte hain.

PICTURE. Char mini-panels, ek per case, har ek mein box layout aur uska $S$ show hai.

Case $n = 0$ (empty array). Hamara ground rule isse rule out karta hai — koi kaam nahi, koi speedup nahi, $S = 0/0$ undefined hai. Kuch draw karne ko nahi.
Case $n = w$ (exactly ek full register). $S = w / ⌈ 1 ⌉ = w /1 = w$ . Full speed, koi waste nahi.
Case $n < w$ (lanes se kam elements, jaise $n = 3, w = 8$ ). $S = 3/ ⌈ 3/8 ⌉ = 3/1 = 3$ . Aap phir bhi ek instruction issue karte ho lekin sirf $3$ lanes real data carry karti hain — speedup $3$ hai, $8$ nahi. Tiny arrays ideal tak nahi pahunch sakti.
Case $n = 1$ (ek single element). $S = 1/ ⌈ 1/ w ⌉ = 1/1 = 1$ . Bilkul koi speedup nahi — SIMD scalar mein degenerate ho jaata hai, aur setup overhead ise slower bana sakta hai.
Case "not divisible" (jaise $n = 10, w = 8$ ). $S = 10/2 = 5$ , ideal $8$ se neeche kyunki doosri instruction mein lanes waste hain (parent note ka remainder problem).

Real speedup $3$ – $6$ par kyun aata hai $w$ ki jagah — memory bandwidth, unaligned loads, scalar tails — yeh sab is arithmetic ceiling ke upar practical ceiling hain. Memory bandwidth particularly Cache Optimization se jodti hai: agar data kaafi fast nahi aa sakta, extra lanes idle baithte hain.

Ek-picture summary

KYA. Ek blueprint jo poori chain compress karta hai: $n$ boxes ki scalar row, $⌈ n / w ⌉$ registers mein grouping, do time-bars, aur woh ratio jo $t$ cancel hone ke baad bachta hai — $S \approx w$ par khatam.

KYUN. Taaki poora argument aapke dimaag mein ek single image ki tarah rahe, saat scattered ones ki tarah nahi. Jab baad mein yaad aaye "SIMD $w$ times faster kyun hai?", yeh picture replay karni chahiye: same kaam, kam presses, time-per-press cancel, sirf lane-count bachti hai. Poore page ka payload ek nazar mein yahi hai.

Recall Feynman retelling

Socho ek row of chocolates jo tumhe wrap karni hai. Unhe ek ek karke wrap karne mein utni hi moves lagengi jitni chocolates hain — yeh hai $T_{scalar} = n \cdot t$ , jahan $t$ ek wrap ka time hai. (Aur kam se kam ek chocolate chahiye, $n \geq 1$ — empty row wrap karna "faster" nahi hai, woh bas kuch nahi hai.)

Ab tumhe ek magic tray milti hai jo ek single press mein $w$ chocolates wrap karti hai — aur crucially, ek press utna hi time leta hai jitna ek chocolate haath se wrap karna, kyunki tray apne saare slots ek saath kaam karti hai. Tum $w$ ek baar mein load karte ho, toh button sirf $⌈ n / w ⌉$ baar press karte ho — upar round off karke kyunki half-full tray ko bhi ek poora press chahiye. Yeh hai $T_{SIMD}$ .

"Kitni baar faster?" bas purana time naaye time ke upar hai. Time-per-press $t$ dono mein appear karta hai, toh cancel ho jaata hai — matlab yeh matter nahi karta ki wrapping fast hai ya slow, sirf yeh kita tray mein kitne fit hote hain. Aap ke paas bachta hai $S = n / ⌈ n / w ⌉$ .

Agar tumhare paas bahut saari chocolates hain, toh odd leftover tray barely matter karti hai aur answer exactly tray size par settle ho jaata hai, $S \approx w$ : ek 8-lane tray 8× faster hai. Lekin sirf ek chocolate ke saath, tray tumhe kuch nahi deti ( $S = 1$ ), aur ek leftover handful ke saath wasted tray slots tumhe ideal se neeche kheench dete hain. Yahi gap — plus real-world snags jaise data bahut slowly aana — wahi hai jo shiny "8×" ko practice mein solid "5×" bana deta hai.

Recall Quick self-check

Speedup mein $t$ kyun cancel hota hai? ::: Kyunki humne assume kiya tha ki ek vector instruction utne hi $t$ cycles leti hai jitne ek scalar instruction ( $t_{vector} = t_{scalar}$ ); ratio sirf elements ki count vs. instructions rakhta hai, toh $t$ divide ho jaata hai. $n = 10$ , $w = 8$ ke liye $S$ kya hai? ::: $S = 10/ ⌈ 10/8 ⌉ = 10/2 = 5$ . Ideal speedup exactly $w$ kyun hai? ::: Kyunki $n ≫ w$ ke saath, $⌈ n / w ⌉ \approx n / w$ , aur $n \div (n / w) = w$ . $n = 1$ hone par kya hota hai? ::: $S = 1/ ⌈ 1/ w ⌉ = 1$ — koi speedup nahi; SIMD scalar mein collapse ho jaata hai. $n \geq 1$ kyun hona chahiye? ::: $n = 0$ ke liye dono times $0$ hain aur $S = 0/0$ undefined hai — aap koi kaam nahi karne ko speed up nahi kar sakte.