 |
Peano
|
|
Peano
|
Recursive load balancing micking the behaviour of the guided partitioning in OpenMP. More...
#include <RecursiveBipartition.h>
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 |
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.
| 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.
|
virtual |
Definition at line 29 of file RecursiveBipartition.cpp.
|
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 178 of file RecursiveBipartition.cpp.
References _state(), and toolbox::loadbalancing::dumpStatistics().
|
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 _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 192 of file RecursiveBipartition.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 70 of file RecursiveBipartition.cpp.
References _state(), tarch::mpi::Rank::getInstance(), 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 49 of file RecursiveBipartition.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 86 of file RecursiveBipartition.h.
|
private |
If it equals the rank, then we are allowed to do something.
Definition at line 93 of file RecursiveBipartition.h.
1.10.0