Peano 4
Loading...
Searching...
No Matches
peano4::grid::Spacetree Class Reference

Represents one tree. More...

#include <Spacetree.h>

Collaboration diagram for peano4::grid::Spacetree:

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::GridVertexStackGridVertexStackMap
 

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, intgetAdjacentRanksForNewVertex (GridVertex coarseGridVertices[TwoPowerD], const tarch::la::Vector< Dimensions, int > &vertexPositionWithin3x3Patch) const
 
void split (int treeId, const SplitInstruction &instruction)
 Add a split instruction.
 
std::set< intgetNeighbourTrees (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, intconvertToIntegerVector (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

Constructor & Destructor Documentation

◆ Spacetree() [1/2]

peano4::grid::Spacetree::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()

peano4::grid::Spacetree::~Spacetree ( )

Definition at line 80 of file Spacetree.cpp.

Member Function Documentation

◆ areAllVerticesNonHanging()

bool peano4::grid::Spacetree::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, peano4::grid::GridVertex::HangingVertex, and k.

◆ areAllVerticesRefined()

bool peano4::grid::Spacetree::areAllVerticesRefined ( GridVertex vertices[TwoPowerD]) const
private

Definition at line 103 of file Spacetree.cpp.

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

◆ areAllVerticesUnrefined()

bool peano4::grid::Spacetree::areAllVerticesUnrefined ( GridVertex vertices[TwoPowerD]) const
private

Definition at line 109 of file Spacetree.cpp.

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

◆ convertToIntegerVector()

tarch::la::Vector< Dimensions, int > peano4::grid::Spacetree::convertToIntegerVector ( const std::bitset< Dimensions > & in)
staticprivate

Little helper.

Should likely go into la or utils.

Definition at line 334 of file Spacetree.cpp.

◆ descend()

void peano4::grid::Spacetree::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 1207 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, k, 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 peano4::grid::Spacetree::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 799 of file Spacetree.cpp.

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

Here is the call graph for this function:

◆ evaluateGridControlEvents()

void peano4::grid::Spacetree::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 1121 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 > peano4::grid::Spacetree::getAdjacentRanksForNewVertex ( GridVertex coarseGridVertices[TwoPowerD],
const tarch::la::Vector< Dimensions, int > & vertexPositionWithin3x3Patch ) const
private
Todo

Definition at line 586 of file Spacetree.cpp.

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

Here is the call graph for this function:

◆ getGridStatistics()

peano4::grid::GridStatistics peano4::grid::Spacetree::getGridStatistics ( ) const

Definition at line 1917 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 > peano4::grid::Spacetree::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
calledByReceivingProcessThe 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 886 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 peano4::grid::Spacetree::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 834 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 peano4::grid::Spacetree::getSplittingTree ( ) const
private
Returns
Id of splitting tree or -1 if there's none.

Definition at line 1908 of file Spacetree.cpp.

◆ incrementNumberOfAdjacentRefinedLocalCells()

void peano4::grid::Spacetree::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 1106 of file Spacetree.cpp.

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

Here is the call graph for this function:

◆ isCellSplitCandidate()

bool peano4::grid::Spacetree::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 1637 of file Spacetree.cpp.

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

Here is the call graph for this function:

◆ isFaceAlongPeriodicBoundaryCondition()

bool peano4::grid::Spacetree::isFaceAlongPeriodicBoundaryCondition ( GridVertex vertex[TwoPowerD],
int faceNumber,
bool calledByReceivingProcess ) const
private

Definition at line 810 of file Spacetree.cpp.

References logTraceInWith2Arguments, logTraceOutWith2Arguments, and TwoPowerD.

◆ isInvolvedInJoinOrFork()

bool peano4::grid::Spacetree::isInvolvedInJoinOrFork ( ) const

Definition at line 2050 of file Spacetree.cpp.

◆ isSpacetreeNodeLocal()

bool peano4::grid::Spacetree::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 peano4::grid::Spacetree::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 peano4::grid::Spacetree::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 2033 of file Spacetree.cpp.

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

◆ joinWithWorker()

void peano4::grid::Spacetree::joinWithWorker ( int id)
private

Definition at line 2042 of file Spacetree.cpp.

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

Here is the call graph for this function:

◆ loadVertices()

void peano4::grid::Spacetree::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 614 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 peano4::grid::Spacetree::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 1919 of file Spacetree.cpp.

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

Here is the call graph for this function:

◆ mayJoinWithMaster()

bool peano4::grid::Spacetree::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 2026 of file Spacetree.cpp.

References peano4::grid::Running.

◆ mayJoinWithWorker()

bool peano4::grid::Spacetree::mayJoinWithWorker ( ) const
private

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

Definition at line 2021 of file Spacetree.cpp.

References peano4::grid::Running.

◆ maySplit()

bool peano4::grid::Spacetree::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 2015 of file Spacetree.cpp.

References peano4::grid::Running.

◆ mergeCellFromWorkerWithMasterThroughoutJoin()

void peano4::grid::Spacetree::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 1855 of file Spacetree.cpp.

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

Here is the call graph for this function:

◆ mergeGridVertexAdjacencyListsAtHorizontalDomainBoundary()

void peano4::grid::Spacetree::mergeGridVertexAdjacencyListsAtHorizontalDomainBoundary ( GridVertex & vertex,
const GridVertex & inVertex,
int neighbour )
private

◆ mergeGridVertexRefinementStateAtHorizontalDomainBoundary()

void peano4::grid::Spacetree::mergeGridVertexRefinementStateAtHorizontalDomainBoundary ( GridVertex & vertex,
const GridVertex & inVertex,
int neighbour )
private

◆ receiveAndMergeGridVertexAtHorizontalBoundary()

void peano4::grid::Spacetree::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 1005 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(), k, 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 peano4::grid::Spacetree::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 342 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 peano4::grid::Spacetree::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 1349 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 peano4::grid::Spacetree::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 261 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 peano4::grid::Spacetree::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 452 of file Spacetree.cpp.

References assertion2.

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

Here is the caller graph for this function:

◆ sendGridVertex()

void peano4::grid::Spacetree::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 1065 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 peano4::grid::Spacetree::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 1462 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 peano4::grid::Spacetree::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 551 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 peano4::grid::Spacetree::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 1931 of file Spacetree.cpp.

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

Here is the call graph for this function:

◆ splitCellTopDown()

void peano4::grid::Spacetree::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 1814 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 peano4::grid::Spacetree::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, ThreePowerD, and peano4::grid::toString().

Here is the call graph for this function:

◆ storeVertices()

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

◆ toString()

std::string peano4::grid::Spacetree::toString ( ) const

Definition at line 1959 of file Spacetree.cpp.

References peano4::grid::toString().

Here is the call graph for this function:

◆ traverse()

void peano4::grid::Spacetree::traverse ( TraversalObserver & observer,
bool calledFromSpacetreeSet = false )

◆ updateSplittingCounter()

void peano4::grid::Spacetree::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 1899 of file Spacetree.cpp.

◆ updateVertexAfterLoad()

void peano4::grid::Spacetree::updateVertexAfterLoad ( GridVertex & vertex,
GridVertex fineGridVertices[TwoPowerD],
const tarch::la::Vector< Dimensions, int > & fineVertexPositionWithinPatch,
TraversalObserver & observer )
private

This operation has multiple purposes.

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 371 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 peano4::grid::Spacetree::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
fineVertexPositionWithinPatchPosition 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 471 of file Spacetree.cpp.

References dfor2, peano4::grid::EmptyRun, enddforx, peano4::grid::GridVertex::EraseTriggered, peano4::grid::GridVertex::Erasing, peano4::grid::GridVertex::getIsAntecessorOfRefinedVertexInCurrentTreeSweep(), peano4::grid::GridVertex::getIsParentOfSubtreeVertexInCurrentTreeSweep(), peano4::grid::GridVertex::getNumberOfAdjacentRefinedLocalCells(), peano4::grid::GridVertex::getState(), peano4::grid::InvalidRank(), k, logDebug, logTraceInWith2Arguments, logTraceOutWith2Arguments, peano4::grid::GridVertex::New, peano4::grid::GridVertex::Refined, peano4::grid::GridVertex::RefinementTriggered, peano4::grid::GridVertex::Refining, peano4::grid::Running, peano4::grid::GridVertex::setAdjacentRanks(), peano4::grid::GridVertex::setState(), peano4::grid::GridVertex::toString(), peano4::grid::toString(), TwoPowerD, and peano4::grid::GridVertex::Unrefined.

Here is the call graph for this function:

◆ updateVertexRanksWithinCell()

void peano4::grid::Spacetree::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 1116 of file Spacetree.cpp.

References dfor2, enddforx, k, and TwoPowerD.

Friends And Related Symbol Documentation

◆ peano4::grid::tests::SpacetreeTest

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 peano4::grid::Spacetree::_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

◆ 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: