Vectorization and SIMD

Modern processors achieve high throughput not merely by running faster clocks but by doing more work per cycle. While pipelining allows instructions to overlap in time, Vectorization uses Single Instruction, Multiple Data (SIMD) capabilities to overlap execution in space. For a deep learning compiler, mapping scalar mathematical descriptions to these vector units is the single most effective transformation for increasing arithmetic density.

The SIMD Abstraction

In a standard scalar execution model, an operation like adding two arrays involves loading one element from each array, adding them, and storing the result. This process repeats for every element. SIMD architectures introduce vector registers that can hold multiple data elements, lanes, simultaneously.

For instance, a 512-bit register (such as those found in AVX-512 instruction sets) can hold sixteen 32-bit floating-point numbers. A single hardware instruction vaddps triggers the addition of all sixteen pairs in parallel.

To utilize this hardware, the compiler must identify loops where iterations are independent and contiguous. Consider the standard vector addition loop:

$C[i] = A[i] + B[i]$

In a scalar compilation, the CPU executes $N$ load, add, and store sequences. In a vectorized compilation with a vector width of $W$, the CPU executes $N/W$ sequences. The efficiency gain is theoretically linear with the vector width, though memory bandwidth often acts as a saturation point.

Comparison of scalar iterative processing versus parallel SIMD processing for a vector width of 4.

Data Dependencies and Legality

Not all loops are candidates for vectorization. The primary constraint is data dependency. The compiler performs dependence analysis to ensure that the execution of a block of iterations in parallel yields the same result as sequential execution.

The most common blocker is a Loop-Carried Dependency, where an iteration depends on the result of a previous iteration suitable for the same vector block.

Consider the following accumulation:

$A[i] = A[i-1] + B[i]$

Here, $A[i]$ cannot be calculated until $A[i-1]$ is known. This Read-After-Write (RAW) dependency forces sequential execution. However, reductions (like summing an array) are a special case. While they mathematically have dependencies, compilers use tree-based reduction strategies or specific horizontal hardware instructions to vectorize them efficiently.

Memory Alignment and Strides

Vector units operate most efficiently when data is loaded from memory addresses aligned to the vector size (e.g., 64-byte alignment for 512-bit vectors). Unaligned memory access often incurs a performance penalty or requires multiple load instructions to construct a single vector register.

When generating code, the compiler analyzes the memory access pattern, known as the stride.

1. Unit Stride (Stride-1): Elements are contiguous in memory (e.g., A[i], A[i+1]). This allows for efficient block loads.
2. Constant Stride: Elements are spaced regularly (e.g., accessing every 4th element). The compiler may use "gather" instructions, which are significantly slower than block loads.
3. Random Access: Indices are computed dynamically (e.g., A[B[i]]). This usually prevents effective vectorization or requires expensive gather operations that may degrade performance below scalar levels.

Handling Loop Boundaries: Peeling and Tails

Rarely is the loop trip count $N$ a perfect multiple of the vector width $W$. The compiler must generate code to handle the boundaries. This typically results in a three-stage structure:

1. Peeling Loop: If the starting pointer address is not aligned, the compiler may generate a scalar loop that executes the first few iterations until the memory pointer reaches an aligned address.
2. Vector Body: The main kernel executes the bulk of the data using aligned vector instructions.
3. Remainder (Tail) Loop: After the vector body completes, a few iterations may remain ($N \pmod W$). These are executed sequentially or using a masked vector operation.

Modern architectures like SVE (Scalable Vector Extensions) and AVX-512 introduce predicate registers (masks) that allow the vector loop to handle the tail without reverting to scalar instructions, simply by deactivating lanes that correspond to out-of-bounds indices.

Performance drops periodically when the data size is not a multiple of the vector width, forcing the execution of slower scalar tail loops.

Predication and Control Flow

Control flow within a loop (if/else statements) traditionally breaks vectorization because SIMD units share a single instruction pointer. If lane 0 takes the true branch and lane 1 takes the false branch, a standard processor cannot execute both simultaneously.

To resolve this, compilers use predication (or masking). The compiler executes both branches for all lanes but uses a bitmask to commit only the valid results.

For a statement like: $R[i] = (A[i] > 0) \: ? \: B[i] : C[i]$

The vectorized logic proceeds as follows:

1. Compare vector $A$ with 0 to generate a mask $M$.
2. Compute vector $B$ (execute "then" block).
3. Compute vector $C$ (execute "else" block).
4. Merge results using $M$: select from $B$ where $M$ is 1, and from $C$ where $M$ is 0.

This technique, often implemented via vblend or masked move instructions, converts control dependency into data dependency. It preserves parallelism but increases the total instruction count since both paths are effectively calculated.

Lowering to Intrinsics

In frameworks like MLIR or TVM, vectorization is explicit. The high-level schedule defines the vector width, and the lowering pass translates this into hardware-specific intrinsics or LLVM IR vector types.

For example, an MLIR vector.transfer_read operation maps abstract tensor data into a vector register. The subsequent operations work on vector<4xf32> types rather than scalar f32. This ensures that when the code reaches the backend (LLVM), the instruction selector can easily map these operations to the target ISA (Instruction Set Architecture), such as x86 AVX2 or ARM NEON.

Effective vectorization often requires coordination with loop tiling. Tiling ensures data resides in L1 cache, while vectorization ensures that once data is in registers, it is processed at maximum arithmetic intensity.