Peano 4
Loading...
Searching...
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)
 Constructor.
 
virtual ~AbstractLoadBalancing ()
 Destructor.
 
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
 
Configuration_configuration
 
CostMetrics_costMetrics
 
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 ( )
virtual

Definition at line 29 of file RecursiveBipartition.cpp.

Member Function Documentation

◆ finishStep()

void toolbox::loadbalancing::strategies::RecursiveBipartition::finishStep ( )
overridevirtual

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
overridevirtual

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 )
private

Wrapper around the spacetree set which also updates the blacklist.

Rationale

I originally wanted to add an assertion

  assertionEquals(_stepsToWaitForNextLoadBalancingDecision,0);

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 ( )
private

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 ( )
private

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.

Stagnation

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
staticprivate

Definition at line 86 of file RecursiveBipartition.h.

◆ _roundRobinToken

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

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

See also
updateState()

Definition at line 93 of file RecursiveBipartition.h.


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