# Force layout — the two-lane engine (GPU-when-available / gatling-CPU) — design
> **Class:** `design` · **Function axis:** `f0` the whole two-lane layout · `f1` the CPU
> gatling lane (parallel forest build + fused FR step) · `f2` the parallel-attraction
> schemes (gather vs `gatling_reduce` scatter-reduce) · `f3` the GPU lane (wgpu
> `cs_layout`) + runtime selection · `f4` the benchmark + Loki numbers · `f5` the new
> znippy `gatling_reduce` primitive.
> Strict: every claim points at a real `file:line`. rayon is FORBIDDEN — gatling only.
## f0 — the whole
The force-directed layout is the one expensive layout `facett_graphnav` offers, and it
runs **converge-once-then-freeze**: `GraphNav::positions()`
(`facett-graphnav/src/lib.rs:1148`) caches the converged positions keyed on the graph's
structural signature and only re-runs when the structure changes. This design makes that
**one-time converge cost snappy at 30 000 nodes** via **two interchangeable layout
backends**, runtime-selected:
- **GPU lane** — when built `--features gpu` AND a usable wgpu adapter exists at runtime,
the layout runs entirely in VRAM on the wgpu compute engine
(`facett-graphview/src/gpu_layout.rs` + `layout.wgsl`).
- **CPU lane** (always built, the deterministic golden) — the Fruchterman–Reingold
driver (`facett-graphnav/src/layout.rs::force_directed`), with **every phase** fanned
across all cores through znippy **gatling** (`../../znippy-zoomies`).
Selection lives in `layout::force_selected` (`facett-graphnav/src/layout.rs`): the `Force`
arm tries the GPU lane (`#[cfg(feature="gpu")]` + a runtime adapter probe) and falls
through to the CPU lane on a GPU-less box, so the default build + every determinism/golden
test runs the CPU reference unchanged.
## f1 — the CPU gatling lane
The old driver ran the 120-iteration FR loop with **only repulsion** parallel; the
per-edge **attraction** and per-node **integrate** ran single-core, and — the real stall —
`NBodyTree::build` ran **serial every iteration** (~40 % of the repulsion cost, measured).
The rewrite makes a step exactly **two core-saturating passes**:
1. **Parallel forest build** — `NBodyTree::build_parallel` (`facett-core/src/barnes_hut.rs`)
partitions space into a fixed grid of `(2^D)^pd` buckets, builds every bucket's subtree
**on its own core** (`gatling_for_each` over buckets), and keeps them as a **forest of
arenas** — no serial splice/copy. Determinism: bodies fold into a bucket in ascending
global-index order and the arenas stay in bucket order, so the field is byte-stable for
any worker count. `force()` walks each arena with a fixed per-root DFS.
2. **Fused per-node pass** — `barnes_hut::fr_step` does, in ONE `gatling_for_each` over the
`n` nodes: the Barnes–Hut repulsion query + the attraction gather + the
temperature-capped integrate. Each node is written by exactly one worker → disjoint,
hazard-free, deterministic.
The only serial residue left is the O(n) bounds + bucketing + grouping inside the build
(cheap; a `gatling_reduce` bounds fold was measured net-negative at ≤100k — the min/max is
too cheap to beat the per-iteration thread-spawn, see `root_bounds`).
## f2 — the parallel-attraction schemes (gather vs scatter-reduce)
The attraction phase has a **write hazard**: each edge `(a,b)` writes `disp[a]` AND
`disp[b]`, so a naive `gatling_for_each` over edges would race. Two correct, deterministic
solutions were built and benchmarked:
- **Gather (shipped, `fr_step`)** — flip the loop: each node `i` *gathers* the spring pull
from its incident edges (pre-built `adjacency`, fixed neighbour order). Disjoint output,
no partial buffers, and it **fuses** with repulsion+integrate into one pass. This is the
"disjoint node-range ownership" scheme.
- **Scatter-reduce (`fr_step_scatter`, `CpuLane::GatlingScatter`)** — keep the per-edge
scatter but give each worker a **private** displacement buffer, then merge the buffers
deterministically. This is expressed with the **new znippy `gatling_reduce` fold
primitive** (f5). It does the edge-distance work once per edge (vs twice for the gather)
but needs `workers` full-size partial buffers + a merge pass, so it is **three passes**,
not two.
**Measured:** the gather wins for the sparse graphs a graph-navigator shows (30k: gather
~577 ms vs scatter ~786 ms), so the gather is the shipped default; the scatter-reduce is
the tested, wired, benchmarked comparison lane (it would win on dense/high-degree graphs).
Both match the serial reference within float tolerance and both saturate ~9.7/12 cores.
## f2b — the serial mirror + the shared box-fit (dedup cluster J)
The single-core / small-graph FR step and the box-fit rescale used to be **re-inlined per
leaf** — the duplication audit's cluster J. They now live ONCE in
`facett-core::barnes_hut`, so the FR loop body exists in exactly one place per lane:
- **`fr_step_serial`** — the serial twin of `fr_step`: exact O(n²) all-pairs repulsion
below `BH_THRESHOLD` (keeps the small-graph exact reference), serial Barnes–Hut above,
then the SAME per-node attraction *gather* + temperature-capped integrate as the gatling
step. THREE production drivers now share this ONE loop body, each passing its own
`k`/`temp`; the inline exact loops are all gone:
- `facett-graphnav::layout`'s serial lane (2-D);
- `facett-graph3d::callgraph_layouts::force2d` (2-D, `temp=16.0`);
- `facett-graph3d::lib::Graph3D::layout` → `Layout3D::Force` — the **PRIMARY 3-D graph
layout** (production, `temp=0.04`, `adjacency(n, &self.edges)`). This was a SECOND full
inline FR loop that survived the first cluster-J pass (the verifier's find, 2026-07-29):
it ran `fr_step::<3>` at scale and `fr_step_serial::<3>` below threshold — the exact same
delegation `force2d` uses — so it keeps core-saturation at scale (five-zeros) and stays
on the exact serial reference below threshold.
All three seed on a ring/sphere, so none reaches the coincident-node degeneracy discussed
below; every structural/snapshot golden (graph3d: 81 lib + render_callchain + dataset_volume
+ neon/rabbit/travels PNGs — none of which pin an exact `Layout3D::Force` position) stays green.
- **`normalize_box`** — the `[-0.9,0.9]²` aspect-preserving box-fit (`*1.8` centre-and-divide).
Was byte-identical in THREE leaves; all now delegate to the core one:
`facett-graphnav::layout::normalize`, `facett-graphview::world::normalize` (its own comment
said "matches the navigator's normalize"), and — the second cluster-J survivor the verifier
found — `facett-graphview::gpu_layout::gpu::normalize_box` (the GPU-lane box-fit at
`force_layout_gpu_on`, `#[cfg(feature="gpu")]`), which was byte-identical to core's.
`facett-graphview::gpu_layout::step_cpu` is deliberately NOT folded in — it is a genuinely
different velocity+damping+gravity+mass model (the WGSL `cs_layout` CPU-parity mirror), not
the temperature-capped FR step, so it stays its own home.
### The coincident-node behavior change (deliberately documented, NOT patched)
The pre-dedup graphnav/`force2d` inline loops carried a `dist < 0.01` deterministic-jitter
branch that nudged near-coincident nodes apart. `fr_step_serial` (and `fr_step`) instead
clamp the pairwise distance to `MIN_DIST` (1e-3) and let the **zero direction vector** of an
*exactly* coincident pair carry a zero push — so two nodes at the identical position stay
stuck, where the old code would have separated them. This is **safe for every shipped
caller**: all seed on a ring/sphere (no two nodes coincident at the seed), and near- but not
exactly-coincident nodes still get a huge (clamped-`dist²`) repulsion that flings them apart,
so only the measure-zero *exact* coincidence is affected — which no seed and no golden hits.
A minimal restore would trigger only on `d2 == 0.0` (never on the old `< 0.01` threshold,
which fires for near-coincident pairs that DO occur mid-converge and would perturb existing
byte-exact goldens), and would have to inject a deterministic non-zero direction into the hot,
now-shared core kernel used by all three drivers. That ADDS code to core for a case the shipped
seeds provably never reach, against the "don't add code that isn't needed" rule. Decision:
**left as-is and documented here.** If a future caller seeds nodes at identical positions
(e.g. a streamed graph that places new nodes on top of a parent), separate them in the SEED,
not in the shared step.
## f3 — the GPU lane + runtime selection
The wgpu compute engine already existed (`gpu_layout.rs`, `layout.wgsl`, entry `cs_layout`,
ping-pong VRAM buffers, an O(n²) inverse-square repulsion + Hooke springs + gravity,
velocity-integrated) with a `step_cpu` parity reference — but was **unused** by the
navigators. It is wired in as a layout backend (L5 reuse — consumed, not rewritten):
- `gpu_layout::gpu_layout_available()` — the runtime adapter probe (compute shaders + ≥4
storage buffers).
- `gpu_layout::force_layout_gpu_on(device,queue,n,edges,iters)` — the **warm-device** front
door (a wgpu host already holds a live device): stream a CSR, iterate `cs_layout` in
VRAM, read back, fit to `[-1,1]²`. `force_layout_gpu` is the one-shot wrapper that also
creates the device.
The GPU model integrates velocity, so it **settles fast**: total edge length is within
~5 % of converged by ~60–80 steps (400 was overkill), so `FORCE_ITERS_GPU = 80`. The GPU
lane may differ from the CPU lane in float-reduction order, so the equivalence test is
**bbox/topology-preserving** (`gpu_front_door_lays_out_in_box_and_contracts_edges`), NOT
byte-equality; the step-level `gpu_layout_matches_cpu_reference` proves `cs_layout ==
step_cpu`. The CPU lane stays the deterministic golden.
## f4 — the benchmark + Loki numbers
`facett-graphnav/examples/force_bench.rs` measures a FULL 120-iteration converge for
n ∈ {10k, 30k, 100k} across: (a) single-core serial baseline, (b) the gatling gather lane
(+ core-saturation from `/proc/self/stat`), (b2) the gatling scatter-reduce lane, (c) the
GPU warm lane. **Machine: Loki (Ryzen 9 7900, 12c/24t, 64GB, RTX 5080).**
| n | serial (1 core) | gatling CPU | speedup | cores busy | scatter-reduce | GPU warm (80 it) |
|--:|--:|--:|--:|--:|--:|--:|
| 10 000 | 1032 ms | 208 ms | 5.0× | 8.9 | 297 ms (8.5c) | 97 ms |
| 30 000 | 3727 ms | 577 ms | 6.5× | 9.8 | 786 ms (9.7c) | 295 ms |
| 100 000 | 14 920 ms | 1980 ms | 7.5× | 10.2 | 2616 ms (10.4c) | 1422 ms |
One-time GPU device init ≈ 240 ms (paid once per process; a wgpu host already has a live
device). **Hot-phase** core saturation (isolated: parallel build + fused query) measures
**10.0/12 at 30k, 10.7/12 at 100k** — single-core repulsion 21.1 ms/call → parallel
3.5 ms/call (6×); the whole-run 9.7–10.2 average includes the per-iteration serial O(n)
build bookkeeping (Amdahl residue).
**Snappy verdict** (bar: a 30k one-time converge well under a second): **hit on both
lanes** — CPU gatling 577 ms (7× faster than the 3.7 s single-core baseline), GPU warm
295 ms (and 10k in 97 ms, under the aggressive 150 ms bar). At 30k the O(n log n) CPU lane
is competitive with the O(n²) GPU lane; the GPU's edge is a warm device fully offloading
the 12 CPU cores, and it scales further once a GPU Barnes–Hut lands (roadmap in
`facett-graphview/.nornir/elite-graph-engine.md`).
## f5 — the new znippy `gatling_reduce` primitive
The znippy gatling surface had only element-wise primitives (`gatling_for_each` /
`gatling_run` / `_balanced` / `gatling_map_*` / `gatling_scanlines`) — none expresses a
**fold / scatter-reduce** (combine across indices, or scatter into overlapping slots).
So a new primitive was invented in `znippy-zoomies/gatling/src/gatling_forkjoin.rs`:
gatling_reduce(n, n_workers, init, fold, merge) -> A
`workers` fixed contiguous partitions, each folded into a **private** accumulator, then
merged in **ascending partition order** — deterministic (reproducible run-to-run). It is
the reduction sibling of `gatling_for_each`, rayon-free scoped threads. RED-when-broken
tests: `reduce_matches_serial_fold_all_worker_counts` and (the write-hazard case)
`scatter_reduce_matches_serial_scatter`. facett consumes it in `fr_step_scatter` (the
attraction scatter-reduce lane, f2).