FluidNumerics / FluidNumerics/SELF

AMR Stage 2: distributed forest (remove the O(global elements) per-rank replication)

Open
#173 0 comments 0 reactions 0 assignees View on GitHub
Dominant language
Fortran
Stars
92
Forks
13
Avg merge
20h 38m
Merged PRs (30d)
7

Description

Stage 2 of #167, deliberately deferred there. #167 delivered Stage 1 (point-to-point solution migration) and left the forest replicated.

## What is still replicated

- **The forest itself.** Every rank stores and mutates the full quadtree/octree, so forest memory is O(global elements) per rank.
- **The refinement flags.** One `MPI_Allgatherv` of an `int` per element per epoch (`src/SELF_AMRController_{2,3}D.f90`), which is what makes every rank apply identical mutations.
- **The transfer plan**, as a consequence: `sourceKind`/`sourceElem`/`family`/`depth`/`path` are computed identically on every rank.
- **The base mesh tables**, allgathered once at `Init` (`InitForestFromDecomposedMesh`) — a one-time startup cost, but also O(global).

## The design premise this breaks

This is the part worth recording before anyone starts, because it is the load-bearing consequence.

Stage 1's migration is cheap *precisely because the plan is replicated*. Each rank derives its own window **and every peer's window** locally, so the send and receive runs are the same intersection (`OwnedRun`) evaluated independently on both ends of every pair — they match by construction, with no count exchange, no handshake, and no collective. A distributed forest removes that premise: a rank would no longer know what its peers' new ranges reference, so the schedule has to be negotiated (a small alltoall of counts, a scan, or a neighbourhood exchange) rather than deduced. Any Stage 2 design should state up front what replaces the deduction, and should not silently regress migration into a collective-per-epoch pattern in the process of removing a different collective.

Related: `Balance2to1` becomes a neighbourhood iteration to a fixed point rather than a local sweep over a complete forest, and `EmitMesh`'s global connectivity/`mortarInfo` construction — which currently relies on every rank being able to see every leaf — needs rethinking, as do the `SideExchange`/`MortarExchange` invariants that consume it (global side ids, replicated `mortarInfo`).

## Shape of the work (p4est-style)

Keep only the rank's leaf window plus a one-layer ghost halo of the forest; exchange refinement flags with neighbours instead of allgathering them; balance by neighbourhood iteration. Reference: Burstedde, Wilcox & Ghattas, *p4est: Scalable algorithms for parallel AMR on forests of octrees*, SIAM J. Sci. Comput. 2011.

## Measurement first — what is and is not a bottleneck today

#167 measured the following on the AMR examples (per-rank totals over a run), which is the baseline any Stage 2 case should be argued against:

- Migration traffic after Stage 1: **0.95 MB** at 4 ranks and **1.80 MB** at 8 ranks in 3-D, down from 53.9 MB and 62.9 MB. Migration is no longer the scaling problem.
- Peak RSS at example scale is dominated by the replicated forest, the geometry double-buffers and the halo tables — the migration buffer removed in Stage 1 was smaller than the run-to-run noise. **The forest replication is now the O(global) term that remains**, which is exactly why this issue exists, but it has not yet been shown to bind at any rank count actually run.
- The flag allgather is one `int` per element per epoch and has never appeared in a profile.

Suggested trigger for doing this work: a run where forest memory per rank, or the flag allgather, is measurably a limit — e.g. a multi-node run at a rank count where O(global elements) per rank stops fitting comfortably, or a mesh large enough that the replicated plan's O(nNew) per-rank work shows up against the adaptation cost. Until then Stage 1 plus the existing diagnostics look like the right operating point, and this is a substantially more invasive change than Stage 1 was.

## Acceptance

- Forest and plan memory per rank scale with the rank's own leaves plus its halo, not with the global element count.
- No new collective inside the time-stepping loop (CLAUDE.md §5); adaptation epochs remain the only communication points.
- Results bit-identical to the replicated path for the same partition, or a documented and justified reason why not.
- Tests at >= 4 ranks (two ranks cannot distinguish several classes of routing and balance bug — see #167), plus the determinism checks that currently rely on replication (the cross-rank leaf-checksum assertion in the AMR MPI regressions will need a distributed equivalent).
- `docs/Contributing/AMR3D-Design.md` §4 and `docs/Learning/AdaptiveMeshRefinement.md` (Stage 5, §6.5) updated; both currently document the replicated design as current and this as outstanding.

Contributor guide

Open the contributing guide

Research direction

Start with docs/Contributing/AMR3D-Design.md §4 and docs/Learning/AdaptiveMeshRefinement.md Stage 5 §6.5, then inspect src/SELF_AMRController_{2,3}D.f90, InitForestFromDecomposedMesh, Balance2to1, EmitMesh, SideExchange, and MortarExchange. Run the AMR MPI regressions with at least 4 ranks. Done means forest and plan memory scale with local leaves plus halo, no time-stepping-loop collective is added, and distributed determinism checks pass.

Written by the indexing model from the issue text.

Assessment

Tech stack
fortran
Domain
distributed-systems, hpc
Issue type
Feature
Difficulty
5/5
Estimated time
Over a week
Activity status
Active
Clarity
Mostly clear
Newbie friendliness
35/100

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.