Linus Baumberger
3.1 KiB
Optimization: AVX2 vectorization of the ped-ped loop
- Author: Linus
- Predecessor: variant_inlining_7_SoA.cpp
- File(s): variants/variant_inlining_7_SoA_AVX2.cpp
- Status: TBD, positive locally (approx.2 times)
What this changes
First AVX2 pass through the ped-ped inner loop. The j loop strides by
4 and processes 4 pedestrians at once on __m256d registers. SoA from
the predecessor variant is what makes the loads contiguous, otherwise
this would not have been clean to write.
The i == j skip is now a mask instead of continue. I also pad all
the per-pedestrian arrays to a multiple of 4 (n_p_pad) so the loop
doesn't need a scalar tail. Padding positions are set to 1e9 so even
without the mask the lane would contribute ~0 via exp(very negative),
but the mask makes it deterministic. Same mask is also used to zero out
the i==j lane after the body.
The scalar exp() is still called 4 times per j step into a scratch
array.
Code (relevant snippet)
See variants/variant_inlining_7_SoA_AVX2.cpp for the full inner loop.
Structure is: build the active mask from j_idx vs i and n_p, run
the vector body on 4 lanes at a time, blend in a safe denom so the
i==j lane does not produce a NaN, mask the per-lane force contribution,
then accumulate into acc_x and acc_y. After the j loop a horizontal
sum folds the accumulators into the scalar f_alpha_dt.
Benchmark
Conditions: min of N runs (TBD), N_ITER=1000, -O3 -march=native -flto.
Diff is vs variant_inlining_7_SoA.
local runs show a clear speedup over the SoA-only predecessor. exact
numbers TBD on the test machine, but the qualitative picture is that
the 4 scalar exp() calls inside the j loop now dominate.
x86
Machine: TBD
Frequency: TBD
| N | W(n) [Flops] | T(n) [Cycles] | Performance [Flops/Cycle] | Diff vs Predecessor |
|---|---|---|---|---|
| 50 | ||||
| 100 | ||||
| 200 | ||||
| 500 | ||||
| 1000 |
ARM (Apple)
Not applicable, this variant uses AVX2 intrinsics
Analysis
The win comes from doing 4 ped-ped interactions per j step instead of 1.
Loads are contiguous thanks to SoA, and the inner body is mostly
straight-line sub, fmadd, mul, sqrt, one div, plus a blendv
and a couple of cmp/and for the mask. No branches in the j loop
other than the loop counter.
I expected exp() to become the bottleneck once everything around it
was vectorized, and the profile confirmed it. The horizontal sum at the
end of the j loop only happens once per outer iter, not per j step, so
its cost is small.
Takeaway
First real perf jump for the ped-ped force, but limited by the scalar
exp call still inside the loop. Sets up the polyexp variant.