SIMD — vector instructions, SSE - AVX — Coding notes

WHY does SIMD exist?

WHAT problem it solves: the instruction overhead per element and under-used wide datapaths.

HOW the hardware does it: the register file is widened (128/256/512 bits). An instruction like addps cuts the register into independent lanes and fires all the adders in parallel — no carry crosses lane boundaries.

Definitions

Formula How many lanes? (derive it, don't memorize)

A register holds a fixed number of bits. An element occupies a fixed number of bits. So: $\text{lanes} = \frac{\text{register width (bits)}}{\text{element size (bits)}}$ Why this is true: packing is just laying elements end-to-end with no gaps. Count how many fit.

Examples (compute, then verify the table): $\frac{128}{32}=4 \text{ floats (SSE)} \qquad \frac{256}{32}=8 \text{ floats (AVX)} \qquad \frac{512}{32}=16 \text{ floats (AVX-512)}$ $\frac{256}{64}=4 \text{ doubles} \qquad \frac{256}{8}=32 \text{ int8} \qquad \frac{512}{16}=32 \text{ int16}$

Figure — SIMD — vector instructions, SSE - AVX

HOW a vector add actually executes

Worked example

c[i] = a[i] + b[i] for 8 floats with AVX

// intrinsics (compiler-portable SIMD)
__m256 va = _mm256_loadu_ps(&a[i]);   // load 8 floats (unaligned ok)
__m256 vb = _mm256_loadu_ps(&b[i]);   // load 8 floats
__m256 vc = _mm256_add_ps(va, vb);    // 8 adds in ONE instruction
_mm256_storeu_ps(&c[i], vc);          // store 8 floats

Why loadu not load? _mm256_load_ps requires a 32-byte-aligned address or it faults; loadu tolerates any address (slightly slower historically, equal on modern CPUs). Why process 8 at a time? $256/32 = 8$ lanes — that's the natural stride. Why a remainder loop is needed: if the array length isn't a multiple of 8, the last len % 8 elements are done with a scalar tail loop.

Worked example The full vectorized loop (with tail)

size_t i = 0;
for (; i + 8 <= n; i += 8) {                 // Why: only step while a full vector fits
    __m256 va = _mm256_loadu_ps(a + i);
    __m256 vb = _mm256_loadu_ps(b + i);
    _mm256_storeu_ps(c + i, _mm256_add_ps(va, vb));
}
for (; i < n; ++i) c[i] = a[i] + b[i];       // Why: scalar tail for leftover elements

Worked example Horizontal reduction — summing an array

Lane-wise ops are easy; combining across lanes ("horizontal") is the tricky part.

__m256 acc = _mm256_setzero_ps();
for (size_t i = 0; i + 8 <= n; i += 8)
    acc = _mm256_add_ps(acc, _mm256_loadu_ps(a + i)); // Why: keep 8 partial sums
// Now fold 8 partial sums -> 1
__m128 lo = _mm256_castps256_ps128(acc);      // lanes 0..3
__m128 hi = _mm256_extractf128_ps(acc, 1);    // lanes 4..7
__m128 s  = _mm_add_ps(lo, hi);               // 4 partial sums
s = _mm_hadd_ps(s, s);                         // pairwise add
s = _mm_hadd_ps(s, s);                         // again -> total in lane 0
float total = _mm_cvtss_f32(s);

Why fold instead of summing each lane in the loop? Keeping 8 independent accumulators avoids a long dependency chain → the CPU pipelines additions; we only pay the expensive cross-lane fold once, at the end.

Steel-manned mistakes

Active recall

Recall How do you compute the number of lanes? (cover and answer)

$\text{lanes} = \dfrac{\text{register width in bits}}{\text{element size in bits}}$ . E.g. AVX (256) with f32 (32) → 8 lanes.

Recall Why isn't real speedup equal to the lane count?

Amdahl's law (non-vectorizable fraction) + memory bandwidth ceiling + setup/tail overhead + possible downclocking.

Recall What is the difference between

addps and addss? addps = packed, adds all lanes; addss = scalar, only lane 0.

Recall Why keep multiple accumulators in a SIMD sum?

To break the dependency chain so additions pipeline; you do the cross-lane fold only once at the end.

Recall Feynman: explain SIMD to a 12-year-old

Imagine a teacher grading papers. Normally she grades one paper at a time. SIMD is like a magic stamp that's 8 stamps wide — she lines up 8 papers and stamps "+5" on all of them in one press. The action (stamp +5) is the same; only the papers differ. So she finishes 8× faster — as long as she can grab 8 papers fast enough off the pile (that's the memory limit!).

Forecast-then-verify drill

Flashcards

What does SIMD stand for?

Single Instruction, Multiple Data — one instruction operates on many packed data elements at once.

128-bit / 256-bit / 512-bit.

xmm (SSE, 128), ymm (AVX, 256), zmm (AVX-512, 512).

Formula for number of lanes?

lanes = register_width_bits / element_size_bits.

Lanes for AVX with f32?

256/32 = 8.

Lanes for AVX-512 with int8?

512/8 = 64.

Difference between addps and addss?

packed (all lanes) vs scalar (lane 0 only).

Why is real speedup less than lane count?

Amdahl's law, memory bandwidth limit, setup/tail overhead, possible downclocking.

Amdahl speedup formula?

1 / ((1-f) + f/lanes), f = vectorizable fraction.

Why need a scalar tail loop?

array length may not be a multiple of the lane count; leftover elements done one at a time.

What is a 'horizontal' operation?

an operation combining values across lanes (e.g. sum all lanes), as opposed to lane-wise vertical ops.

Why keep multiple SIMD accumulators in a reduction?

to break the dependency chain so the additions pipeline; fold once at the end.

What is vzeroupper for?

avoids the costly SSE/AVX (non-VEX/VEX) state-transition penalty.

Why can SIMD float reductions differ from scalar?

float addition isn't associative; lane-grouping reorders adds → different rounding.

loadu vs load (aligned)?

load requires alignment (faults otherwise); loadu allows any address.

Connections

Data-Level Parallelism — SIMD is the in-core form of DLP.
Amdahl's Law — caps achievable speedup.
Memory Bandwidth and the Roofline Model — why compute-bound vs memory-bound decides SIMD payoff.
Cache and Alignment — aligned loads, cache lines vs vector width.
Auto-vectorization and the Compiler — -O3 -march=native, -ffast-math.
GPU SIMT — the GPU cousin (Single Instruction, Multiple Threads).
Floating Point Representation — non-associativity of FP addition.

Concept Map

Hinglish (regional understanding)

Intuition Hinglish mein samjho

Dekho, SIMD ka matlab hai Single Instruction, Multiple Data. Normally ek add instruction sirf ek number add karta hai. Lekin jab tumhe ek poore array pe same kaam karna ho — jaise har pixel ko brighten karna ya do vectors add karna — to har element ke liye alag instruction fetch/decode karna waste hai. SIMD bolta hai: register ko chauda kar do (128, 256, ya 512 bits) aur usme kai numbers "pack" kar do, phir ek hi instruction se saare lanes pe parallel mein operation chala do. SSE = 128-bit, AVX = 256-bit, AVX-512 = 512-bit.

Kitne lanes milenge? Simple: register_width / element_size. AVX (256 bit) mein agar float (32 bit) hai to 256/32 = 8 lanes. Matlab ek instruction mein 8 floats add ho gaye — theoretically 8x speed. Yaad rakho ye theoretical hai. Real life mein Amdahl's law lagta hai (sirf vectorizable hissa fast hota hai) aur zyada baar tumhara loop memory bandwidth se bottleneck hota hai — yaani RAM se data laana hi slow hai, compute nahi. Isiliye blindly "AVX matlab 8x" maan lena galti hai.

Coding mein tum intrinsics use karte ho jaise _mm256_loadu_ps, _mm256_add_ps, _mm256_storeu_ps. Loop ko 8 ke step mein chalao, aur jo bachte hain (length 8 ka multiple nahi) unke liye ek chhota scalar tail loop likho. Ek aur important cheez: array sum (reduction) karte time saare lanes ko end mein ek baar fold karo, beech mein nahi — taaki dependency chain na bane aur pipeline bhar jaaye. Aur dhyan rahe, float addition associative nahi hota, isliye SIMD sum ka rounding scalar se thoda alag ho sakta hai — ML/graphics mein chalega, strict reproducibility mein nahi.

SIMD — vector instructions, SSE - AVX

WHY does SIMD exist?

Definitions

HOW a vector add actually executes

Steel-manned mistakes

Active recall

Forecast-then-verify drill

Flashcards

Connections

Concept Map

Hinglish (regional understanding)

Go deeper — visual, from zero

Test yourself — Computer Architecture (Deep)

Connections