Vector - SIMD instructions (SSE, AVX, NEON)

Overview

SIMD (Single Instruction Multiple Data) is a parallel execution model where one instruction operates on multiple data elements simultaneously. Modern CPUs implement this through vector instruction sets like SSE, AVX (x86), and NEON (ARM).

WHY this matters: Processing arrays/matrices element-by-element in loops is slow. SIMD lets you process4, 8, or 16 elements in a single cycle, delivering 4×–16× speedups for media, ML, signal processing, and scientific computing.

[!intuition] The Core Idea

Imagine you're a cashier adding up prices:

• Scalar way: Add one price at a time: $3 +$5 + $2 +$7 = ... (4 steps)
• SIMD way: Line up four prices, add all four simultaneously in one step

CPUs do this with special wide registers (128-bit, 256-bit, 512-bit) that hold multiple numbers packed together. One instruction adds/multiplies/compares ALL of them at once.

The key constraint: All data elements must undergo the same operation (that's the "Single Instruction" part). Perfect for arrays, not for irregular workloads.

[!definition] SIMD Architecture Components

1. Vector Registers

Wide registers that hold multiple scalar values:

• SSE (Streaming SIMD Extensions): 128-bit XMM registers → 4×32-bit floats or 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 or 16× 8-bit

2. Vector Instructions

Each instruction operates on all lanes of the vector register:

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

3. Data Packing

Elements are stored contiguously in memory, loaded into vector registers in one operation:

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

[!formula] SIMD Speedup Derivation

WHY derive this? To understand when SIMD helps and by how much.

Starting Point: Scalar Execution Time

For $n$ elements, each taking $t$ cycles: $T_{\text{scalar}} = n \cdot t$

SIMD Execution Time

With vector width $w$ (elements per register):

• Elements per instruction: $w$
• Number of vector instructions: $\lceil n/w \rceil$
• Each vector instruction: $t$ cycles (same latency, but processes $w$ elements)

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

WHY ceiling? Partial vectors still need a full instruction.

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$

For large $n$ where $n \gg w$: $\boxed{S \approx w}$

WHAT this means:

• AVX with 256-bit registers processing 32-bit floats: $w = 8$ → 8× speedup
• AVX-512: $w = 16$ → 16× speedup

Reality check: Actual speedups are3×–6× due to:

• Memory bandwidth bottlenecks
• Unaligned data requiring extra shuffles
• Loop overhead and scalar remnants

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

Task: Add two arrays of 4 floats: 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

WHY this works:

• movaps = move aligned packed single-precision (requires 16-byte alignment)
• addps = add packed single-precision, operates on all 4 lanes in parallel
• CPU's vector ALU has 4 parallel aders, all fed by one instruction

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

Task: Compute $\mathbf{a} \cdot \mathbf{b} = \sum_{i=0}^{7} a_i \cdot b_i$ (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]

WHY this step? We've paralelized 8 multiplications into 1 instruction.

; 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]

WHY horizontal adds? Vector registers don't automatically sum across lanes. We manually reduce: 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: Increase brightness of16 pixels by adding 20 to each (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

WHY saturating add (vqadd)? Regular add wraps: 250 + 20 = 14(overflow). Saturating add clamps: 250 + 20 = 255 (capped at max).

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

[!mistake] Common Mistakes

Mistake 1: Ignoring Data Alignment

Wrong idea: "I'll just load any address into SIMD registers."

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

Why it feels right: Regular loads work with any address.

The fix:

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

WHY alignment matters: CPU fetches memory in cache-line-sized chunks (64 bytes). Aligned loads fetch one chunk; unaligned may fetch two, doubling bandwidth.

Mistake 2: Not Handling Loop Remainders

Wrong idea:

for (int i = 0; i < n; i += 8) {
    process_8_elements_AVX(arr + i);
}
// If n=10, last 2 elements IGNORED!

Why it feels right: Focus on the fast path.

The 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: The scalar tail seems inefficient, but correctness > speed. Modern compilers often auto-vectorize this.

Mistake 3: SIMD for Branchy Code

Wrong idea: "Use SIMD for: if (a[i] > 0) b[i]++; else b[i]--;"

Why it feels right: It's a loop over an array!

The problem: SIMD requires all lanes execute the same instruction. Branches break this. You'd need:

1. Vector compare → mask
2. Vector increment
3. Vector decrement
4. Blend results with mask

Result: Slower than scalar code due to overhead.

The fix: SIMD works for data-parallel, branch-free code. Use scalar for control-heavy loops.

[!recall]- Feynman Explanation (Explain to a 12-year-old)

Imagine you're a teacher grading 16 math tests. Normally, you grade one at a time—read answer, mark right/wrong, next test. That's how computers usually work: one number at a time.

But what if you invented a magic table where you lay out 16 tests side-by-side, and when you stamp "CORRECT," it magically stamps all 16 at once? That's SIMD!

The computer has special super-wide calculators (like a calculator that's4 regular calculators glued together). You load4 numbers into it, press "+", and it adds all 4 pairs instantly.

The catch: All 4 numbers must do the same thing. You can't add the first pair, multiply the second, and subtract the third. Same operation for everyone. That's why it's called "Single Instruction, Multiple Data."

Games use this to draw graphics fast (adding colors to millions of pixels). Your phone camera uses it to apply filters to every pixel at once. Any time you need to do the same simple math on a huge list of numbers, SIMD is your friend.

[!mnemonic] Remember SIMD Benefits

"SIMD = Same Instruction, Massive Dividends"

• Speed: 4×–16× faster for array operations
• Ideal for: Images, Media, Math arrays
• Must be: Memory-aligned, branchless
• Data paralelism: Same op on all lanes

Instruction sets:

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

Connections

• Flynn's Taxonomy — SIMD is one of the four parallel models (vs MIMD)
• Cache Optimization — SIMD requires contiguous, aligned data for cache efficiency
• GPU Architecture — GPUs are massively-wide SIMD (thousands of ALUs)
• Loop Vectorization — Compiler auto-transforms scalar loops to SIMD
• Data Paralelism — SIMD is the hardware implementation of data-parallel algorithms
• Instruction-Level Parallelism — SIMD complements superscalar/pipelining
• Auto-vectorization — Modern compilers generate SSE/AVX automatically when safe

Key Takeaways

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

Key Takeaways

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

#flashcards/hardware

What does SIMD stand for and what's the core idea? :: Single Instruction Multiple Data — one instruction operates on multiple data elements simultaneously using wide vector registers.

Concept Map

Hinglish (regional understanding)

Hinglish (regional understanding)