Peano 4
Loading...
Searching...
No Matches
RecursiveBipartition.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::RecursiveBipartition"
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=recursive-bipartition"
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() << ")";
44
45 return msg.str();
46}
47
48
50 if (_state == State::SwitchedOff) {
51 logDebug("updateState()", "don't update as we have switched off");
52 } else if (areRanksUnemployed()) {
54 logDebug("updateState()", "switch to state " << ::toString(_state));
55 } else if (isInterRankBalancingBad() and _roundRobinToken == tarch::mpi::Rank::getInstance().getRank()) {
57 logDebug("updateState()", "switch to state " << ::toString(_state));
58 } else if (isIntraRankBalancingBad()) {
60 logDebug("updateState()", "switch to state " << ::toString(_state));
61 } else {
63
64 _roundRobinToken++;
65 _roundRobinToken = _roundRobinToken % tarch::mpi::Rank::getInstance().getNumberOfRanks();
66 }
67}
68
69
71#if PeanoDebug > 0
72 logInfo("updateLoadBalancing()", "load balancing's state=" << toString());
73#endif
74
75 switch (_state) {
77 int heaviestSpacetree = getIdOfHeaviestLocalSpacetree(_configuration->getWorstCaseBalancingRatio(_state));
78 int numberOfLocalUnrefinedCellsOfHeaviestSpacetree = getWeightOfHeaviestLocalSpacetree();
79 if (
80 fitsIntoMemory(_state)
81 and
82 heaviestSpacetree!=NoHeaviestTreeAvailable
83 and
84 not _blacklist.isBlacklisted(heaviestSpacetree)
85 and
86 numberOfLocalUnrefinedCellsOfHeaviestSpacetree > _configuration->getMinTreeSize(_state)
87 and
88 _costMetrics->getLightestRank()!=tarch::mpi::Rank::getInstance().getRank()
89 ) {
90 int cellsPerCore = std::max(
91 {1, numberOfLocalUnrefinedCellsOfHeaviestSpacetree / 2, _configuration->getMinTreeSize(_state)}
92 );
93
94 logInfo(
95 "updateLoadBalancing()",
96 "Not all ranks are used. Lightest global rank is rank " << _costMetrics->getLightestRank(
97 ) << ", so assign this rank " << cellsPerCore << " cell(s)"
98 );
99 triggerSplit(heaviestSpacetree, cellsPerCore, _costMetrics->getLightestRank());
100 } else if (heaviestSpacetree != NoHeaviestTreeAvailable) {
101 logInfo(
102 "updateLoadBalancing()",
103 "can't split heaviest tree " << heaviestSpacetree << " even though this tree is too heavy"
104 );
105 }
106 } break;
108 int heaviestSpacetree = getIdOfHeaviestLocalSpacetree();
109 int numberOfLocalUnrefinedCellsOfHeaviestSpacetree = getWeightOfHeaviestLocalSpacetree();
110 if (
111 fitsIntoMemory(_state)
112 and
113 heaviestSpacetree!=NoHeaviestTreeAvailable
114 and
115 not _blacklist.isBlacklisted(heaviestSpacetree)
116 and
117 numberOfLocalUnrefinedCellsOfHeaviestSpacetree > _configuration->getMinTreeSize(_state)
118 ) {
119 logInfo(
120 "updateLoadBalancing()",
121 "biggest local tree "
122 << heaviestSpacetree << " is too heavy as it hosts " << numberOfLocalUnrefinedCellsOfHeaviestSpacetree
123 << " cells"
124 );
125 int cellsPerCore = std::max(
126 {1, numberOfLocalUnrefinedCellsOfHeaviestSpacetree / 2, _configuration->getMinTreeSize(_state)}
127 );
128
129 logInfo(
130 "updateLoadBalancing()",
131 "lightest global rank is rank "
132 << _costMetrics->getLightestRank() << ", so assign this rank " << cellsPerCore << " cell(s)"
133 );
134 triggerSplit(heaviestSpacetree, cellsPerCore, _costMetrics->getLightestRank());
135 } else if (heaviestSpacetree != NoHeaviestTreeAvailable) {
136 logInfo(
137 "updateLoadBalancing()",
138 "can't split heaviest tree "
139 << heaviestSpacetree
140 << " and fork off to remote rank as this tree is on the blacklist or split does not fit into local memory anymore"
141 );
142 }
143 } break;
145 int heaviestSpacetree = getIdOfHeaviestLocalSpacetree();
146 int numberOfLocalUnrefinedCellsOfHeaviestSpacetree = getWeightOfHeaviestLocalSpacetree();
147 if (
148 fitsIntoMemory(_state)
149 and
150 heaviestSpacetree!=NoHeaviestTreeAvailable
151 and
152 not _blacklist.isBlacklisted(heaviestSpacetree)
153 and
154 numberOfLocalUnrefinedCellsOfHeaviestSpacetree > _configuration->getMinTreeSize(_state)
155 ) {
156 int cellsPerCore = std::max(
157 {1, numberOfLocalUnrefinedCellsOfHeaviestSpacetree / 2, _configuration->getMinTreeSize(_state)}
158 );
159 logInfo(
160 "updateLoadBalancing()", "split tree on local rank and assign it " << cellsPerCore << " cell(s)" << toString()
161 );
162 triggerSplit(heaviestSpacetree, cellsPerCore, tarch::mpi::Rank::getInstance().getRank());
163 } else if (heaviestSpacetree != NoHeaviestTreeAvailable) {
164 logInfo(
165 "updateLoadBalancing()",
166 "can't split heaviest tree "
167 << heaviestSpacetree
168 << " on local rank as this tree is on the blacklist or split does not fit into local memory anymore"
169 );
170 }
171 } break;
172 default:
173 break;
174 }
175}
176
177
179 _statistics.updateGlobalView();
180 _costMetrics->updateGlobalView();
181 _blacklist.update();
182
183 updateLoadBalancing();
184 updateState();
185
186 _statistics.notifyOfStateChange(_state);
187
189}
190
191
193 int sourceTree, int numberOfCells, int targetRank
194) {
197 );
198 if (not success) {
199 logInfo("triggerSplit()", "wanted to split local rank " << sourceTree << " but failed");
200 }
201
202 _blacklist.triggeredSplit(sourceTree);
203 _statistics.incLocalNumberOfSplits();
204}
#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.
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
Abstract interface to tweak the behaviour of the recursive subdivision.
void notifyOfStateChange(State state)
RecursiveBipartition(Configuration *configuration=new DefaultConfiguration(), CostMetrics *costMetrics=new toolbox::loadbalancing::metrics::CellCount())
Set up recursive subdivision.
void triggerSplit(int sourceTree, int numberOfCells, int targetRank)
Wrapper around the spacetree set which also updates the blacklist.
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.
void updateLoadBalancing()
Core actions where we take the action and translate it into action - what a pun.
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