Vector - SIMD instructions (SSE, AVX, NEON)

6.1.11 · Hardware › Parallelism & Multicore

Overview

SIMD (Single Instruction Multiple Data) ek parallel execution model hai jisme ek instruction multiple data elements par simultaneously operate karta hai. Modern CPUs is cheez ko vector instruction sets jaise SSE, AVX (x86), aur NEON (ARM) ke through implement karte hain.

YE KYUN ZAROORI HAI: Arrays/matrices ke elements ko loop mein ek-ek karke process karna slow hota hai. SIMD tumhe 4, 8, ya 16 elements ek hi cycle mein process karne deta hai, aur media, ML, signal processing, aur scientific computing ke liye 4×–16× speedup deliver karta hai.

[!intuition] Core Idea

Socho tum ek cashier ho jo prices add kar raha hai:

• Scalar tarika: Ek-ek price add karo: $3+$5 + $2+$7 = ... (4 steps)
• SIMD tarika: Char prices line up karo, ek hi step mein charon ko simultaneously add karo

CPUs ye kaam special wide registers (128-bit, 256-bit, 512-bit) se karte hain jo multiple numbers packed karke rakhte hain. Ek instruction unhe saare ek saath add/multiply/compare karta hai.

Key constraint: Saare data elements pe same operation honi chahiye (yahi "Single Instruction" wala part hai). Arrays ke liye perfect hai, irregular workloads ke liye nahi.

[!definition] SIMD Architecture Components

1. Vector Registers

Wide registers jo multiple scalar values hold karte hain:

• SSE (Streaming SIMD Extensions): 128-bit XMM registers → 4×32-bit floats ya 2×64-bit doubles
• AVX (Advanced Vector Extensions): 256-bit YMM registers → 8×32-bit floats
• AVX-512: 512-bit ZMM registers → 16×32-bit floats
• NEON (ARM): 128-bit Q registers → 4×32-bit ya 16×8-bit

2. Vector Instructions

Har instruction vector register ke saare lanes par operate karta hai:

ADDPS xmm0, xmm1  ; Add 4 packed single-precision floats
MULPD ymm2, ymm3  ; Multiply packed double-precision floats

3. Data Packing

Elements memory mein contiguously store hote hain, aur ek hi operation mein vector registers mein load ho jaate hain:

Memory: [a0, a1, a2, a3] → XMM0 = [a0|a1|a2|a3]

[!formula] SIMD Speedup Derivation

YE KYUN DERIVE KARTE HAIN? Ye samajhne ke liye ki SIMD kab aur kitna help karta hai.

Starting Point: Scalar Execution Time

$n$ elements ke liye, har ek $t$ cycles leta hai: $T_{\text{scalar}}=n\cdot t$

SIMD Execution Time

Vector width $w$ ke saath (elements per register):

• Elements per instruction: $w$
• Number of vector instructions: $\lceil n/w\rceil$
• Har vector instruction: $t$ cycles (same latency, lekin $w$ elements process karta hai)

$T_{\text{SIMD}}=\lceil n/w\rceil \cdot t$

CEILING KYUN? Partial vectors ko bhi ek poori instruction chahiye.

Theoretical Speedup

$S=\frac{T_{\text{scalar}}}{T_{\text{SIMD}}}=\frac{n\cdot t}{\lceil n/w\rceil \cdot t}\approx \frac{n}{n/w}=w$

Bade $n$ ke liye jahan $n\gg w$: $\boxed{S\approx w}$

ISKA MATLAB:

• AVX 256-bit registers se 32-bit floats process karte waqt: $w=8$ → 8× speedup
• AVX-512: $w=16$ → 16× speedup

Reality check: Actual speedups 3×–6× hote hain kyunki:

• Memory bandwidth bottlenecks hote hain
• Unaligned data ko extra shuffles chahiye hote hain
• Loop overhead aur scalar remnants hote hain

[!example] Example 1: Vector Addition (SSE)

Task: Do arrays of 4 floats add karo: a[] + b[] = c[]

Scalar Code (pseudo-assembly)

for i = 0 to 3:
    load a[i] → register1
    load b[i] → register r2
    add r1, r2 → r3
    store r3 → c[i]

Cycles: 4 iterations × (2 loads + 1 add + 1 store) = ~16 operations

SSE Code

movaps xmm0, [a]     ; Load all 4 floats from a[] into xmm0
movaps xmm1, [b]     ; Load all 4 floats from b[] into xmm1
addps  xmm0, xmm1    ; Add all 4 pairs simultaneously
movaps [c], xmm0     ; Store all 4 results

Cycles: 2 loads + 1 add + 1 store = ~4 operations → 4× faster

YE KYUN KAAM KARTA HAI:

• movaps = move aligned packed single-precision (16-byte alignment chahiye)
• addps = add packed single-precision, ek instruction se saare 4 lanes par parallel operate karta hai
• CPU ke vector ALU mein 4 parallel adders hain, jo ek instruction se fed hote hain

[!example] Example 2: Dot Product (AVX)

Task: $\mathbf{a}\cdot \mathbf{b}={\sum }_{i=0}^7{a}_i\cdot b_i$ compute karo (8 floats)

Derivation from Scalar Operations

Step 1: Element-wise multiply $[a_0{b}_0,a_1{b}_1,..,a_7{b}_7]$

Step 2: Horizontal sum $\text{sum}=a_0{b}_0+a_1{b}_1+...+a_7{b}_7$

AVX Implementation

vmovaps ymm0, [a]      ; Load 8 floats from a
vmovaps ymm1, [b]      ; Load 8 floats from b
vmulps  ymm2, ymm0, ymm1   ; ymm2 = [a0*b0, a1*b1, ..., a7*b7]

YE STEP KYUN? Humne 8 multiplications ko 1 instruction mein parallelize kar diya.

; Horizontal add: sum all 8 lanes
vextractf128 xmm3, ymm2, 1  ; Extract upper 4 elements
vaddps xmm2, xmm2, xmm3     ; Add lower 4 + upper 4 →4 sums
vhaddps xmm2, xmm2    ; Horizontal add twice
vhaddps xmm2, xmm2    ; Final sum in xmm2[0]

HORIZONTAL ADDS KYUN? Vector registers lanes ke across automatically sum nahi karte. Hum manually reduce karte hain: 8 → 4 → 2 → 1.

Performance: Scalar loop: 8 muls + 7 adds = 15 ops. AVX: 1 mul + 4 reduce ops ≈ 3× faster.

[!example] Example 3: Image Brightness (NEON on ARM)

Task: 16 pixels ki brightness ko 20 add karke badhao (8-bit values).

NEON Code (intrinsics)

uint8x16_t pixels = vld1q_u8(image_ptr);  // Load 16 bytes
uint8x16_t brightness = vdupq_n_u8(20);   // Duplicate 20 into all 16 lanes
uint8x16_t result = vqaddq_u8(pixels, brightness);  // Saturating add
vst1q_u8(output_ptr, result);             // Store 16 bytes

SATURATING ADD (vqadd) KYUN? Regular add wrap karta hai: 250 + 20 = 14 (overflow). Saturating add clamp karta hai: 250 + 20 = 255 (max pe cap).

Performance: 16 pixels 4 instructions mein vs. 16 scalar add/clamp operations.

[!mistake] Common Mistakes

Mistake 1: Data Alignment Ignore Karna

Galat soch: "Main koi bhi address SIMD registers mein load kar lunga."

float *ptr = malloc(17);  // Not 16-byte aligned!
__m128 vec = _mm_load_ps(ptr);  // CRASH or slow unaligned trap

Ye sahi kyun lagta hai: Regular loads kisi bhi address se kaam karte hain.

Fix:

• _mm_loadu_ps() use karo (unaligned load, slower but safe)
• YA data align karo: float *ptr = aligned_alloc(16, 64);

ALIGNMENT KYUN ZAROORI HAI: CPU memory ko cache-line-sized chunks (64 bytes) mein fetch karta hai. Aligned loads ek chunk fetch karte hain; unaligned do fetch kar sakta hai, jo bandwidth double kar deta hai.

Mistake 2: Loop Remainders Handle Na Karna

Galat soch:

for (int i = 0; i < n; i += 8) {
    process_8_elements_AVX(arr + i);
}
// Agar n=10 ho, toh last 2 elements IGNORE ho jaate hain!

Ye sahi kyun lagta hai: Fast path par focus rehta hai.

Fix:

int simd_count = (n / 8) * 8;
for (int i = 0; i < simd_count; i += 8) {
    process_8_elements_AVX(arr + i);
}
// Scalar cleanup
for (int i = simd_count; i < n; i++) {
    process_1_element(arr[i]);
}

Steel-man: Scalar tail inefficient lagta hai, lekin correctness > speed. Modern compilers aksar ise auto-vectorize kar dete hain.

Mistake 3: Branchy Code ke Liye SIMD Use Karna

Galat soch: "SIMD use karo: if (a[i] > 0) b[i]++; else b[i]--;"

Ye sahi kyun lagta hai: Ye ek array par loop hai!

Problem: SIMD ke liye zaroori hai ki saare lanes same instruction execute karein. Branches ise tod dete hain. Tumhe chahiye hoga:

1. Vector compare → mask
2. Vector increment
3. Vector decrement
4. Mask se results blend karo

Result: Overhead ki wajah se scalar code se bhi slow ho jaata hai.

Fix: SIMD data-parallel, branch-free code ke liye kaam karta hai. Control-heavy loops ke liye scalar use karo.

[!recall]- Feynman Explanation (Ek 12 saal ke bachhe ko samjhao)

Socho tum ek teacher ho jo 16 math tests grade kar rahe ho. Normally, tum ek-ek karke grade karte ho — answer padhte ho, sahi/galat mark karte ho, agla test. Computers bhi aise hi kaam karte hain: ek baar mein ek number.

Lekin agar tumne ek magic table bana li jahan tum 16 tests side-by-side rakhte ho, aur jab tum "CORRECT" stamp karo toh wo magically saare 16 par ek saath stamp ho jaata hai? Yahi SIMD hai!

Computer mein special super-wide calculators hote hain (jaise ek calculator jo 4 regular calculators ko jokar banaya gaya ho). Tum usme 4 numbers load karte ho, "+" press karte ho, aur wo instantly saare 4 pairs add kar deta hai.

Catch: Saare 4 numbers ko same kaam karna hoga. Pehli pair add, doosri multiply, aur teesri subtract nahi kar sakte. Sabke liye same operation. Isliye iska naam "Single Instruction, Multiple Data" hai.

Games is cheez ka use graphics fast draw karne ke liye karte hain (lakhon pixels mein colors add karte hain). Tumhare phone ka camera ise har pixel par ek saath filters apply karne ke liye use karta hai. Jab bhi tumhe ek bade list of numbers par same simple math karna ho, SIMD tumhara dost hai.

[!mnemonic] SIMD Benefits Yaad Karo

"SIMD = Same Instruction, Massive Dividends"

• Speed: Array operations ke liye 4×–16× faster
• Ideal for: Images, Media, Math arrays
• Must be: Memory-aligned, branchless
• Data parallelism: Saare lanes par same op

Instruction sets:

• SSE: Streaming SIMD Extensions (x86, 128-bit)
• AVX: Advanced Vector eXtensions (x86, 256/512-bit)
• NEON: ARM ka jawab ("lights up" mobile performance)

Connections

• Flynn's Taxonomy — SIMD chaar parallel models mein se ek hai (MIMD ke mukable)
• Cache Optimization — SIMD ko cache efficiency ke liye contiguous, aligned data chahiye
• GPU Architecture — GPUs massively-wide SIMD hain (thousands of ALUs)
• Loop Vectorization — Compiler scalar loops ko automatically SIMD mein transform karta hai
• Data Paralelism — SIMD data-parallel algorithms ki hardware implementation hai
• Instruction-Level Parallelism — SIMD superscalar/pipelining ko complement karta hai
• Auto-vectorization — Modern compilers jab safe ho toh SSE/AVX automatically generate karte hain

Key Takeaways

1. SIMD = One Instruction, Multiple Data: Har CPU cycle mein 4–16 elements process karo
2. Teen major ISAs: SSE (128-bit), AVX (256/512-bit x86), NEON (128-bit ARM)
3. Ideal workloads: Dense arrays, no branches, har element par same operation
4. Speedup formula: $S\approx w$ jahan $w$ vector width hai (elements per register)
5. Critical requirements: Data alignment, loop remainders handle karna, branch-free code
6. Real-world uses: Image/video processing, neural networks, physics simulations, audio DSP

Key Takeaways

1. SIMD = One Instruction, Multiple Data: Har CPU cycle mein 4–16 elements process karo
2. Teen major ISAs: SSE (128-bit), AVX (256/512-bit x86), NEON (128-bit ARM)
3. Ideal workloads: Dense arrays, no branches, har element par same operation
4. Speedup formula: $S\approx w$ jahan $w$ vector width hai (elements per register)
5. Critical requirements: Data alignment, loop remainders handle karna, branch-free code
6. Real-world uses: Image/video processing, neural networks, physics simulations, audio DSP

#flashcards/hardware

SIMD ka full form kya hai aur core idea kya hai? :: Single Instruction Multiple Data — ek instruction wide vector registers use karke multiple data elements par simultaneously operate karta hai.

Concept Map