SIMD

SIMD is a data-level parallelism architecture where a single machine instruction operates on multiple data elements concurrently. Unlike MIMD (Multiple Instruction, Multiple Data) which executes different instructions on different data, SIMD applies one operation—such as addition or multiplication—across a vector of values in a single clock cycle. This is implemented in modern CPUs via vector processing units with register widths like 128-bit (SSE), 256-bit (AVX2), and 512-bit (AVX-512), allowing simultaneous computation on 4, 8, or 16 single-precision floats respectively.

In vector search, SIMD accelerates the core bottleneck: distance calculations between query and database vectors. Libraries like FAISS and ScaNN use hand-tuned SIMD intrinsics to compute Euclidean distance, inner product, or cosine similarity on batches of dimensions simultaneously. For example, a 128-dimensional float vector can be processed in 8 chunks of 16 using AVX-512, reducing the instruction count by an order of magnitude compared to scalar loops. This is critical for brute-force search and product quantization decoding.

Developers access SIMD capabilities through two primary paths:

• Compiler auto-vectorization: Modern compilers like GCC and Clang automatically transform scalar loops into SIMD instructions when safe, requiring no code changes but limited by aliasing and dependency constraints.
• Explicit intrinsics: Low-level functions like _mm256_add_ps that map directly to AVX instructions, giving engineers precise control over register allocation and data alignment. Libraries like sse2neon bridge x86 SIMD to ARM NEON for cross-platform deployment.
• High-level wrappers: Abstractions like Google's Highway library provide portable SIMD across architectures.

A critical SIMD instruction for vector search is Fused Multiply-Add, which computes (a × b) + c in a single operation with a single rounding step. This is the atomic unit of dot product computation. On AVX2 and AVX-512, FMA instructions double the throughput of multiply-add sequences, directly accelerating inner product and matrix multiplication kernels. FAISS heavily leverages FMA for both exact search and product quantization distance lookups, achieving near-peak theoretical FLOPs on modern CPUs.

GPUs extend the SIMD paradigm to SIMT (Single Instruction, Multiple Threads), where warps of 32 threads execute the same instruction on different data elements. NVIDIA's Tensor Cores apply SIMD-like operations on 4×4 matrix tiles in a single cycle, accelerating the matrix multiplications at the heart of transformer attention and embedding generation. In vector search, GPU-accelerated libraries like RAFT and FAISS GPU use these capabilities to perform brute-force search over millions of vectors in microseconds.

SIMD performance is highly sensitive to memory alignment. Loading unaligned data into SIMD registers incurs penalties or requires slower unaligned load instructions. Vector search libraries carefully align embedding arrays to 32-byte or 64-byte boundaries and structure data in Struct-of-Arrays (SoA) layout rather than Array-of-Structs to enable contiguous, coalesced SIMD loads. Cache-friendly access patterns that minimize TLB misses and leverage prefetching are essential to keeping SIMD execution units fed with data.

The compiler-driven process of transforming scalar code into SIMD instructions. Auto-vectorization analyzes loops for data independence and emits packed arithmetic operations. Manual vectorization uses intrinsics—C functions mapping directly to assembly instructions like _mm256_add_ps for AVX—to guarantee throughput. Key considerations include memory alignment to 32-byte or 64-byte boundaries and avoiding gather/scatter operations that break contiguous access patterns.

Intel's 512-bit SIMD instruction set extension processing 16 single-precision floats per cycle. Critical for vector distance calculations in FAISS and ScaNN. Features include mask registers for conditional execution without branching and VNNI (Vector Neural Network Instructions) for accelerating INT8 convolution operations. Adoption is limited by downclocking—the CPU reduces frequency when executing heavy 512-bit workloads to manage thermals.

ARM's 128-bit SIMD architecture mandatory in AArch64 processors. Operates on 32 registers, each holding four 32-bit floats. Heavily leveraged in mobile and edge ML inference for matrix multiplication and activation functions. The vaddq_f32 intrinsic performs four parallel additions. Apple's AMX (Apple Matrix coprocessor) extends NEON with a dedicated systolic array for teraflops-scale operations on M-series chips.

NVIDIA's Single Instruction, Multiple Thread (SIMT) model generalizes SIMD by grouping 32 threads into a warp executing in lockstep. Unlike CPU SIMD, SIMT hides memory latency through zero-overhead context switching between warps. CUDA cores operate on scalar registers, but the warp scheduler broadcasts one instruction across all lanes. Divergence occurs when threads within a warp hit different branch targets, serializing execution and reducing throughput.

Hand-tuned assembly routines exploiting SIMD to compute L2 distance, inner product, and cosine similarity on packed vectors. FAISS implements fvec_L2sqr using AVX2 to process 8 floats simultaneously:

• Load 8 query components into a YMM register
• Broadcast and subtract from 8 database components
• Fused multiply-add to accumulate squared differences
• Horizontal reduction via _mm256_hadd_ps These kernels achieve >90% of theoretical peak FLOPS on modern x86 processors.

SIMD throughput often exceeds memory subsystem capacity, creating a compute-bound vs. memory-bound tradeoff. The roofline model visualizes this: a kernel's operational intensity (FLOPS/byte) determines whether it's limited by peak compute or DRAM bandwidth. Vector search is typically memory-bound—distance kernels apply few operations per byte loaded. Solutions include prefetching via _mm_prefetch intrinsics and cache blocking to reuse data in L1/L2 caches.