simd vectorization techniques

**SIMD Vectorization Techniques** are **methods for exploiting Single Instruction Multiple Data parallelism by processing multiple data elements simultaneously using wide vector registers and specialized instructions** — modern CPUs with AVX-512 can process 16 single-precision floats or 64 bytes per instruction, delivering 8-16× throughput improvement over scalar code for data-parallel workloads. **SIMD Instruction Set Evolution:** - **SSE (128-bit)**: Streaming SIMD Extensions process 4 floats or 2 doubles per instruction — introduced in 1999, still the baseline for x86 SIMD compatibility - **AVX/AVX2 (256-bit)**: Advanced Vector Extensions double the register width to 8 floats or 4 doubles — AVX2 adds integer operations and fused multiply-add (FMA) for 2× throughput over SSE - **AVX-512 (512-bit)**: processes 16 floats, 8 doubles, or 64 bytes per instruction — includes mask registers for predicated execution, scatter/gather for non-contiguous memory access, and conflict detection - **ARM NEON/SVE**: NEON provides 128-bit fixed-width SIMD, SVE (Scalable Vector Extension) supports variable-length vectors from 128 to 2048 bits — SVE code adapts automatically to hardware vector width **Auto-Vectorization (Compiler-Driven):** - **Loop Vectorization**: the compiler transforms scalar loops into SIMD operations — analyzes data dependencies, memory access patterns, and control flow to determine vectorizability - **Vectorization Reports**: GCC -fopt-info-vec, Clang -Rpass=loop-vectorize, ICC -qopt-report=5 generate reports explaining why loops were or weren't vectorized — essential for diagnosing missed optimizations - **Aliasing Issues**: pointers that might alias (point to overlapping memory) prevent vectorization — restrict keyword (__restrict__) or #pragma ivdep tells the compiler that pointers don't alias - **Alignment**: aligned memory access (_mm256_load_ps) is faster than unaligned (_mm256_loadu_ps) on some architectures — alignas(32) or posix_memalign ensures 32-byte alignment for AVX **Intrinsics Programming:** - **Load/Store**: _mm256_load_ps loads 8 floats from aligned memory into a __m256 register, _mm256_store_ps writes back — fundamental operations for moving data between memory and vector registers - **Arithmetic**: _mm256_add_ps (addition), _mm256_mul_ps (multiplication), _mm256_fmadd_ps (fused multiply-add) — FMA computes a×b+c in a single instruction with single rounding, improving both performance and accuracy - **Shuffle/Permute**: _mm256_shuffle_ps, _mm256_permute_ps rearrange elements within vector registers — critical for matrix transposition, horizontal reductions, and AoS-to-SoA conversion - **Comparison/Masking**: _mm256_cmp_ps generates a mask from element-wise comparisons, _mm256_blendv_ps selects elements based on a mask — enables branchless conditional logic within vectors **Common Vectorization Patterns:** - **Array Reduction**: sum/min/max of an array — accumulate partial results in a vector register, then perform a horizontal reduction (log2(lane_count) shuffle-and-add operations) at the end - **Stencil Computation**: slide a window across data using shift and blend operations — process N elements per iteration where N is the vector width - **Lookup Table**: _mm256_i32gather_ps loads non-contiguous elements using index vectors — enables vectorized hash table probes and histogram updates - **String Processing**: _mm256_cmpeq_epi8 compares 32 bytes simultaneously against a target character — used in memchr, strlen, and JSON parsing for 10-20× speedup over scalar **Performance Pitfalls:** - **Data Layout**: Array of Structures (AoS) forces gather/scatter operations that are 4-8× slower than contiguous loads — Structure of Arrays (SoA) layout enables direct vector loads - **Horizontal Operations**: operations across vector lanes (horizontal add, broadcast from one lane) are typically 3-5× slower than vertical (element-wise) operations — restructure algorithms to maximize vertical operations - **Frequency Throttling**: AVX-512 instructions cause CPU frequency reduction (100-200 MHz on many Intel processors) due to power consumption — the throughput benefit must exceed the frequency penalty - **Remainder Handling**: when array length isn't a multiple of vector width, the remaining elements require either scalar processing, masked operations (AVX-512), or padding — masked stores prevent out-of-bounds writes **SIMD vectorization is one of the most impactful single-core optimizations available — a well-vectorized inner loop on AVX-512 hardware processes 16× more data per cycle than scalar code, and when combined with multi-threading, achieves near-theoretical-peak CPU throughput for compute-bound workloads.**