Peano 4
Loading...
Searching...
No Matches
peano4::grid Namespace Reference

The grid namespace is Peano's core. More...

Namespaces

namespace  internal
 
namespace  tests
 

Data Structures

struct  AutomatonState
 
class  EmptyTraversalObserver
 Empty observer. More...
 
struct  GridControlEvent
 
struct  GridStatistics
 
struct  GridTraversalEvent
 
class  GridTraversalEventGenerator
 Translate grid traversal automaton's transitions into user events. More...
 
struct  GridVertex
 
class  PeanoCurve
 Utility functions specific to the Peano SFC. More...
 
class  Spacetree
 Represents one tree. More...
 
class  TraversalObserver
 
class  TraversalVTKPlotter
 Observer which pipes the automaton transitions into a VTK file. More...
 

Enumerations

enum class  VertexType { New , Hanging , Persistent , Delete }
 
enum class  FaceType { New , Hanging , Persistent , Delete }
 
enum class  CellType { New , Persistent , Delete }
 
enum class  SpacetreeState {
  EmptyRun , NewRoot , NewFromSplit , Running ,
  JoinTriggered , Joining , Joined
}
 
enum class  LoadStoreComputeFlag {
  LoadFromInputStream_ProvideToCalculations_StoreToOutputStream , LoadFromInputStream_ProvideToCalculations_Discard , CreateDummy_ProvideToCalculations_StoreToOutputStream , CreateDummy_ProvideToCalculations_Discard ,
  NoData
}
 Flag to control data movements. More...
 

Functions

void clear (GridStatistics &statistics, bool isGlobalMasterTree)
 The term clear() is not 100% correct, as the number of stationary traversals is not reset to a dummy but instead incremented.
 
std::vector< GridControlEventmerge (std::vector< GridControlEvent > events, const double Tolerance=0.1)
 Merge set of refinement/coarsening commands.
 
GridVertex createVertex (GridVertex::State state, const tarch::la::Vector< Dimensions, double > &x, int level, const tarch::la::Vector< TwoPowerD, int > &adjacentRanks, bool isNewFineGridVertex)
 Factory mechanism.
 
bool isSpacetreeNodeRefined (GridVertex vertices[TwoPowerD])
 A spacetree node is refined if any of its adjacent vertices holds one of the following flags:
 
bool willVertexBeRefined (const GridVertex &vertex)
 A vertex will be refined if it is already refined or currently refining.
 
bool hasVertexBeenRefined (const GridVertex &vertex)
 A vertex has been refined if it is (already) refined or is erasing or the erase has been triggered.
 
std::bitset< TwoPowerDwillVerticesBeRefined (GridVertex vertices[TwoPowerD])
 A vertex is unrefined if it is hanging.
 
std::bitset< TwoPowerDhaveVerticesBeenRefined (GridVertex vertices[TwoPowerD])
 
bool isSpacetreeNodeLocal (GridVertex vertices[TwoPowerD], bool splittingIsConsideredLocal, bool joiningIsConsideredLocal, int id)
 A spacetree node as 2^d adjacent vertices.
 
std::string toString (VertexType type)
 
std::string toString (FaceType type)
 
std::string toString (CellType type)
 
constexpr int InvalidRank (-1)
 
std::string toString (SpacetreeState state)
 
bool overlaps (const tarch::la::Vector< Dimensions, double > &x, const GridControlEvent &event)
 
bool overlaps (const AutomatonState &x, const GridControlEvent &event)
 
bool isContained (const AutomatonState &x, const GridControlEvent &event, double upscaleAutomatonState=1.0)
 isContained() is defined over the closed interval, i.e.
 
void reduceGridControlEvents (std::vector< GridControlEvent > &events)
 Peano 4 does not reduce any grid control events globally.
 
std::string toString (const std::vector< GridControlEvent > &events)
 
std::string toString (const std::list< GridControlEvent > &events)
 
bool loadPersistently (LoadStoreComputeFlag flag)
 Data is stored persistently on input/output stream.
 
bool storePersistently (LoadStoreComputeFlag flag)
 Data is stored persistently on input/output stream.
 
bool computeOnData (LoadStoreComputeFlag flag)
 Data is stored persistently on input/output stream.
 
std::string toString (LoadStoreComputeFlag flag)
 
LoadStoreComputeFlag constructLoadStoreComputeFlag (bool predicateForLoad, bool predicateForStore)
 Constructs a data storage scheme.
 
LoadStoreComputeFlag constructLoadStoreComputeFlag (bool predicateToUseData, bool predicateForLoad, bool predicateForStore)
 Constructs a data storage scheme.
 

Detailed Description

The grid namespace is Peano's core.

There are a few key classes in this namespace which realise Peano's core:

  • GridVertex: Represents one vertex of the tree. These vertices are geometric objects and do not carry any user data. They solely span the grid.
  • Spacetree: Represents one tree. A tree is totally defined via its vertices. When we run through the mesh, we have a unique AutomatonState and the vertices which give us all information we need for our DFS.
  • PeanoCurve: A collection of utility routines which are used to work with the Peano SFC. The routines therein help us to identify which stacks are to be accessed. This is main purpose of this routine collection/class.
  • GridTraversalEvent and TraversalObserver: The spacetree holds the grid data and manages the grid traversal through its automaton. It does not invoke any user routines, manage partitions or move around user data. It however issues GridTraversalEvents and passes them over to a TraversalObserver. That's where the user code plugs in.
  • GridTraversalEventGenerator Translates the transitions of the tree traversal automaton into GridTraversalEvents. It is a collection of utility routines.

Enumeration Type Documentation

◆ CellType

enum class peano4::grid::CellType
strong
Enumerator
New 
Persistent 
Delete 

Definition at line 270 of file grid.h.

◆ FaceType

enum class peano4::grid::FaceType
strong
Enumerator
New 
Hanging 
Persistent 
Delete 

Definition at line 268 of file grid.h.

◆ LoadStoreComputeFlag

Flag to control data movements.

This flag is used to determine data movements. It has nothing to do with which events are triggered at any point. It simply controls which data is moved between the stacks by the tree traversal automaton. The routine constructLoadStoreComputeFlag() provides some documentation of the semantics of the variants, while loadPersistently(), storePersistently() and computeOnData() are used to make decisions which data to copy/move from stack to stack.

Enumerator
LoadFromInputStream_ProvideToCalculations_StoreToOutputStream 
LoadFromInputStream_ProvideToCalculations_Discard 
CreateDummy_ProvideToCalculations_StoreToOutputStream 
CreateDummy_ProvideToCalculations_Discard 
NoData 

Definition at line 22 of file LoadStoreComputeFlag.h.

◆ SpacetreeState

enum class peano4::grid::SpacetreeState
strong
Enumerator
EmptyRun 

Not yet a new root.

Just got created, so we have to run through the cloned data once, just to get it into the right order, and then we can really mirror the master's traversal and send out stuff (in state NewRoot).

NewRoot 
NewFromSplit 

Set if this tree results from a split and if this is the first grid sweep when the former owner actually is in the mode splitting.

Running 
JoinTriggered 

Join has been triggered for this tree.

Nothing is happening yet. It is only the worker that updates all adjacency lists. These updates however are not yet given to the master.

Joining 
Joined 

Definition at line 278 of file grid.h.

◆ VertexType

enum class peano4::grid::VertexType
strong
Enumerator
New 
Hanging 
Persistent 
Delete 

Definition at line 266 of file grid.h.

Function Documentation

◆ clear()

◆ computeOnData()

bool peano4::grid::computeOnData ( LoadStoreComputeFlag flag)

Data is stored persistently on input/output stream.

These actions are derived from the storage annotation. They do not imply in any way that events are called or are not called. That is, we we only control data movements and initialisations. In this particular case, we use the predicate to find out if we have to initialise stack data once we have created it (as it is hanging or brand new). We always set the meta data, but some stack entries holds (smart) pointers and by default point into the nirvana. They might have to be initialised explicitly by using the default constructor.

See also
peano4::stacks::STDVectorStackOverSmartPointers Study the documentation of the constructor with the ObjectConstruction::NoData argument in detail.
peano4.output.Observer for the usage of this routine within an observer
LoadStoreComputeFlag for an overview
constructLoadStoreComputeFlag() for a discussion of the data flow semantics

Definition at line 72 of file LoadStoreComputeFlag.cpp.

References assertion.

◆ constructLoadStoreComputeFlag() [1/2]

peano4::grid::LoadStoreComputeFlag peano4::grid::constructLoadStoreComputeFlag ( bool predicateForLoad,
bool predicateForStore )

Constructs a data storage scheme.

Same as constructLoadStoreComputeFlag(bool,bool,bool), assuming that its predicateToUseData holds all the time.

Definition at line 95 of file LoadStoreComputeFlag.cpp.

References constructLoadStoreComputeFlag().

Referenced by constructLoadStoreComputeFlag().

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

◆ constructLoadStoreComputeFlag() [2/2]

peano4::grid::LoadStoreComputeFlag peano4::grid::constructLoadStoreComputeFlag ( bool predicateToUseData,
bool predicateForLoad,
bool predicateForStore )

Constructs a data storage scheme.

Same as the other constructor, assuming that its predicateToUseData holds all the time. This routine is often used by user code to construct the enum, i.e. it is a sole helper routine. Peano itself does not directly use it.

predicateToUseData predicateForLoad predicateForStore Result Description
False False False NoData Just ignore the data, as it is not used
False True False LoadFromInputStream_ProvideToCalculations_Discard Load it (and keep it as you've loaded it anyway) but then throw it away, as it is not used
False False True CreateDummy_ProvideToCalculations_StoreToOutputStream It will not be used, but create a dummy, as it has to be stored eventually
False True True assertion Makes no sense
True False False CreateDummy_ProvideToCalculations_Discard Data is required temporarily throughout calculations but not persistent in-between two grid sweeps
True True False LoadFromInputStream_ProvideToCalculations_Discard Data flow-wisely the same as False, True, False
True False True CreateDummy_ProvideToCalculations_StoreToOutputStream Introduce a new piece of data into the data flow. Same as false, false, true
True True True LoadFromInputStream_ProvideToCalculations_StoreToOutputStream Proper piece of data that's held persistently in-between two mesh sweeps

Definition at line 99 of file LoadStoreComputeFlag.cpp.

References assertion, CreateDummy_ProvideToCalculations_Discard, CreateDummy_ProvideToCalculations_StoreToOutputStream, LoadFromInputStream_ProvideToCalculations_Discard, LoadFromInputStream_ProvideToCalculations_StoreToOutputStream, and NoData.

◆ createVertex()

peano4::grid::GridVertex peano4::grid::createVertex ( GridVertex::State state,
const tarch::la::Vector< Dimensions, double > & x,
int level,
const tarch::la::Vector< TwoPowerD, int > & adjacentRanks,
bool isNewFineGridVertex )

Factory mechanism.

We expect the calling code to tell us about the adjacent ranks of a vertex. There is a routine Spacetree::getAdjacentRanksForNewVertex() which allows you to distill adjacency information while you step down within the tree and create new vertices. This is information we write directly into the new data plus the backup of the old data. This means, by the time we create a new vertex, anybody analysing the adjacency information things that this data has always been there.

Dummy values

There are a few attributes which should have dummy values. There are also a few attributes which are set later on throughout the traversal, but I should initialise them here properly to ensure that valgrind's memchecker doesn't complain.

Parameters
adjacentRanksTypically the result from Spacetree::getAdjacentRanksForNewVertex(coarseGridVertices,vertexPositionWithin3x3Patch).

Definition at line 65 of file grid.cpp.

References peano4::grid::GridVertex::setAdjacentRanks(), peano4::grid::GridVertex::setBackupOfAdjacentRanks(), peano4::grid::GridVertex::setHasBeenAntecessorOfRefinedVertexInPreviousTreeSweep(), peano4::grid::GridVertex::setIsAntecessorOfRefinedVertexInCurrentTreeSweep(), peano4::grid::GridVertex::setLevel(), peano4::grid::GridVertex::setNumberOfAdjacentRefinedLocalCells(), peano4::grid::GridVertex::setState(), and state.

Referenced by peano4::grid::Spacetree::loadVertices(), and peano4::grid::Spacetree::traverse().

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

◆ hasVertexBeenRefined()

bool peano4::grid::hasVertexBeenRefined ( const GridVertex & vertex)

A vertex has been refined if it is (already) refined or is erasing or the erase has been triggered.

Definition at line 254 of file grid.cpp.

References peano4::grid::GridVertex::getState().

Referenced by haveVerticesBeenRefined(), and isSpacetreeNodeRefined().

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

◆ haveVerticesBeenRefined()

std::bitset< TwoPowerD > peano4::grid::haveVerticesBeenRefined ( GridVertex vertices[TwoPowerD])

Definition at line 268 of file grid.cpp.

References assertion, hasVertexBeenRefined(), and TwoPowerD.

Referenced by peano4::grid::GridTraversalEventGenerator::createGenericCellTraversalEvent().

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

◆ InvalidRank()

◆ isContained()

bool peano4::grid::isContained ( const AutomatonState & x,
const GridControlEvent & event,
double upscaleAutomatonState = 1.0 )

isContained() is defined over the closed interval, i.e.

we look if x is contained within the cube spanned by x including its faces.

Returns
x is completely embedded into event. x is subject to a re-calibration.

Definition at line 44 of file grid.cpp.

References tarch::la::allGreaterEquals(), tarch::la::allSmallerEquals(), assertion1, peano4::grid::GridControlEvent::getOffset(), peano4::grid::GridControlEvent::getWidth(), and state.

Referenced by peano4::grid::Spacetree::evaluateGridControlEvents().

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

◆ isSpacetreeNodeLocal()

bool peano4::grid::isSpacetreeNodeLocal ( GridVertex vertices[TwoPowerD],
bool splittingIsConsideredLocal,
bool joiningIsConsideredLocal,
int id )

A spacetree node as 2^d adjacent vertices.

So there are 2^d integers stored within these vertices that overlap with the current node. They all have to be the same. If they identify the local _id, then the node is local. They are also local if the markers are set to RankOfCellWitchWillBeJoined. This magic constant identifies cells on a worker which might join into their master.

Throughout the splitting process, an id might be already set to a remote rank, though it still is technically and logically local. So this routine interprets locality pretty technical and even marks those cells as non-local (anymore) which still are for another grid sweep or two.

Referenced by peano4::grid::GridTraversalEventGenerator::createGenericCellTraversalEvent(), peano4::grid::Spacetree::descend(), peano4::grid::GridTraversalEventGenerator::getTreeOwningSpacetreeNode(), peano4::grid::Spacetree::isCellSplitCandidate(), peano4::grid::Spacetree::mergeCellFromWorkerWithMasterThroughoutJoin(), peano4::grid::Spacetree::splitCellTopDown(), and peano4::grid::Spacetree::splitOrJoinCellBottomUp().

Here is the caller graph for this function:

◆ isSpacetreeNodeRefined()

bool peano4::grid::isSpacetreeNodeRefined ( GridVertex vertices[TwoPowerD])

A spacetree node is refined if any of its adjacent vertices holds one of the following flags:

  • refining If all vertices are refining or hanging or triggered, but none of them has one of the flags discussed below, then we run into a brand new cell of the tree.
  • refinement-triggered
  • erase-triggered We want to erase this spacetree node, but the erase process is not triggered yet.
  • erasing If none of the other vertices holds another flag of this list, then this cell is to be removed.

Definition at line 242 of file grid.cpp.

References dfor2, enddforx, hasVertexBeenRefined(), k, and willVertexBeRefined().

Referenced by peano4::grid::Spacetree::descend(), peano4::grid::Spacetree::splitCellTopDown(), and peano4::grid::Spacetree::splitOrJoinCellBottomUp().

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

◆ loadPersistently()

bool peano4::grid::loadPersistently ( LoadStoreComputeFlag flag)

Data is stored persistently on input/output stream.

These actions are derived from the storage annotation. They do not imply in any way that events are called or are not called. That is, we we only control data movements and initialisations.

See also
peano4.output.Observer for the usage of this routine within an observer
LoadStoreComputeFlag for an overview
constructLoadStoreComputeFlag() for a discussion of the data flow semantics

Definition at line 27 of file LoadStoreComputeFlag.cpp.

References assertion.

◆ merge()

std::vector< peano4::grid::GridControlEvent > peano4::grid::merge ( std::vector< GridControlEvent > events,
const double Tolerance = 0.1 )

Merge set of refinement/coarsening commands.

This routine has two roles:

  • It shall reduce the number of refine events, so the actual AMR checks are faster when we next trigger the traversal
  • It brings together the erase events: Erases are only triggered if a cell is completely embedded into an event. See Spacetree::evaluateGridControlEvents() for details. However, if we have two adjacent erase events, then it might happen that none of them hosts a cell, while the merger of the two of them does host one.

Algorithm

The algorithm works in multiple steps:

  • We separate erase from refine events.
  • We remove those erase events which are overwritten by refinement events. As we work conservatively, refinement events are always more important than coarsening ones.
  • Sort the events
  • Create the erase power set.
  • The code is asked to fuse multiple adjacent refinement events into fewer large ones, and to fuse multiple coarsening events as well. This reduces the event count, and gives the coarsening more flexibility (see discussion above).
  • We join the remaining erase and refinement lists.

Sorting

We sort the respective events along x,y,z offset. In 2d, this doesn't make that much of a difference, for d>2 it is important: The merger of multiple events works in a greedy fashion. Otherwise, it would be too slow. Due to this greediness, we now might run into situations where we are stuck. Consider a 2x2x2 cube of refinement operations which all have the same target resolution. It should be possible to merge this cube into one single large cube. However, we might end up with

   (r_111,r_211), (r_121,r_122), (r_212,r_222), r_112, r221)

These six events now can't be merged greedily anymore.

Once we sort the events by x,y,z, the original input sequence implicitly ensures that we first merge along the z direction, then along y, and finally along x:

   (r_111,r1_112,r_121,r_122,r_211,r1_212,r_221,r_222)

Erasing the mesh (again)

We have to create the power sets over all erase events. This gives the mesh the opportunity to see faster where erases are possible, as it also handle non-rectangular regions: Assume there's a large L-shape of erase instructions consisting of three erase commands. Our algorithm will create a rectangle plus a square when it fuses the erases.

Consequently, any cell overlapping with the boundary between the square and the rectangle will not be erased.

If we had not merged the three cubic erases forming the L into 2+1 but into 2+2, we would also cover the boundary of the L shape. Therefore, it is important that we construct the power set before we merge events.

The power set construction very quickly explodes, i.e. leads to a vast number of events. I thus manually truncate the creation of new events.

Remark: I had to remove this power set step, as it turned out to be too time consuming.

Properties

The algorithm has to be idempotent, i.e. if we invoke it multiple times over the input set, the outcome should always remain the same.

Parameters
eventsSet of events which we try to merge
ToleranceRelative tolerance passed into the actual merger, i.e. the tolerance at which two events are merged, even though they might not exactly be adjacent. A default of 10% (relative tolerance) is sufficient for most cases, but there might be situation where a larger tolerance is reasonable to ensure that some events which are slightly disjoint are actually merged, too.

Definition at line 113 of file grid.cpp.

References logDebug, logTraceInWith1Argument, and logTraceOutWith1Argument.

Referenced by swift2::commitGridControlEvents(), exahype2::RefinementControlService::finishStep(), peano4::grid::tests::GridControlEventTest::testMerge1(), peano4::grid::tests::GridControlEventTest::testMerge2(), peano4::grid::tests::GridControlEventTest::testMerge3(), and peano4::grid::Spacetree::traverse().

Here is the caller graph for this function:

◆ overlaps() [1/2]

bool peano4::grid::overlaps ( const AutomatonState & x,
const GridControlEvent & event )

◆ overlaps() [2/2]

bool peano4::grid::overlaps ( const tarch::la::Vector< Dimensions, double > & x,
const GridControlEvent & event )

◆ reduceGridControlEvents()

void peano4::grid::reduceGridControlEvents ( std::vector< GridControlEvent > & events)

Peano 4 does not reduce any grid control events globally.

If you want to reduce these events, you have to do so manually. Operation becomes identify if you don't compile with MPI.

This is a blocking routine, and it thus requires all ranks to call it at exactly the same time. Use it with care. In ExaHyPE 2, e.g., I prefer a more anarchic exchange of grid control events.

Definition at line 395 of file grid.cpp.

References tarch::mpi::Rank::getCommunicator(), tarch::mpi::Rank::getInstance(), tarch::mpi::Rank::getNumberOfRanks(), tarch::mpi::Rank::getRank(), j, and logDebug.

Here is the call graph for this function:

◆ storePersistently()

bool peano4::grid::storePersistently ( LoadStoreComputeFlag flag)

Data is stored persistently on input/output stream.

These actions are derived from the storage annotation. They do not imply in any way that events are called or are not called. That is, we we only control data movements and initialisations.

See also
peano4.output.Observer for the usage of this routine within an observer
LoadStoreComputeFlag for an overview
constructLoadStoreComputeFlag() for a discussion of the data flow semantics

Definition at line 49 of file LoadStoreComputeFlag.cpp.

References assertion.

◆ toString() [1/7]

std::string peano4::grid::toString ( CellType type)

Definition at line 305 of file grid.cpp.

◆ toString() [2/7]

std::string peano4::grid::toString ( const std::list< GridControlEvent > & events)

Definition at line 103 of file grid.cpp.

◆ toString() [3/7]

std::string peano4::grid::toString ( const std::vector< GridControlEvent > & events)

Definition at line 90 of file grid.cpp.

◆ toString() [4/7]

std::string peano4::grid::toString ( FaceType type)

Definition at line 291 of file grid.cpp.

◆ toString() [5/7]

std::string peano4::grid::toString ( LoadStoreComputeFlag flag)

Definition at line 6 of file LoadStoreComputeFlag.cpp.

◆ toString() [6/7]

std::string peano4::grid::toString ( SpacetreeState state)

Definition at line 317 of file grid.cpp.

References state.

◆ toString() [7/7]

std::string peano4::grid::toString ( VertexType type)

◆ willVertexBeRefined()

bool peano4::grid::willVertexBeRefined ( const GridVertex & vertex)

A vertex will be refined if it is already refined or currently refining.

It also will be refined if the erase is only triggered.

Definition at line 249 of file grid.cpp.

References peano4::grid::GridVertex::getState().

Referenced by isSpacetreeNodeRefined(), and willVerticesBeRefined().

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

◆ willVerticesBeRefined()

std::bitset< TwoPowerD > peano4::grid::willVerticesBeRefined ( GridVertex vertices[TwoPowerD])

A vertex is unrefined if it is hanging.

Returns
bitset of vertices for which isVertexRefined() holds. If you wanna find out whether a cell is refined, you can compare the result to zero. You can also use isSpacetreeNodeRefined() instead.

Definition at line 259 of file grid.cpp.

References assertion, TwoPowerD, and willVertexBeRefined().

Referenced by peano4::grid::GridTraversalEventGenerator::createGenericCellTraversalEvent().

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