SIMD — vector instructions, SSE - AVX: Exercises

Before we start, two pieces of shorthand we will lean on constantly:

The figure below draws exactly this picture: a 256-bit shelf sliced into 8 coloured f32 boxes. Look at the yellow double-arrow marking the full width $W = 256$ ; each box is 32 bits ( $e$ ), so counting the boxes gives $256/32 = 8$ lanes. Keep this image in mind — every "how many lanes?" problem is just re-counting boxes on this shelf.

Figure — SIMD — vector instructions, SSE - AVX

L1 — Recognition

Recall Solution 1.1

256 bits ⇒ AVX/AVX2 ⇒ ymm. The mnemonic from the parent note: SSE 128 (xmm), AVX 256 (ymm), AVX-512 512 (zmm) — the numbers literally double. 256 sits in the middle, so it is AVX, register name ymm0–ymm15.

Recall Solution 1.2

addps = packed single → operates on all lanes at once.
addss = scalar single → touches only lane 0, ignores the rest.

A 128-bit SSE register holds $128/32 = 4$ floats, so addps is the one that does 4 additions in a single instruction. addss does exactly 1.

Recall Solution 1.3

ps = packed single = 32-bit float (f32)
pd = packed double = 64-bit float (f64)
b = byte = 8-bit integer
w = word = 16-bit integer
d = dword = 32-bit integer
q = qword = 64-bit integer

L2 — Application

Recall Solution 2.1

Divide $W = 512$ by each element size $e$ : $\frac{512}{32} = 16 (f32), \frac{512}{64} = 8 (f64), \frac{512}{8} = 64 (int8)$ $\frac{512}{16} = 32 (int16), \frac{512}{32} = 16 (int32), \frac{512}{64} = 8 (int64)$ Notice: halve the element size ⇒ double the lanes. int8 (8 bits) gives the most lanes (64) because each element is smallest.

Recall Solution 2.2

Full vectors process 8 at a time. Using floor (round down — see the definition above), the number of full iterations is $⌊ \frac{100}{8} ⌋ = 12 (covers 12 \times 8 = 96 elements) .$ The leftover tail is the remainder, i.e. mod: $100 mod 8 = 100 - 96 = 4 elements.$ So 12 vector iterations + a 4-element scalar tail loop. The tail exists because 100 is not a multiple of 8.

Recall Solution 2.3

Ideal speedup $\leq$ lane count $= W / e$ .

SSE f64: $128/64 = 2$ → up to 2×.
AVX f64: $256/64 = 4$ → up to 4×.

Doubles are twice as wide as floats, so you get half the lanes and half the ceiling of the f32 case.

L3 — Analysis

Recall Solution 3.1

Amdahl's law for the vectorized fraction (see Amdahl's Law): $Speedup = \frac{1}{( 1 - f ) + \frac{f}{lanes}} = \frac{1}{0.1 + \frac{0.9}{8}} = \frac{1}{0.1 + 0.1125} = \frac{1}{0.2125} \approx 4.71 \times .$ Even with 8 lanes, the sticky 10% serial part chops you from 8× down to ~4.7× — barely more than half of the "obvious" answer. The serial fraction dominates once the parallel part is fast.

Recall Solution 3.2

This is a Roofline question (see Memory Bandwidth and the Roofline Model).

Memory ceiling: $50 GB/s \div 12 bytes/elem = 4.17 \times 1 0^{9}$ elements/s.
Compute ceiling: $200 GFLOP/s \div 1 flop/elem = 2.0 \times 1 0^{11}$ elements/s.

The smaller ceiling wins: $4.17 \times 1 0^{9} ≪ 2.0 \times 1 0^{11}$ , so the loop is memory-bound. You get ~4.17 billion elements/s, roughly 48× below the compute ceiling. Adding more SIMD lanes here does almost nothing — you must feed the bytes faster. This is exactly the parent note's warning that "AVX is not always 8× faster."

Recall Solution 3.3

A single running total creates a dependency chain: iteration $k + 1$ 's add cannot start until iteration $k$ 's add finishes. If one float add has latency $L$ cycles, $N$ adds take $\approx N \cdot L$ cycles even though the adder could accept a new op every cycle.

Eight independent lanes give eight independent chains. While lane 0's add is in flight, lanes 1–7 are also adding — the pipeline stays full, so throughput ≈ 1 add/cycle instead of 1 add per $L$ cycles. We pay the expensive cross-lane fold only once, at the end. This is latency-hiding via independent work.

L4 — Synthesis

Recall Solution 4.1

Follow the parent note's fold. The split step is the one to get right: a 256-bit ymm is two stacked 128-bit halves, and you name each half with a specific intrinsic:

__m128 lo = _mm256_castps256_ps128(acc);   // lanes 0..3 — a free "reinterpret", no instruction
__m128 hi = _mm256_extractf128_ps(acc, 1); // lanes 4..7 — extract the UPPER 128 bits (index 1)

_mm256_castps256_ps128 is a zero-cost cast: it just tells the compiler "treat the low 128 bits as an xmm," emitting no instruction. _mm256_extractf128_ps(acc, 1) is a real instruction that copies the upper 128-bit half (the 1 selects the high half; 0 would re-select the low half) into an xmm. Now both halves are 128-bit __m128 values, and we combine:

s = _mm_add_ps(lo, hi) → 4 sums: ${p_{0} + p_{4}, p_{1} + p_{5}, p_{2} + p_{6}, p_{3} + p_{7}}$ . (1 op)
s = _mm_hadd_ps(s, s) → pairwise: lane0 $= (p_{0} + p_{4}) + (p_{1} + p_{5})$ , lane1 $= (p_{2} + p_{6}) + (p_{3} + p_{7})$ . (2nd op)
s = _mm_hadd_ps(s, s) → lane0 $=$ everything $= p_{0} + p_{1} + \dots + p_{7}$ . (3rd op) Then float total = _mm_cvtss_f32(s); reads lane 0.

Total = 3 reduction ops (1 add + 2 hadd), producing $\sum_{k = 0}^{7} p_{k}$ in lane 0. The tree halves the count each step ( $8 \to 4 \to 2 \to 1$ ), which is why it takes $lo g_{2} 8 = 3$ combining steps.

The figure below draws this fold as a binary tree. Read it top to bottom: the 8 blue circles are the starting partials $p_{0} .. p_{7}$ ; the first (pink) row is the 4-lane add that pairs $p_{k}$ with $p_{k + 4}$ ; the yellow row is the first hadd; the single off-white node at the bottom is the total in lane 0. Notice each row has half the nodes of the one above — that halving is exactly why the count of combining steps is $lo g_{2} 8 = 3$ , matching the op count in the solution.

Recall Solution 4.2

_mm256_load_ps needs address % 32 == 0. The C standard only promises that malloc returns memory aligned for any fundamental object type — that guarantee is at least alignof(max_align_t), which is commonly 16 bytes but is not required to be 32. So a malloc'd buffer is not guaranteed to be 32-byte aligned; its base (and hence &a[i]) may land at any 4-byte-aligned offset (a float is 4 bytes). Wherever that offset is not a multiple of 32, the aligned load faults: $address mod 32 \neq = 0 \Rightarrow fault .$ Of the 8 possible 4-byte-aligned offsets ${0, 4, 8, 12, 16, 20, 24, 28}$ within a 32-byte window, only offset $0$ is safe — so 7 of 8 offsets crash. See Cache and Alignment. Fixes: (a) use _mm256_loadu_ps (unaligned, tolerates any address, equal speed on modern CPUs), or (b) explicitly request 32-byte alignment with aligned_alloc(32, ...) / posix_memalign so the base is guaranteed 32-byte aligned — never rely on malloc happening to over-align.

Recall Solution 4.3

Throughput $\propto lanes \times clock$ .

AVX2: $8 \times 3.0 = 24.0$ (lane·GHz).
AVX-512: $16 \times 2.1 = 33.6$ (lane·GHz).

Ratio $= 33.6/24.0 = 1.4$ . AVX-512 wins by 1.4× here — because the doubled lanes (2×) more than offset the 30% clock loss (×0.7): $2 \times 0.7 = 1.4$ . The parent note's warning ("bigger isn't always better") bites only when the downclock is steeper than the lane gain — e.g. if AVX-512 dropped below $1.5$ GHz, AVX2 would win.

L5 — Mastery

Recall Solution 5.1

(a) Floating-point addition is not associative (see Floating Point Representation): $(x + y) + z$ can round differently from $x + (y + z)$ because each + rounds its intermediate result to the nearest representable f32. The 8-lane fold groups additions into a tree, changing which intermediates get rounded, so the last bit(s) of the total may differ from the scalar left-to-right order. Neither is "wrong" — they're differently-rounded valid answers.

(b) Because reordering changes results, a standards-conforming compiler must preserve the exact scalar order by default, which forbids the parallel tree. Only when you promise you don't care — -ffast-math (or -fassociative-math) — will Auto-vectorization and the Compiler reorder the additions and emit the SIMD reduction. Fine for graphics/ML; dangerous where bit-exact reproducibility is required.

Recall Solution 5.2

Replace lanes in Amdahl's law by the achievable per-part speedup $s = 3$ (bandwidth-capped): $Speedup = \frac{1}{( 1 - f ) + \frac{f}{s}} = \frac{1}{0.05 + \frac{0.95}{3}} = \frac{1}{0.05 + 0.31667} = \frac{1}{0.36667} \approx 2.73 \times .$ So despite 8 lanes on paper and 95% vectorizable code, the real win is only ~2.7×, because (i) the vector part hits the memory wall at 3×, and (ii) the last 5% serial part still costs. This is the honest, layered answer the parent note keeps pointing at: apply the ceilings in order — lane count first, then the Roofline bandwidth cap to get the achievable per-part speedup, and only then Amdahl for the whole program. Skipping straight to "8×" would have overstated the win by nearly 3×.

Recall Solution 5.3

Throughput $= lanes \times clock \times parallel units$ (1 op/cycle).

AVX-512 core: $16 \times 3.0 \times 1 0^{9} \times 1 = 4.8 \times 1 0^{10}$ elem/s.
GPU: $32 \times 1.4 \times 1 0^{9} \times 80 = 3.584 \times 1 0^{12}$ elem/s.

Ratio $= 3.584 \times 1 0^{12} /4.8 \times 1 0^{10} \approx 74.7 \times$ . The GPU wins ~75× at peak. The architectural idea: massive replication of SIMD lanes across many schedulers — SIMT is "SIMD width × huge thread/warp count." The CPU spends silicon on caches and out-of-order logic; the GPU spends it on more lanes. (Real workloads narrow this gap via memory limits and PCIe transfer — the same Amdahl's Law and Memory Bandwidth and the Roofline Model caveats apply.)

Where to go next

Recall What you should now be able to do

Count lanes for any width/type from $W / e$ and sanity-check any "how many at once?" claim.
Predict full-vector iterations plus the scalar tail for any array length.
Layer the three ceilings in order — lane count → Roofline bandwidth → Amdahl — to get an honest speedup, not the marketing "8×".
Reason about alignment faults, AVX-512 downclocking, float-reduction reproducibility, and the SIMD→SIMT scale-up.

Next steps: revisit the parent SIMD topic note and re-read its "steel-manned mistakes" now that you've computed the numbers behind them. Then push outward: Memory Bandwidth and the Roofline Model to formalise the bandwidth wall, Auto-vectorization and the Compiler to let the compiler emit these loops for you, and GPU SIMT to see the same lane idea replicated thousands of times.

Active recall — quick self-check

Recall Lanes for AVX-512 with int16, and why?

$512/16 = 32$ . Each int16 is 16 bits; count how many 16-bit boxes fit in the 512-bit shelf.

Recall Full vector iterations + tail for

$n = 100$ , AVX f32? $⌊ 100/8 ⌋ = 12$ vector iterations; $100 mod 8 = 4$ scalar tail elements.

Recall Why fold with a tree of

$lo g_{2} (lanes)$ steps? Each combining step halves the number of partials ( $8 \to 4 \to 2 \to 1$ ), so 8 lanes need exactly 3 combining ops.

Recall When does AVX-512 lose to AVX2?

When the downclock is steeper than the lane gain: $\frac{lanes _{512}}{lanes _{256}} < \frac{f _{256}}{f _{512}}$ .