Implement Efficient Dot Product Using SIMD

Topic Overview

Dot Product with FMA

A dot product sums element-wise products: sum(a[i]*b[i]). SIMD loads chunks, multiplies, and accumulates in a vector register; horizontal reduction produces the final scalar.

cCopy
Loading…

Reduction Tree

Fold acc with _mm256_hadd_ps or extract 128-bit lanes and add serially. FMA (a*b+c in one op) saves latency on Intel since Haswell.

For example, dotting length-8 float vectors needs one FMA and a short horizontal add instead of eight multiplies and seven scalar adds.

For this exercise, you will implement SIMD dot product and validate against a double-precision reference sum. This task asks you to report numeric error bounds for float accumulation order differences.

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.

Your Task

Vectorise a dot product. The multiplies parallelise trivially. The sum doesn't: a SIMD version keeps 4 or 8 partial sums (one per lane) and adds them together at the end with a horizontal reduction. That changes the order of floating-point additions, so the vector results differ slightly from the scalar one. Compare all three against a double-precision reference to see how big the difference is, and in which direction.

Input

One experiment per line: dot N SEED (1 ≤ N ≤ 100000).

Data

Generate a then b with one generator: x = (x · 1103515245 + 12345) mod 2^31 starting from x = SEED, advanced before every value. Each value is ((x >> 8) mod 2001 − 1000) / 1000, computed in float (a[0], a[1], …, a[N−1], then b[0], …).

Four results

• reference: double products, summed in double in index order.
• scalar: float; s = s + a[i]·b[i] in index order.
• sse (4 lanes): for the first 4·⌊N/4⌋ elements, lane i mod 4 accumulates a[i]·b[i] in float. Reduce as (l0 + l1) + (l2 + l3), then add the remaining elements in index order.
• avx (8 lanes): the same with 8 lanes, reduced as ((l0 + l1) + (l2 + l3)) + ((l4 + l5) + (l6 + l7)).

Every product is rounded to float before it is added. Do not fuse multiply and add.

Output

cCopy
Loading…

Values use six decimals, errors are |result − reference| in %.2e format. Print a blank line between experiments.

Example

Input:

cCopy
Loading…

Output:

cCopy
Loading…

Requirements

1. The vector versions keep one accumulator per lane and reduce with the exact pairing above. Intrinsics (_mm_mul_ps, _mm_add_ps, shuffles for the reduction) or GCC vector types both work.
2. Keep multiply and add as separate operations so that no compiler fuses them into an FMA.

Hidden tests cover N below the vector width, a large N where the orderings visibly diverge, and N not a multiple of 8.