Orthogonal recursive bisection of a Dim-dimensional global cell grid into numBlocks axis-aligned blocks; by the suite's convention block b is owned by rank b. More...

#include <block_decomposer.hpp>

Public Member Functions
	BlockDecomposer ()=default

	BlockDecomposer (std::size_t numBlocks, IVec< Dim > globalSize)
	Equal-cell-count ORB: see init(numBlocks, globalSize).

	BlockDecomposer (std::size_t numBlocks, IVec< Dim > globalSize, const std::vector< Real > &weights)
	Weighted ORB: see init(numBlocks, globalSize, weights).

	BlockDecomposer (std::size_t numBlocks, IVec< Dim > globalSize, const IVec< Dim > &align)
	Aligned ORB (coarsenable): see the aligned init() below.

void	init (std::size_t numBlocks, IVec< Dim > globalSize)
	Build the decomposition of a `globalSize` cell grid into `numBlocks` blocks (equal cell count).

void	init (std::size_t numBlocks, IVec< Dim > globalSize, const IVec< Dim > &align)
	Aligned ORB: force every split position (and hence every block origin/size) on axis k to be a multiple of `align[k]`.

void	init (std::size_t numBlocks, IVec< Dim > globalSize, const IVec< Dim > &align, const IVec< Dim > &cellExtent)
	Anisotropic-cell aligned ORB: `cellExtent[k]` is how many underlying FINE cells one cell of this grid spans along axis k.

void	init (std::size_t numBlocks, IVec< Dim > globalSize, const std::vector< Real > &weights)
	Weighted ORB: balance the total weight per block instead of the cell count.

void	init (std::size_t numBlocks, IVec< Dim > globalSize, const std::vector< Real > &weights, const IVec< Dim > &align)
	Aligned weighted ORB — COARSE-FIRST, never snap-after (amr/docs/amr_mg_core_boundary.md §11.4; suite docs/DECOMPOSITION_AND_MULTIGRID.md open problem 9).

std::size_t	numBlocks () const
	Number of blocks.

const IVec< Dim > &	globalSize () const
	Global grid size in cells per axis.

const std::vector< IVec< Dim > > &	origins () const
	Inclusive lower corner of every block, in global cell coordinates, indexed by block.

const std::vector< IVec< Dim > > &	sizes () const
	Extent in cells of every block, indexed by block.

Block< Dim >	block (std::size_t b) const
	Block `b` as (origin, size). Precondition: `b < numBlocks()` (unchecked).

int	ownerOf (const IVec< Dim > &g) const
	Owning block index of a global cell coordinate. Caller must wrap into [0, globalSize) first.

void	flattenTree (std::vector< int > &splitDim, std::vector< Index > &splitVal) const
	Flatten the implicit ORB tree into two parallel arrays for a device-callable ownerOf: for node `i`, `splitDim[i]` is the split axis (−1 ⇒ leaf), `splitVal[i]` the split coordinate (internal) or the block index (leaf); children sit at 2i+1 / 2i+2.

Index	linearGlobal (const IVec< Dim > &g) const
	Global multi-index -> global linear index (x-fastest: I = x + ynx + znx*ny).

IVec< Dim >	multiGlobal (Index lin) const
	Global linear index -> global multi-index (inverse of linearGlobal).

BlockDecomposer< Dim >	coarsened (const IVec< Dim > &ratio) const
	Derive the NESTED coarse decomposition: each block, split value and the global size divided by `ratio` per axis (ratio[k] is 1 or the integer coarsening factor).

BlockDecomposer< Dim >	refined (const IVec< Dim > &ratio) const
	Derive the NESTED fine decomposition: the exact inverse of `coarsened()` — global size, split values, block origins and block sizes each MULTIPLIED by `ratio` per axis.

int	treeDepth () const
	Depth of the deepest leaf of the ORB tree (root = 0).

BlockDecomposer< Dim >	agglomerated (int depth, std::vector< int > groupOf=nullptr, std::vector< int > rootOf=nullptr) const
	Coarse-level TELESCOPING: the decomposition obtained by merging ORB siblings — truncate the bisection tree at `depth`, so every node at that depth (and every original leaf above it) becomes a block whose box is exactly the union of its subtree's leaf boxes.

Detailed Description

template<int Dim>
class peclet::core::decomp::BlockDecomposer< Dim >

Orthogonal recursive bisection of a Dim-dimensional global cell grid into numBlocks axis-aligned blocks; by the suite's convention block b is owned by rank b.

Construction is deterministic and needs no communication, so every rank that builds it from the same arguments holds the same (replicated) decomposition. Indexing is x-fastest throughout (linearGlobal).

Definition at line 33 of file block_decomposer.hpp.

Constructor & Destructor Documentation

◆ BlockDecomposer() [1/4]

template<int Dim>

peclet::core::decomp::BlockDecomposer< Dim >::BlockDecomposer ( )

default

◆ BlockDecomposer() [2/4]

template<int Dim>

peclet::core::decomp::BlockDecomposer< Dim >::BlockDecomposer	(	std::size_t	numBlocks,
		IVec< Dim >	globalSize
	)

inline

Equal-cell-count ORB: see init(numBlocks, globalSize).

Definition at line 37 of file block_decomposer.hpp.

References peclet::core::decomp::BlockDecomposer< Dim >::globalSize(), peclet::core::decomp::BlockDecomposer< Dim >::init(), and peclet::core::decomp::BlockDecomposer< Dim >::numBlocks().

◆ BlockDecomposer() [3/4]

template<int Dim>

peclet::core::decomp::BlockDecomposer< Dim >::BlockDecomposer	(	std::size_t	numBlocks,
		IVec< Dim >	globalSize,
		const std::vector< Real > &	weights
	)

inline

Weighted ORB: see init(numBlocks, globalSize, weights).

Definition at line 39 of file block_decomposer.hpp.

References peclet::core::decomp::BlockDecomposer< Dim >::globalSize(), peclet::core::decomp::BlockDecomposer< Dim >::init(), and peclet::core::decomp::BlockDecomposer< Dim >::numBlocks().

◆ BlockDecomposer() [4/4]

template<int Dim>

peclet::core::decomp::BlockDecomposer< Dim >::BlockDecomposer	(	std::size_t	numBlocks,
		IVec< Dim >	globalSize,
		const IVec< Dim > &	align
	)

inline

Aligned ORB (coarsenable): see the aligned init() below.

Definition at line 43 of file block_decomposer.hpp.

References peclet::core::decomp::BlockDecomposer< Dim >::globalSize(), peclet::core::decomp::BlockDecomposer< Dim >::init(), and peclet::core::decomp::BlockDecomposer< Dim >::numBlocks().

Member Function Documentation

◆ init() [1/5]

template<int Dim>

void peclet::core::decomp::BlockDecomposer< Dim >::init	(	std::size_t	numBlocks,
		IVec< Dim >	globalSize
	)

inline

Build the decomposition of a globalSize cell grid into numBlocks blocks (equal cell count).

Definition at line 49 of file block_decomposer.hpp.

References peclet::core::decomp::BlockDecomposer< Dim >::globalSize(), and peclet::core::decomp::BlockDecomposer< Dim >::numBlocks().

Referenced by peclet::core::decomp::BlockDecomposer< Dim >::BlockDecomposer(), peclet::core::decomp::BlockDecomposer< Dim >::BlockDecomposer(), peclet::core::decomp::BlockDecomposer< Dim >::BlockDecomposer(), peclet::core::decomp::BlockDecomposer< Dim >::init(), and peclet::core::halo::rebalanceByParticleCount().

◆ init() [2/5]

template<int Dim>

void peclet::core::decomp::BlockDecomposer< Dim >::init	(	std::size_t	numBlocks,
		IVec< Dim >	globalSize,
		const IVec< Dim > &	align
	)

inline

Aligned ORB: force every split position (and hence every block origin/size) on axis k to be a multiple of align[k].

This is what makes a decomposition safely COARSENABLE — a geometric multigrid can then derive each coarse level by coarsened() (halving in place) and every level nests, so restrict/prolong stay purely local. Set align[k] = 2^(levels axis k coarsens). align[k] == 1 is the classic unaligned split. globalSize[k] must be a multiple of align[k].

Definition at line 62 of file block_decomposer.hpp.

References peclet::core::decomp::BlockDecomposer< Dim >::globalSize(), and peclet::core::decomp::BlockDecomposer< Dim >::numBlocks().

◆ init() [3/5]

template<int Dim>

void peclet::core::decomp::BlockDecomposer< Dim >::init	(	std::size_t	numBlocks,
		IVec< Dim >	globalSize,
		const IVec< Dim > &	align,
		const IVec< Dim > &	cellExtent
	)

inline

Anisotropic-cell aligned ORB: cellExtent[k] is how many underlying FINE cells one cell of this grid spans along axis k.

It affects ONLY the choice of split axis, which then compares size[k]*cellExtent[k] (the physical extent) instead of the raw cell count. Required when decomposing a grid whose axes were coarsened by DIFFERENT factors — there equal cell counts do not mean equal extents, and comparing counts makes the ORB bisect the wrong axis (which is how a coarse-first partition ends up cutting a direction the fine grid would never have cut). All ones (the default) reproduces the isotropic ORB exactly.

Definition at line 77 of file block_decomposer.hpp.

References peclet::core::decomp::BlockDecomposer< Dim >::globalSize(), peclet::core::decomp::BlockDecomposer< Dim >::init(), and peclet::core::decomp::BlockDecomposer< Dim >::numBlocks().

◆ init() [4/5]

template<int Dim>

void peclet::core::decomp::BlockDecomposer< Dim >::init	(	std::size_t	numBlocks,
		IVec< Dim >	globalSize,
		const std::vector< Real > &	weights
	)

inline

Weighted ORB: balance the total weight per block instead of the cell count.

weights is a per-cell weight array over the global grid (size == product(globalSize), x-fastest). Each split is placed on the integer cell boundary whose cumulative weight is closest to the sub-block's target fraction. Reduces bit-exactly to the unweighted init() when all weights are equal.

Definition at line 88 of file block_decomposer.hpp.

References peclet::core::decomp::BlockDecomposer< Dim >::globalSize(), and peclet::core::decomp::BlockDecomposer< Dim >::numBlocks().

◆ init() [5/5]

template<int Dim>

void peclet::core::decomp::BlockDecomposer< Dim >::init	(	std::size_t	numBlocks,
		IVec< Dim >	globalSize,
		const std::vector< Real > &	weights,
		const IVec< Dim > &	align
	)

inline

Aligned weighted ORB — COARSE-FIRST, never snap-after (amr/docs/amr_mg_core_boundary.md §11.4; suite docs/DECOMPOSITION_AND_MULTIGRID.md open problem 9).

Every split value, block origin and block size on axis k is a multiple of align[k], so coarsened(align) divides cleanly and in-place lifting nests for log2(align[k]) levels; align_ is set to align.

Construction: sum weights onto the grid coarsened by align (coarse cell c carries the total fine weight of its align-box), run the EXISTING weighted ORB there (align_ = 1), then the EXISTING exact inverse refined(align). On the coarse grid one cell IS the alignment quantum, so a balanced split is never rounded into an unbalanced one — which is what snapping a fine-grid split does (96|96 → 128|64). The unweighted aligned init above is the snapping one and is deliberately left as it is.

Contract: align[k] >= 1, globalSize[k] % align[k] == 0, weights covers the global grid x-fastest. The coarse ORB is told each coarse cell's extent (cellExtent = align) — inert when align is the same on every axis (the split-axis comparisons scale uniformly), and the settled rule for anisotropic coarsening otherwise. With align all ones this is bit-exactly init(numBlocks, globalSize, weights): the coarse grid is the grid, each coarse weight is a one-term sum (a copy), the ORB is the same call and refined({1,…}) multiplies by 1.

Pure and replicated: no communication, so weights must be the same global field on every rank. The contract is checked by assert only — a violation in an NDEBUG build is undefined behaviour, not an exception. chooseAlignedWeighted picks align from an imbalance budget.

Definition at line 124 of file block_decomposer.hpp.

References peclet::core::decomp::BlockDecomposer< Dim >::globalSize(), and peclet::core::decomp::BlockDecomposer< Dim >::numBlocks().

◆ numBlocks()

template<int Dim>

std::size_t peclet::core::decomp::BlockDecomposer< Dim >::numBlocks ( ) const

inline

Number of blocks.

Definition at line 171 of file block_decomposer.hpp.

◆ globalSize()

template<int Dim>

const IVec< Dim > & peclet::core::decomp::BlockDecomposer< Dim >::globalSize ( ) const

inline

Global grid size in cells per axis.

Definition at line 173 of file block_decomposer.hpp.

◆ origins()

template<int Dim>

const std::vector< IVec< Dim > > & peclet::core::decomp::BlockDecomposer< Dim >::origins ( ) const

inline

Inclusive lower corner of every block, in global cell coordinates, indexed by block.

Definition at line 175 of file block_decomposer.hpp.

Referenced by peclet::core::halo::GridHaloTopology< Dim >::buildTopology(), and peclet::core::decomp::weightImbalance().

◆ sizes()

template<int Dim>

const std::vector< IVec< Dim > > & peclet::core::decomp::BlockDecomposer< Dim >::sizes ( ) const

inline

Extent in cells of every block, indexed by block.

Definition at line 177 of file block_decomposer.hpp.

Referenced by peclet::core::halo::GridHaloTopology< Dim >::buildTopology(), and peclet::core::decomp::weightImbalance().

◆ block()

template<int Dim>

Block< Dim > peclet::core::decomp::BlockDecomposer< Dim >::block ( std::size_t b ) const

inline

Block b as (origin, size). Precondition: b < numBlocks() (unchecked).

Definition at line 180 of file block_decomposer.hpp.

◆ ownerOf()

template<int Dim>

int peclet::core::decomp::BlockDecomposer< Dim >::ownerOf ( const IVec< Dim > & g ) const

inline

Owning block index of a global cell coordinate. Caller must wrap into [0, globalSize) first.

Definition at line 183 of file block_decomposer.hpp.

Referenced by peclet::core::halo::GridHaloTopology< Dim >::buildTopology().

◆ flattenTree()

template<int Dim>

void peclet::core::decomp::BlockDecomposer< Dim >::flattenTree	(	std::vector< int > &	splitDim,
		std::vector< Index > &	splitVal
	)		const

inline

Flatten the implicit ORB tree into two parallel arrays for a device-callable ownerOf: for node i, splitDim[i] is the split axis (−1 ⇒ leaf), splitVal[i] the split coordinate (internal) or the block index (leaf); children sit at 2i+1 / 2i+2.

Uploaded once by ParticleMigratorView so the per-particle owner lookup runs on the device (D1). Mirrors ownerOf exactly.

Definition at line 196 of file block_decomposer.hpp.

Referenced by peclet::core::halo::ParticleMigratorView< Dim >::init().

◆ linearGlobal()

template<int Dim>

Index peclet::core::decomp::BlockDecomposer< Dim >::linearGlobal ( const IVec< Dim > & g ) const

inline

Global multi-index -> global linear index (x-fastest: I = x + y*nx + z*nx*ny).

Definition at line 206 of file block_decomposer.hpp.

Referenced by peclet::core::halo::GridHaloTopology< Dim >::buildTopology(), peclet::core::halo::rebalanceByParticleCount(), and peclet::core::decomp::weightImbalance().

◆ multiGlobal()

template<int Dim>

IVec< Dim > peclet::core::decomp::BlockDecomposer< Dim >::multiGlobal ( Index lin ) const

inline

Global linear index -> global multi-index (inverse of linearGlobal).

Definition at line 216 of file block_decomposer.hpp.

Referenced by peclet::core::halo::GridHaloTopology< Dim >::buildTopology().

◆ coarsened()

template<int Dim>

BlockDecomposer< Dim > peclet::core::decomp::BlockDecomposer< Dim >::coarsened ( const IVec< Dim > & ratio ) const

inline

Derive the NESTED coarse decomposition: each block, split value and the global size divided by ratio per axis (ratio[k] is 1 or the integer coarsening factor).

The tree shape and leaf order are preserved, so rank r's coarse block is exactly rank r's fine block coarsened in place — the invariant a geometric-multigrid restrict/prolong relies on (coarse-local i ↔ fine-local ratio*i). Exact iff this decomposition was built aligned to a multiple of ratio on each coarsened axis (see the aligned init); asserts divisibility in debug builds.

Definition at line 231 of file block_decomposer.hpp.

◆ refined()

template<int Dim>

BlockDecomposer< Dim > peclet::core::decomp::BlockDecomposer< Dim >::refined ( const IVec< Dim > & ratio ) const

inline

Derive the NESTED fine decomposition: the exact inverse of coarsened() — global size, split values, block origins and block sizes each MULTIPLIED by ratio per axis.

This is the "decompose coarse, refine upward" route to a multigrid-safe partition, and it is strictly stronger than building the fine ORB with an alignment. Aligning the fine ORB decides the split and then snaps it, so a balanced split can be rounded into an unbalanced one (the pathological case: 96|96 snapped to 128|64, a 2:1 cascade). Refining upward instead lets the ORB balance on the coarse grid, where one coarse cell IS the alignment quantum — so the fine blocks are multiples of ratio by construction, coarsened() nests exactly for log2(ratio) levels, and the load balance is the best achievable at that granularity.

Caller's responsibility: ratio should be the coarsening the hierarchy will actually perform (2^levels per axis, bounded by that axis's factors of two), and the coarse grid must hold at least numBlocks cells.

Definition at line 272 of file block_decomposer.hpp.

◆ treeDepth()

template<int Dim>

int peclet::core::decomp::BlockDecomposer< Dim >::treeDepth ( ) const

inline

Depth of the deepest leaf of the ORB tree (root = 0).

A decomposition of P blocks has depth ceil(log2 P) when balanced, more when P is not a power of two.

Definition at line 303 of file block_decomposer.hpp.

◆ agglomerated()

template<int Dim>

BlockDecomposer< Dim > peclet::core::decomp::BlockDecomposer< Dim >::agglomerated	(	int	depth,
		std::vector< int > *	groupOf = `nullptr`,
		std::vector< int > *	rootOf = `nullptr`
	)		const

inline

Coarse-level TELESCOPING: the decomposition obtained by merging ORB siblings — truncate the bisection tree at depth, so every node at that depth (and every original leaf above it) becomes a block whose box is exactly the union of its subtree's leaf boxes.

The result tiles the domain, nests with this decomposition by construction (each of its blocks is a union of a CONTIGUOUS run of this decomposition's blocks, since leaves are numbered in-order), needs no partitioner and no graph, and — the point — restores the parity a geometric multigrid needs: a merged block's origin is its PARENT's split value, one tree level up, so a partition whose blocks have gone odd after k halvings recovers even blocks by merging. groupOf[b] receives the new block index of each old block b; the new block's owning rank is by convention the LOWEST old rank in its group (rootOf). depth 0 is the whole grid on one block. Tree heap indices are preserved for the kept nodes, so coarsened()/refined()/ownerOf work on the result unchanged; dropped nodes are reset to leaves so coarsened() skips them.

Definition at line 321 of file block_decomposer.hpp.

The documentation for this class was generated from the following file:

block_decomposer.hpp

Public Member Functions

Detailed Description

Constructor & Destructor Documentation

◆ BlockDecomposer() [1/4]

◆ BlockDecomposer() [2/4]

◆ BlockDecomposer() [3/4]

◆ BlockDecomposer() [4/4]

Member Function Documentation

◆ init() [1/5]

◆ init() [2/5]

◆ init() [3/5]

◆ init() [4/5]

◆ init() [5/5]

◆ numBlocks()

◆ globalSize()

◆ origins()

◆ sizes()

◆ block()

◆ ownerOf()

◆ flattenTree()

◆ linearGlobal()

◆ multiGlobal()

◆ coarsened()

◆ refined()

◆ treeDepth()

◆ agglomerated()