Linus Baumberger
78 lines
3.1 KiB
Markdown
78 lines
3.1 KiB
Markdown
# 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.
|