nordisk/facett

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).

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).