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

Recursive load balancing micking the behaviour of the guided partitioning in OpenMP. More...

#include <RecursiveBipartition.h>

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

Public Member Functions

 RecursiveBipartition (Configuration *configuration=new DefaultConfiguration(), CostMetrics *costMetrics=new toolbox::loadbalancing::metrics::CellCount())
 Set up recursive subdivision.
virtual ~RecursiveBipartition ()
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

void triggerSplit (int sourceTree, int numberOfCells, int targetRank)
 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.

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

Recursive load balancing micking the behaviour of the guided partitioning in OpenMP.

This is one of the simplest load balancing strategies one can think about. We try to mimick the behaviour of OpenMP's guided scheduling: We determine the maximum number vs the minimum number of unrefined inner cells within a check set. If the ratio between the two is worse than the balancing threshold, we split the maximum tree into two parts.

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.

The splitting stops, once we have met the maximum number of trees on a node (or cannot split anymore).

Definition at line 48 of file RecursiveBipartition.h.

Constructor & Destructor Documentation

◆ RecursiveBipartition()

toolbox::loadbalancing::strategies::RecursiveBipartition::RecursiveBipartition ( 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 RecursiveBipartition.cpp.

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

Here is the call graph for this function:

◆ ~RecursiveBipartition()

toolbox::loadbalancing::strategies::RecursiveBipartition::~RecursiveBipartition ( )

Definition at line 29 of file RecursiveBipartition.cpp.

Member Function Documentation

◆ finishStep()

void toolbox::loadbalancing::strategies::RecursiveBipartition::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 178 of file RecursiveBipartition.cpp.

References toolbox::loadbalancing::dumpStatistics().

Here is the call graph for this function:

◆ toString()

std::string toolbox::loadbalancing::strategies::RecursiveBipartition::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 RecursiveBipartition.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::RecursiveBipartition::triggerSplit ( int sourceTree,
int numberOfCells,
int targetRank )

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 192 of file RecursiveBipartition.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::RecursiveBipartition::updateLoadBalancing ( )

Core actions where we take the action and translate it into action - what a pun.

Please call this routine before you invoke updateState().

Definition at line 70 of file RecursiveBipartition.cpp.

References tarch::mpi::Rank::getInstance(), tarch::mpi::Rank::getRank(), toolbox::loadbalancing::getWeightOfHeaviestLocalSpacetree(), toolbox::loadbalancing::InterRankBalancing, toolbox::loadbalancing::InterRankDistribution, toolbox::loadbalancing::IntraRankBalancing, logInfo, and toString().

Here is the call graph for this function:

◆ updateState()

void toolbox::loadbalancing::strategies::RecursiveBipartition::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 49 of file RecursiveBipartition.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::RecursiveBipartition::_log

Definition at line 86 of file RecursiveBipartition.h.

◆ _roundRobinToken

int toolbox::loadbalancing::strategies::RecursiveBipartition::_roundRobinToken

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

See also

Definition at line 93 of file RecursiveBipartition.h.

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