Deterministic SumBoundary

[BenWibking]

For our code, we need a deterministic version of SumBoundary.

We have implemented a deterministic particle deposition algorithm, which we have verified this for individual FABs, but due to the use of atomics in SumBoundary, it is not reproducible on GPU after calling SumBoundary.

Somewhat related: #3739.

@chongchonghe @WeiqunZhang

[BenWibking]

These are two possible implementation strategies ChatGPT suggested after analyzing the code:

Goal

- Make SumBoundary produce bitwise-identical results across runs on GPUs by enforcing a fixed summation order instead of relying on atomic adds.

Root Cause

- Current GPU path uses Gpu::Atomic::AddNoRet (or per-cell CAS locks when no native atomic add). Atomics are correct but non-deterministic
because thread/block scheduling changes the addition order.

Option A — Conflict Coloring (Recommended)

- Idea: Partition copy tags into a few “colors” so tags in the same color have disjoint destination regions. Apply colors in a fixed order using
plain +=.
- Where: Replace the non-thread-safe GPU branches in:
    - PC_local_gpu (extern/amrex/Src/Base/AMReX_PCI.H)
    - unpack_recv_buffer_gpu (extern/amrex/Src/Base/AMReX_FBI.H)
- Steps:
    - Build conflict graph per destination fab: two tags conflict if their dbox overlap on that fab.
    - Deterministically order tags (current generation order is already deterministic).
    - Greedy color per destination fab: assign lowest color with no conflict; store color_id with each tag.
    - For color = 0..max_color:
    - Launch `detail::fab_to_fab(copy_tags_of_color, scomp, dcomp, ncomp, detail::CellAdd<T0,T1>())`.
    - No atomics; no overlaps within a color.
- Determinism:
    - Colors processed in increasing order → fixed summation order across tags.
    - Within a color, operations commute but do not overlap targets, so ordering is irrelevant.
- Performance:
    - Typical overlap chromatic number is small (faces/edges/corners), so 2–6 passes are common.
    - Avoids extra large buffers and sorting; minimal code churn.

Option B — Gather + Segmented Deterministic Reduce

- Idea: Convert all contributions into a flat list with a deterministic global index, then reduce per destination cell in that exact order.
- Where: New code path (e.g., fab_to_fab_deterministic_add) used when op == ADD and !is_thread_safe.
- Steps:
    - Generate contributions in deterministic tag-and-cell order:
    - Compute per-tag contribution counts; exclusive-scan to get a unique base offset.
    - Each thread writes one entry to `contrib[i] = {dst_linear_index, comp, source_order_id, value}` at its predetermined `i` (no atomics).
- Order contributions:
    - Sort by `(dst_linear_index, comp, source_order_id)` or avoid sorting by precomputing per-cell ranges; sorting is simpler and deterministic
given keys.
- Segmented reduction:
    - For each `(dst, comp)` segment, run a single-thread sequential loop summing in array order; write to `dfab`.
    - Process many segments in parallel (one thread per segment); segments are short (<= 26 neighbors in 3D).
- Determinism:
    - Fixed input generation + fixed sort key + sequential per-segment accumulation → bitwise reproducible.
- Performance:
    - Extra memory proportional to contributions; a sort per kernel launch; fine because segment sizes are small.

Small Tweaks

- Add a new op: FabArrayBase::ADD_DETERMINISTIC (or a runtime knob) to opt into the deterministic path without breaking existing
performance-sensitive code.
- Ensure math flags are consistent (disable fast-math/fused ops if cross-compiler determinism is required).
- Keep CPU path unchanged (already deterministic due to sequential tag application per destination tile).

Integration Points

- AMReX_PCI.H::PC_local_gpu:
    - Replace calls to fab_to_fab_atomic_add with either:
    - Color-based multi-pass `fab_to_fab(..., CellAdd)`; or
    - New `fab_to_fab_deterministic_add`.
- AMReX_FBI.H::unpack_recv_buffer_gpu:
    - Same replacement when handling received buffers.
- Add helpers in AMReX_FBI.H:
    - Coloring utilities for Array4CopyTag<T0,T1>.
    - Or fab_to_fab_deterministic_add implementing gather + sort + segmented sum.

Trade-offs

- Coloring:
    - Pros: Simple, low overhead, no big buffers, easy to reason about.
    - Cons: Multiple kernel passes; requires robust overlap detection/coloring.
- Gather+reduce:
    - Pros: Fully general and trivially deterministic; easy to verify.
    - Cons: Extra memory and sorting cost.

[AlexanderSinn]

You can try to set the Gpu launch region to false around SumBoundary calls (amrex::Gpu::setLaunchRegion(false);), while using no OMP and managed memory. This should be deterministic, albeit very slow.

[WeiqunZhang]

Maybe we can launch a single-block kernel to do the unpacking for SumBoundary. We can then go through each subbox one by one.

[WeiqunZhang]

I can provide an alternative PR using the single-block approach. You can compare performance with your multi-pass approach.

[chongchonghe]

I can provide an alternative PR using the single-block approach. You can compare performance with your multi-pass approach.

This would be great! Thanks.