Peano 4
No Matches
toolbox::loadbalancing::strategies::SplitOversizedTree Class Reference

Find trees that are bigger than largest tree size and split them. More...

#include <SplitOversizedTree.h>

Inheritance diagram for toolbox::loadbalancing::strategies::SplitOversizedTree:
Collaboration diagram for toolbox::loadbalancing::strategies::SplitOversizedTree:

Public Member Functions

 SplitOversizedTree (Configuration *configuration=new DefaultConfiguration(), CostMetrics *costMetrics=new toolbox::loadbalancing::metrics::CellCount())
 Set up recursive subdivision.
virtual ~SplitOversizedTree ()
virtual void finishStep () override
 Triggers actual load balancing data exchange, triggers rebalancing, and dumps statistics.
virtual std::string toString () const override
 I need the stats here mainly for debugging purposes.
- Public Member Functions inherited from toolbox::loadbalancing::AbstractLoadBalancing
 AbstractLoadBalancing (Configuration *configuration, CostMetrics *costMetrics)
virtual ~AbstractLoadBalancing ()
virtual void enable (bool)
 Switch on/off.
virtual bool hasSplitRecently () const
bool isEnabled (bool globally) const
 Clarifies whether load balancing is, in principle, enabled.
virtual int getGlobalNumberOfTrees () const
 Delegate to stats.
virtual bool hasStagnated () const
 A load balancing can either be stagnating or be switched off for this predicate to hold.
virtual void finishSimulation ()
void setConfigurationAndMetricsNullWithoutDelete ()
 This is only used when you concatenate balancing rules and you want to disable any deletion.

Private Member Functions

bool doesLocalTreeViolateThreshold () const
 Is the balancing on the rank ok.
double getTargetTreeCost () const
void triggerSplit (int sourceTree, int targetRank, int numberOfSplits)
 Wrapper around the spacetree set which also updates the blacklist.
void updateState ()
void updateLoadBalancing ()
 Core actions where we take the action and translate it into action - what a pun.
int computeNumberOfSplits (int sourceTree) const

Private Attributes

int _roundRobinToken
 If it equals the rank, then we are allowed to do something.

Static Private Attributes

static tarch::logging::Log _log

Additional Inherited Members

- Static Public Attributes inherited from toolbox::loadbalancing::AbstractLoadBalancing
static constexpr int NoHeaviestTreeAvailable = -1
 Is used by tree identification and either indicates that there are no trees at all or means that the heaviest tree is on the blacklist.
- Protected Member Functions inherited from toolbox::loadbalancing::AbstractLoadBalancing
bool fitsIntoMemory (State state) const
 Ensure enough memory is left-over.
bool isInterRankBalancingBad () const
 Is the balancing between the ranks ok.
bool isIntraRankBalancingBad () const
 Is the balancing on the rank ok.
bool areRanksUnemployed () const
double getWeightOfHeaviestLocalSpacetree () const
int getIdOfHeaviestLocalSpacetree () const
 Determines the maximum spacetree size a tree should have in the optimal case.
int getIdOfHeaviestLocalSpacetree (double tolerance) const
 Similar to getIdOfHeaviestLocalSpacetree() but you might get one of the trees back that is close to the heaviest one up to tolerance.
- Protected Attributes inherited from toolbox::loadbalancing::AbstractLoadBalancing
Blacklist _blacklist
Statistics _statistics
State _state
 Ensure that you invoke.
- Static Protected Attributes inherited from toolbox::loadbalancing::AbstractLoadBalancing
static tarch::logging::Log _log

Detailed Description

Find trees that are bigger than largest tree size and split them.

This routine works if and only if you prescribe a maximum tree size. If you do not specify a maximum tree size, it takes the optimal subtree size per core as guideline. Whenever a tree is bigger than this threshold, it forks off a new tree. However, the forked off tree is at most as big as the threshold, as we don't want to create recursive splitting patterns. See RecursiveBipartition if you are interested in the latter.

This strategy is often used "late" throughout the grid construction. We can phrase it the other way round: As it is an incremental strategy, we have to assume that even a dynamically constructed grid is well ahead of this balancing. So we split aggressively, top-down here. Consult a discussion of splitting variants and constraints in peano4::grid::Spacetree::isCellTopDownSplitCandidate() and peano4::grid::Spacetree::isCellBottomUpSplitCandidate(), peano4::grid::Spacetree::splitOrJoinCell() and the general domain decomposition overview.

While forking off trees once they exceed a certain threshold is not as elegant as iterative, recursive splits, this strategy avoids very deep tree topologies. These become an issue in line with some domain split-up constraints, as the logical tree topology's depth obviously is constraint by the depth of the global spacetree. That is, this load balancing scheme is advantageous if recursive splitting fails.

I recommend to use this strategy if the following things hold:

  1. Another strategy has already spread out over all ranks, so all ranks are busy with at least one tree. In this case, we use this strategy as a post-balancing step within a cascade of decompositions.
  2. We have a good grasp of the load distribution at the time when this load balancing step kicks in already.

The second item implies that I've seen this strategy struggle for strongly adaptive, fine meshes and meshes with a very inhomogeneous load pattern.

Definition at line 65 of file SplitOversizedTree.h.

Constructor & Destructor Documentation

◆ SplitOversizedTree()

toolbox::loadbalancing::strategies::SplitOversizedTree::SplitOversizedTree ( Configuration * configuration = new DefaultConfiguration(),
CostMetrics * costMetrics = new toolbox::loadbalancing::metrics::CellCount() )

Set up recursive subdivision.

The ownership of the pointer goes over to the recursive subdivision instance, i.e. you don't have to delete the passed object.

Definition at line 17 of file SplitOversizedTree.cpp.

References toolbox::loadbalancing::AbstractLoadBalancing::_state, toolbox::loadbalancing::AbstractLoadBalancing::_statistics, assertion, toolbox::loadbalancing::InterRankDistribution, and toolbox::loadbalancing::Statistics::notifyOfStateChange().

Here is the call graph for this function:

◆ ~SplitOversizedTree()

toolbox::loadbalancing::strategies::SplitOversizedTree::~SplitOversizedTree ( )

Definition at line 29 of file SplitOversizedTree.cpp.

Member Function Documentation

◆ computeNumberOfSplits()

int toolbox::loadbalancing::strategies::SplitOversizedTree::computeNumberOfSplits ( int sourceTree) const

◆ doesLocalTreeViolateThreshold()

bool toolbox::loadbalancing::strategies::SplitOversizedTree::doesLocalTreeViolateThreshold ( ) const

Is the balancing on the rank ok.

Definition at line 71 of file SplitOversizedTree.cpp.

References peano4::parallel::SpacetreeSet::getInstance(), and peano4::parallel::SpacetreeSet::getLocalSpacetrees().

Here is the call graph for this function:

◆ finishStep()

void toolbox::loadbalancing::strategies::SplitOversizedTree::finishStep ( )

Triggers actual load balancing data exchange, triggers rebalancing, and dumps statistics.

Spread equally

This step is usually called early throughout the grid construction. At this point, we want to bring in ranks as soon as possible. However, it is very unlikely that the grid at that point will allow us to balance properly. We will likely have something like 27 cells for 8 ranks. With integer arithmetics, we would now get 3 cells per rank with the remainder of cells remaining on rank 0. This is not a big issue for small meshes, but for large meshes even a tiny overloading of rank 0 can result in an out-of-memory situation. I therefore have this module increment within the for loop such that module imbalances are at least spread out.

Implements toolbox::loadbalancing::AbstractLoadBalancing.

Definition at line 169 of file SplitOversizedTree.cpp.

References toolbox::loadbalancing::dumpStatistics().

Here is the call graph for this function:

◆ getTargetTreeCost()

double toolbox::loadbalancing::strategies::SplitOversizedTree::getTargetTreeCost ( ) const

◆ toString()

std::string toolbox::loadbalancing::strategies::SplitOversizedTree::toString ( ) const

I need the stats here mainly for debugging purposes.

The load balancing alread dumps information per time step. This routine however is more elaborate/detailed and not used by default.

Reimplemented from toolbox::loadbalancing::AbstractLoadBalancing.

Definition at line 32 of file SplitOversizedTree.cpp.

References peano4::parallel::SpacetreeSet::getInstance(), peano4::parallel::SpacetreeSet::getLocalSpacetrees(), toolbox::loadbalancing::getWeightOfHeaviestLocalSpacetree(), and toString().

Here is the call graph for this function:

◆ triggerSplit()

void toolbox::loadbalancing::strategies::SplitOversizedTree::triggerSplit ( int sourceTree,
int targetRank,
int numberOfSplits )

Wrapper around the spacetree set which also updates the blacklist.


I originally wanted to add an assertion


which is correct for the very first split. However, if a tree splits multiple times, then the first split will set this counter to something greater to 0 and therefore the assertion will fail for the next split. So I removed this statement.

Definition at line 206 of file SplitOversizedTree.cpp.

References peano4::SplitInstruction::AggressiveTopDown, peano4::parallel::SpacetreeSet::getInstance(), logInfo, and peano4::parallel::SpacetreeSet::split().

Here is the call graph for this function:

◆ updateLoadBalancing()

void toolbox::loadbalancing::strategies::SplitOversizedTree::updateLoadBalancing ( )

◆ updateState()

void toolbox::loadbalancing::strategies::SplitOversizedTree::updateState ( )

Init has-spread-over-all-ranks flag

By the time we construct the load balancing, we often haven't initialised the MPI environment properly yet. At least, I don't want to rely on this. Therefore, I set _hasSpreadOutOverAllRanks to false by default, and then make updateGlobalView() set it to true for the non-0 rank. The 0-rank case is covered anyway.

Round-robin balancing

I test my load balancing typically first with a rather regular grid. What happens here is that the grid is decomposed and one or two ranks are slightly `‘too light’'. All the others identify a rank to which they could outsource cells and then all outsource to the same ranks at the same time. To avoid this, I introduce a round-robin token such that only one rank at a time does balance in-between ranks (the other types of lb are not affected). This way, it cannot happen that a high number of ranks all outsource cells to the same ''victim'' in one rush.


Weird things can happen with our greedy approach: We might have three heavy trees on our rank which all cover regions that cannot be forked further (as they have already children or cover boundaries or some AMR regions). In this case, it might happen that we rotate through: We ask tree 1 to split, then tree 2, then 3. Once the split of 3 has finished (unsuccessfully), 1 has already left the blacklist. We end up with a cycle.

Therefore, we increase the time how long a tree stays on the blacklist everytime the maximum tree weight has not changed. This way, we avoid the rotations.

If everybody is on the blacklist, then we have obviously tried to split every tree and it did not really work, so we would like to split further, but we have run into a stagnation.

Definition at line 50 of file SplitOversizedTree.cpp.

References tarch::mpi::Rank::getInstance(), tarch::mpi::Rank::getNumberOfRanks(), toolbox::loadbalancing::InterRankBalancing, toolbox::loadbalancing::InterRankDistribution, toolbox::loadbalancing::IntraRankBalancing, logDebug, toolbox::loadbalancing::SwitchedOff, toString(), and toolbox::loadbalancing::WaitForRoundRobinToken.

Here is the call graph for this function:

Field Documentation

◆ _log

tarch::logging::Log toolbox::loadbalancing::strategies::SplitOversizedTree::_log

Definition at line 102 of file SplitOversizedTree.h.

◆ _roundRobinToken

int toolbox::loadbalancing::strategies::SplitOversizedTree::_roundRobinToken

If it equals the rank, then we are allowed to do something.

See also

Definition at line 109 of file SplitOversizedTree.h.

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