CPU & Computer ArchitectureSIMD & VectorizationHard

Implement SIMD Operations Using SSE2 Intrinsics

Master the fundamental concepts of simd & vectorization through this focused micro-challenge.

~90 minutes SIMD & Vectorization Ready to learn

Topic Overview

128-bit SIMD with SSE2

SSE2 extends x86 registers to 128 bits (__m128i, __m128d). Intrinsics map directly to instructions like PADDQ and MULPD, giving deterministic vector code without inline assembly.

c
Loading…

Alignment and Types

Aligned loads: _mm_load_si128 requires 16-byte alignment
Unaligned: _mm_loadu_si128 for heap buffers
Horizontal sum: need shuffle/add steps to fold vector to scalar

For example, adding four 32-bit integers in one instruction uses one __m128i chunk instead of four scalar adds.

For this exercise, you will rewrite the scalar loop using SSE2 integer or double intrinsics. This task asks you to verify results bit-identical to scalar code before claiming speedup.

Working Through the Exercise

Keep the relevant datasheet, ISA manual, or architecture textbook chapter open while you implement. When your output disagrees with the reference trace on the same program, the bug is usually a mis-decoded opcode, a stale register read, or a flag bit left unchanged after arithmetic.

Trace first: walk one failing input by hand before changing random lines
Read the manual: skim the official doc for the mechanism named in this task
Compare baselines: save measurements from the prior step so speedups are honest

For this exercise, you will use those habits while implementing the requirement in the starter code. Microarchitectural product names change across CPU generations, but the control ideas (fetch, bypass, cache lines, vector lanes) stay stable enough to debug from first principles.

Implementation Task

Your Task

Vectorise element-wise add and mul on int32 arrays the way SSE2 code must: 4 lanes per 128-bit register, with scalar code before the vector loop until the pointer is 16-byte aligned (the prologue), aligned vector operations in the middle, and scalar code for the remainder after it (the epilogue). Verify the vector result against the scalar one and count the instructions saved.

Input

One experiment per line: run OP N OFFSET. OP is add or mul, 1 ≤ N ≤ 100000, and OFFSET is the address of a[0] modulo 16 (a multiple of 4: 0, 4, 8 or 12). The arrays a, b, c share that alignment.

Data and kernel

a[i] = 3i − 7, b[i] = (i mod 11) − 5, and c[i] = a[i] OP b[i] in 32-bit wrap-around arithmetic.

Loop structure

prologue: P = ((16 − OFFSET) mod 16) / 4 scalar elements, at most N.
vector body: V = ⌊(N − P) / 4⌋ chunks of 4 lanes, all aligned.
epilogue: the remaining E = N − P − 4V elements, scalar.

The scalar version costs N operations and the SIMD version P + V + E.

Output

c
Loading…

Print the first min(N, 8) results. The checksum is the 64-bit sum of all c[i]. If the vector result ever differed from the scalar one it would print (MISMATCH), so a correct solution always prints matches scalar.

Example

Input:

c
Loading…

Output:

c
Loading…

Requirements

The vector body processes 4 lanes per step: SSE2 intrinsics (_mm_loadu_si128, _mm_add_epi32, …) or GCC vector types both work. OFFSET is simulated, your real arrays have their own alignment, so use the unaligned load/store forms in your program; only the prologue/body/epilogue counts follow OFFSET.
SSE2 has no 32-bit low multiply (_mm_mullo_epi32 is SSE4.1). If you use intrinsics for mul, build it from _mm_mul_epu32 and shuffles, or multiply lanes in scalar code.

Hidden tests cover every offset, N smaller than the prologue, and large arrays where the prologue and epilogue are negligible.