Peano 4
Loading...
Searching...
No Matches
peano4::parallel::SpacetreeSet Class Reference

The spacetree set has to be a singleton, as it is reponsible to accept requests for new trees from remote ranks. More...

#include <SpacetreeSet.h>

Inheritance diagram for peano4::parallel::SpacetreeSet:
Collaboration diagram for peano4::parallel::SpacetreeSet:

Data Structures

class  TraverseTask
 Each task triggers the traversal of one specific spacetree. More...
 

Public Member Functions

 ~SpacetreeSet ()
 As the setis a singleton and a service, it has to deregister itself.
 
void answerQuestions ()
 Run through the set of unanswered questions and, well, answer them.
 
virtual void receiveDanglingMessages () override
 We poll the tree management messages.
 
void init (const tarch::la::Vector< Dimensions, double > &offset, const tarch::la::Vector< Dimensions, double > &width, const std::bitset< Dimensions > &periodicBC=0)
 
virtual void shutdown () override
 
void traverse (peano4::grid::TraversalObserver &observer)
 Invoke traverse on all spacetrees in parallel.
 
peano4::grid::GridStatistics getGridStatistics () const
 Return statistics object for primary spacetree.
 
peano4::grid::GridStatistics getGridStatistics (int treeId) const
 
bool split (int treeId, const peano4::SplitInstruction &instruction, int targetRank)
 Split a local tree.
 
bool isLocalSpacetree (int treeId) const
 Codes hold one spacetree set per rank.
 
std::set< intgetLocalSpacetrees () const
 
- Public Member Functions inherited from tarch::services::Service
virtual ~Service ()
 

Static Public Member Functions

template<class Container >
static void exchangeAllHorizontalDataExchangeStacks (Container &stackContainer, int spacetreeId, bool symmetricDataCardinality)
 Realise domain boundary exchange (over multiple scales)
 
template<class Container >
static void exchangeAllPeriodicBoundaryDataStacks (Container &stackContainer, int spacetreeId)
 Exchange periodic BC data.
 
template<class Container >
static void exchangeAllVerticalDataExchangeStacks (Container &stackContainer, int spacetreeId, int parentId)
 
template<class Container >
static void deleteAllStacks (Container &stackContainer, int spacetreeId)
 
template<class Container >
static void finishAllOutstandingSendsAndReceives (Container &stackContainer, int spacetreeId)
 This routine finishes all the sends and receives that are still active, i.e.
 
template<class Container >
static void streamDataFromSplittingTreeToNewTree (Container &stackContainer, int master, int worker)
 Copies (streams) data from the master to the worker.
 
template<class Container >
static void streamDataFromJoiningTreeToMasterTree (Container &stackContainer, int master, int worker)
 
static SpacetreeSetgetInstance ()
 

Private Types

enum class  SpacetreeSetState { Waiting , TraverseTreesAndExchangeData }
 

Private Member Functions

peano4::grid::SpacetreegetSpacetree (int id)
 
const peano4::grid::SpacetreegetSpacetree (int id) const
 
int getAnswerTag (int targetSpacetreeId) const
 
void exchangeHorizontalDataBetweenTrees (peano4::grid::TraversalObserver &observer)
 
void exchangeVerticalDataBetweenTrees (peano4::grid::TraversalObserver &observer)
 
void deleteAllStacks (peano4::grid::TraversalObserver &observer, int spacetreeId)
 I do this after a join/after I've removed an empty tree.
 
void streamDataFromSplittingTreesToNewTrees (peano4::grid::TraversalObserver &observer)
 Copy the data from a splitting tree onto its new workers.
 
void createNewTrees ()
 This operation should be called pretty close towards the end of a traversal.
 
void deleteClonedObservers ()
 
void addSpacetree (int masterId, int newTreeId)
 Adds a new spacetree to the set.
 
void streamLocalVertexInformationToMasterThroughVerticalStacks (int spacetreeId, int parentId, const std::set< int > &joiningIds)
 Whenever we join two partitions, we have to stream data from the worker to the master.
 
void cleanUpTrees (peano4::grid::TraversalObserver &observer)
 
std::set< intgetLocalTreesMergingWithWorkers () const
 I need this routine for technical reasons: Prior to the sweep of trees, I have to identify all of those trees which wanna merge with their workers.
 
void createObserverCloneIfRequired (peano4::grid::TraversalObserver &observer, int treeId)
 Quick lookup whether an observer clone for this tree id does already exist.
 
 SpacetreeSet ()
 
 SpacetreeSet (const SpacetreeSet &)=delete
 
SpacetreeSetoperator= (const SpacetreeSet &)=delete
 

Static Private Member Functions

static std::string toString (SpacetreeSetState state)
 

Private Attributes

std::vector< peano4::parallel::TreeManagementMessage_unansweredMessages
 
int _requestMessageTag
 I use this tag to identify messages send from one tree to another rank.
 
int _answerMessageTag
 Never use this tag directly.
 
std::list< peano4::grid::Spacetree_spacetrees
 These are the local spacetrees.
 
SpacetreeSetState _state
 The state identifies what the set is doing right now.
 
std::map< int, peano4::grid::TraversalObserver * > _clonedObserver
 I create/clone one observer per local tree.
 

Static Private Attributes

static SpacetreeSet _singleton
 
static tarch::logging::Log _log
 Logging device.
 
static tarch::multicore::BooleanSemaphore _semaphore
 Semaphore to protect container holding all the local trees.
 

Friends

class peano4::grid::Spacetree
 

Additional Inherited Members

- Protected Attributes inherited from tarch::services::Service
tarch::multicore::RecursiveSemaphore _receiveDanglingMessagesSemaphore
 Recursive semaphores.
 

Detailed Description

The spacetree set has to be a singleton, as it is reponsible to accept requests for new trees from remote ranks.

So there is only one set.

Author
Tobias Weinzierl

Definition at line 41 of file SpacetreeSet.h.

Member Enumeration Documentation

◆ SpacetreeSetState

Enumerator
Waiting 
TraverseTreesAndExchangeData 

Definition at line 302 of file SpacetreeSet.h.

Constructor & Destructor Documentation

◆ SpacetreeSet() [1/2]

peano4::parallel::SpacetreeSet::SpacetreeSet ( )
private

Definition at line 27 of file SpacetreeSet.cpp.

◆ SpacetreeSet() [2/2]

peano4::parallel::SpacetreeSet::SpacetreeSet ( const SpacetreeSet & )
privatedelete

◆ ~SpacetreeSet()

peano4::parallel::SpacetreeSet::~SpacetreeSet ( )

As the setis a singleton and a service, it has to deregister itself.

Otherwise, the overall service landscape still might try to call receiveDanglingMessages().

Definition at line 70 of file SpacetreeSet.cpp.

Member Function Documentation

◆ addSpacetree()

void peano4::parallel::SpacetreeSet::addSpacetree ( int masterId,
int newTreeId )
private

Adds a new spacetree to the set.

The responsibility goes over to the set. The operation clones the original spacetree handed in into a new spacetree with the id newTreeId.

Local node

If the new tree will be a local tree, we simply add a new tree object. The Spacetree's constructor takes care of all the "cloning". Clone here means a setup. We traverse this tree afterwards separately to stream all data in.

Distributed memory In a distributed memory environment, we have to break up the creation into a set of sends forth and back through TreeManagementMessages. This routine is the one that sends out the requests. Multithreading

I may not globally lock this routine, as I otherwise would block the createObserverCloneIfRequired(). So I literally "only" protect the actual push back in the vector.

Call sequence

The operation is used by createNewTrees() .

Definition at line 219 of file SpacetreeSet.cpp.

References peano4::parallel::TreeManagementMessage::Acknowledgement, assertion1, assertionMsg, peano4::parallel::TreeManagementMessage::CreateNewRemoteTree, peano4::parallel::TreeManagementMessage::getAction(), peano4::parallel::Node::getInstance(), tarch::mpi::Rank::getInstance(), peano4::parallel::Node::getRank(), logDebug, logTraceInWith2Arguments, logTraceOut, peano4::parallel::TreeManagementMessage::receive(), peano4::grid::AutomatonState::send(), peano4::parallel::TreeManagementMessage::sendAndPollDanglingMessages(), peano4::parallel::TreeManagementMessage::setAction(), peano4::parallel::TreeManagementMessage::setMasterSpacetreeId(), peano4::parallel::TreeManagementMessage::setWorkerSpacetreeId(), state, and peano4::parallel::TreeManagementMessage::toString().

Referenced by createNewTrees().

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

◆ answerQuestions()

void peano4::parallel::SpacetreeSet::answerQuestions ( )

Run through the set of unanswered questions and, well, answer them.

The following messages are received/handled:

split() is something any rank can trigger at any time. Most default load balancers call it throughout the end of the grid sweep. addSpacetree() is called by the set through createNewTrees() just before all observers are deleted and the traversal terminates. cleanUpTrees() just arises before that one.

No all of these messages can be answered at any point of the local grid sweeps. That is, we may never add a tree to the local tree collection while we are right in the middle of traversals on this rank, e.g. We may not insert or remove trees from the global data structure while we are still traversing some local trees or run some data exchange. I originally tried to protect the whole code by a _state==SpacetreeSetState::Waiting check, i.e. to make the set react if and only if we are not doing anything anyway. That did not work properly, as tree requests for example are to be handled immediately. So what I do now is that I pipe all requests into a vector. Then, I run through the vector and, depending on the set state, do answer messages or leave them in the queue for the time being.

This approach leads to errors whenever a message send-out is followed by a second message that provides further details. The first message might be buffered locally, and, as we can't answer the first one immediately, the second message (of another datatype) will be interpreted as yet another request. So that means that every single message exchange with the set always has to be follow a send-acknowledge pattern.

Action::RequestNewRemoteTree

Can be answered any time, as it literally just books a new number but nothing more happens at this point. The acknowledgement message carries the new tree's number.

Action::CreateNewRemoteTree

This message triggers the insertation of a new tree into the local set of spacetrees. We thus may handle it if and only if we are the end of a traversal. The message logically consists of two parts: The master of a new tree (which has previously used Action::RequestNewRemoteTree to get a new tree's number) sends out the create message, waits for the acknowledgement and then sends out the tree state, to the rank hosting the new tree can actually create the data structure. This last step is followed by an acknowledge message which carries no particular information. That is, this message exchange belongs to the one-way information flow, but we have one acknowledgement message to say "go ahead", and one message to say "ok, we got it".

Action::RemoveChildTreeFromBooksAsChildBecameEmpty

This is a simple one though we have again to ensure that it is handled if and only if we have finishes the local traversals and thus can safely manipulate the local spacetree.

Data consistency

In this routine, we have to be very careful with the data consistency. While we are running through the set of unanswered messages, new ones might drop in. However, C++ is not very happy if a vector is added further elements while we are traversing it (in theory, it might happen that it is expanded and thus copied). So what I do is something different: I first run through the vector and take those out that I know that I can handle. Then I handle these guys and return - well-aware that meanwhile further messages might have dropped in. Which is something I don't care, as I rely on the calling code just to invoke answer again if it is important for the code's progress.

Todo
replyToUnansweredMessages() sollte der Name sein

Definition at line 88 of file SpacetreeSet.cpp.

References peano4::parallel::TreeManagementMessage::Acknowledgement, assertion, assertionMsg, peano4::parallel::TreeManagementMessage::CreateNewRemoteTree, tarch::mpi::Rank::getCommunicator(), peano4::parallel::Node::getInstance(), tarch::mpi::Rank::getInstance(), peano4::parallel::TreeManagementMessage::JoinWithWorker, logDebug, logInfo, peano4::grid::AutomatonState::receive(), peano4::parallel::TreeManagementMessage::RemoveChildTreeFromBooksAsChildBecameEmpty, peano4::parallel::TreeManagementMessage::RequestNewRemoteTree, peano4::parallel::Node::reserveId(), peano4::parallel::TreeManagementMessage::send(), peano4::parallel::TreeManagementMessage::setAction(), peano4::parallel::TreeManagementMessage::setWorkerSpacetreeId(), and state.

Referenced by traverse().

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

◆ cleanUpTrees()

void peano4::parallel::SpacetreeSet::cleanUpTrees ( peano4::grid::TraversalObserver & observer)
private

Merge process

We make the worker first of all decide whether to merge or not. A worker has the control/knowledge whether to join or not. When a rank wants to join, we first of all run the workers. Then, all data is the join buffers. After that, we sweep through the masters to take up the data. So we may not merge both the worker and the master into their workers at the same time. If we did so, we'd not be able to run all the merging trees in parallel.

Definition at line 613 of file SpacetreeSet.cpp.

References peano4::grid::Spacetree::_childrenIds, _requestMessageTag, _spacetrees, peano4::grid::Spacetree::_statistics, peano4::parallel::TreeManagementMessage::Acknowledgement, assertion1, assertionMsg, deleteAllStacks(), peano4::parallel::Node::deregisterId(), peano4::parallel::TreeManagementMessage::getAction(), getAnswerTag(), peano4::grid::GridStatistics::getCoarseningHasBeenVetoed(), tarch::mpi::Rank::getCommunicator(), peano4::grid::Spacetree::getGridStatistics(), peano4::parallel::Node::getInstance(), tarch::mpi::Rank::getInstance(), tarch::mpi::Rank::getRank(), peano4::parallel::Node::getRank(), getSpacetree(), peano4::grid::Joined, logDebug, logError, logInfo, logTraceIn, logTraceOut, peano4::parallel::TreeManagementMessage::receive(), peano4::parallel::TreeManagementMessage::RemoveChildTreeFromBooksAsChildBecameEmpty, peano4::parallel::TreeManagementMessage::send(), peano4::grid::GridStatistics::setRemovedEmptySubtree(), and peano4::parallel::TreeManagementMessage::toString().

Referenced by traverse().

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

◆ createNewTrees()

void peano4::parallel::SpacetreeSet::createNewTrees ( )
private

This operation should be called pretty close towards the end of a traversal.

I recommend to invoke it after cleanUpTrees(). It creates new trees and thus might invoke remote method calls on other ranks. It is thus important that all the data exchange locally is done - otherwise we might ask another rank to create a tree for us, while the other rank still waits for boundary data from our side.

See also
exchangeDataBetweenTrees() for details.

Definition at line 489 of file SpacetreeSet.cpp.

References _spacetrees, and addSpacetree().

Referenced by traverse().

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

◆ createObserverCloneIfRequired()

void peano4::parallel::SpacetreeSet::createObserverCloneIfRequired ( peano4::grid::TraversalObserver & observer,
int treeId )
private

Quick lookup whether an observer clone for this tree id does already exist.

If not, we create one quickly.

Multithreading

This operation uses a lock on the semaphore to ensure that no two threads insert an observer into the global table at the same time.

Definition at line 291 of file SpacetreeSet.cpp.

References _clonedObserver, _semaphore, assertion2, and peano4::grid::TraversalObserver::clone().

Referenced by deleteAllStacks(), exchangeHorizontalDataBetweenTrees(), exchangeVerticalDataBetweenTrees(), and streamDataFromSplittingTreesToNewTrees().

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

◆ deleteAllStacks() [1/2]

template<class Container >
void peano4::parallel::SpacetreeSet::deleteAllStacks ( Container & stackContainer,
int spacetreeId )
static

Definition at line 21 of file SpacetreeSet.cpph.

References assertion, peano4::parallel::Node::getInstance(), tarch::mpi::Rank::getInstance(), and logDebug.

Referenced by cleanUpTrees(), and deleteAllStacks().

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

◆ deleteAllStacks() [2/2]

void peano4::parallel::SpacetreeSet::deleteAllStacks ( peano4::grid::TraversalObserver & observer,
int spacetreeId )
private

I do this after a join/after I've removed an empty tree.

Have to call it explicitly, as a join does not delete/throw away the data. It simply hands on data ownership.

Definition at line 362 of file SpacetreeSet.cpp.

References _clonedObserver, peano4::grid::Spacetree::_vertexStack, createObserverCloneIfRequired(), deleteAllStacks(), logTraceInWith1Argument, and logTraceOut.

Here is the call graph for this function:

◆ deleteClonedObservers()

void peano4::parallel::SpacetreeSet::deleteClonedObservers ( )
private
See also
_clonedObserver

Definition at line 498 of file SpacetreeSet.cpp.

References _clonedObserver.

Referenced by traverse().

Here is the caller graph for this function:

◆ exchangeAllHorizontalDataExchangeStacks()

template<class Container >
void peano4::parallel::SpacetreeSet::exchangeAllHorizontalDataExchangeStacks ( Container & stackContainer,
int spacetreeId,
bool symmetricDataCardinality )
static

Realise domain boundary exchange (over multiple scales)

This routine realises the boundary data exchange, i.e. it send outs in iteration n and receives (see counterpart routine), but the received data is used only in traversal n+1. The whole exchange thus asynchronous (logically).

Typically, this routine is called by user observers to for their user-defined data. We however also use it within the grid to trigger the actual vertex data exchange. As these routines all are invoked via tasks, this routine is typically invoked by multiple threads concurrently.

Deep copy semantics for shared memory

Whenever we copy a container over to another thread, we use the clone(). When we study the memory ownership, it is important to memorise that the boundary exchange containers are copies of "real" containers of the code. That is, the mesh looks at a face or vertex and stores its content persistently within the tree. Once it has done this, it analyses if this face or vertex is adjacent to a domain boundary. If so, it copies the data of interest into the boundary container. After the traversal, this copy is either sent out to another rank, or we clone() it into the container of another tree on the same rank (shared memory data exchange). After that, the original boundary container is cleared.

If you work with containers over pointers, the clone() should create a deep copy, whereas otherwise any push and pull only moves pointers around. That is, a container holding boundary data basically holds pointers to data that is also held by containers administering interior data. After the traversal, it is the clone() which ensures that we actually create copies, i.e. work with real halo data which is replicated if data belongs to another tree - even if that tree resides on the same rank. Therefore, we can clear() the output stack. All data there had been pointers to data which are still held by the local tree.

It is the responsibility of the actual merge to ensure that data on the input containers are probably merged into the local data. If these data are pointers, it is the responsibility of the merge to ensure that they are properly deleted. The input stack will be empty after the traversal, as the grid management will pull all data and pipe it into merges, but if they hold pointers, you have to take special care.

See also
python4/peano4/toolbox/particles/ParticleSet.template.h and the merge() implementation therein for an example of a merge of a set of pointers.

Copy semantics for distributed memory

If you launch a distributed memory exchange, it is the responsibility of the container to create a real copy on the incoming rank. If your container managed pointers, this is obviously a deep copy. It is also the container's responsibility to ensure that all data are freed when we call clear() after the send is complete.

If your container holds pointers, it holds pointers which are also held by some containers that are responsible for the interior. So the clear() is just fine, as it eliminates redundant pointers.

Parameters
symmetricDataCardinalityIf two ranks A and B are adjacent to each other, and if A send n entries to B, then B received exactly n entries in turn.
See also
finishAllOutstandingSendsAndReceives();

Definition at line 141 of file SpacetreeSet.cpph.

References assertion, assertion4, assertion8, assertionMsg, peano4::grid::TraversalObserver::BoundaryExchange, peano4::parallel::Node::getGridDataExchangeMetaInformation(), peano4::parallel::Node::getInputStackNumberForHorizontalDataExchange(), peano4::parallel::Node::getInstance(), tarch::mpi::Rank::getInstance(), peano4::parallel::Node::getOutputStackNumberForHorizontalDataExchange(), tarch::mpi::Rank::getRank(), peano4::parallel::Node::getRank(), peano4::parallel::Node::getTreeNumberTiedToExchangeStackNumber(), peano4::parallel::Node::HorizontalData, peano4::parallel::Node::isHorizontalDataExchangeOutputStackNumber(), logDebug, logTraceInWith2Arguments, and logTraceOut.

Referenced by exchangeHorizontalDataBetweenTrees().

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

◆ exchangeAllPeriodicBoundaryDataStacks()

template<class Container >
void peano4::parallel::SpacetreeSet::exchangeAllPeriodicBoundaryDataStacks ( Container & stackContainer,
int spacetreeId )
static

Exchange periodic BC data.

Close to trivial routine, as it basically examines whether anything has been written to a stack that is associated with periodic BCs. If so, the corresponding stack is copied over onto the respective input stack for the subsequent iteration. This routine should degenerate to nop on all ranks besides rank 0.

Definition at line 296 of file SpacetreeSet.cpph.

References assertion4, peano4::parallel::Node::getInstance(), peano4::parallel::Node::isPeriodicBoundaryExchangeOutputStackNumber(), logDebug, logTraceInWith2Arguments, logTraceOut, and peano4::parallel::Node::mapPeriodicBoundaryExchangeOutputStackOntoInputStack().

Referenced by exchangeHorizontalDataBetweenTrees().

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

◆ exchangeAllVerticalDataExchangeStacks()

template<class Container >
void peano4::parallel::SpacetreeSet::exchangeAllVerticalDataExchangeStacks ( Container & stackContainer,
int spacetreeId,
int parentId )
static

Prepare new children after fork

When we prepare new children, we have to map output stack on output stack, as both trees are not yet inverted at the time we invoke this routine. That is, the master's output stack is mapped on to the new child's outpu stack. The master is inverted automatically later on (that's the last thing we do throughout the traversal). For the new child, we have to invert manually however. This is done in exchangeDataBetweenExistingAndNewTreesAndRerunNewTrees().

Parameters
childrenIdsDepending on the context, this is either the children or the new children that are just about to be kicked off

Definition at line 131 of file SpacetreeSet.cpph.

References logTraceInWith2Arguments, and logTraceOutWith2Arguments.

Referenced by exchangeVerticalDataBetweenTrees().

Here is the caller graph for this function:

◆ exchangeHorizontalDataBetweenTrees()

void peano4::parallel::SpacetreeSet::exchangeHorizontalDataBetweenTrees ( peano4::grid::TraversalObserver & observer)
private

Multithreading

I originally intended to make this routine use tasks. However, the data transfer routines do modify the underlying map/stack structures of Peano, as new containers are created, data is moved around, and so forth. So the data exchange per se is not thread-safe. As we do not/can not use threads, we have to be careful with the order. I originally had a loop over the trees that triggered per tree the data exchange and then waited for MPI. Obviously, this does not work with rendezvous protocol. We need two loops. The first one triggers all the MPI sends/receives and it also realises the local data exchange. The second one waits for all MPI operations to terminate.

Definition at line 447 of file SpacetreeSet.cpp.

References _clonedObserver, _spacetrees, peano4::grid::Spacetree::_vertexStack, createObserverCloneIfRequired(), exchangeAllHorizontalDataExchangeStacks(), exchangeAllPeriodicBoundaryDataStacks(), finishAllOutstandingSendsAndReceives(), logDebug, logTraceIn, logTraceOut, and peano4::grid::toString().

Referenced by traverse().

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

◆ exchangeVerticalDataBetweenTrees()

void peano4::parallel::SpacetreeSet::exchangeVerticalDataBetweenTrees ( peano4::grid::TraversalObserver & observer)
private

◆ finishAllOutstandingSendsAndReceives()

template<class Container >
void peano4::parallel::SpacetreeSet::finishAllOutstandingSendsAndReceives ( Container & stackContainer,
int spacetreeId )
static

This routine finishes all the sends and receives that are still active, i.e.

it searched for pending MPI requests and waits for them to finish. After this is ensured, the routine runs over all stacks and ensures that all temporary data is released. The last step is important, as we otherwise quickly run out of memory - we replicate all data structures whenever we fork and as C++ vectors don't release memory, this memory would be lost without a manual freeing.

Definition at line 238 of file SpacetreeSet.cpph.

References tarch::timing::Watch::getCPUTime(), tarch::mpi::Rank::getInstance(), tarch::services::ServiceRepository::getInstance(), logDebug, logTraceInWith1Argument, logTraceOutWith1Argument, tarch::services::ServiceRepository::receiveDanglingMessages(), tarch::mpi::Rank::setDeadlockTimeOutTimeStamp(), tarch::mpi::Rank::setDeadlockWarningTimeStamp(), tarch::timing::Watch::stop(), tarch::mpi::Rank::triggerDeadlockTimeOut(), and tarch::mpi::Rank::writeTimeOutWarning().

Referenced by exchangeHorizontalDataBetweenTrees(), exchangeVerticalDataBetweenTrees(), and streamDataFromSplittingTreesToNewTrees().

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

◆ getAnswerTag()

int peano4::parallel::SpacetreeSet::getAnswerTag ( int targetSpacetreeId) const
private
Returns
tag that one should use to answer one particular spacetree

Definition at line 73 of file SpacetreeSet.cpp.

References peano4::parallel::Node::getInstance(), and peano4::parallel::Node::getLocalTreeId().

Referenced by cleanUpTrees(), and split().

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

◆ getGridStatistics() [1/2]

◆ getGridStatistics() [2/2]

peano4::grid::GridStatistics peano4::parallel::SpacetreeSet::getGridStatistics ( int treeId) const

Definition at line 708 of file SpacetreeSet.cpp.

References assertion2, peano4::grid::Spacetree::getGridStatistics(), tarch::mpi::Rank::getInstance(), getSpacetree(), and isLocalSpacetree().

Here is the call graph for this function:

◆ getInstance()

peano4::parallel::SpacetreeSet & peano4::parallel::SpacetreeSet::getInstance ( )
static

Definition at line 31 of file SpacetreeSet.cpp.

Referenced by swift2::timestepping::computeAdmissibleTimeStepSizeFromGlobalMeshSizeAndMaximumVelocity(), toolbox::loadbalancing::strategies::SplitOversizedTree::computeNumberOfSplits(), toolbox::loadbalancing::strategies::SplitOversizedTree::doesLocalTreeViolateThreshold(), toolbox::loadbalancing::dumpStatistics(), toolbox::loadbalancing::strategies::Hardcoded::finishStep(), toolbox::loadbalancing::CostMetrics::getCostOfLocalRank(), toolbox::loadbalancing::metrics::CellCount::getCostOfLocalTree(), toolbox::loadbalancing::AbstractLoadBalancing::getIdOfHeaviestLocalSpacetree(), toolbox::loadbalancing::AbstractLoadBalancing::getIdOfHeaviestLocalSpacetree(), toolbox::loadbalancing::strategies::SpreadOutHierarchically::getNumberOfSplitsOnLocalRank(), toolbox::loadbalancing::strategies::SplitOversizedTree::getTargetTreeCost(), toolbox::loadbalancing::getWeightOfHeaviestLocalSpacetree(), toolbox::loadbalancing::AbstractLoadBalancing::getWeightOfHeaviestLocalSpacetree(), peano4::initSingletons(), toolbox::loadbalancing::AbstractLoadBalancing::isInterRankBalancingBad(), toolbox::loadbalancing::AbstractLoadBalancing::isIntraRankBalancingBad(), runParallel(), runParallel(), selectNextAlgorithmicStep(), peano4::shutdownSingletons(), step(), toolbox::loadbalancing::strategies::RecursiveBipartition::toString(), toolbox::loadbalancing::strategies::SplitOversizedTree::toString(), toolbox::loadbalancing::strategies::SpreadOut::triggerSplit(), toolbox::loadbalancing::strategies::SpreadOutHierarchically::triggerSplit(), toolbox::loadbalancing::strategies::SpreadOutOnceGridStagnates::triggerSplit(), toolbox::loadbalancing::strategies::RecursiveBipartition::triggerSplit(), toolbox::loadbalancing::strategies::SplitOversizedTree::triggerSplit(), toolbox::loadbalancing::Blacklist::update(), updateDomainDecomposition(), toolbox::loadbalancing::Statistics::updateGlobalView(), toolbox::loadbalancing::metrics::CellCount::updateGlobalView(), toolbox::loadbalancing::strategies::SplitOversizedTree::updateLoadBalancing(), and toolbox::loadbalancing::strategies::SpreadOutHierarchically::updateState().

Here is the caller graph for this function:

◆ getLocalSpacetrees()

◆ getLocalTreesMergingWithWorkers()

std::set< int > peano4::parallel::SpacetreeSet::getLocalTreesMergingWithWorkers ( ) const
private

I need this routine for technical reasons: Prior to the sweep of trees, I have to identify all of those trees which wanna merge with their workers.

This is an analysis I have to do before I actually traverse any worker. Because of this traversal, more trees might denote their workers as joining, so if I query the joining field after the traversal, I intermix newly joining and old joining ranks.

Definition at line 478 of file SpacetreeSet.cpp.

References _spacetrees.

◆ getSpacetree() [1/2]

peano4::grid::Spacetree & peano4::parallel::SpacetreeSet::getSpacetree ( int id)
private

Definition at line 820 of file SpacetreeSet.cpp.

References _spacetrees, assertion3, and tarch::mpi::Rank::getInstance().

Referenced by cleanUpTrees(), getGridStatistics(), and split().

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

◆ getSpacetree() [2/2]

const peano4::grid::Spacetree & peano4::parallel::SpacetreeSet::getSpacetree ( int id) const
private

Definition at line 830 of file SpacetreeSet.cpp.

References _spacetrees, assertion3, and tarch::mpi::Rank::getInstance().

Here is the call graph for this function:

◆ init()

void peano4::parallel::SpacetreeSet::init ( const tarch::la::Vector< Dimensions, double > & offset,
const tarch::la::Vector< Dimensions, double > & width,
const std::bitset< Dimensions > & periodicBC = 0 )

◆ isLocalSpacetree()

bool peano4::parallel::SpacetreeSet::isLocalSpacetree ( int treeId) const

Codes hold one spacetree set per rank.

With this routine, you can find out whether a local set contains a particular id.

Definition at line 742 of file SpacetreeSet.cpp.

References _spacetrees.

Referenced by getGridStatistics(), and updateDomainDecomposition().

Here is the caller graph for this function:

◆ operator=()

SpacetreeSet & peano4::parallel::SpacetreeSet::operator= ( const SpacetreeSet & )
privatedelete

◆ receiveDanglingMessages()

void peano4::parallel::SpacetreeSet::receiveDanglingMessages ( )
overridevirtual

We poll the tree management messages.

Messages are not answered directly. Instead, we buffer them in _unansweredMessages and hand over to replyToUnansweredMessages().

See the description in mpi.h for a howto where this routine is used and how to use it.

Implements tarch::services::Service.

Definition at line 196 of file SpacetreeSet.cpp.

References tarch::mpi::Rank::getInstance(), logDebug, logTraceIn, logTraceOut, peano4::parallel::TreeManagementMessage::receive(), and peano4::parallel::TreeManagementMessage::toString().

Here is the call graph for this function:

◆ shutdown()

void peano4::parallel::SpacetreeSet::shutdown ( )
overridevirtual

◆ split()

bool peano4::parallel::SpacetreeSet::split ( int treeId,
const peano4::SplitInstruction & instruction,
int targetRank )

Split a local tree.

If the target tree shall be stored on the local node, then you pass

int getRank(int treeId) const
You hand in a tree number and the node tells you on which rank such a tree is hosted.
Definition Node.cpp:119
static Node & getInstance()
This operation returns the singleton instance.
Definition Node.cpp:108

as last argument. Splits on the local node allow Peano to exploit more cores on the node. The details of the total splitting procedure are discussed in Peano's generic domain decomposition discussion.

Parameters
treeIdId of tree that should split, i.e. give away cells to a new tree
cellsNumber of cells to deploy to a new tree. This count refers to the status-quo, i.e. if dynamic adaptivity makes an unrefined node of the tree unfold in the next step, the new \( 3^d \) children do count only with one towards this quota.
targetRankRank which should host the new tree.

Definition at line 762 of file SpacetreeSet.cpp.

References _requestMessageTag, peano4::parallel::TreeManagementMessage::Acknowledgement, assertion, assertionMsg, peano4::parallel::TreeManagementMessage::getAction(), getAnswerTag(), peano4::parallel::Node::getInstance(), tarch::mpi::Rank::getInstance(), tarch::getMemoryUsage(), getSpacetree(), tarch::getTotalMemory(), peano4::parallel::TreeManagementMessage::getWorkerSpacetreeId(), logDebug, logInfo, logTraceInWith3Arguments, logTraceOutWith1Argument, logWarning, tarch::MByte, peano4::parallel::TreeManagementMessage::receiveAndPollDanglingMessages(), peano4::parallel::TreeManagementMessage::RequestNewRemoteTree, peano4::parallel::Node::reserveId(), peano4::parallel::TreeManagementMessage::sendAndPollDanglingMessages(), peano4::parallel::TreeManagementMessage::setAction(), peano4::parallel::TreeManagementMessage::setMasterSpacetreeId(), peano4::parallel::TreeManagementMessage::setWorkerSpacetreeId(), and peano4::parallel::TreeManagementMessage::toString().

Referenced by runParallel(), toolbox::loadbalancing::strategies::SpreadOut::triggerSplit(), toolbox::loadbalancing::strategies::SpreadOutHierarchically::triggerSplit(), toolbox::loadbalancing::strategies::SpreadOutOnceGridStagnates::triggerSplit(), toolbox::loadbalancing::strategies::RecursiveBipartition::triggerSplit(), toolbox::loadbalancing::strategies::SplitOversizedTree::triggerSplit(), and updateDomainDecomposition().

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

◆ streamDataFromJoiningTreeToMasterTree()

template<class Container >
void peano4::parallel::SpacetreeSet::streamDataFromJoiningTreeToMasterTree ( Container & stackContainer,
int master,
int worker )
static

Definition at line 14 of file SpacetreeSet.cpph.

◆ streamDataFromSplittingTreesToNewTrees()

void peano4::parallel::SpacetreeSet::streamDataFromSplittingTreesToNewTrees ( peano4::grid::TraversalObserver & observer)
private

Copy the data from a splitting tree onto its new workers.

When we split a tree, we realise this split in two grid sweeps where the second sweep breaks up the traversal into three logical substeps. In the first sweep, the splitting master tells everybody around that it will split. No split is done though. After this first sweep, the grid data structure is replicated on the new worker. Please note that we only replicate the grid, i.e. there's no user information associated with it yet.

In the second sweep, the master still "owns" all data, i.e. it receives all boundary data and merges it in. However, it does not send out boundary data anymore. Instead, it takes all data that should go over to the new worker and dumps it in the vertical data exchange stack. That's part one of the second sweep. Part two means that the new worker runs through its mesh for the first time and incorporates all the streamed user data. After that, we have to run through the grid one more time on the worker (without any action) to get all the data into the right order.

Vertex grid data

The copying of the whole tree data is literally a copying of the output stack of the master. It happens after the master has finished its splitting traversal. peano4::grid::Spacetree::traverse() does invert the traversal direction in an epilogue automatically. Therefore, by the time we hit this routine, we have to copy over the input stack - it is already in the right order for the "counter"- traversal.

We always have to invoke the data exchange for both the master and the worker, i.e. we call it twice. This way, we invoke the data exchange on the destination rank (MPI receive) and on the source rank (MPI send). For a single-node split, the second invocation degenerates to nop automatically. See streamDataFromSplittingTreeToNewTree() which implements a simple emptyness check.

User data

It is only the vertex grid data that is copied over in one rush prior to the splitting state. User data is streamed within the splitting state. See Spacetree::sendUserData(). The latter routine dumps data in the vertical data exchange stacks, and these stacks subsequently are then transferred over by the present routine, too.

Stack types

All the routines copy over the stream stack data, i.e. the stacks for the vertical data exchange. It is hence important to recognise that the normal stacks are not transferred.

See also
streamDataFromSplittingTreeToNewTree()
peano4::grid::Spacetree::sendUserData()

Definition at line 403 of file SpacetreeSet.cpp.

References _clonedObserver, _spacetrees, peano4::grid::Spacetree::_vertexStack, assertion3, createObserverCloneIfRequired(), peano4::maps::HierarchicalStackMap< T >::empty(), peano4::grid::EmptyRun, finishAllOutstandingSendsAndReceives(), peano4::maps::HierarchicalStackMap< T >::getForPush(), peano4::grid::PeanoCurve::getInputStackNumber(), peano4::parallel::Node::getOutputStackNumberForVerticalDataExchange(), logTraceInWith1Argument, logTraceOut, and streamDataFromSplittingTreeToNewTree().

Referenced by traverse().

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

◆ streamDataFromSplittingTreeToNewTree()

template<class Container >
void peano4::parallel::SpacetreeSet::streamDataFromSplittingTreeToNewTree ( Container & stackContainer,
int master,
int worker )
static

Copies (streams) data from the master to the worker.

These are complete copies of the data set as we know that both trees afterwards will coarsen their mesh and thus free resources.

Invoked by user code from streamDataFromSplittingTreeToNewTree() and by spacetree set through SpacetreeSet::streamDataFromSplittingTreesToNewTrees(). SpacetreeSet runs over the set of trees with the label EmptyRun, i.e. those that haven't done any iteration yet. It then invokes this routine (indirectly) on the master. That is, even if you are on a rank where the master does not exist, the code will temporarily create an observer for the master and then ask this observer to trigger the data exchange.

We have to trigger the routine multiple times, to ensure we catch both the on-rank and the between-rank case. As a consequence, we may only stream if the destination stack is still empty.

All data that are streamed are clones of the original data. These clones are created by peano4::parallel::SpacetreeSet::streamDataFromSplittingTreesToNewTrees() before we trigger this routine.

On-rank realisation

If source and destination rank are the same, a tree splits up into two trees both residing on the same MPI rank. We therefore simply copy the stream. As this routine is invoked on the master, it is the master that creates the stream on the worker and befills it.

Please note that in this particular case, the routine is called twice: We call it per rank for the splitting trees and then for the empty ones. The second call however degenerates to nop.

Where to the clones happen?

Data exchange between different ranks

If the master rank is the local guy, then we have to trigger a send. Otherwise, we trigger a receive. The message exchange consists of two phases. An integer message first is exchanged. It carries the number of messages. After that, I send out the actual data.

We don't have to finish any sends, i.e. wait for Isends or Irecvs. SpacetreeSet will call finishAllOutstandingSendsAndReceives() later on.

The routine is idempotent on a single rank, i.e. you can call it multiple times. Only the first one will copy, all the others will become nop. It is not idempotent in a parallel sense. It has to be idempotent, as I indeed have to call it twice in a distributed memory environment: I have to call it on the receiver side and on the sender side.

Data ownership

The routine solely accesses vertical/stream stacks, i.e. checks getOutputStackNumberForVerticalDataExchange(). That is, we assume that all data are ready to be streamed out. For user data, the spacetree's peano4::grid::Spacetree::sendUserData() will deposit all outgoing user data in the respective output buffers. That is, by the time we hit streamDataFromSplittingTreeToNewTree(), all user data is already in a (temporary) output stream. For the actual tree data, we have to deposit it there manually. This happens in peano4::parallel::SpacetreeSet::streamDataFromSplittingTreesToNewTrees().

If we send out data via MPI, I assume that the data resides within a bespoke buffer. tryToFinishSendOrReceive() after all clears the buffer once it has gone out. So it is kind of safe to deposit data in a temporary buffer once. The send implicitly will clear it. After that, the garbage collection will eventually really free the underlying memory.

If the target tree and the destination tree reside on the same rank, this routine does a plain copy-over. In this case, we have to delete the (temporary) stack that is used to stream out stuff after the copy. Otherwise, it will be dead memory in the code. Even worse, should the source tree later on stream once again to the same tree - as the tree meanwhile has degenerated or fused back into the master code - then we get a memory corruption as you can't clone into an existing stack.

In peano4::parallel::SpacetreeSet::streamDataFromSplittingTreesToNewTrees() we might copy data multiple times if we immediately erase it after the clone. Therefore, I check per call (the function is called twice) whether the target buffer is empty. If so, I copy over. In any case, teh source buffer is deleted if it is not empty - even though I have not cloned it in the second step. This is kind of a hack, but no better one comes to my mind. The whole discussion is not relevant for inter-rank communication as we know that the buffer won't be deleted before the data has not been sent out - which is only once for the whole cycle.

Definition at line 31 of file SpacetreeSet.cpph.

References assertion4, assertionMsg, peano4::grid::TraversalObserver::ForkDomain, peano4::parallel::Node::getGridDataExchangeMetaInformation(), peano4::parallel::Node::getInstance(), tarch::mpi::Rank::getInstance(), peano4::grid::PeanoCurve::getOutputStackNumber(), peano4::parallel::Node::getOutputStackNumberForVerticalDataExchange(), peano4::parallel::Node::getRank(), tarch::mpi::IntegerMessage::getValue(), logDebug, logTraceInWith2Arguments, logTraceOutWith2Arguments, tarch::mpi::IntegerMessage::receiveAndPollDanglingMessages(), tarch::mpi::IntegerMessage::send(), and peano4::parallel::Node::VerticalData.

Referenced by streamDataFromSplittingTreesToNewTrees().

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

◆ streamLocalVertexInformationToMasterThroughVerticalStacks()

void peano4::parallel::SpacetreeSet::streamLocalVertexInformationToMasterThroughVerticalStacks ( int spacetreeId,
int parentId,
const std::set< int > & joiningIds )
private

Whenever we join two partitions, we have to stream data from the worker to the master.

In principle, I could omit this, as I realise a `‘only degenerated trees may join’' policy. However, it can happen that a tree joins while other trees split or have split or join as well. While we run through the joining phase, these other ranks have sent their updated info to the worker that is about to join. The master that will hold the data in the future is not aware (yet) of any topology changes. Therefore, it is important that the worker still merges all incoming information into its local tree and then forwards it (streams it) to its master. The master in turn has to traverse later (in a secondary tree traversal) and take this updated topological information into account. This is a stream operation. Therefore, we not only have to exchange stacks, we also have to revert them to transform the stack into a stream.

All of this painful stuff is done for the vertex data only. For the user data, we can rely on our traditional vertical data exchange mechanisms.

See also
peano4::stacks::STDVectorStack::revert()

Definition at line 307 of file SpacetreeSet.cpp.

References logTraceInWith2Arguments, and logTraceOut.

Referenced by exchangeVerticalDataBetweenTrees().

Here is the caller graph for this function:

◆ toString()

std::string peano4::parallel::SpacetreeSet::toString ( SpacetreeSetState state)
staticprivate

Definition at line 78 of file SpacetreeSet.cpp.

References state.

◆ traverse()

void peano4::parallel::SpacetreeSet::traverse ( peano4::grid::TraversalObserver & observer)

Invoke traverse on all spacetrees in parallel.

Sequence

It is important that I don't answer to spacetree request messages while I am running through the spacetree set. Some of these request messages add further elements to the set. However, the set should remain invariant while I run through it. So I introduced the _state. See also _unansweredMessages.

So when I'm done with the local traversal, I have to ensure that all other sets have got their tree modifications through. That is: If another rank wants to insert a tree, that has to happen in the right traversal. As the other rank will wait for an acknowledgement of the addition, there is no risk that this rank has already proceeded wrongly into the next grid sweep. However, the target rank has to answer the request in the right one and may not proceed to early.

So I introduce a barrier. The barrier has to do two things: On the one hand, it has to receive dangling messages. On the other hand, it should answer messages that it has not answered before. In principle, this is indirectly done through receiveDanglingMessages(). However, I played around with running the dangling thing if and only if iprobe tells me that there are new messages. So to be on the safe side, I rather invoke the answer routines manually here.

There are two options where to place the barrier: We could add it to the end of traverse() or right after we've received the startup message. There are two different kinds of messages: messages that can be answered straightaway (give me a new rank) or others which can be answered only in-between iterations. If we add a barrier right at the begin of a traversal, then we are fine, as the typical split (asking for further ranks) arises in-between traversals.

Definition at line 508 of file SpacetreeSet.cpp.

References _spacetrees, _state, answerQuestions(), assertionMsg, tarch::mpi::Rank::barrier(), cleanUpTrees(), peano4::parallel::Node::continueToRun(), createNewTrees(), deleteClonedObservers(), peano4::grid::EmptyRun, exchangeHorizontalDataBetweenTrees(), exchangeVerticalDataBetweenTrees(), tarch::timing::Watch::getCPUTime(), peano4::parallel::Node::getInstance(), tarch::logging::Statistics::getInstance(), tarch::mpi::Rank::getInstance(), tarch::services::ServiceRepository::getInstance(), peano4::grid::Joined, peano4::grid::Joining, peano4::grid::JoinTriggered, tarch::logging::Statistics::log(), logDebug, logTraceIn, logTraceInWith1Argument, logTraceOut, peano4::grid::NewFromSplit, peano4::grid::NewRoot, tarch::services::ServiceRepository::receiveDanglingMessages(), peano4::grid::Running, tarch::multicore::spawnAndWait(), tarch::timing::Watch::stop(), streamDataFromSplittingTreesToNewTrees(), TraverseTreesAndExchangeData, and Waiting.

Referenced by runParallel(), runParallel(), and step().

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

Friends And Related Symbol Documentation

◆ peano4::grid::Spacetree

friend class peano4::grid::Spacetree
friend

Definition at line 43 of file SpacetreeSet.h.

Field Documentation

◆ _answerMessageTag

int peano4::parallel::SpacetreeSet::_answerMessageTag
private

Never use this tag directly.

It is the first tag of a series fo answer tags. To find the right one for a particular application context, use getAnswerTag().

Definition at line 323 of file SpacetreeSet.h.

◆ _clonedObserver

std::map< int, peano4::grid::TraversalObserver* > peano4::parallel::SpacetreeSet::_clonedObserver
private

I create/clone one observer per local tree.

This is an on-the-fly process. At the end of the set traversal, we delete all of clones. Originally, I did this delete right after the creation and the subsequent traversal. However, we need the observer clone once more for the data exchange. To avoid reclones, I store all clones in this map and then delete them en bloc.

See also
deleteClonedObservers

Definition at line 347 of file SpacetreeSet.h.

Referenced by createObserverCloneIfRequired(), deleteAllStacks(), deleteClonedObservers(), exchangeHorizontalDataBetweenTrees(), exchangeVerticalDataBetweenTrees(), and streamDataFromSplittingTreesToNewTrees().

◆ _log

tarch::logging::Log peano4::parallel::SpacetreeSet::_log
staticprivate

Logging device.

Definition at line 295 of file SpacetreeSet.h.

◆ _requestMessageTag

int peano4::parallel::SpacetreeSet::_requestMessageTag
private

I use this tag to identify messages send from one tree to another rank.

All answers go through an answer tag. To identify the right one, please use getAnswerTag(). The tag should be const, but I set it in init() and therefore I had to remove the const - even though its logically not possible to change it.

Definition at line 316 of file SpacetreeSet.h.

Referenced by cleanUpTrees(), and split().

◆ _semaphore

tarch::multicore::BooleanSemaphore peano4::parallel::SpacetreeSet::_semaphore
staticprivate

Semaphore to protect container holding all the local trees.

Definition at line 300 of file SpacetreeSet.h.

Referenced by createObserverCloneIfRequired().

◆ _singleton

peano4::parallel::SpacetreeSet peano4::parallel::SpacetreeSet::_singleton
staticprivate

Definition at line 45 of file SpacetreeSet.h.

◆ _spacetrees

◆ _state

SpacetreeSetState peano4::parallel::SpacetreeSet::_state
private

The state identifies what the set is doing right now.

The flag is for example used by receiveDanglingMessages() as we may not create new trees or change tree states while we are running through them or realise their data exchange.

Definition at line 335 of file SpacetreeSet.h.

Referenced by traverse().

◆ _unansweredMessages

std::vector<peano4::parallel::TreeManagementMessage> peano4::parallel::SpacetreeSet::_unansweredMessages
private

Definition at line 47 of file SpacetreeSet.h.


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