GALAXY v0.7.0 - GALAXY — Barnes–Hut Self-Gravity and GPU Tree Construction

This release substantially expands GALAXY beyond its established prescribed-field and logical-u64 particle runtimes by adding a separate, opt-in resident self-gravity execution family.

The new Barnes–Hut path progresses from a deterministic CPU reference through Morton-ordered flat trees, executable GPU force traversal, persistent multi-step GPU evolution, and finally GPU-side tree construction.

The existing browser, native CPU, fixed-potential GPU, and logical-u64 execution contracts remain intact.

Major additions

Resident Barnes–Hut self-gravity

Added a deterministic planar Barnes–Hut N-body reference implementation with:

• mutually coupled resident bodies;
• deterministic quadtree construction;
• total-mass and centre-of-mass aggregation;
• classical Barnes–Hut s / d < theta opening control;
• explicit rejection of aggregate cells containing the target body;
• Plummer-style gravitational softening;
• kick–drift–kick leapfrog integration;
• deterministic disc and collision fixtures;
• bounded-depth handling for coincident bodies;
• exact O(N²) direct-force verification.

This execution family is intentionally separate from GALAXY's logical-u64 tiled runtime because self-gravity couples the complete resident population.

Independent direct-force oracle

Added a separate all-pairs force evaluator so the Barnes–Hut approximation does not validate itself.

Validation includes:

• theta-zero parity against direct forces;
• bounded RMS and worst-relative error gates;
• deterministic probe selection;
• bounded direct-force probes for larger workloads;
• explicit avoidance of hidden O(N²) verification costs in high-count GPU runs.

Barnes–Hut browser laboratory

Added a dedicated browser entrypoint:

barnes-hut.html

The laboratory provides:

• live evolving self-gravity;
• quadtree visualization;
• tree-depth overlays;
• force-term accounting;
• direct-force probe audits;
• theta, softening, bucket and timestep controls;
• deterministic seeded presets;
• binary-disc encounter;
• rotating-disc and cold-collapse scenarios.

The visualizer makes the tree approximation and direct-force error surface observable rather than treating Barnes–Hut as a black box.

Native Barnes–Hut CPU runtime

Added the standalone nbody/ Rust crate.

It provides:

• recursive Barnes–Hut reference traversal;
• exact direct-force evaluation;
• deterministic fixtures;
• leapfrog integration;
• checksums;
• force and tree statistics;
• verification commands;
• machine-readable receipts.

New commands include:

verify

run

and later flat-tree verification and probe commands.

BH #2A — Morton / flat-tree substrate

Added a GPU-oriented pointer-free Barnes–Hut representation.

Features include:

• 16-bit-per-axis coordinate quantization;
• 32-bit Morton/Z-order keys;
• stable spatial ordering;
• preservation of resident order for equal Morton keys;
• explicit body-to-Morton-position mapping;
• flat cell arrays;
• explicit u32 child indices;
• contiguous Morton body ranges;
• bottom-up mass and centre-of-mass aggregation;
• iterative stack traversal;
• deterministic topology checksums.

The flat-tree implementation retains f64 arithmetic so topology migration is verified independently from later GPU precision changes.

New flat-tree verification

Added:

verify-flat

and:

flat-probe

These verify:

• theta-zero parity with the direct O(N²) oracle;
• theta-0.5 accuracy;
• agreement with the recursive Barnes–Hut implementation;
• stable equal-key ordering;
• configured maximum-depth handling;
• exact root range and total mass preservation;
• repeatable topology checksums.

Tree construction and traversal timing are reported separately.

BH #2B1 — GPU transfer ABI and force traversal

Added a frozen f32/u32 GPU-facing Barnes–Hut ABI.

Record sizes are explicitly defined for:

• settings;
• resident bodies;
• Morton entries;
• flat cells;
• acceleration outputs.

A canonical packed-byte fixture verifies cross-backend layout consistency.

Vulkan / WGSL Barnes–Hut traversal

Added real Barnes–Hut force traversal through wgpu and WGSL.

The shader performs:

• iterative flat-tree traversal;
• leaf direct-force evaluation;
• Barnes–Hut aggregate acceptance;
• Morton-range self-exclusion;
• deterministic child visitation;
• f32 acceleration output.

This is an actual GPU compute path, not a decorative or disconnected accelerator layer.

CUDA parity surface

Added matched CUDA Barnes–Hut traversal source with:

• equivalent transfer-record layout;
• compile-time size assertions;
• matching traversal semantics;
• target-range self-exclusion.

Host-side CI verifies CUDA ABI/source parity without falsely claiming CUDA execution on non-NVIDIA runners.

GPU traversal verifier

Added:

galaxy-bh-gpu

The verifier reports:

• CPU tree construction;
• f32 packing;
• GPU transfer;
• GPU traversal dispatch;
• GPU readback;
• full GPU-vs-flat-CPU comparison;
• bounded deterministic direct-force probes.

Large particle counts no longer trigger a complete O(N²) CPU solve before GPU execution.

BH #2B2 — evolving GPU self-gravity

Added persistent GPU-resident N-body state.

New GPU state includes:

• position;
• mass;
• velocity;
• persistent acceleration buffers.

Added WGSL integration kernels for:

• half-kick + drift;
• final half-kick.

The resulting multi-step execution contract is:

GPU force -> GPU kick/drift -> tree rebuild -> GPU force -> GPU final kick

Boundary acceleration is reused, so an N-step run performs N+1 force solves, rather than recomputing both force boundaries independently every step.

New evolution executable

Added:

galaxy-bh-evolve

Features include:

• disc and collision presets;
• multi-step GPU evolution;
• persistent GPU state;
• explicit tree-rebuild synchronization boundaries;
• final direct-force probes;
• state and topology checksums;
• conservation diagnostics;
• bounded full CPU trajectory comparison.

Receipts include:

• force-solve count;
• tree-rebuild count;
• topology changes;
• state checksums;
• total mass drift;
• centre-of-mass drift;
• linear-momentum drift;
• angular-momentum drift;
• separate CPU/GPU stage timings.

BH #2C — GPU tree construction

GALAXY now constructs the Barnes–Hut tree on the GPU for the BH #2C execution path.

The device-side tree build performs:

• GPU root-bounds calculation;
• parallel Morton key generation;
• deterministic GPU bitonic ordering;
• resident-body sorted-position assignment;
• flat-cell topology construction;
• bottom-up mass and centre-of-mass aggregation;
• direct hand-off to the existing GPU force traversal.

During BH #2C evolution there are:

• zero host particle readbacks inside the step loop;
• zero CPU tree rebuilds inside the step loop.

The persistent drifted GPU state feeds the GPU tree builder directly.

Deterministic GPU ordering

Morton entries are ordered by:

(Morton code, body index)

This supplies a deterministic total ordering and preserves the intent of the stable host ordering when Morton keys collide.

GPU topology contract

BH #2C intentionally defines a new f32 GPU topology representation rather than claiming bit-identical cell numbering with the f64 host tree.

The GPU tree retains the important scientific invariants:

• contiguous sorted body ranges;
• explicit child links;
• bounded Morton depth;
• target-range membership;
• deterministic ordering;
• bottom-up aggregates.

Correctness is established by force and trajectory comparison against the frozen BH #2A/B2B2 references.

BH #2C verifier

Added:

galaxy-bh-gpu-tree

The verifier performs complete multi-step self-gravity with GPU-built trees and records:

• GPU tree-build count;
• force-solve count;
• zero host rebuild/readback assertions;
• tree buffer sizes;
• cell, leaf and maximum-depth statistics;
• root bounds;
• deterministic repeated-tree checksums;
• GPU-vs-BH #2A force error;
• bounded direct-force error;
• full GPU-vs-f64 trajectory error;
• stage-specific GPU tree-construction timings.

The initial BH #2C builder is intentionally correctness-first and limited to 4,096 resident bodies.

Control-heavy bounds, ordering, topology and aggregate stages are currently serialized GPU kernels. This is a device-ownership and correctness milestone, not a production GPU-tree performance claim.

Validation results

The deterministic Mesa Vulkan CI fixture successfully executed the complete GPU Barnes–Hut stack.

For a 128-body, three-step self-gravity run:

• host tree rebuilds during BH #2C evolution: 0
• host particle readbacks during steps: 0
• force solves: 4
• evolution tree builds: 4
• GPU tree overflow: none
• repeated unchanged-state GPU tree checksum: identical

Final GPU-tree force versus BH #2A flat f64 reference:

• RMS relative error: approximately 4.22e-7
• maximum relative error: approximately 2.72e-6

Final bounded exact direct-force probes:

• RMS relative error: approximately 0.879%
• maximum relative error: approximately 2.14%

Three-step GPU trajectory versus the f64 BH #2A reference:

• position RMS relative error: approximately 5.17e-8
• position maximum relative error: approximately 1.52e-7
• velocity RMS relative error: approximately 9.19e-8
• velocity maximum relative error: approximately 2.92e-7

These figures are correctness evidence from Mesa software Vulkan and are not hardware GPU performance claims.

CI and reproducibility

The native GPU workflow now validates:

• Barnes–Hut Rust tests;
• transfer-record ABI;
• CUDA source/layout parity;
• BH #2B1 GPU traversal;
• BH #2B2 persistent-state evolution;
• BH #2C GPU-built-tree evolution;
• existing fixed-potential GPU kernels;
• legacy runtime smoke tests;
• Docker packaging.

Existing CPU, retro-portability, u64 tiled-runtime, memory-wall and host-auto workflows remain green.

Runtime source fingerprints now cover the Barnes–Hut GPU shaders, GPU tree builder, evolution executable and CPU oracle sources.

Documentation

Updated:

• README.md
• ROADMAP.md
• docs/BARNES-HUT.md
• docs/GPU-RUNTIME.md
• nbody/README.md

The documentation now explicitly separates:

• prescribed-field test-particle dynamics;
• resident mutually coupled Barnes–Hut self-gravity;
• CPU recursive reference;
• CPU flat-tree reference;
• GPU traversal;
• GPU evolution;
• GPU tree construction.

Scientific and performance boundaries

This release does not claim:

• logical-u64 tiling for mutually interacting self-gravity;
• GPU-resident populations beyond available physical memory;
• hydrodynamics;
• gas evolution;
• star formation;
• a full baryonic/dark-matter density solver;
• CUDA execution where only source/ABI parity was checked;
• hardware GPU speed from software-Vulkan CI;
• production-quality parallel GPU tree construction.

The BH #2C tree builder establishes the correctness boundary required before those construction stages are parallelized and benchmarked.

Next phase

The next experimental rung is BH #2D — parallel GPU tree construction.

Planned work includes:

• parallel bounds reduction;
• scalable radix/Morton sorting;
• parallel range and topology construction;
• parallel aggregate reduction;
• hardware GPU execution and timing;
• comparison against both BH #2C and the frozen host-built BH #2B2 oracle.

The governing principle remains:

correctness and provenance first; performance claims only after the measured implementation earns them.