MFC
Exascale flow solver
Loading...
Searching...
No Matches
m_amr_cluster Module Reference

Berger-Rigoutsos clustering of a sparse tag list into separated block boxes, identically on every rank: tag signatures, bisection, canonical Morton order and min-separation merge. More...

Functions/Subroutines

impure subroutine s_amr_box_sig (tags, ts, te, blo0, bhi0, sig, off, nsig)
 Concatenated 1D tag signatures of box [blo0:bhi0] from tags ts:te: sig(off(d) + t - blo0(d)) counts the in-box tagged cells at position t along d. One signature serves the trim, the count and every split. nsig is the used length.
pure subroutine s_amr_trim_from_sig (sig, off, blo0, bhi0, blo, bhi, ok, ntag)
 Shrink box [blo:bhi] to the tight bbox of its tagged cells (first/last nonzero of each axis signature) and return their count; ok = .false. if none tagged.
pure subroutine s_amr_find_split_sig (sig, off, blo0, blo, bhi, sax, spos, ok)
 Bisect a trimmed box: on the longest splittable axis prefer the widest zero-signature hole, else the strongest signature inflection (Laplacian sign change). ok = .false. if no axis admits a split leaving both children >= min_child cells.
pure subroutine s_cl_partition (wt, ts, te, sax, spos, lo)
 Partition wt(:, ts:te) in place by coord(sax) < spos; the low child is ts:lo-1 and the high child lo:te.
impure subroutine s_cl_exchange (tagc, np2, sb, sc, sd, rb, rc, rd)
 Nonblocking exchange: receive rc(q) words into rb at rd(q) and send sc(q) words from sb at sd(q), per peer plist(q).
impure subroutine s_cl_add_peer (rr, np2)
 Register rank rr as a peer of the narrow reduction if not yet listed.
impure subroutine s_cl_reduce_depth (nbat, bsig, bofs, blen, bnov, bwide, bovr)
 Sum the depth's batched signatures across ranks. Wide nodes (every rank overlaps) ride one ALLREDUCE. Narrow nodes reduce point-to-point within their small rank brick: members send to the root bovr(1,:), which sums and sends the total back. Both ends enumerate nodes in the same global order, so one aggregated message per peer per phase matches without negotiation.
impure subroutine s_cl_union (alo, ahi, nacc)
 Union the per-rank accepted boxes (rank-local subtrees are walked only by their owner). Rank order is not serial acceptance order; the Morton sort that follows removes the dependence. alo/ahi grow to the union (the cap applies to the merged set).
impure subroutine s_cl_bisect (tags, ntag_in, reduce, alo, ahi, nacc, capped)
 Level-order Berger-Rigoutsos descent: accepts boxes into alo/ahi(:, 1:nacc). Every shared node of a depth rides one reduction, so the collective count is O(tree depth). A child's overlapping ranks are a subset of its parent's, so every rank walks the whole shared subtree in the same order. Children are appended past ncur and shifted down when the depth closes (peak occupancy 3*ncur <= the 4*cap + 8 the arrays carry).
impure subroutine s_cl_morton_sort (alo, ahi, nacc)
 Sort boxes by the Morton key of lo so the merge input depends on the box set alone, not on the rank-dependent acceptance order. Accepted boxes are disjoint, so the keys are distinct; the sort is stable for any collision.
impure subroutine s_cl_merge (alo, ahi, nacc)
 Min-separation merge: two boxes are separated only if some active dim's gap reaches thr; else fuse to their bounding box. Fusing only shrinks gaps, so the fixed point (groups with mutually separated bounding boxes) does not depend on the fusion order; a group keeps its lowest index, so the output order does not either. Each box in list order sweeps the 3^d bins around its lo (bin width ext_max + thr holds every too-close partner), absorbs every later box found too close and is absorbed by the lowest earlier one, until a sweep finds nothing. Bins are rebuilt when a grown box outgrows the cell width.
impure subroutine, public s_amr_cluster (tags, ntag_in, boxes, nboxes, reduce)
 Cluster a sparse tag list tags(1:3, 1:ntag_in) of level-0 cell coords into separated block boxes, identically on every rank. Berger-Rigoutsos bisection until a box's tag efficiency reaches amr_cluster_eff (or it is atomic or the amr_max_blocks cap is hit), then merge boxes whose amr_buf-padded extents come within buff_size. Boxes are raw tagged extents; the caller pads, clamps and size-caps each. reduce: tags is this rank's local list and node signatures are reduced across ranks; otherwise tags is already replicated.

Variables

integer, parameter amr_cl_wide = 8
 A node is wide when its box spans more ranks than this; wide nodes use the batched collective, narrow ones reduce among their few overlapping ranks. 8 is one 2x2x2 brick of ranks.
integer, dimension(:), allocatable pidx
 Scratch of the narrow point-to-point reduction (pidx is all-zero between depths).
integer, dimension(:), allocatable plist
integer, dimension(:), allocatable scnt
integer, dimension(:), allocatable rcnt
integer, dimension(:), allocatable sdsp2
integer, dimension(:), allocatable rdsp2
integer, dimension(:), allocatable soff
integer, dimension(:), allocatable roff
integer, dimension(:), allocatable sbuf
integer, dimension(:), allocatable rbuf
integer, dimension(:), allocatable creq
integer, dimension(:), allocatable wbuf

Detailed Description

Berger-Rigoutsos clustering of a sparse tag list into separated block boxes, identically on every rank: tag signatures, bisection, canonical Morton order and min-separation merge.

Function/Subroutine Documentation

◆ s_amr_box_sig()

impure subroutine m_amr_cluster::s_amr_box_sig ( integer, dimension(:,:), intent(in) tags,
integer, intent(in) ts,
integer, intent(in) te,
integer, dimension(3), intent(in) blo0,
integer, dimension(3), intent(in) bhi0,
integer, dimension(:), intent(out) sig,
integer, dimension(3), intent(out) off,
integer, intent(out) nsig )
private

Concatenated 1D tag signatures of box [blo0:bhi0] from tags ts:te: sig(off(d) + t - blo0(d)) counts the in-box tagged cells at position t along d. One signature serves the trim, the count and every split. nsig is the used length.

Definition at line 399 of file m_amr_cluster.fpp.f90.

Here is the caller graph for this function:

◆ s_amr_cluster()

impure subroutine, public m_amr_cluster::s_amr_cluster ( integer, dimension(:,:), intent(in) tags,
integer, intent(in) ntag_in,
type(t_box), dimension(:), intent(out), allocatable boxes,
integer, intent(out) nboxes,
logical, intent(in) reduce )

Cluster a sparse tag list tags(1:3, 1:ntag_in) of level-0 cell coords into separated block boxes, identically on every rank. Berger-Rigoutsos bisection until a box's tag efficiency reaches amr_cluster_eff (or it is atomic or the amr_max_blocks cap is hit), then merge boxes whose amr_buf-padded extents come within buff_size. Boxes are raw tagged extents; the caller pads, clamps and size-caps each. reduce: tags is this rank's local list and node signatures are reduced across ranks; otherwise tags is already replicated.

Definition at line 1044 of file m_amr_cluster.fpp.f90.

Here is the call graph for this function:

◆ s_amr_find_split_sig()

pure subroutine m_amr_cluster::s_amr_find_split_sig ( integer, dimension(:), intent(in) sig,
integer, dimension(3), intent(in) off,
integer, dimension(3), intent(in) blo0,
integer, dimension(3), intent(in) blo,
integer, dimension(3), intent(in) bhi,
integer, intent(out) sax,
integer, intent(out) spos,
logical, intent(out) ok )
private

Bisect a trimmed box: on the longest splittable axis prefer the widest zero-signature hole, else the strongest signature inflection (Laplacian sign change). ok = .false. if no axis admits a split leaving both children >= min_child cells.

smallest box the bisection may produce; amr_blocking_factor raises it to stop over-generation

Definition at line 455 of file m_amr_cluster.fpp.f90.

Here is the caller graph for this function:

◆ s_amr_trim_from_sig()

pure subroutine m_amr_cluster::s_amr_trim_from_sig ( integer, dimension(:), intent(in) sig,
integer, dimension(3), intent(in) off,
integer, dimension(3), intent(in) blo0,
integer, dimension(3), intent(in) bhi0,
integer, dimension(3), intent(inout) blo,
integer, dimension(3), intent(inout) bhi,
logical, intent(out) ok,
integer, intent(out) ntag )
private

Shrink box [blo:bhi] to the tight bbox of its tagged cells (first/last nonzero of each axis signature) and return their count; ok = .false. if none tagged.

Definition at line 425 of file m_amr_cluster.fpp.f90.

Here is the caller graph for this function:

◆ s_cl_add_peer()

impure subroutine m_amr_cluster::s_cl_add_peer ( integer, intent(in) rr,
integer, intent(inout) np2 )
private

Register rank rr as a peer of the narrow reduction if not yet listed.

Definition at line 564 of file m_amr_cluster.fpp.f90.

Here is the caller graph for this function:

◆ s_cl_bisect()

impure subroutine m_amr_cluster::s_cl_bisect ( integer, dimension(:,:), intent(in) tags,
integer, intent(in) ntag_in,
logical, intent(in) reduce,
integer, dimension(:,:), intent(out) alo,
integer, dimension(:,:), intent(out) ahi,
integer, intent(out) nacc,
logical, intent(out) capped )
private

Level-order Berger-Rigoutsos descent: accepts boxes into alo/ahi(:, 1:nacc). Every shared node of a depth rides one reduction, so the collective count is O(tree depth). A child's overlapping ranks are a subset of its parent's, so every rank walks the whole shared subtree in the same order. Children are appended past ncur and shifted down when the depth closes (peak occupancy 3*ncur <= the 4*cap + 8 the arrays carry).

Definition at line 710 of file m_amr_cluster.fpp.f90.

Here is the call graph for this function:
Here is the caller graph for this function:

◆ s_cl_exchange()

impure subroutine m_amr_cluster::s_cl_exchange ( integer, intent(in) tagc,
integer, intent(in) np2,
integer, dimension(:), intent(inout) sb,
integer, dimension(:), intent(in) sc,
integer, dimension(:), intent(in) sd,
integer, dimension(:), intent(inout) rb,
integer, dimension(:), intent(in) rc,
integer, dimension(:), intent(in) rd )
private

Nonblocking exchange: receive rc(q) words into rb at rd(q) and send sc(q) words from sb at sd(q), per peer plist(q).

Definition at line 540 of file m_amr_cluster.fpp.f90.

Here is the caller graph for this function:

◆ s_cl_merge()

impure subroutine m_amr_cluster::s_cl_merge ( integer, dimension(:,:), intent(inout) alo,
integer, dimension(:,:), intent(inout) ahi,
integer, intent(inout) nacc )
private

Min-separation merge: two boxes are separated only if some active dim's gap reaches thr; else fuse to their bounding box. Fusing only shrinks gaps, so the fixed point (groups with mutually separated bounding boxes) does not depend on the fusion order; a group keeps its lowest index, so the output order does not either. Each box in list order sweeps the 3^d bins around its lo (bin width ext_max + thr holds every too-close partner), absorbs every later box found too close and is absorbed by the lowest earlier one, until a sweep finds nothing. Bins are rebuilt when a grown box outgrows the cell width.

Definition at line 852 of file m_amr_cluster.fpp.f90.

Here is the call graph for this function:
Here is the caller graph for this function:

◆ s_cl_morton_sort()

impure subroutine m_amr_cluster::s_cl_morton_sort ( integer, dimension(:,:), intent(inout) alo,
integer, dimension(:,:), intent(inout) ahi,
integer, intent(in) nacc )
private

Sort boxes by the Morton key of lo so the merge input depends on the box set alone, not on the rank-dependent acceptance order. Accepted boxes are disjoint, so the keys are distinct; the sort is stable for any collision.

Definition at line 827 of file m_amr_cluster.fpp.f90.

Here is the call graph for this function:
Here is the caller graph for this function:

◆ s_cl_partition()

pure subroutine m_amr_cluster::s_cl_partition ( integer, dimension(:,:), intent(inout) wt,
integer, intent(in) ts,
integer, intent(in) te,
integer, intent(in) sax,
integer, intent(in) spos,
integer, intent(out) lo )
private

Partition wt(:, ts:te) in place by coord(sax) < spos; the low child is ts:lo-1 and the high child lo:te.

Definition at line 519 of file m_amr_cluster.fpp.f90.

Here is the caller graph for this function:

◆ s_cl_reduce_depth()

impure subroutine m_amr_cluster::s_cl_reduce_depth ( integer, intent(in) nbat,
integer, dimension(:), intent(inout) bsig,
integer, dimension(:), intent(in) bofs,
integer, dimension(:), intent(in) blen,
integer, dimension(:), intent(in) bnov,
logical, dimension(:), intent(in) bwide,
integer, dimension(:,:), intent(in) bovr )
private

Sum the depth's batched signatures across ranks. Wide nodes (every rank overlaps) ride one ALLREDUCE. Narrow nodes reduce point-to-point within their small rank brick: members send to the root bovr(1,:), which sums and sends the total back. Both ends enumerate nodes in the same global order, so one aggregated message per peer per phase matches without negotiation.

Definition at line 576 of file m_amr_cluster.fpp.f90.

Here is the call graph for this function:
Here is the caller graph for this function:

◆ s_cl_union()

impure subroutine m_amr_cluster::s_cl_union ( integer, dimension(:,:), intent(inout), allocatable alo,
integer, dimension(:,:), intent(inout), allocatable ahi,
integer, intent(inout) nacc )
private

Union the per-rank accepted boxes (rank-local subtrees are walked only by their owner). Rank order is not serial acceptance order; the Morton sort that follows removes the dependence. alo/ahi grow to the union (the cap applies to the merged set).

Definition at line 673 of file m_amr_cluster.fpp.f90.

Here is the caller graph for this function:

Variable Documentation

◆ amr_cl_wide

integer, parameter m_amr_cluster::amr_cl_wide = 8
private

A node is wide when its box spans more ranks than this; wide nodes use the batched collective, narrow ones reduce among their few overlapping ranks. 8 is one 2x2x2 brick of ranks.

Definition at line 390 of file m_amr_cluster.fpp.f90.

◆ creq

integer, dimension(:), allocatable m_amr_cluster::creq
private

Definition at line 392 of file m_amr_cluster.fpp.f90.

◆ pidx

integer, dimension(:), allocatable m_amr_cluster::pidx
private

Scratch of the narrow point-to-point reduction (pidx is all-zero between depths).

Definition at line 392 of file m_amr_cluster.fpp.f90.

◆ plist

integer, dimension(:), allocatable m_amr_cluster::plist
private

Definition at line 392 of file m_amr_cluster.fpp.f90.

◆ rbuf

integer, dimension(:), allocatable m_amr_cluster::rbuf
private

Definition at line 392 of file m_amr_cluster.fpp.f90.

◆ rcnt

integer, dimension(:), allocatable m_amr_cluster::rcnt
private

Definition at line 392 of file m_amr_cluster.fpp.f90.

◆ rdsp2

integer, dimension(:), allocatable m_amr_cluster::rdsp2
private

Definition at line 392 of file m_amr_cluster.fpp.f90.

◆ roff

integer, dimension(:), allocatable m_amr_cluster::roff
private

Definition at line 392 of file m_amr_cluster.fpp.f90.

◆ sbuf

integer, dimension(:), allocatable m_amr_cluster::sbuf
private

Definition at line 392 of file m_amr_cluster.fpp.f90.

◆ scnt

integer, dimension(:), allocatable m_amr_cluster::scnt
private

Definition at line 392 of file m_amr_cluster.fpp.f90.

◆ sdsp2

integer, dimension(:), allocatable m_amr_cluster::sdsp2
private

Definition at line 392 of file m_amr_cluster.fpp.f90.

◆ soff

integer, dimension(:), allocatable m_amr_cluster::soff
private

Definition at line 392 of file m_amr_cluster.fpp.f90.

◆ wbuf

integer, dimension(:), allocatable m_amr_cluster::wbuf
private

Definition at line 392 of file m_amr_cluster.fpp.f90.