 |
Peano
|
|
Peano
|
Find trees that are bigger than largest tree size and split them. More...
#include <SplitOversizedTree.h>
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) | |
| 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 | |
| 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 |
| Configuration * | _configuration |
| CostMetrics * | _costMetrics |
| State | _state |
| Ensure that you invoke. | |
| Static Protected Attributes inherited from toolbox::loadbalancing::AbstractLoadBalancing | |
| static tarch::logging::Log | _log |
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:
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.
| 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().
|
virtual |
Definition at line 29 of file SplitOversizedTree.cpp.
|
private |
Definition at line 201 of file SplitOversizedTree.cpp.
References _state(), peano4::parallel::SpacetreeSet::getGridStatistics(), peano4::parallel::SpacetreeSet::getInstance(), peano4::parallel::SpacetreeSet::getLocalSpacetrees(), and peano4::grid::GridStatistics::getNumberOfLocalUnrefinedCells().
|
private |
Is the balancing on the rank ok.
Definition at line 71 of file SplitOversizedTree.cpp.
References _state(), peano4::parallel::SpacetreeSet::getInstance(), and peano4::parallel::SpacetreeSet::getLocalSpacetrees().
|
overridevirtual |
Triggers actual load balancing data exchange, triggers rebalancing, and dumps statistics.
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 187 of file SplitOversizedTree.cpp.
References _state(), and toolbox::loadbalancing::dumpStatistics().
|
private |
Definition at line 252 of file SplitOversizedTree.cpp.
References _state(), peano4::parallel::SpacetreeSet::getInstance(), tarch::mpi::Rank::getInstance(), tarch::multicore::Core::getInstance(), peano4::parallel::SpacetreeSet::getLocalSpacetrees(), tarch::mpi::Rank::getNumberOfRanks(), and tarch::multicore::Core::getNumberOfThreads().
|
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 SplitOversizedTree.cpp.
References _state(), peano4::parallel::SpacetreeSet::getInstance(), peano4::parallel::SpacetreeSet::getLocalSpacetrees(), toolbox::loadbalancing::getWeightOfHeaviestLocalSpacetree(), and toString().
|
private |
Wrapper around the spacetree set which also updates the blacklist.
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 228 of file SplitOversizedTree.cpp.
References _state(), peano4::parallel::SpacetreeSet::getInstance(), logInfo, and peano4::parallel::SpacetreeSet::split().
|
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 93 of file SplitOversizedTree.cpp.
References _state(), peano4::parallel::SpacetreeSet::getInstance(), tarch::mpi::Rank::getInstance(), peano4::parallel::SpacetreeSet::getLocalSpacetrees(), tarch::mpi::Rank::getRank(), toolbox::loadbalancing::getWeightOfHeaviestLocalSpacetree(), toolbox::loadbalancing::InterRankBalancing, toolbox::loadbalancing::InterRankDistribution, toolbox::loadbalancing::IntraRankBalancing, logInfo, and toString().
|
private |
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.
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 _state(), 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.
|
staticprivate |
Definition at line 102 of file SplitOversizedTree.h.
|
private |
If it equals the rank, then we are allowed to do something.
Definition at line 109 of file SplitOversizedTree.h.
1.10.0