Peano

Searching...

No Matches

Represents one tree. More...

#include <Spacetree.h>

Collaboration diagram for peano4::grid::Spacetree:

[legend]

Public Member Functions
	Spacetree (const tarch::la::Vector< Dimensions, double > &offset, const tarch::la::Vector< Dimensions, double > &width, const std::bitset< Dimensions > &periodicBC=0)

	~Spacetree ()

void	traverse (TraversalObserver &observer, bool calledFromSpacetreeSet=false)

GridStatistics	getGridStatistics () const

std::string	toString () const

bool	isInvolvedInJoinOrFork () const

Static Public Attributes
static constexpr int	RankOfPeriodicBoundaryCondition = -2
	Periodic boundary conditions are technically realised as domain decomposition, i.e.

static constexpr int	NumberOfStationarySweepsToWaitAtLeastTillJoin = 2

Private Types
typedef peano4::maps::HierarchicalStackMap< peano4::stacks::GridVertexStack >	GridVertexStackMap

Private Member Functions
bool	isCellSplitCandidate (GridVertex coarseGridVertices[TwoPowerD], GridVertex fineGridVertices[TwoPowerD]) const
	Can a cell be split (deployed to another rank)

void	evaluateGridControlEvents (const AutomatonState &fineGridState, GridVertex coarseGridVertices[TwoPowerD], GridVertex fineGridVertices[TwoPowerD])
	Should only be called for inner cells.

void	markVerticesAroundForkedCell (GridVertex coarseGridVertices[TwoPowerD], GridVertex fineGridVertices[TwoPowerD]) const
	setIsAntecessorOfRefinedVertexInCurrentTreeSweep()

bool	isVertexAdjacentToLocalSpacetree (GridVertex vertex, bool splittingIsConsideredLocal, bool joiningIsConsideredLocal) const
	Returns if a vertex is local to adjacent tree.

bool	doesRankIndexIdentifyHorizontalDataExchange (int rank, bool calledByReceivingProcess) const
	You may exchange data horizontally with rank if and only if.

void	descend (const AutomatonState &state, GridVertex vertices[TwoPowerD], TraversalObserver &observer)

bool	isSpacetreeNodeLocal (GridVertex vertices[TwoPowerD], bool splittingIsConsideredLocal, bool joiningIsConsideredLocal) const
	Wrapper around GridTraversalEventGenerator::isSpacetreeNodeLocal()

bool	areAllVerticesRefined (GridVertex vertices[TwoPowerD]) const

bool	areAllVerticesUnrefined (GridVertex vertices[TwoPowerD]) const

bool	areAllVerticesNonHanging (GridVertex vertices[TwoPowerD]) const
	Could also be called areAllVerticesPersistent() in the Peano terminology.

void	loadVertices (const AutomatonState &fineGridState, GridVertex coarseGridVertices[TwoPowerD], GridVertex fineGridVertices[TwoPowerD], const tarch::la::Vector< Dimensions, int > &cellPositionWithin3x3Patch, TraversalObserver &observer)
	Load the vertices of one cell.

void	storeVertices (const AutomatonState &fineGridState, GridVertex coarseGridVertices[TwoPowerD], GridVertex fineGridVertices[TwoPowerD], const tarch::la::Vector< Dimensions, int > &cellPositionWithin3x3Patch, TraversalObserver &observer)

void	updateVertexAfterLoad (GridVertex &vertex, GridVertex fineGridVertices[TwoPowerD], const tarch::la::Vector< Dimensions, int > &fineVertexPositionWithinPatch, TraversalObserver &observer)
	This operation has multiple purposes.

void	removeDuplicateEntriesFromAdjancyListInEvent (GridTraversalEvent &event) const
	Some of the entries in the event are modelled as array (for example the set of neighbours of a vertex), though they are logically sets.

void	receiveAndMergeUserData (const AutomatonState &state, TraversalObserver &observer, const GridTraversalEvent &enterCellTraversalEvent, GridVertex fineGridVertices[TwoPowerD])

void	sendUserData (const AutomatonState &state, TraversalObserver &observer, const GridTraversalEvent &enterCellTraversalEvent, GridVertex fineGridVertices[TwoPowerD])
	Send user data.

void	splitOrJoinCellBottomUp (GridVertex vertex[TwoPowerD], GridVertex fineGridVertices[TwoPowerD])
	Realise the splits and joins.

void	splitCellTopDown (GridVertex vertex[TwoPowerD], GridVertex fineGridVertices[TwoPowerD])
	Split cell in a top down fashion.

void	mergeCellFromWorkerWithMasterThroughoutJoin (GridVertex vertex[TwoPowerD], GridVertex fineGridVertices[TwoPowerD])
	Merge data from worker with master data throughout join.

bool	shouldEraseAdjacencyInformation (const GridVertex &vertex, GridVertex coarseGridVertices[TwoPowerD], tarch::la::Vector< Dimensions, int > fineVertexPositionWithinPatch) const

void	updateVertexBeforeStore (GridVertex &vertex, GridVertex fineGridVertices[TwoPowerD], const tarch::la::Vector< Dimensions, int > &fineVertexPositionWithinPatch)

tarch::la::Vector< TwoPowerD, int >	getAdjacentRanksForNewVertex (GridVertex coarseGridVertices[TwoPowerD], const tarch::la::Vector< Dimensions, int > &vertexPositionWithin3x3Patch) const

void	split (int treeId, const SplitInstruction &instruction)
	Add a split instruction.

std::set< int >	getNeighbourTrees (const GridVertex &vertex, bool calledByReceivingProcess) const
	Get the ids of the surrounding cells of a vertex.

int	getNeighbourTrees (GridVertex vertex[TwoPowerD], int faceNumber, bool calledByReceivingProcess) const
	Get the ids of the surround ids of a face.

bool	isFaceAlongPeriodicBoundaryCondition (GridVertex vertex[TwoPowerD], int faceNumber, bool calledByReceivingProcess) const

void	sendGridVertex (const GridVertex &vertex)
	This one is to be invoked if and only if a vertex goes to the in/out stacks.

void	receiveAndMergeGridVertexAtHorizontalBoundary (GridVertex &vertex)
	Manage the data exchange after a vertex is loaded for the first time.

void	receiveAndMergeGridVertexAtVerticalBoundary (GridVertex &vertex)
	This is a merge routine for vertical data exchange.

void	mergeGridVertexRefinementStateAtHorizontalDomainBoundary (GridVertex &vertex, const GridVertex &inVertex, int neighbour)
	Called by receiveAndMergeGridVertexAtHorizontalBoundary().

void	mergeGridVertexAdjacencyListsAtHorizontalDomainBoundary (GridVertex &vertex, const GridVertex &inVertex, int neighbour)

	Spacetree (int newId, int masterId, const tarch::la::Vector< Dimensions, double > &offset, const tarch::la::Vector< Dimensions, double > &width, bool traversalInverted)
	Only used by SpacetreeSet to create children of the original tree.

void	joinWithMaster ()
	Join with master.

void	joinWithWorker (int id)

bool	mayJoinWithMaster () const
	Only ranks that have no kids are allowed to join.

bool	mayJoinWithWorker () const
	We allow at most one join at a time and not while we split.

bool	maySplit () const
	Is the tree in principle allowed to split.

int	getSplittingTree () const

void	updateSplittingCounter (int treeId)
	Reduce splitting counter.

Static Private Member Functions
static void	incrementNumberOfAdjacentRefinedLocalCells (GridVertex vertices[TwoPowerD])
	Every local refined cell should call this routine.

static void	refineState (const AutomatonState &coarseGrid, AutomatonState fineGrid[ThreePowerD], tarch::la::Vector< Dimensions, int > fineGridPosition=tarch::la::Vector< Dimensions, int >(0), int axis=Dimensions-1)
	Takes a state (describing a node in the tree) and returns the \( 3^d \) states on the next finer level along the Peano SFC.

static tarch::la::Vector< Dimensions, int >	convertToIntegerVector (const std::bitset< Dimensions > &in)
	Little helper.

static bool	restrictToCoarseGrid (const tarch::la::Vector< Dimensions, int > &coarseVertexPosition, const tarch::la::Vector< Dimensions, int > &fineVertexPosition)
	Determines whether to restrict a vertex to the coarser level or not.

static void	updateVertexRanksWithinCell (GridVertex fineGridVertices[TwoPowerD], int newId)
	If a cell gets a new id, we have to update its vertices.

Private Attributes
int	_id

SpacetreeState	_spacetreeState

AutomatonState	_root
	The root of a spacetree corresponds to the initial state of the tree traversal automaton.

GridStatistics	_statistics

int	_masterId
	This is not a static master.

std::set< int >	_childrenIds

const std::bitset< Dimensions >	_periodicBC
	Indicate per axis whether we have periodic boundary conditions.

SplitSpecification	_splitTriggered
	A split is identified by a tuple of id and cell count which tells the code how many cells should go to a particular id.

std::set< int >	_splitting

GridTraversalEventGenerator	_gridTraversalEventGenerator

std::set< int >	_hasSplit
	I need this post-mortem list to identify which tree structures have to be copied/replicated where.

std::set< int >	_joinTriggered
	This should be -1 if no join is triggered.

std::set< int >	_joining
	If master: Set of workers that should join.

std::vector< peano4::grid::GridControlEvent >	_gridControlEvents
	We get these control events when we kick off the traversal and then realise/interpret them.

std::vector< int >	_splittedCells

Static Private Attributes
static tarch::logging::Log	_log

static constexpr int	NoJoin = -1

static GridVertexStackMap	_vertexStack

Friends
class	peano4::parallel::SpacetreeSet

class	peano4::grid::tests::SpacetreeTest

Detailed Description

Represents one tree.

Definition at line 40 of file Spacetree.h.

Member Typedef Documentation

◆ GridVertexStackMap

typedef peano4::maps::HierarchicalStackMap< peano4::stacks::GridVertexStack > peano4::grid::Spacetree::GridVertexStackMap

private

Definition at line 150 of file Spacetree.h.

Constructor & Destructor Documentation

◆ Spacetree() [1/2]

Spacetree< _Geometry, _Item, THRESHOLD, SPLIT_FACTOR, _TaskBackend >::Spacetree	(	int	newId,
		int	masterId,
		const tarch::la::Vector< Dimensions, double > &	offset,
		const tarch::la::Vector< Dimensions, double > &	width,
		bool	traversalInverted )

private

Only used by SpacetreeSet to create children of the original tree.

We have to set the stats's stationary counter manually, as clear() does not reset it. We furthermore set it to -2, as we'll need two iterations to set a new remote spacetree up.

Definition at line 48 of file Spacetree.cpp.

References _id, _root, _statistics, peano4::grid::clear(), DimensionsTimesTwo, logInfo, NumberOfStationarySweepsToWaitAtLeastTillJoin, peano4::grid::AutomatonState::setAccessNumber(), peano4::grid::AutomatonState::setEvenFlags(), peano4::grid::AutomatonState::setH(), peano4::grid::AutomatonState::setInverted(), peano4::grid::AutomatonState::setLevel(), peano4::grid::GridStatistics::setStationarySweeps(), and peano4::grid::AutomatonState::setX().

Here is the call graph for this function:

◆ Spacetree() [2/2]

Spacetree< _Geometry, _Item, THRESHOLD, SPLIT_FACTOR, _TaskBackend >::Spacetree	(	const tarch::la::Vector< Dimensions, double > &	offset,
		const tarch::la::Vector< Dimensions, double > &	width,
		const std::bitset< Dimensions > &	periodicBC = 0 )

Definition at line 21 of file Spacetree.cpp.

References _id, _periodicBC, _root, _statistics, peano4::grid::clear(), DimensionsTimesTwo, logDebug, peano4::grid::NewRoot, peano4::grid::AutomatonState::setAccessNumber(), peano4::grid::AutomatonState::setEvenFlags(), peano4::grid::AutomatonState::setH(), peano4::grid::AutomatonState::setInverted(), peano4::grid::AutomatonState::setLevel(), peano4::grid::GridStatistics::setStationarySweeps(), and peano4::grid::AutomatonState::setX().

Here is the call graph for this function:

◆ ~Spacetree()

Spacetree< _Geometry, _Item, THRESHOLD, SPLIT_FACTOR, _TaskBackend >::~Spacetree ( )

Definition at line 80 of file Spacetree.cpp.

Member Function Documentation

◆ areAllVerticesNonHanging()

bool Spacetree< _Geometry, _Item, THRESHOLD, SPLIT_FACTOR, _TaskBackend >::areAllVerticesNonHanging ( GridVertex vertices[TwoPowerD] ) const

private

Could also be called areAllVerticesPersistent() in the Peano terminology.

Definition at line 97 of file Spacetree.cpp.

References dfor2, enddforx, and peano4::grid::GridVertex::HangingVertex.

◆ areAllVerticesRefined()

bool Spacetree< _Geometry, _Item, THRESHOLD, SPLIT_FACTOR, _TaskBackend >::areAllVerticesRefined ( GridVertex vertices[TwoPowerD] ) const

private

Definition at line 103 of file Spacetree.cpp.

References dfor2, enddforx, and peano4::grid::GridVertex::Refined.

◆ areAllVerticesUnrefined()

bool Spacetree< _Geometry, _Item, THRESHOLD, SPLIT_FACTOR, _TaskBackend >::areAllVerticesUnrefined ( GridVertex vertices[TwoPowerD] ) const

private

Definition at line 109 of file Spacetree.cpp.

References dfor2, enddforx, and peano4::grid::GridVertex::Unrefined.

◆ convertToIntegerVector()

tarch::la::Vector< Dimensions, int > Spacetree< _Geometry, _Item, THRESHOLD, SPLIT_FACTOR, _TaskBackend >::convertToIntegerVector ( const std::bitset< Dimensions > & in )

staticprivate

Little helper.

Should likely go into la or utils.

Definition at line 335 of file Spacetree.cpp.

◆ descend()

void Spacetree< _Geometry, _Item, THRESHOLD, SPLIT_FACTOR, _TaskBackend >::descend	(	const AutomatonState &	state,
		GridVertex	vertices[TwoPowerD],
		TraversalObserver &	observer )

private

Veto erases

The routine markVerticesAroundForkedCell() is used in this routine to ensure that we don't erase the grid over a worker domain. We have to do this both on the master and the worker. The worker invokes the veto coarsening when it comes from a coarse remote tree and runs into local fine grid cell. The master does it the other way round: It sets the vetos if we hit a remote cell out from the local tree. In both cases, the bottom-up analysis of the flag ensures that the information propagates all the way up the grid hierarchies.

Definition at line 1208 of file Spacetree.cpp.

References assertion, dfor2, dfor3, peano4::utils::dLinearised(), peano4::grid::EmptyRun, enddforx, endzfor, peano4::grid::TraversalObserver::enterCell(), peano4::grid::AutomatonState::getH(), peano4::grid::PeanoCurve::getLoopDirection(), peano4::grid::isSpacetreeNodeLocal(), peano4::grid::isSpacetreeNodeRefined(), peano4::grid::Joined, peano4::grid::TraversalObserver::leaveCell(), peano4::grid::TraversalObserver::loadCell(), logDebug, logTraceInWith2Arguments, logTraceOut, tarch::la::min(), peano4::grid::NewFromSplit, peano4::grid::Running, state, peano4::grid::TraversalObserver::storeCell(), ThreePowerD, peano4::grid::AutomatonState::toString(), peano4::grid::toString(), TwoPowerD, and zfor3.

Here is the call graph for this function:

◆ doesRankIndexIdentifyHorizontalDataExchange()

bool Spacetree< _Geometry, _Item, THRESHOLD, SPLIT_FACTOR, _TaskBackend >::doesRankIndexIdentifyHorizontalDataExchange	(	int	rank,
		bool	calledByReceivingProcess ) const

private

You may exchange data horizontally with rank if and only if.

a grid entity is local
this predicate holds for rank

See also: getNeighbourTrees()

Definition at line 800 of file Spacetree.cpp.

References peano4::grid::InvalidRank(), and peano4::grid::Joining.

Here is the call graph for this function:

◆ evaluateGridControlEvents()

void Spacetree< _Geometry, _Item, THRESHOLD, SPLIT_FACTOR, _TaskBackend >::evaluateGridControlEvents	(	const AutomatonState &	fineGridState,
		GridVertex	coarseGridVertices[TwoPowerD],
		GridVertex	fineGridVertices[TwoPowerD] )

private

Should only be called for inner cells.

We run over all the grid refinement/erase events and first check if there are overlaps (refinement) or if the state is completely embedded within the current cell.

If there's an overlap with a refinement event, then we refine all adjacent vertices which are not yet refined.

If there's an erase event that's relevant, then we erase all adjacent vertices which are refined. To avoid that we have oscillations, I make the cell twice as big along each coordinate axis.

Definition at line 1122 of file Spacetree.cpp.

References tarch::la::allGreaterEquals(), tarch::la::allSmaller(), assertion1, dfor2, peano4::grid::EmptyRun, enddforx, peano4::grid::GridControlEvent::Erase, peano4::grid::GridVertex::EraseTriggered, peano4::grid::AutomatonState::getH(), peano4::grid::GridVertex::HangingVertex, peano4::grid::isContained(), peano4::grid::Joining, logDebug, logTraceInWith2Arguments, logTraceOutWith3Arguments, peano4::grid::NewFromSplit, peano4::grid::overlaps(), peano4::grid::GridControlEvent::Refine, peano4::grid::GridVertex::Refined, peano4::grid::GridVertex::RefinementTriggered, state, peano4::grid::AutomatonState::toString(), peano4::grid::toString(), TwoPowerD, and peano4::grid::GridVertex::Unrefined.

Here is the call graph for this function:

◆ getAdjacentRanksForNewVertex()

tarch::la::Vector< TwoPowerD, int > Spacetree< _Geometry, _Item, THRESHOLD, SPLIT_FACTOR, _TaskBackend >::getAdjacentRanksForNewVertex	(	GridVertex	coarseGridVertices[TwoPowerD],
		const tarch::la::Vector< Dimensions, int > &	vertexPositionWithin3x3Patch ) const

private

Todo

Definition at line 587 of file Spacetree.cpp.

References dfor2, enddforx, peano4::grid::InvalidRank(), and logDebug.

Here is the call graph for this function:

◆ getGridStatistics()

peano4::grid::GridStatistics Spacetree< _Geometry, _Item, THRESHOLD, SPLIT_FACTOR, _TaskBackend >::getGridStatistics ( ) const

Definition at line 1806 of file Spacetree.cpp.

Referenced by peano4::parallel::SpacetreeSet::cleanUpTrees(), and peano4::parallel::SpacetreeSet::getGridStatistics().

Here is the caller graph for this function:

◆ getNeighbourTrees() [1/2]

std::set< int > Spacetree< _Geometry, _Item, THRESHOLD, SPLIT_FACTOR, _TaskBackend >::getNeighbourTrees	(	const GridVertex &	vertex,
		bool	calledByReceivingProcess ) const

private

Get the ids of the surrounding cells of a vertex.

This operation studies the vertex only. Please check manually whether your code is in the states SpacetreeState::NewFromSplit or SpacetreeState::EmptyRun. Joining is not taken into account either. So as a summary: I do analyse the vertex data and I do take into account whether subranks are currently joining or triggered to split. But I do ignore the current spacetree's state.

The operation returns the empty set if a vertex is not local. It also returns the empty set if a vertex is hanging.

Parameters

calledByReceivingProcess The operation relies on GridTraversalEventGenerator::getAdjacentRanksOfFace() to find the adjacent faces. This routine in turn uses getBackupOfAdjacentRanks() if you invoke it on the receiving side and the new adjacent ranks otherwise.

Definition at line 887 of file Spacetree.cpp.

References peano4::grid::GridVertex::getAdjacentRanks(), peano4::grid::GridVertex::getBackupOfAdjacentRanks(), and TwoPowerD.

Here is the call graph for this function:

◆ getNeighbourTrees() [2/2]

int Spacetree< _Geometry, _Item, THRESHOLD, SPLIT_FACTOR, _TaskBackend >::getNeighbourTrees	(	GridVertex	vertex[TwoPowerD],
		int	faceNumber,
		bool	calledByReceivingProcess ) const

private

Get the ids of the surround ids of a face.

We really return only neighbour ids, i.e. no ids of periodic boundary conditions.

Implementation remarks

The domain ids (adjacency lists) along the boundary tell us what the neighbour number is. If a neighbouring rank has triggered a split, we get an updated adjacency list for affected vertices. This list is immediately merged into the the local vertex. The new entries however are only to be taken into account when we send data. For receives, we should stick to the old entries. Therefore, we use the backup of the adjacency list when we receive data, but we use the updated/new list when we send out stuff.

If we bump into a new vertex, we should explicitly ignore it when we receive. After all, new vertices cannot yet have triggered incoming data. The counterpart is deleted vertices which should not contribute towards a send command.

Returns: -1 (TraversalObserver::NoData) if there's no neighbour or face is not local.

Definition at line 835 of file Spacetree.cpp.

References peano4::grid::EmptyRun, peano4::grid::InvalidRank(), logDebug, logTraceInWith3Arguments, logTraceOutWith1Argument, peano4::grid::NewFromSplit, peano4::grid::TraversalObserver::NoData, and TwoPowerD.

Here is the call graph for this function:

◆ getSplittingTree()

int Spacetree< _Geometry, _Item, THRESHOLD, SPLIT_FACTOR, _TaskBackend >::getSplittingTree ( ) const

private

Returns: Id of splitting tree or -1 if there's none.

Definition at line 1797 of file Spacetree.cpp.

◆ incrementNumberOfAdjacentRefinedLocalCells()

void Spacetree< _Geometry, _Item, THRESHOLD, SPLIT_FACTOR, _TaskBackend >::incrementNumberOfAdjacentRefinedLocalCells ( GridVertex vertices[TwoPowerD] )

staticprivate

Every local refined cell should call this routine.

We increment the respective counter. Upon storage, we then refine if the counter equals 2^d. This way we avoid hanging vertices within the domain.

Definition at line 1107 of file Spacetree.cpp.

References dfor2, enddforx, logDebug, and peano4::grid::toString().

Here is the call graph for this function:

◆ isCellSplitCandidate()

bool Spacetree< _Geometry, _Item, THRESHOLD, SPLIT_FACTOR, _TaskBackend >::isCellSplitCandidate	(	GridVertex	coarseGridVertices[TwoPowerD],
		GridVertex	fineGridVertices[TwoPowerD] ) const

private

Can a cell be split (deployed to another rank)

Not all cells are a fit and can be deployed to another rank even though the spacetree set wants to split a tree. Please read through Peano's domain decomposition discussion and the two splitting constraints therein to understand why this routine may or may not label a cell as splitable.

Cells that disqualify for splitting are

Cells which a adjacent to a periodic boundary conditions. Such cells (including their adjacent vertices) all are kept on tree 0 so all periodic boundary data exchange happens on tree 0 only.
Non-local cells (obviously)
Local cells whose master is not local. If we'd move such cells to another rank, we'd destroy the logical tree topology.
Cells that are adjacent of hanging nodes, while the parent cell is not splitable.

Definition at line 1638 of file Spacetree.cpp.

References tarch::la::contains(), dfor2, enddforx, and peano4::grid::isSpacetreeNodeLocal().

Here is the call graph for this function:

◆ isFaceAlongPeriodicBoundaryCondition()

bool Spacetree< _Geometry, _Item, THRESHOLD, SPLIT_FACTOR, _TaskBackend >::isFaceAlongPeriodicBoundaryCondition	(	GridVertex	vertex[TwoPowerD],
		int	faceNumber,
		bool	calledByReceivingProcess ) const

private

Definition at line 811 of file Spacetree.cpp.

References logTraceInWith2Arguments, logTraceOutWith2Arguments, and TwoPowerD.

◆ isInvolvedInJoinOrFork()

bool Spacetree< _Geometry, _Item, THRESHOLD, SPLIT_FACTOR, _TaskBackend >::isInvolvedInJoinOrFork ( ) const

Definition at line 1939 of file Spacetree.cpp.

◆ isSpacetreeNodeLocal()

bool Spacetree< _Geometry, _Item, THRESHOLD, SPLIT_FACTOR, _TaskBackend >::isSpacetreeNodeLocal	(	GridVertex	vertices[TwoPowerD],
		bool	splittingIsConsideredLocal,
		bool	joiningIsConsideredLocal ) const

private

Wrapper around GridTraversalEventGenerator::isSpacetreeNodeLocal()

This is a boolean which solely studies the vertices passed in. The generator is the more powerful routine. It offers, for example, an operation GridTraversalEventGenerator::getTreeOwningSpacetreeNode() to find out who actually owns a cell.

Definition at line 115 of file Spacetree.cpp.

◆ isVertexAdjacentToLocalSpacetree()

bool Spacetree< _Geometry, _Item, THRESHOLD, SPLIT_FACTOR, _TaskBackend >::isVertexAdjacentToLocalSpacetree	(	GridVertex	vertex,
		bool	splittingIsConsideredLocal,
		bool	joiningIsConsideredLocal ) const

private

Returns if a vertex is local to adjacent tree.

In the definition here, hanging vertices are never adjacent to the local tree. This is different to the definition in the event generator, where hanging nodes are taken into account.

See also: GridTraversalEventGenerator::isVertexAdjacentToLocalSpacetree() for a slightly different notion of locality.

Definition at line 82 of file Spacetree.cpp.

References peano4::grid::GridVertex::getState(), and peano4::grid::GridVertex::HangingVertex.

Here is the call graph for this function:

◆ joinWithMaster()

void Spacetree< _Geometry, _Item, THRESHOLD, SPLIT_FACTOR, _TaskBackend >::joinWithMaster ( )

private

Join with master.

Call this routine only for degenerated trees, i.e. for trees without any refined local cells.

We have to be careful with the merges. Often when we fork a tree, this tree first is not refined further. We need a couple of sweeps to see whether a tree is refined further or not.

Definition at line 1922 of file Spacetree.cpp.

References assertion, assertion1, and peano4::grid::JoinTriggered.

◆ joinWithWorker()

void Spacetree< _Geometry, _Item, THRESHOLD, SPLIT_FACTOR, _TaskBackend >::joinWithWorker ( int id )

private

Definition at line 1931 of file Spacetree.cpp.

References assertion2, logInfo, and peano4::grid::toString().

Here is the call graph for this function:

◆ loadVertices()

void Spacetree< _Geometry, _Item, THRESHOLD, SPLIT_FACTOR, _TaskBackend >::loadVertices	(	const AutomatonState &	fineGridState,
		GridVertex	coarseGridVertices[TwoPowerD],
		GridVertex	fineGridVertices[TwoPowerD],
		const tarch::la::Vector< Dimensions, int > &	cellPositionWithin3x3Patch,
		TraversalObserver &	observer )

private

Load the vertices of one cell.

The load process has to be done along the local order of the Peano SFC. For this, I rely on PeanoCurve::getFirstVertexIndex().

Hanging vertices

I originally thought that I might be able to run hanging vertices through the in/out stacks, too. In Peano 3, I had such a feature. Yet, there I had a way more complicated logic. In Peano 4, I simplify the logic. As a consequence, I don't know how many adjacent cells a hanging vertex has and thus create a hanging vertex per adjacent cell.

Definition at line 615 of file Spacetree.cpp.

References assertion, assertion2, assertion3, assertionEquals5, assertionNumericalEquals5, peano4::grid::createVertex(), peano4::grid::Delete, peano4::grid::GridVertex::Delete, peano4::utils::dLinearised(), peano4::grid::PeanoCurve::getFirstVertexIndex(), peano4::grid::AutomatonState::getH(), peano4::grid::AutomatonState::getLevel(), peano4::grid::PeanoCurve::getVertexReadStackNumber(), peano4::grid::AutomatonState::getX(), peano4::grid::Hanging, peano4::grid::GridVertex::HangingVertex, peano4::grid::PeanoCurve::isInOutStack(), logDebug, logTraceInWith3Arguments, logTraceOutWith1Argument, tarch::la::multiplyComponents(), peano4::grid::New, peano4::grid::GridVertex::New, peano4::grid::Persistent, peano4::grid::AutomatonState::toString(), peano4::grid::toString(), and TwoPowerD.

Here is the call graph for this function:

◆ markVerticesAroundForkedCell()

void Spacetree< _Geometry, _Item, THRESHOLD, SPLIT_FACTOR, _TaskBackend >::markVerticesAroundForkedCell	(	GridVertex	coarseGridVertices[TwoPowerD],
		GridVertex	fineGridVertices[TwoPowerD] ) const

private

setIsAntecessorOfRefinedVertexInCurrentTreeSweep()

If a cell is given away to another rank, we have to mark the vertices of its mother cell such that we do not coarsen above it and thus effectively remove our whole splitted subpartition. We do this by two means: First, we set the marker setIsAntecessorOfRefinedVertexInCurrentTreeSweep(). We erase at most one level at a time in Peano. Therefore, this flag effectively vetoes any erase call. This flag ensures that updateVertexAfterLoad() in the next grid sweep will erase the mesh.

We do so on both the master and the worker. On the master cell, i.e. the one that forks another cell off, it is clear that we have to mark the vertices, as the vertex information ("hey, I have forked off a finer grid cell and you therefore shall not erase the mesh here") has to propagate immediately. We also set it on the worker, as its vertices will be subject to boundary data exchange. This way, we inform neighbours about the topology, too.

Definition at line 1808 of file Spacetree.cpp.

References assertion1, dfor2, enddforx, peano4::grid::GridVertex::HangingVertex, and peano4::grid::toString().

Here is the call graph for this function:

◆ mayJoinWithMaster()

bool Spacetree< _Geometry, _Item, THRESHOLD, SPLIT_FACTOR, _TaskBackend >::mayJoinWithMaster ( ) const

private

Only ranks that have no kids are allowed to join.

This is implicitly ensured as we have only degenerated trees here, i.e. we only allow a tree to join if it does not host local spacetree nodes. Furthermore, we require a tree to be stationary, i.e. to linger around like that for a while.

See also: join()

Definition at line 1915 of file Spacetree.cpp.

References peano4::grid::Running.

◆ mayJoinWithWorker()

bool Spacetree< _Geometry, _Item, THRESHOLD, SPLIT_FACTOR, _TaskBackend >::mayJoinWithWorker ( ) const

private

We allow at most one join at a time and not while we split.

Definition at line 1910 of file Spacetree.cpp.

References peano4::grid::Running.

◆ maySplit()

bool Spacetree< _Geometry, _Item, THRESHOLD, SPLIT_FACTOR, _TaskBackend >::maySplit ( ) const

private

Is the tree in principle allowed to split.

A tree cannot split if it is brand new or currently involved in some load balancing. Even if a tree is allowed to split, it does not mean that any split might be successful. A tree might for example be stationary yet host so few cells that it cannot split anymore without violating Peano's domain decomposition constraints. This per-cell decision is made by peano4::grid::Spacetree::isCellTopDownSplitCandidate() and peano4::grid::Spacetree::isCellBottomUpSplitCandidate().

Definition at line 1904 of file Spacetree.cpp.

References peano4::grid::Running.

◆ mergeCellFromWorkerWithMasterThroughoutJoin()

void Spacetree< _Geometry, _Item, THRESHOLD, SPLIT_FACTOR, _TaskBackend >::mergeCellFromWorkerWithMasterThroughoutJoin	(	GridVertex	vertex[TwoPowerD],
		GridVertex	fineGridVertices[TwoPowerD] )

private

Merge data from worker with master data throughout join.

Join process

If we receive a remote cell, then this cell is not refined. In this case the (former) workers holds all the valid adjacency data: We might on a master receive a cell right from the middle of the worker's domain where the master has no clue about any adjacency. So we might think that we can copy over the (former) worker's adjacency data.

As we also receive hanging vertices from the worker, we can safely (and pretty naively) copy over the adjacency. THe first non-hanging vertex will bring in the right adjacency information.

There is however one tricky special case. Assume that a rank A serves as master to B and C and both of these workers merge into A. We furthermore study one vertex in-between B and C. The merge runs as follows:

Rank B tells rank C that it will merge its cell into A.
Rank C tells rank B that it will merge its cell into A.
Both ranks update their respective local adjacency lists.
Rank B streams its vertex up to rank A.

If we now simply copied the adjacency list from B, we'd loose the information that a cell is adjacent to C. B has already updated its list, so it is slightly "ahead" of time.

So for a successful merge, it is important that we actually only reset the flags of this very cell. We do so through updateVertexRanksWithinCell(). This logic relies on the fact that we keep adjacency flags of all vertices which are remote yet just one level below the current rank. This check, realised in updateVertexBeforeStore(), ensures we kind of know what we do.

Joins

If we join (parts of) a worker into the local partition, it can happen that the rank receives a vertex that used to be remote before. As a consequence, the local copy of a vertex holds invalid data whereas the incoming data holds up-to-date adjacency information. So if a vertex is remote locally, we take the worker's vertex to deliver accurate adjacency data. The only alteration we make is that we replace the RankOfCellWitchWillBeJoined markers with the rank of the worker. RankOfCellWitchWillBeJoined is used to mark those cells which go to the worker in the join triggered phase, i.e. it is used only on the worker and only to prepare a join.

See also: updateVertexBeforeStore()

Definition at line 1767 of file Spacetree.cpp.

References peano4::grid::isSpacetreeNodeLocal(), logDebug, peano4::grid::toString(), and TwoPowerD.

Here is the call graph for this function:

◆ mergeGridVertexAdjacencyListsAtHorizontalDomainBoundary()

void Spacetree< _Geometry, _Item, THRESHOLD, SPLIT_FACTOR, _TaskBackend >::mergeGridVertexAdjacencyListsAtHorizontalDomainBoundary	(	GridVertex &	vertex,
		const GridVertex &	inVertex,
		int	neighbour )

private

Definition at line 907 of file Spacetree.cpp.

References peano4::grid::GridVertex::getAdjacentRanks(), peano4::grid::InvalidRank(), logDebug, peano4::grid::GridVertex::setAdjacentRanks(), peano4::grid::GridVertex::toString(), and TwoPowerD.

Here is the call graph for this function:

◆ mergeGridVertexRefinementStateAtHorizontalDomainBoundary()

void Spacetree< _Geometry, _Item, THRESHOLD, SPLIT_FACTOR, _TaskBackend >::mergeGridVertexRefinementStateAtHorizontalDomainBoundary	(	GridVertex &	vertex,
		const GridVertex &	inVertex,
		int	neighbour )

private

Called by receiveAndMergeGridVertexAtHorizontalBoundary().

Besides tons of assertions, the routine realises the mergers of the refinement flags and the setIsAntecessorOfRefinedVertexInCurrentTreeSweep. Please consult receiveAndMergeGridVertexAtHorizontalBoundary() for a higher level overview.

Definition at line 928 of file Spacetree.cpp.

References assertion3, assertion4, assertion6, assertionEquals4, tarch::la::contains(), tarch::la::countEqualEntries(), peano4::grid::GridVertex::Delete, tarch::la::equals(), peano4::grid::GridVertex::EraseTriggered, peano4::grid::GridVertex::Erasing, peano4::grid::GridVertex::HangingVertex, logDebug, peano4::grid::GridVertex::New, peano4::grid::GridVertex::Refined, peano4::grid::GridVertex::RefinementTriggered, peano4::grid::GridVertex::Refining, and peano4::grid::GridVertex::Unrefined.

Here is the call graph for this function:

◆ receiveAndMergeGridVertexAtHorizontalBoundary()

void Spacetree< _Geometry, _Item, THRESHOLD, SPLIT_FACTOR, _TaskBackend >::receiveAndMergeGridVertexAtHorizontalBoundary ( GridVertex & vertex )

private

Manage the data exchange after a vertex is loaded for the first time.

The operation has three jobs to do:

We backup the adjacency ranks.
Exchange vertices along domain boundary.
Exchange vertices belonging to periodic boundaries.

The order of these three steps is important. The first one is a simple copy. The other ones loop over neighbours and call a series of operations. Logically, domain boundaries and periodic boundaries for me are both realised by domain cuts. Therefore, we use the same routines within.

Backup of adjacency data

It is convenient to merge the adjacency flags straightaway after a vertex has been loaded and its boundary counterparts have dropped in. However, once we merge we loose the information about the previous traversal's adjacency. This means, when we construct the neighbour information (who merges with what) for the user data (createEnterCellTraversalEvent()) we lack the information we actually need. Therefore, this routine backups the adjacency information from the vertex.

Boundary data exchange (grid)

For a local vertex, i.e. one adjacent to the current active tree, which is neighbouring another tree, we do receive this tree's data copy and then merge it into the local tree.

This approach doesn't work straightforwardly when we split: Lets assume tree 0 is triggered to split into 0 and 1. In a first step, tree 0 enters the state split triggered. It now updates all adjacency lists, so boundary data is already sent out to 1 - even though 1 is not instantiated yet. Once we are done, we copy over (parts of) tree 0 into tree 1, so tree 1 now does exist and is well-prepared to receive the data already dropped by 0. This second step is the actual splitting step. Now, other ranks have still sent in data to 0 which actually should go to 1. We receive those guys, but we have to eliminate explicitly any incoming data we'd expect from 1 as 1 didn't have the chance yet to send it out.

The function is called directly after a vertex has been read from the input stream. Please note that an update of the refinement states (e.g. switch from refinement-triggered to refining) happens after the merge. Any update of the refinement state in this operation hence immediately affects the vertex updates in this very iteration.

The update of the adjacency information is simple: If a neighbour tells us that it has changed an adjacency entry in one of its own fields, i.e. if it has changed its own entry, we copy this information over. Otherwise, we ignore any updates (there should not be any).

Periodic boundary conditions

Periodic boundary conditions fall back to standard boundary data exchanges through specialised stacks. They are supported on tree 0 only. Different to standard boundaries, we don't have to update any adjacency data here, as all periodic values are always handled on spacetree 0.

Horizontal vs. vertical

Has to happen before receiveAndMergeGridVertexAtVerticalBoundary(). See the receiveAndMergeGridVertexAtVerticalBoundary()'s documentation for an explanation. Some more reasons are given in the guidebook.

Context

The routine is called by updateVertexAfterLoad(). The counterpart of the routine is sendGridVertex(). However, as my sends are literally just memcopies, sends are way simpler than this routine. The operation affects solely the grid's vertices. It does not interfere with any user data. In principle, this follows my pattern that the grid has to be there first and then events are triggered afterwards.

Definition at line 1006 of file Spacetree.cpp.

References assertion, assertion1, assertion3, assertion4, dfor2, peano4::grid::EmptyRun, enddforx, peano4::grid::GridVertex::getAdjacentRanks(), peano4::parallel::Node::getInputStackNumberForHorizontalDataExchange(), peano4::parallel::Node::getInstance(), peano4::parallel::Node::getOutputStacksForPeriodicBoundaryExchange(), peano4::parallel::Node::getPeriodicBoundaryExchangeInputStackNumberForOutputStack(), peano4::grid::InvalidRank(), logDebug, logTraceInWith1Argument, logTraceOut, peano4::grid::NewFromSplit, peano4::grid::GridVertex::setBackupOfAdjacentRanks(), and peano4::grid::GridVertex::toString().

Here is the call graph for this function:

◆ receiveAndMergeGridVertexAtVerticalBoundary()

void Spacetree< _Geometry, _Item, THRESHOLD, SPLIT_FACTOR, _TaskBackend >::receiveAndMergeGridVertexAtVerticalBoundary ( GridVertex & vertex )

private

This is a merge routine for vertical data exchange.

It is important that you merge

Join behaviour

If we are joining in another rank, we might get update adjacency information for this rank. Such adjacency updates are important for the outgoing data, i.e. for the send. Logically, the master and the dying worker run in parallel, that is the updates on the worker belong logically into steps after the actual load.

It therefore is important that you invoke this operation afer receiveAndMergeGridVertexAtVerticalBoundary() and that this routine overwrites the adjacentRanks yet not the backup of this field. This way, we are consistent with any horizontal merges on the worker.

See also: receiveAndMergeGridVertexAtHorizontalBoundary()

Definition at line 343 of file Spacetree.cpp.

References assertion3, assertionVectorNumericalEquals3, tarch::la::contains(), peano4::grid::GridVertex::getAdjacentRanks(), peano4::parallel::Node::getInputStackNumberForVerticalDataExchange(), peano4::parallel::Node::getInstance(), logDebug, logTraceInWith2Arguments, logTraceOut, peano4::grid::GridVertex::setAdjacentRanks(), and peano4::grid::GridVertex::toString().

Here is the call graph for this function:

◆ receiveAndMergeUserData()

void Spacetree< _Geometry, _Item, THRESHOLD, SPLIT_FACTOR, _TaskBackend >::receiveAndMergeUserData	(	const AutomatonState &	state,
		TraversalObserver &	observer,
		const GridTraversalEvent &	enterCellTraversalEvent,
		GridVertex	fineGridVertices[TwoPowerD] )

private

Implementation

Run through the vertices in the Peano vertex order (modified z depending on curve orientation). This information is already implicitly encoded in the order of the indices within the event. So no fancy arithmetics is required here anymore.

Definition at line 1350 of file Spacetree.cpp.

References assertion, assertion3, peano4::grid::TraversalObserver::BoundaryExchange, peano4::grid::TraversalObserver::CreateOrDestroyHangingGridEntity, peano4::grid::TraversalObserver::CreateOrDestroyPersistentGridEntity, peano4::grid::EmptyRun, peano4::grid::GridTraversalEvent::getFaceDataFrom(), peano4::grid::GridTraversalEvent::getFaceDataTo(), peano4::parallel::Node::getInputStackNumberForHorizontalDataExchange(), peano4::parallel::Node::getInstance(), peano4::grid::GridTraversalEvent::getIsFaceLocal(), peano4::grid::GridTraversalEvent::getIsVertexLocal(), peano4::parallel::Node::getOutputStackForPeriodicBoundaryExchange(), peano4::parallel::Node::getOutputStacksForPeriodicBoundaryExchange(), peano4::parallel::Node::getPeriodicBoundaryExchangeInputStackNumberForOutputStack(), peano4::grid::GridTraversalEvent::getVertexDataFrom(), peano4::grid::GridTraversalEvent::getVertexDataTo(), peano4::grid::PeanoCurve::isInOutStack(), peano4::grid::Joined, logDebug, logTraceInWith3Arguments, logTraceOut, peano4::grid::NewFromSplit, peano4::grid::TraversalObserver::PeriodicBoundaryDataSwap, peano4::grid::TraversalObserver::receiveAndMergeFace(), peano4::grid::TraversalObserver::receiveAndMergeVertex(), state, peano4::grid::AutomatonState::toString(), peano4::grid::GridTraversalEvent::toString(), peano4::grid::toString(), and TwoPowerD.

Here is the call graph for this function:

◆ refineState()

void Spacetree< _Geometry, _Item, THRESHOLD, SPLIT_FACTOR, _TaskBackend >::refineState	(	const AutomatonState &	coarseGrid,
		AutomatonState	fineGrid[ThreePowerD],
		tarch::la::Vector< Dimensions, int >	fineGridPosition = tarch::la::Vector<Dimensions,int>(0),
		int	axis = Dimensions-1 )

staticprivate

Takes a state (describing a node in the tree) and returns the \( 3^d \) states on the next finer level along the Peano SFC.

This routine is basically the grammar generation of Bader et al. It relies internally on a recursive call of the other refineState() routine along the spatial dimensions.

The array fineGrid is filled along the Peano SFC. So you don't have to traverse the array with a zfor - a simple for is sufficient.

Definition at line 262 of file Spacetree.cpp.

References assertion, assertion6, peano4::utils::dLinearised(), peano4::grid::AutomatonState::getH(), peano4::grid::AutomatonState::getLevel(), peano4::grid::AutomatonState::getX(), peano4::grid::PeanoCurve::invertEvenFlag(), peano4::grid::PeanoCurve::isTraversePositiveAlongAxis(), peano4::grid::PeanoCurve::setEntryFace(), peano4::grid::PeanoCurve::setExitFace(), peano4::grid::AutomatonState::setH(), peano4::grid::AutomatonState::setLevel(), peano4::grid::AutomatonState::setX(), ThreePowerD, peano4::grid::AutomatonState::toString(), peano4::grid::toString(), and TwoTimesD.

Here is the call graph for this function:

◆ removeDuplicateEntriesFromAdjancyListInEvent()

void peano4::grid::Spacetree::removeDuplicateEntriesFromAdjancyListInEvent ( GridTraversalEvent & event ) const

private

Some of the entries in the event are modelled as array (for example the set of neighbours of a vertex), though they are logically sets.

So I befill the lists and then eventually remove duplicates from the lists before I hand out the event. As a result, the lists hold set data, i.e. each entry only once.

Routine could even be static. Nothing changes in the spacetree state. We actually don't even need it.

◆ restrictToCoarseGrid()

bool Spacetree< _Geometry, _Item, THRESHOLD, SPLIT_FACTOR, _TaskBackend >::restrictToCoarseGrid	(	const tarch::la::Vector< Dimensions, int > &	coarseVertexPosition,
		const tarch::la::Vector< Dimensions, int > &	fineVertexPosition )

staticprivate

Determines whether to restrict a vertex to the coarser level or not.

Definition at line 453 of file Spacetree.cpp.

References assertion2.

Referenced by peano4::grid::tests::SpacetreeTest::testRestrictToCoarseGrid().

Here is the caller graph for this function:

◆ sendGridVertex()

void Spacetree< _Geometry, _Item, THRESHOLD, SPLIT_FACTOR, _TaskBackend >::sendGridVertex ( const GridVertex & vertex )

private

This one is to be invoked if and only if a vertex goes to the in/out stacks.

The routine should be called just before the vertex goes to the output stack. We call it in updateVertexBeforeStore() here, so this constraints automatically is followed.

The routine builds up a set over integers into which it adds all ranks that have to receive a copy. Once this is done, it iterates over the set and sends out data. The two-step scheme becomes necessary, as we have to avoid that vertices are sent around multiple times.

As this routine is called from within updateVertexBeforeStore(), we may assume that this is not an empty tree run.

Definition at line 1066 of file Spacetree.cpp.

References assertion2, peano4::grid::EmptyRun, peano4::grid::GridVertex::getAdjacentRanks(), peano4::parallel::Node::getInstance(), peano4::parallel::Node::getOutputStackNumberForHorizontalDataExchange(), peano4::parallel::Node::getOutputStacksForPeriodicBoundaryExchange(), peano4::grid::JoinTriggered, logDebug, logTraceInWith2Arguments, logTraceOutWith1Argument, peano4::grid::GridVertex::setAdjacentRanks(), peano4::grid::GridVertex::toString(), peano4::grid::toString(), and TwoPowerD.

Here is the call graph for this function:

◆ sendUserData()

void Spacetree< _Geometry, _Item, THRESHOLD, SPLIT_FACTOR, _TaskBackend >::sendUserData	(	const AutomatonState &	state,
		TraversalObserver &	observer,
		const GridTraversalEvent &	enterCellTraversalEvent,
		GridVertex	fineGridVertices[TwoPowerD] )

private

Send user data.

Send out data along the MPI boundary (horizontal) and stream data to the splitting, new workers (vertical). This routine is called within descend() as epilogue, i.e. after all data have been stored savely away on the output streams.

Data order on output stacks

When we send out data, we send that data from the output stack, i.e. we assume that the user code has already piped its stuff there. As the output data structure is a stack, we have to be careful: If a cell writes N pieces of data to the output stream and we want to copy the first piece of data into an output stream for MPI, then we have to pick the Nth entry from the output stream. With our modified top(), we can access these elements directly. We just have to be careful that top() equals actually a top(0), so picking the Nth element requires us to call top(N-1).

Masking and selecting transfer data

The routine here does not realise the actual data transfer. It delegates the actual streaming to the observer's sendFace(), sendVertex() and sendCell(). As observers are provided by the user - most frequently generated through the Python API - we know which user data we have tied to the mesh and hence can champion the data transfer.

This separation of concerns implies that the sendXXX routines also can decide to mask out sent data. However, we have to be careful with this masking: We indeed want to be able to mask out horizontal data transfer and vertical data transfer which corresponds to the domain decomposition data exchange. We do not want to mask anything out that has to do with splits or joins.

Todo: Was passiert bei dynamic AMR?

See also: peano4::parallel::SpacetreeSet::streamDataFromSplittingTreeToNewTree() for a discussion of the splitting process and the required data flows.

Definition at line 1463 of file Spacetree.cpp.

References assertion, assertion4, peano4::grid::TraversalObserver::BoundaryExchange, tarch::la::contains(), peano4::grid::TraversalObserver::CreateOrDestroyHangingGridEntity, peano4::grid::TraversalObserver::CreateOrDestroyPersistentGridEntity, peano4::grid::EmptyRun, peano4::grid::TraversalObserver::ForkDomain, peano4::parallel::Node::getInstance(), peano4::parallel::Node::getOutputStackForPeriodicBoundaryExchange(), peano4::parallel::Node::getOutputStackNumberForHorizontalDataExchange(), peano4::parallel::Node::getOutputStackNumberForVerticalDataExchange(), peano4::parallel::Node::getOutputStacksForPeriodicBoundaryExchange(), peano4::grid::PeanoCurve::isInOutStack(), peano4::grid::Joined, logDebug, logTraceInWith3Arguments, logTraceOutWith3Arguments, peano4::grid::TraversalObserver::PeriodicBoundaryDataSwap, state, peano4::grid::AutomatonState::toString(), peano4::grid::toString(), and TwoPowerD.

Here is the call graph for this function:

◆ shouldEraseAdjacencyInformation()

bool Spacetree< _Geometry, _Item, THRESHOLD, SPLIT_FACTOR, _TaskBackend >::shouldEraseAdjacencyInformation	(	const GridVertex &	vertex,
		GridVertex	coarseGridVertices[TwoPowerD],
		tarch::la::Vector< Dimensions, int >	fineVertexPositionWithinPatch ) const

private

Implementation

We only remove adjacency information for unrefined outside vertices and we are very restrictive what we consider to be outside. Indeed, we consider any vertex still local when we are in a join or fork. If a vertex is really outside but refined, we wait for the erase to pass through before we consider erasing any adjacency info.

See also: updateVertexAfterLoad Erases refined vertices outside of local domain.

Definition at line 552 of file Spacetree.cpp.

References tarch::la::contains(), peano4::utils::dLinearised(), peano4::grid::GridVertex::getState(), logTraceInWith2Arguments, logTraceOutWith1Argument, peano4::grid::GridVertex::toString(), and peano4::grid::GridVertex::Unrefined.

Here is the call graph for this function:

◆ split()

void Spacetree< _Geometry, _Item, THRESHOLD, SPLIT_FACTOR, _TaskBackend >::split	(	int	treeId,
		const SplitInstruction &	instruction )

private

Add a split instruction.

Add a new split instruction. Peano's documentation discusses splits in detail, and also clarifies why we need two different approaches to split (see SplitInstruction).

If we add a split, we should commit to one split type: Either all of our splits are top-down or all of them are bottom-up. If we had both types in one grid sweep, we could run into inconsistent grid configurations. At the moment, this is an assumption, i.e. it might work, but I'm just not sure if it really holds.

This constrains (only one type of splitting) is not necessary algorithmically. The logic would support a sequence of different split types. However, both splits use the same helper data structures, and they might be messed up with different split types are combined.

Definition at line 1820 of file Spacetree.cpp.

References assertion3, logWarning, peano4::SplitInstruction::numberOfFineGridCells, and peano4::grid::toString().

Here is the call graph for this function:

◆ splitCellTopDown()

void Spacetree< _Geometry, _Item, THRESHOLD, SPLIT_FACTOR, _TaskBackend >::splitCellTopDown	(	GridVertex	vertex[TwoPowerD],
		GridVertex	fineGridVertices[TwoPowerD] )

private

Split cell in a top down fashion.

The algorithm logic behind this splitting strategy is very simple: We first find out what the next split-off tree would be.

If a cell's parent is deployed to this tree, deploy the current octant too. After all, we want to split in a top-down manner.
If an octant's parent is not yet deployed but the cell would be a split candidate, we trigger the split.
If we deploy an unrefined octant to a new tree, we have to decrease the internal counter by calling updateSplittingCounter().

Unfortunately, the actual splitting is not that simple: We cannot alter the adjacency information of a vertex on-the-fly without running risk to change the vertex ownership. Therefore, we only realise the analysis here and deploy the actual split realisation to splitOrJoinCellBottomUp(). Analysis means that we push a marker on the helper stack _splittedCells whenever we want to split. And we update our internal splitting counters. But we do not realise the split itself, i.e. we do not alter adjacency information.

See also: splitOrJoinCellBottomUp()

Definition at line 1726 of file Spacetree.cpp.

References peano4::SplitInstruction::AggressiveTopDown, assertion, peano4::grid::isSpacetreeNodeLocal(), peano4::grid::isSpacetreeNodeRefined(), logDebug, and peano4::grid::toString().

Here is the call graph for this function:

◆ splitOrJoinCellBottomUp()

void Spacetree< _Geometry, _Item, THRESHOLD, SPLIT_FACTOR, _TaskBackend >::splitOrJoinCellBottomUp	(	GridVertex	vertex[TwoPowerD],
		GridVertex	fineGridVertices[TwoPowerD] )

private

Realise the splits and joins.

This routine alters the vertex adjacency information. That is, it does not yet really split or join. It identifies where to split and join. The adjacency information will be exchanged with (potential) neighbours after this grid traversal and the actual splitting or joining then happens in the next grid sweep. That is, this routine realises the SplitTriggered or JoinTriggered phase. See the discussion in Peano's domain decomposition documentation for a discussion of these subsequent phases.

On the split side, we have two types of splits: Splits that are identified bottom-up. These splits are realised carefully and never split off too many cells. The other splits are top-down splits and they are more aggressive, i.e. they might split off too many cells eventually. What type of split you want to have is controlled by a flag within the split specification when you call split().

Bottom-up splits

The split logic is protected by one big check if splits are active. If no splits are triggered, there is no need to check things further. Any further logic is guided by the fact if a spacetree node is refined and if it is a potential split candidate. The latter is determined by evaluating isCellSplitCandidate().

Our logic is that we focus first of all on the fine grid cells: We aim to split a certain number of fine grid cells into a new tree. If all children of a refined node are split into the same new tree, and if this (parent) node is a potential split candidate, too, then we move it to the newly created tree as well.

We realise an \( LR(3^d) \) grammar to identify the latter situation. This grammar uses the container (stack) _splittedCells over integers.

Every leaf pushes a marker into this container: _id if it is and remains local, the new id if the node has been split, and a -1 otherwise.
A refined cell induces a reduce on the container. \( 3^d\) markers are removed and analysed: If they all have the same id as the next split marker to be used, we add it.
A refined cell finally adds its marker again.

It is important that I evaluate the reduce analysis even if no splits are do be done anymore. Because it might happen that I have just done exactly 9 splits for example (2d) and thus, the parent of these 9 guys should go to the remote node, too. The punchline is that only leaves check if they have to fork. The behaviour of refined octants follows the decisions made for their children before.

Top-down splits

The down splits are discussed in splitCellTopDown(). This is where all the logic sits. The present routine merely impleemnts the decisions made there.

Rationale

I originally realised the splits solely bottom-up, i.e. decided to omit any analysis if the coarse node has already been split. This way, it is very easy to accommodate Peano's two fundamental splitting constraints: We simply veto the split-off of any cell with a hanging node. However, such an approach leads to the situation where adaptive mesh refinements severely constrain the algorithm. In the example in the general discussion

../../documentation/Doxygen/domain-decomposition/regularity-constraint.png

we would not split off any of the cells that are adjacent to the AMR boundary. As we never split off a cell unless all of its children are of the same rank, we would never ever split off the green cell. This is bad in a situation where only splitting off the green cell and all of its children would yield a good domain decomposition. So a sole bottom-up approach is not an option.

See also: splitCellTopDown()

Definition at line 1657 of file Spacetree.cpp.

References peano4::SplitInstruction::AggressiveTopDown, assertion, assertionMsg, peano4::SplitInstruction::BottomUp, peano4::grid::isSpacetreeNodeLocal(), peano4::grid::isSpacetreeNodeRefined(), logDebug, and ThreePowerD.

Here is the call graph for this function:

◆ storeVertices()

void Spacetree< _Geometry, _Item, THRESHOLD, SPLIT_FACTOR, _TaskBackend >::storeVertices	(	const AutomatonState &	fineGridState,
		GridVertex	coarseGridVertices[TwoPowerD],
		GridVertex	fineGridVertices[TwoPowerD],
		const tarch::la::Vector< Dimensions, int > &	cellPositionWithin3x3Patch,
		TraversalObserver &	observer )

private

Definition at line 736 of file Spacetree.cpp.

References assertion, peano4::grid::Delete, peano4::utils::dLinearised(), peano4::grid::PeanoCurve::getFirstVertexIndex(), peano4::grid::PeanoCurve::getVertexWriteStackNumber(), peano4::grid::Hanging, peano4::grid::PeanoCurve::isInOutStack(), logDebug, logTraceInWith1Argument, logTraceOutWith1Argument, peano4::grid::New, peano4::grid::Persistent, peano4::grid::toString(), and TwoPowerD.

Here is the call graph for this function:

◆ toString()

std::string Spacetree< _Geometry, _Item, THRESHOLD, SPLIT_FACTOR, _TaskBackend >::toString ( ) const

Definition at line 1848 of file Spacetree.cpp.

References peano4::grid::toString().

Here is the call graph for this function:

◆ traverse()

void Spacetree< _Geometry, _Item, THRESHOLD, SPLIT_FACTOR, _TaskBackend >::traverse	(	TraversalObserver &	observer,
		bool	calledFromSpacetreeSet = false )

See also: GridTraversalEvent for a discussion of the arising actions. The traversal actually does not issue these actions. It invokes only an observer and hands in the GridTraversalEvent. It is then up to the observer to read out the event and to issue the actions.

Parameters

calledFromSpacetreeSet If you use traverse directly, please do not alter this value

Definition at line 123 of file Spacetree.cpp.

References assertion, assertion2, peano4::grid::TraversalObserver::beginTraversal(), peano4::grid::clear(), peano4::grid::createVertex(), dfor2, peano4::utils::dLinearised(), peano4::grid::EmptyRun, enddforx, peano4::grid::TraversalObserver::endTraversal(), peano4::grid::TraversalObserver::getGridControlEvents(), tarch::logging::Statistics::getInstance(), peano4::grid::InvalidRank(), peano4::grid::Joined, peano4::grid::Joining, peano4::grid::JoinTriggered, tarch::logging::Statistics::log(), logDebug, logInfo, logTraceIn, logTraceOut, peano4::grid::merge(), peano4::grid::NewFromSplit, peano4::grid::NewRoot, peano4::grid::GridVertex::Refined, peano4::grid::GridVertex::Refining, peano4::grid::Running, peano4::grid::GridVertex::setAdjacentRanks(), peano4::grid::GridVertex::setHasBeenParentOfSubtreeVertexInPreviousTreeSweep(), peano4::grid::toString(), TwoPowerD, and TwoTimesD.

Here is the call graph for this function:

◆ updateSplittingCounter()

void Spacetree< _Geometry, _Item, THRESHOLD, SPLIT_FACTOR, _TaskBackend >::updateSplittingCounter ( int treeId )

private

Reduce splitting counter.

Every tree in the list of trees for which we have to trigger a split has an integer counter which highlights how many cells still to offload to the newly created tree. Decrement this counter.

However, do not remove the entry from the split triggered set. We need all of these indices to know in the next sweep which child trees are now in the state splitting i.e. transition from split triggered into splitting.

If we have top-down splits, we might split off two many cells. In this case, ensure that the internal counter does not underrun zero.

Definition at line 1788 of file Spacetree.cpp.

◆ updateVertexAfterLoad()

void Spacetree< _Geometry, _Item, THRESHOLD, SPLIT_FACTOR, _TaskBackend >::updateVertexAfterLoad	(	GridVertex &	vertex,
		GridVertex	fineGridVertices[TwoPowerD],
		const tarch::la::Vector< Dimensions, int > &	fineVertexPositionWithinPatch,
		TraversalObserver &	observer )

private

This operation has multiple purposes.

Merge with neighbour vertices. See receiveAndMergeGridVertexAtHorizontalBoundary().
Roll over the flags. These guys now are merged already. See receiveAndMergeGridVertexAtHorizontalBoundary().
Do the refinement flag (state) update.
Erase non-local vertices if they do not carry a veto flag.

Flag update

Implements the standard refinement status transition, i.e. a triggered becomes actually ing. And if a vertex has been refining or erasing in the previous sweep, we finally update it to refined or unrefined.

This operation has to be called whenever we load a vertex from the input stream, i.e. we touch it for the very first time. We are not allowed to invoke it after we've created a new vertex.

We don't do any statistics here. I've moved all the statistics into updateVertexBeforeStore().

Definition at line 372 of file Spacetree.cpp.

References peano4::grid::EmptyRun, peano4::grid::GridVertex::EraseTriggered, peano4::grid::GridVertex::Erasing, peano4::parallel::Node::getInstance(), peano4::parallel::Node::getOutputStackNumberForVerticalDataExchange(), peano4::grid::Joining, logDebug, logTraceInWith2Arguments, logTraceOutWith1Argument, peano4::grid::NewFromSplit, peano4::grid::GridVertex::Refined, peano4::grid::GridVertex::RefinementTriggered, peano4::grid::GridVertex::Refining, and peano4::grid::GridVertex::Unrefined.

Here is the call graph for this function:

◆ updateVertexBeforeStore()

void Spacetree< _Geometry, _Item, THRESHOLD, SPLIT_FACTOR, _TaskBackend >::updateVertexBeforeStore	(	GridVertex &	vertex,
		GridVertex	fineGridVertices[TwoPowerD],
		const tarch::la::Vector< Dimensions, int > &	fineVertexPositionWithinPatch )

private

Restriction of veto flags

We make each vertex hold a flag isAntecessorOfRefinedVertex. If it is set, we veto any erasing here. This way, we can ensure that the trees remove at most one level at a time. We illustrate all further explanations with a simple example:

Let the red vertices be refined. In a serial code, the tree is not split. You have to glue together the left and right tree. As the middle level's vertex holds the refinement flag, the top level vertex carries the flag isAntecessorOfRefinedVertex. It consequently never is erased. Users first have to remove the finer level.

If we split up tree into two threads, this approach fails if the flag is restricted per core in the bottom-up steps. By the end of the sweep, the flag is set on the right tree, but it is not set on the left tree. We consequently might decide to erase on the left tree but veto this on the right tree.

To eliminate this behaviour, we split up the flag into a current flag and a flag from the previous solution. This flag is rolled over. If the flag is set, it undoes any erase trigger.

Clean-up of vertices

I originally had the following idea:

If a vertex is remote, we manually clear all of its adjacency flags. This is a security thing. It might happen that such a vertex refers to a tree x and that this index x is later re-used (for a new local subtree for example). In this case, a left-over index might suddenly suggest that a totally irrelevant vertex is adjacent to the newish x tree.

However, this is wrong in some cases: We have to keep our adjacency. Because if we merge later on, we rely on this adjacency to find out which vertices we have to join.

So we have to run for the middle way: We erase all adjacency data but if ad only if a vertex is not adjacent to any kid.

A posteriori refinement

If a vertex is surrounded by \( 2^d \) refined cells and is not a refined vertex, we have this weird situation that we have a hanging vertex right within a regularly refined subdomain. Topologically, this is allowed, but it makes no sense, introduces strange artefacts in the visualisation and is very difficult to explain. So I keep track of the refined adjacent cells and refine a posteriori if all adjacent cells are refined.

Parameters

fineVertexPositionWithinPatch Position of vertex within 3x3 or 3x3x3 patch respectively

See also: updateVertexAfterLoad(); mergeCellFromWorkerWithMasterThroughoutJoin() for an explanation why we have to keep all adjacency information that we actually need later for merges.

Definition at line 472 of file Spacetree.cpp.

Here is the call graph for this function:

◆ updateVertexRanksWithinCell()

void Spacetree< _Geometry, _Item, THRESHOLD, SPLIT_FACTOR, _TaskBackend >::updateVertexRanksWithinCell	(	GridVertex	fineGridVertices[TwoPowerD],
		int	newId )

staticprivate

If a cell gets a new id, we have to update its vertices.

This routine is only used for splits. I originally thought I might use it for joins as well. Indeed I can. But I can only do this on the master. The worker may not update any cell immediately. If I do this, then the adjacency information of the adjacent vertices is overwritten and I loose this clue that these vertices are adjacent to the local, joining rank.

If we split, we have to be careful that we preserve the master-worker topology over the ranks. So this routine may only be called on the master, on a cell that is local, and on a cell whose parent is local, too.

Definition at line 1117 of file Spacetree.cpp.

References dfor2, enddforx, and TwoPowerD.

Friends And Related Symbol Documentation

◆ peano4::grid::tests::SpacetreeTest

friend class peano4::grid::tests::SpacetreeTest

friend

Definition at line 61 of file Spacetree.h.

◆ peano4::parallel::SpacetreeSet

friend class peano4::parallel::SpacetreeSet

friend

Definition at line 60 of file Spacetree.h.

Field Documentation

◆ _childrenIds

std::set<int> peano4::grid::Spacetree::_childrenIds

private

Definition at line 110 of file Spacetree.h.

Referenced by peano4::parallel::SpacetreeSet::cleanUpTrees().

◆ _gridControlEvents

std::vector< peano4::grid::GridControlEvent > peano4::grid::Spacetree::_gridControlEvents

private

We get these control events when we kick off the traversal and then realise/interpret them.

Definition at line 158 of file Spacetree.h.

◆ _gridTraversalEventGenerator

GridTraversalEventGenerator peano4::grid::Spacetree::_gridTraversalEventGenerator

private

Definition at line 128 of file Spacetree.h.

◆ _hasSplit

std::set<int> peano4::grid::Spacetree::_hasSplit

private

I need this post-mortem list to identify which tree structures have to be copied/replicated where.

Definition at line 134 of file Spacetree.h.

◆ _id

int peano4::grid::Spacetree::_id

private

Definition at line 88 of file Spacetree.h.

Referenced by Spacetree(), and Spacetree().

◆ _joining

std::set< int > peano4::grid::Spacetree::_joining

private

If master: Set of workers that should join.

Definition at line 147 of file Spacetree.h.

◆ _joinTriggered

std::set< int > peano4::grid::Spacetree::_joinTriggered

private

This should be -1 if no join is triggered.

Otherwise it holds the id of the joining rank.

Definition at line 142 of file Spacetree.h.

◆ _log

tarch::logging::Log Spacetree< _Geometry, _Item, THRESHOLD, SPLIT_FACTOR, _TaskBackend >::_log

staticprivate

Definition at line 58 of file Spacetree.h.

◆ _masterId

int peano4::grid::Spacetree::_masterId

private

This is not a static master.

There's only a real master-worker relation built into this part of the code when we actually split or join.

This field should be const (it never changes), but in the MPI case, I wanna be able to construct a tree first and then to set the master. Actually, I should introduce a special constructor for this.

Definition at line 109 of file Spacetree.h.

◆ _periodicBC

const std::bitset<Dimensions> peano4::grid::Spacetree::_periodicBC

private

Indicate per axis whether we have periodic boundary conditions.

Definition at line 115 of file Spacetree.h.

Referenced by Spacetree().

◆ _root

AutomatonState peano4::grid::Spacetree::_root

private

The root of a spacetree corresponds to the initial state of the tree traversal automaton.

So we reuse the object here. It is basically the bounding box.

Definition at line 97 of file Spacetree.h.

Referenced by Spacetree(), and Spacetree().

◆ _spacetreeState

SpacetreeState peano4::grid::Spacetree::_spacetreeState

private

Definition at line 90 of file Spacetree.h.

◆ _splittedCells

std::vector<int> peano4::grid::Spacetree::_splittedCells

private

See also: splitOrJoinCellBottomUp() For both the usage and a description how we hijack the routine.

Definition at line 457 of file Spacetree.h.

◆ _splitting

std::set<int> peano4::grid::Spacetree::_splitting

private

Definition at line 126 of file Spacetree.h.

◆ _splitTriggered

SplitSpecification peano4::grid::Spacetree::_splitTriggered

private

A split is identified by a tuple of id and cell count which tells the code how many cells should go to a particular id.

The actual split then is done in a second iteration, i.e. we first bookmark all split requests and then we roll over the requests in the subsequent iteration to be actually performed.

Definition at line 124 of file Spacetree.h.

◆ _statistics

GridStatistics peano4::grid::Spacetree::_statistics

private

Definition at line 99 of file Spacetree.h.

Referenced by peano4::parallel::SpacetreeSet::cleanUpTrees(), Spacetree(), and Spacetree().

◆ _vertexStack

peano4::grid::Spacetree::GridVertexStackMap Spacetree< _Geometry, _Item, THRESHOLD, SPLIT_FACTOR, _TaskBackend >::_vertexStack

staticprivate

Definition at line 152 of file Spacetree.h.

Referenced by peano4::parallel::SpacetreeSet::deleteAllStacks(), peano4::parallel::SpacetreeSet::exchangeHorizontalDataBetweenTrees(), peano4::parallel::SpacetreeSet::exchangeVerticalDataBetweenTrees(), peano4::parallel::SpacetreeSet::shutdown(), and peano4::parallel::SpacetreeSet::streamDataFromSplittingTreesToNewTrees().

◆ NoJoin

constexpr int peano4::grid::Spacetree::NoJoin = -1

staticconstexprprivate

Definition at line 137 of file Spacetree.h.

◆ NumberOfStationarySweepsToWaitAtLeastTillJoin

constexpr int peano4::grid::Spacetree::NumberOfStationarySweepsToWaitAtLeastTillJoin = 2

staticconstexpr

Definition at line 55 of file Spacetree.h.

Referenced by Spacetree().

◆ RankOfPeriodicBoundaryCondition

constexpr int peano4::grid::Spacetree::RankOfPeriodicBoundaryCondition = -2

staticconstexpr

Periodic boundary conditions are technically realised as domain decomposition, i.e.

the vertices along the periodic boundaries carry rank numbers which host RankOfPeriodicBoundaryCondition. So this is the rank number dedicated to periodic BCs. As we treat the BCs as particular neighbour ranks, all data along the periodic BCs is automatically piped onto specialised streams. This holds for both user and grid data.

See also: receiveAndMergeUserData(); sendUserData()

Definition at line 54 of file Spacetree.h.

Referenced by peano4::grid::GridTraversalEventGenerator::areFacesAdjacentToParallelDomainBoundary(), peano4::grid::GridTraversalEventGenerator::areVerticesAdjacentToParallelDomainBoundary(), peano4::parallel::Node::getPeriodicBoundaryNumber(), peano4::parallel::tests::NodeTest::testGetOutputStacksForPeriodicBoundaryExchange(), and peano4::parallel::tests::NodeTest::testGetPeriodicBoundaryNumber().

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

src/peano4/grid/Spacetree.h
src/peano4/grid/Spacetree.cpp

Public Member Functions

Static Public Attributes

Private Types

Private Member Functions

Static Private Member Functions

Private Attributes

Static Private Attributes

Friends

Detailed Description

Member Typedef Documentation

◆ GridVertexStackMap

Constructor & Destructor Documentation

◆ Spacetree() [1/2]

◆ Spacetree() [2/2]

◆ ~Spacetree()

Member Function Documentation

◆ areAllVerticesNonHanging()

◆ areAllVerticesRefined()

◆ areAllVerticesUnrefined()

◆ convertToIntegerVector()

◆ descend()

Veto erases

◆ doesRankIndexIdentifyHorizontalDataExchange()

◆ evaluateGridControlEvents()

◆ getAdjacentRanksForNewVertex()

◆ getGridStatistics()

◆ getNeighbourTrees() [1/2]

◆ getNeighbourTrees() [2/2]

Implementation remarks

◆ getSplittingTree()

◆ incrementNumberOfAdjacentRefinedLocalCells()

◆ isCellSplitCandidate()

◆ isFaceAlongPeriodicBoundaryCondition()

◆ isInvolvedInJoinOrFork()

◆ isSpacetreeNodeLocal()

◆ isVertexAdjacentToLocalSpacetree()

◆ joinWithMaster()

◆ joinWithWorker()

◆ loadVertices()

Hanging vertices

◆ markVerticesAroundForkedCell()

◆ mayJoinWithMaster()

◆ mayJoinWithWorker()

◆ maySplit()

◆ mergeCellFromWorkerWithMasterThroughoutJoin()

Join process

Joins

◆ mergeGridVertexAdjacencyListsAtHorizontalDomainBoundary()

◆ mergeGridVertexRefinementStateAtHorizontalDomainBoundary()

◆ receiveAndMergeGridVertexAtHorizontalBoundary()

Backup of adjacency data

Boundary data exchange (grid)

Periodic boundary conditions

Horizontal vs. vertical

Context

◆ receiveAndMergeGridVertexAtVerticalBoundary()

Join behaviour

◆ receiveAndMergeUserData()

Implementation

◆ refineState()

◆ removeDuplicateEntriesFromAdjancyListInEvent()

◆ restrictToCoarseGrid()

◆ sendGridVertex()

◆ sendUserData()

Data order on output stacks

Masking and selecting transfer data

◆ shouldEraseAdjacencyInformation()

Implementation

◆ split()

◆ splitCellTopDown()

◆ splitOrJoinCellBottomUp()

Bottom-up splits

Top-down splits

Rationale

◆ storeVertices()

◆ toString()

◆ traverse()

◆ updateSplittingCounter()

◆ updateVertexAfterLoad()

Flag update