Peano 4
Loading...
Searching...
No Matches
SplitOversizedTree.cpp
Go to the documentation of this file.
2
3#include "tarch/Assertions.h"
4#include "tarch/tarch.h"
10
11
13 "toolbox::loadbalancing::strategies::SplitOversizedTree"
14);
15
16
18 Configuration* configuration, CostMetrics* costMetrics
19):
20 AbstractLoadBalancing(configuration, costMetrics),
21 _roundRobinToken(0) {
22 assertion(configuration != nullptr);
23 assertion(costMetrics != nullptr);
26}
27
28
30
31
33 std::ostringstream msg;
34
35 msg
36 << "(type=split-oversized-tree"
37 << ",state=" << ::toString(_state) << ",statistics=" << _statistics.toString() << ",cost-metrics="
38 << _costMetrics->toString() << ",round-robin-token=" << _roundRobinToken << ",blacklist=" << _blacklist.toString()
39 << ",heaviest-local-tree=" << getIdOfHeaviestLocalSpacetree() << " (analysed)"
40 << ",heaviest-local-weight=" << getWeightOfHeaviestLocalSpacetree() << " (analysed)"
42 << ",is-inter-rank-balancing-bad=" << isInterRankBalancingBad()
43 << ",is-intra-rank-balancing-bad=" << isIntraRankBalancingBad() << ",target-tree-cost=" << getTargetTreeCost()
44 << ",min-tree-size=" << _configuration->getMinTreeSize(_state) << ")";
45
46 return msg.str();
47}
48
49
51 if (_state == State::SwitchedOff) {
52 logDebug("updateState()", "don't update as we have switched off");
53 } else if (areRanksUnemployed()) {
55 logDebug("updateState()", "switch to state " << ::toString(_state));
56 } else if (isInterRankBalancingBad() and _roundRobinToken == tarch::mpi::Rank::getInstance().getRank() and doesLocalTreeViolateThreshold()) {
58 logDebug("updateState()", "switch to state " << ::toString(_state));
59 } else if (isIntraRankBalancingBad() and doesLocalTreeViolateThreshold()) {
61 logDebug("updateState()", "switch to state " << ::toString(_state));
62 } else {
64
65 _roundRobinToken++;
66 _roundRobinToken = _roundRobinToken % tarch::mpi::Rank::getInstance().getNumberOfRanks();
67 }
68}
69
70
72 if (not _statistics.hasConsistentViewOfWorld()) { //
73 return false;
74 } else if (peano4::parallel::SpacetreeSet::getInstance().getLocalSpacetrees().size() == 0) {
75 return false;
76 } else if (peano4::parallel::SpacetreeSet::getInstance().getLocalSpacetrees().size() == 1) {
77 return true;
78 }
79 else if ( static_cast<int>(peano4::parallel::SpacetreeSet::getInstance().getLocalSpacetrees().size()) >= _configuration->getMaxLocalTreesPerRank(_state) ) {
80 return false;
81 } else {
82 bool result = false;
83
85 result |= _costMetrics->getCostOfLocalTree(p) > getTargetTreeCost();
86 }
87
88 return result;
89 }
90}
91
92
94#if PeanoDebug > 0
95 logInfo("updateLoadBalancing()", "load balancing's state=" << toString());
96#endif
97
98 switch (_state) {
100 int heaviestSpacetree = getIdOfHeaviestLocalSpacetree(_configuration->getWorstCaseBalancingRatio(_state));
101 double weightOfHeaviestSpacetree = getWeightOfHeaviestLocalSpacetree();
102 if (
103 fitsIntoMemory(_state)
104 and
105 heaviestSpacetree!=NoHeaviestTreeAvailable
106 and
107 not _blacklist.isBlacklisted(heaviestSpacetree)
108 and
109 weightOfHeaviestSpacetree > getTargetTreeCost()
110 and
111 _costMetrics->getLightestRank()!=tarch::mpi::Rank::getInstance().getRank()
112 and
113 computeNumberOfSplits(heaviestSpacetree)>0
114 ) {
115 logInfo(
116 "updateLoadBalancing()",
117 "Not all ranks are used. Split once and deploy to lightest global rank " << _costMetrics->getLightestRank()
118 );
119 triggerSplit(heaviestSpacetree, _costMetrics->getLightestRank(), 1);
120 } else if (heaviestSpacetree != NoHeaviestTreeAvailable) {
121 logInfo(
122 "updateLoadBalancing()",
123 "can't split heaviest tree " << heaviestSpacetree << " even though this tree is too heavy " << toString()
124 );
125 }
126 } break;
128 int heaviestSpacetree = getIdOfHeaviestLocalSpacetree();
129 int weightOfHeaviestSpacetree = getWeightOfHeaviestLocalSpacetree();
130 if (fitsIntoMemory(_state) and heaviestSpacetree != NoHeaviestTreeAvailable and not _blacklist.isBlacklisted(heaviestSpacetree) and weightOfHeaviestSpacetree > getTargetTreeCost() and computeNumberOfSplits(heaviestSpacetree) > 0) {
131 logInfo(
132 "updateLoadBalancing()",
133 "biggest local tree "
134 << heaviestSpacetree << " is too heavy as it hosts " << weightOfHeaviestSpacetree
135 << " cells. Try to split tree " << computeNumberOfSplits(heaviestSpacetree)
136 << " times and to offload subsection(s) of tree to " << _costMetrics->getLightestRank() << " " << toString()
137 );
138 triggerSplit(heaviestSpacetree, _costMetrics->getLightestRank(), computeNumberOfSplits(heaviestSpacetree));
139 } else if (heaviestSpacetree != NoHeaviestTreeAvailable) {
140 logInfo(
141 "updateLoadBalancing()",
142 "can't split heaviest tree "
143 << heaviestSpacetree << " and fork off to remote rank,as "
144 << "heaviest tree is on blacklist " << toString()
145 );
146 }
147 } break;
150 if (fitsIntoMemory(_state) and not _blacklist.isBlacklisted(p) and _costMetrics->getCostOfLocalTree(p) > getTargetTreeCost() and computeNumberOfSplits(p) > 0) {
151 logInfo(
152 "updateLoadBalancing()",
153 "local tree "
154 << p << " is too heavy as it has a weight of " << _costMetrics->getCostOfLocalTree(p)
155 << ". Try to split tree " << computeNumberOfSplits(p) << " times on local rank " << toString()
156 << " (max local trees=" << _configuration->getMaxLocalTreesPerRank(_state)
157 << ", min-tree-size=" << _configuration->getMinTreeSize(_state) << ")"
158 );
159 triggerSplit(p, tarch::mpi::Rank::getInstance().getRank(), computeNumberOfSplits(p));
160 }
161 }
162 } break;
163 default:
164 break;
165 }
166}
167
168
170 _statistics.updateGlobalView();
171 _costMetrics->updateGlobalView();
172 _blacklist.update();
173
174 updateLoadBalancing();
175 updateState();
176
177 _statistics.notifyOfStateChange(_state);
178
180}
181
182
184 int numberOfSplits = static_cast<int>(_costMetrics->getCostOfLocalTree(sourceTree) / getTargetTreeCost()) - 1;
185
186 numberOfSplits = std::max(1, numberOfSplits);
187 numberOfSplits = std::min(
188 numberOfSplits,
189 _configuration->getMaxLocalTreesPerRank(_state
191 );
192
193 int currentSourceTreeCells = peano4::parallel::SpacetreeSet::getInstance()
194 .getGridStatistics(sourceTree)
196
197 while (currentSourceTreeCells / (numberOfSplits + 1) < _configuration->getMinTreeSize(_state) and numberOfSplits > 0
198 ) {
199 numberOfSplits--;
200 }
201
202 return numberOfSplits;
203}
204
205
207 int sourceTree, int targetRank, int numberOfSplits
208) {
209 const int numberOfSplitCells = std::max(
210 1,
211 peano4::parallel::SpacetreeSet::getInstance().getGridStatistics(sourceTree).getNumberOfLocalUnrefinedCells()
212 / (1 + numberOfSplits)
213 );
214 for (int i = 0; i < numberOfSplits; i++) {
216 sourceTree,
218 targetRank
219 );
220 if (not success) {
221 logInfo("triggerSplit()", "wanted to split local rank " << sourceTree << " but failed");
222 }
223
224 _blacklist.triggeredSplit(sourceTree);
225 _statistics.incLocalNumberOfSplits();
226 }
227}
228
229
231 const int TargetNumberOfThreads = std::min(
233 _configuration->getMaxLocalTreesPerRank(_state),
235 );
236
237 return _costMetrics->getGlobalCost() / tarch::mpi::Rank::getInstance().getNumberOfRanks() / TargetNumberOfThreads;
238}
#define assertion(expr)
#define logDebug(methodName, logMacroMessageStream)
Definition Log.h:50
#define logInfo(methodName, logMacroMessageStream)
Wrapper macro around tarch::tarch::logging::Log to improve logging.
Definition Log.h:411
bool split(int treeId, const peano4::SplitInstruction &instruction, int targetRank)
Split a local tree.
peano4::grid::GridStatistics getGridStatistics() const
Return statistics object for primary spacetree.
static SpacetreeSet & getInstance()
std::set< int > getLocalSpacetrees() const
Log Device.
Definition Log.h:516
int getNumberOfRanks() const
Definition Rank.cpp:551
static Rank & getInstance()
This operation returns the singleton instance.
Definition Rank.cpp:538
int getRank() const
Return rank of this node.
Definition Rank.cpp:528
static Core & getInstance()
Definition Core.cpp:55
int getNumberOfThreads() const
Returns the number of threads that is used.
Definition Core.cpp:66
Abstract interface to tweak the behaviour of the recursive subdivision.
void notifyOfStateChange(State state)
virtual void finishStep() override
Triggers actual load balancing data exchange, triggers rebalancing, and dumps statistics.
void updateLoadBalancing()
Core actions where we take the action and translate it into action - what a pun.
SplitOversizedTree(Configuration *configuration=new DefaultConfiguration(), CostMetrics *costMetrics=new toolbox::loadbalancing::metrics::CellCount())
Set up recursive subdivision.
virtual std::string toString() const override
I need the stats here mainly for debugging purposes.
void triggerSplit(int sourceTree, int targetRank, int numberOfSplits)
Wrapper around the spacetree set which also updates the blacklist.
bool doesLocalTreeViolateThreshold() const
Is the balancing on the rank ok.
std::string toString(Filter filter)
Definition convert.cpp:170
int getWeightOfHeaviestLocalSpacetree()
This is a helper routine which is used by ExaHyPE's default main for for example.
void dumpStatistics()
Dump the stats of the lb to the terminal (info device).
@ InterRankBalancing
We have completed the first two phases and try to balance between the ranks now to meet the load bala...
@ WaitForRoundRobinToken
You usually don't get this state when we query the configuration, i.e.
@ SwitchedOff
You usually don't get this state when we query the configuration, i.e.
@ InterRankDistribution
Code has not yet spread out over all ranks but would like to do so now.
@ IntraRankBalancing
The code is satisfied with the load balancing quality between the ranks and now spawns more partition...
Instruction to split.
Definition grid.h:34