Study guides · Intermediate

SIMD and loop vectorization

Follow contiguous addition through lanes, tails, aliasing and rounding, then verify the transformation using compiler diagnostics and disassembly.

Ask Logeia about this articleTry the three questionsReview your answers

Updated

On this page
  1. Process several elements with one instruction
  2. Map array indices to lanes
  3. Check legality before asking for vectorization
  4. Treat reductions and rounding separately
  5. Read diagnostics and the actual instructions
  6. Separate packed arithmetic from end-to-end speed
  7. Check lane work against nominal traffic
  8. Solve the tail and dependency exercises
  9. Ask Logeia about this articleCheck your understanding

Process several elements with one instruction

SIMD applies one instruction to several data elements. A 128-bit register can hold four 32-bit floating-point elements and add corresponding lanes. This does not create four operating-system threads. Read the CPU and array-layout material first. We trace a contiguous addition through element expressions, generated instructions and leftover elements, keeping SIMD distinct from overlapping multiple instructions through out-of-order execution.

Database vectorized execution introduces another meaning of vector: operators exchange batches of rows to reduce per-row control overhead. A batch of 1,024 rows does not imply a single CPU instruction processes 1,024 values. A loop within the batch may or may not use SIMD. Batch execution, SIMD and multithreading can coexist, but each has its own prerequisites and costs. The existing vectorized-execution article explains the software batch boundary; this guide examines the instruction-level element boundary.

Map array indices to lanes

Compute out[i]=a[i]+b[i] for indices zero through n minus one. With four lanes, the first group loads elements zero through three of each input and writes their four sums. Each output depends only on its two matching inputs. Contiguous elements of one type make such grouping straightforward. Irregular indices or fields separated inside structures may require gathering or additional rearrangement, and those costs belong in the comparison.

For eleven elements and a width of four, two complete groups cover indices zero through seven and leave three elements. A compiler can handle leftovers with scalar instructions, narrower vectors or masks, depending on the instruction set and transformation. Discarding the remainder produces an incorrect result. Reading beyond an allocation is not justified merely because unwanted lanes are ignored later. Establish that every accessed location is valid before timing the implementation. Count processed indices rather than assuming that a vector loop alone covers every possible input length.

Check legality before asking for vectorization

A compiler must preserve the loop's required meaning. If out overlaps a one-element-shifted portion of a, a write in one iteration may change an input read by the next iteration. Loading four old inputs together can then differ from the original sequential update. An experiment using separately allocated arrays has a different contract from an API permitting overlap. Do not request a transformation by simply ignoring that dependency.

The restrict qualifier in the companion experiment communicates an aliasing contract that the caller must satisfy. It is not merely a performance hint that legitimizes overlapping calls. The example allocates all three arrays separately. Calls with unknown effects, loop-carried updates, complicated control flow and insufficient trip count can also affect vectorization. Read optimization diagnostics to distinguish a transformation that is illegal from one the cost model considers unprofitable. Changing compiler flags without understanding the relevant condition can change semantics or fail to solve the actual obstacle.

Treat reductions and rounding separately

Independent element addition differs from reducing an entire array into one sum. Floating-point rounding means (x+y)+z need not equal x+(y+z) bit for bit. Lane-local partial sums followed by a final combination change the addition order. Mathematical associativity does not establish identical machine results. Use the numerical-stability and cancellation material to specify acceptable error and special-value behavior before deciding which transformations are allowed.

Fast-math options can change assumptions about NaNs, infinities and signed zeros as well as reassociation. Do not attach such flags without explanation and report only a speed difference. The companion addition experiment uses small exactly representable inputs and checks every output, including the tail. If an experiment allows fused multiply-add, explain its single rounding and the convention used to count operations. Keep the numerical contract beside the transformation, so a reader can distinguish a faster permitted implementation from one that solved a different problem.

Read diagnostics and the actual instructions

Build the experiment once with GCC -O3 and once with tree vectorization disabled. Optimization diagnostics identify source locations the compiler reports transforming. Disassembly shows the actual called add function, its packed arithmetic and pointer increments. In the x86-64 build used here, inspect packed addps and scalar addss in remainder handling. Other instruction sets use different names, so absence of one x86 mnemonic is not a portable failure test.

Scalar floating-point operations can still use registers belonging to the SIMD register file. Seeing an xmm register therefore does not by itself prove that multiple elements are being added together. Check the operation's lane count and address progression. The experiment length, 1,048,579, is deliberately not divisible by four, requiring a three-element tail. Also verify the call target: correct output from an unused alternate implementation would not establish that the timed function contains the transformation under discussion.

Separate packed arithmetic from end-to-end speed

Replacing four additions with one packed instruction does not guarantee a fourfold speedup. Loading two inputs, storing an output, handling tails, making calls and sharing execution resources all have costs. Setup can dominate a small array; memory bandwidth can dominate a large one. Faster arithmetic then changes only part of the total. The Roofline guide compares computation and data movement bounds in compatible units instead of converting lane width directly into a promised speed ratio.

Time the add call separately from input initialization and result checking. Save first and repeated observations, compiler version, ISA, CPU and length. The virtualized environment verifies generated instructions and correct outputs, but does not measure exclusive bare-metal peak performance or PMU events. Inspect variation rather than selecting favorable samples. Establishing that packed instructions exist is a different conclusion from establishing a particular speed ratio, and the evidence recorded for each should make that difference clear.

Check lane work against nominal traffic

A four-lane float addition nominally reads 32 input bytes and writes sixteen output bytes while performing four additions. Its intensity is four divided by 48, still one twelfth FLOP/B, just like the scalar element calculation. SIMD changes elements per instruction without inherently reducing required array values. Distinguish improved arithmetic execution at equal nominal intensity from layout or reuse changes that reduce actual traffic. Wider lanes do not abolish a matching memory-bandwidth constraint. This calculation also provides a consistency check between the SIMD and Roofline descriptions of the same operation.

Check complete output coverage and the numerical contract before comparing the two instruction paths.

Solve the tail and dependency exercises

With width four and length ten, two full groups process indices zero through seven, leaving indices eight and nine. Index ten is outside the output allocation, so writing it cannot be justified as merely ignoring a remainder. A masked implementation must identify valid lanes and satisfy the target ISA's memory-access rules. Different tail strategies still owe the same contract: all ten required outputs are correct and no invalid storage is accessed.

Now change the computation to out[i]=out[i-1]+a[i]. Each iteration depends on the previous output, so the simple independent grouping no longer applies. A parallel prefix algorithm is a different candidate, requiring renewed checks of work, order and floating-point behavior. Contiguous storage alone does not establish that every loop will receive the same SIMD transformation. Explain element correspondence, dependencies, numerical requirements and generated instructions before progressing to the executable disassembly lab.

Reading and practice are recorded separately in this browser, for each language.

Learn this in order

Build your CS foundations · STEP 7

Prepare for AI systems · STEP 4

Choose a learning path