Peano
Loading...
Searching...
No Matches
Spacetree.cpp
Go to the documentation of this file.
1#include "Spacetree.h"
2
3#include "grid.h"
5#include "PeanoCurve.h"
6#include "TraversalObserver.h"
12#include "peano4/utils/Loop.h"
14#include "tarch/mpi/Rank.h"
16
17tarch::logging::Log peano4::grid::Spacetree::_log("peano4::grid::Spacetree");
18
20
24 const std::bitset<Dimensions>& periodicBC
25):
26 _id(0),
27 _spacetreeState(SpacetreeState::NewRoot),
28 _root(),
29 _masterId(-1),
30 _periodicBC(periodicBC),
31 _gridTraversalEventGenerator(0) {
32 _root.setLevel(0);
33 _root.setX(offset);
34 _root.setH(width);
35 _root.setInverted(false);
37
38 for (int i = 0; i < DimensionsTimesTwo; i++) {
40 }
41
43 clear(_statistics, _id == 0);
44
45 logDebug("Spacetree(...)", "create spacetree with " << offset << "x" << width << " and periodic BCs=" << _periodicBC);
46}
47
49 int newId,
50 int masterId,
53 bool traversalInverted
54):
55 _id(newId),
56 _spacetreeState(SpacetreeState::EmptyRun),
57 _root(),
58 _statistics(),
59 _masterId(masterId),
60 _periodicBC(0),
61 _splitTriggered(),
62 _splitting(),
63 _gridTraversalEventGenerator(newId) {
64 _root.setLevel(0);
65 _root.setX(offset);
66 _root.setH(width);
67 _root.setInverted(traversalInverted);
68 _root.setEvenFlags(std::bitset<Dimensions>(0));
69
70 for (int i = 0; i < DimensionsTimesTwo; i++) {
72 }
73
75 clear(_statistics, _id == 0);
76
77 logInfo("Spacetree(...)", "created spacetree " << _id << " with master tree " << masterId);
78}
79
81
83 GridVertex vertex, bool splittingIsConsideredLocal, bool joiningIsConsideredLocal
84) const {
86 and _gridTraversalEventGenerator.isVertexAdjacentToLocalSpacetree(
87 vertex,
88 _splitTriggered,
89 _splitting,
90 _joinTriggered,
91 _joining,
92 splittingIsConsideredLocal,
93 joiningIsConsideredLocal
94 );
95}
96
98 bool result = true;
99 dfor2(k) result &= (vertices[kScalar].getState() != GridVertex::State::HangingVertex);
100 enddforx return result;
101}
102
104 bool result = true;
105 dfor2(k) result &= (vertices[kScalar].getState() == GridVertex::State::Refined);
106 enddforx return result;
107}
108
110 bool result = true;
111 dfor2(k) result &= (vertices[kScalar].getState() == GridVertex::State::Unrefined);
112 enddforx return result;
113}
114
116 GridVertex vertices[TwoPowerD], bool splittingIsConsideredLocal, bool joiningIsConsideredLocal
117) const {
118 return _gridTraversalEventGenerator.isSpacetreeNodeLocal(
119 vertices, _splitTriggered, _splitting, _joinTriggered, _joining, splittingIsConsideredLocal, joiningIsConsideredLocal
120 );
121}
122
123void peano4::grid::Spacetree::traverse(TraversalObserver& observer, bool calledFromSpacetreeSet) {
124 logTraceIn("traverse(TraversalObserver)");
125
126 for (int d = 0; d < TwoTimesD; d++) {
127 assertion2(_root.getAccessNumber(d) > -2 * Dimensions, d, _root.toString());
128 assertion2(_root.getAccessNumber(d) < 2 * Dimensions, d, _root.toString());
129 }
130
131 if (calledFromSpacetreeSet) {
132 assertion(_joinTriggered.empty() or _splitTriggered.empty());
133 assertion(_joinTriggered.empty() or _splitting.empty());
134 assertion(_joining.empty() or _splitTriggered.empty());
135 assertion(_joining.empty() or _splitting.empty());
136 logDebug(
137 "traverse(TraversalObserver)",
138 _splitTriggered.size() << " tree split triggered and " << _splitting.size() << " splitting trees on tree " << _id
139 );
140 }
141
142 clear(_statistics, _id == 0);
143
144 if (_spacetreeState == SpacetreeState::EmptyRun or _spacetreeState == SpacetreeState::NewFromSplit or _spacetreeState == SpacetreeState::Joining) {
145 _gridControlEvents.clear();
146 } else {
147 _gridControlEvents = merge(observer.getGridControlEvents());
148
149 const int MagicUpperLimitToWhichIDumpEvents = 4;
150#if PeanoDebug > 0
151 if (_gridControlEvents.empty()) {
152 logInfo("traverse(...)", "got no grid refinement events");
153 } else
154#endif
155 if (not _gridControlEvents.empty() and _gridControlEvents.size() <= MagicUpperLimitToWhichIDumpEvents) {
156 std::ostringstream msg;
157 for (auto& p : _gridControlEvents)
158 msg << p.toString();
159 logInfo("traverse(...)", "got " << _gridControlEvents.size() << " grid control events: " << msg.str());
160 } else if (not _gridControlEvents.empty()) {
161 logInfo("traverse(...)", "got " << _gridControlEvents.size() << " grid control events");
162 }
163
164 if (not _gridControlEvents.empty()) {
166 "grid-control-events", ::peano4::grid::toString(_gridControlEvents)
167 );
168 }
169 }
170
171 _splittedCells.clear();
172
173 const bool isFirstTraversal = _spacetreeState == SpacetreeState::NewRoot;
174
175 GridVertex vertices[TwoPowerD];
177 adjacentRanks(TwoPowerD - 1 - kScalar) = 0;
178 vertices[kScalar] = createVertex(
180 _root.getX() + tarch::la::convertScalar<double>(k),
181 0,
182 adjacentRanks,
183 false
184 );
186 logDebug("traverse(TraversalObserver)", "create " << vertices[kScalar].toString() << " for tree " << _id);
188
189 for (int d = 0; d < Dimensions; d++) {
190 if (_periodicBC[d]) {
191 dfor2(vertex) dfor2(entries) tarch::la::Vector<Dimensions, int> entry = entries;
192 if (vertex(d) == 0) {
193 entry(d) = 0;
194 } else {
195 entry(d) = 1;
196 }
197 vertices[vertexScalar].setAdjacentRanks(peano4::utils::dLinearised(entry, 2), RankOfPeriodicBoundaryCondition);
199 "traverse(TraversalObserver)", "set periodic boundary conditions: " << vertices[vertexScalar].toString()
200 );
202 }
203 }
204
205 observer.beginTraversal(_root.getX(), _root.getH());
206
207 descend(_root, vertices, observer);
208
209 observer.endTraversal(_root.getX(), _root.getH());
210
211 _root.setInverted(not _root.getInverted());
212
213 if (calledFromSpacetreeSet) {
214 _hasSplit.clear();
215 for (auto& rank : _splitting) {
216 _childrenIds.insert(rank);
217 _hasSplit.insert(rank);
218 }
219 _splitting.clear();
220 for (auto& p : _splitTriggered) {
221 if (p.second.numberOfFineGridCells > 0) {
222 logInfo(
223 "traverse(TraversalObserver)",
224 "have not been able to assign enough cells from "
225 << _id << " to new tree " << p.first << " (should have deployed " << p.second << " more cells)"
226 );
227 }
228 _splitting.insert(p.first);
229 }
230 _splitTriggered.clear();
231
232 _joining.clear();
233 _joining.insert(_joinTriggered.begin(), _joinTriggered.end());
234 _joinTriggered.clear();
235
236 switch (_spacetreeState) {
238 _spacetreeState = SpacetreeState::NewFromSplit;
239 break;
242 _spacetreeState = SpacetreeState::Running;
243 break;
245 _spacetreeState = SpacetreeState::Joining;
246 break;
248 _spacetreeState = SpacetreeState::Joined;
249 break;
252 break;
253 }
254 logDebug(
255 "traverse(TraversalObserver)", "switched tree " << _id << " into " << peano4::grid::toString(_spacetreeState)
256 );
257 }
258
259 logTraceOut("traverse(TraversalObserver)");
260}
261
263 const AutomatonState& coarseGrid,
264 AutomatonState fineGridStates[ThreePowerD],
265 tarch::la::Vector<Dimensions, int> fineGridStatesPosition,
266 int axis
267) {
268 if (axis == -1) {
269 int arrayIndex = peano4::utils::dLinearised(fineGridStatesPosition, 3);
270 fineGridStates[arrayIndex] = coarseGrid;
271 fineGridStates[arrayIndex].setLevel(coarseGrid.getLevel() + 1);
272 } else {
273 assertion(axis >= 0);
274 assertion(axis < Dimensions);
275
276 AutomatonState firstCell = coarseGrid;
277 AutomatonState secondCell = coarseGrid;
278 AutomatonState thirdCell = coarseGrid;
279
280 if (PeanoCurve::isTraversePositiveAlongAxis(coarseGrid, axis)) {
281 PeanoCurve::setExitFace(firstCell, axis);
282 } else {
283 PeanoCurve::setEntryFace(firstCell, axis);
284 }
285 firstCell.setH(axis, coarseGrid.getH(axis) / 3.0);
286 fineGridStatesPosition(axis) = 0;
287 firstCell.setX(axis, coarseGrid.getX(axis));
288 refineState(firstCell, fineGridStates, fineGridStatesPosition, axis - 1);
289
290 PeanoCurve::invertEvenFlag(secondCell, axis);
291 PeanoCurve::setEntryFace(secondCell, axis);
292 PeanoCurve::setExitFace(secondCell, axis);
293 secondCell.setH(axis, coarseGrid.getH(axis) / 3.0);
294 fineGridStatesPosition(axis) = 1;
295 secondCell.setX(axis, coarseGrid.getX(axis) + coarseGrid.getH(axis) / 3.0);
296 refineState(secondCell, fineGridStates, fineGridStatesPosition, axis - 1);
297
298 if (PeanoCurve::isTraversePositiveAlongAxis(coarseGrid, axis)) {
299 PeanoCurve::setEntryFace(thirdCell, axis);
300 } else {
301 PeanoCurve::setExitFace(thirdCell, axis);
302 }
303 thirdCell.setH(axis, coarseGrid.getH(axis) / 3.0);
304 fineGridStatesPosition(axis) = 2;
305 thirdCell.setX(axis, coarseGrid.getX(axis) + 2.0 * coarseGrid.getH(axis) / 3.0);
306 refineState(thirdCell, fineGridStates, fineGridStatesPosition, axis - 1);
307 }
308
309 if (axis == Dimensions - 1) {
310 for (int i = 0; i < ThreePowerD; i++) {
311 for (int d = 0; d < TwoTimesD; d++) {
313 fineGridStates[i].getAccessNumber(d) > -2 * Dimensions,
314 i,
315 d,
316 fineGridStates[i].toString(),
317 coarseGrid.toString(),
320 );
322 fineGridStates[i].getAccessNumber(d) < 2 * Dimensions,
323 i,
324 d,
325 fineGridStates[i].toString(),
326 coarseGrid.toString(),
329 );
330 }
331 }
332 }
333}
334
337 for (int d = 0; d < Dimensions; d++) {
338 result[d] = in[d] ? 1 : 0;
339 }
340 return result;
341}
342
344 logTraceInWith2Arguments("receiveAndMergeGridVertexAtVerticalBoundary(GridVertex)", vertex.toString(), _id);
345
346 for (auto p : _joining) {
347 if (tarch::la::contains(vertex.getAdjacentRanks(), p)) {
349 logDebug(
350 "receiveAndMergeGridVertexAtVerticalBoundary(GridVertex)",
351 "merge "
352 << vertex.toString() << " with its replica from worker as worker is joining. Incoming stack no=" << stackNo
353 );
354
355 assertion3(not _vertexStack.getForPop(_id, stackNo)->empty(), _id, stackNo, vertex.toString());
356 GridVertex copyFromFormerWorker = _vertexStack.getForPop(_id, stackNo)->pop();
357
359 vertex.getX(), copyFromFormerWorker.getX(), vertex.toString(), copyFromFormerWorker.toString(), _id
360 );
361
362 vertex.setAdjacentRanks(copyFromFormerWorker.getAdjacentRanks());
363 logDebug(
364 "receiveAndMergeGridVertexAtVerticalBoundary(GridVertex)", "updated adjacency lists: " << vertex.toString()
365 );
366 }
367 }
368
369 logTraceOut("receiveAndMergeGridVertexAtVerticalBoundary(GridVertex)");
370}
371
373 [[maybe_unused]] GridVertex& vertex,
374 [[maybe_unused]] GridVertex fineGridVertices[TwoPowerD],
375 [[maybe_unused]] const tarch::la::Vector<Dimensions, int>& position,
376 [[maybe_unused]] TraversalObserver& observer
377) {
378 logTraceInWith2Arguments("updateVertexAfterLoad(GridVertex&)", vertex.toString(), _id);
379
380 if (_spacetreeState != SpacetreeState::NewFromSplit and _spacetreeState != SpacetreeState::EmptyRun) {
381 receiveAndMergeGridVertexAtHorizontalBoundary(vertex);
382 receiveAndMergeGridVertexAtVerticalBoundary(vertex);
383
384 vertex.setHasBeenAntecessorOfRefinedVertexInPreviousTreeSweep(
385 vertex.getIsAntecessorOfRefinedVertexInCurrentTreeSweep()
386 );
387 vertex.setHasBeenParentOfSubtreeVertexInPreviousTreeSweep(vertex.getIsParentOfSubtreeVertexInCurrentTreeSweep());
388
389 vertex.setIsAntecessorOfRefinedVertexInCurrentTreeSweep(false);
390 vertex.setIsParentOfSubtreeVertexInCurrentTreeSweep(false);
391 vertex.setNumberOfAdjacentRefinedLocalCells(0);
392
393 if (vertex.getState() == GridVertex::State::RefinementTriggered) {
394 if (isVertexAdjacentToLocalSpacetree(vertex, true, true)) {
395 logDebug("updateVertexAfterLoad()", "switch vertex to refining on tree " << _id << ": " << vertex.toString());
396 vertex.setState(GridVertex::State::Refining);
397 _statistics.setStationarySweeps(0);
398 } else {
399 vertex.setState(GridVertex::State::Unrefined);
400 // Could be set by number of adjacent cells, e.g.
401 // Anyway, don't reset stationary counter as this might
402 // stop the tree from merging into its father
403 //_statistics.setStationarySweeps( 0 );
404 }
405 } else if (vertex.getState() == GridVertex::State::EraseTriggered) {
406 if (vertex.getHasBeenAntecessorOfRefinedVertexInPreviousTreeSweep()) {
407 logDebug(
408 "updateVertexAfterLoad(...)",
409 "vertex "
410 << vertex.toString() << " may not be erased on tree " << _id
411 << " as it is father of further refined vertices. Unroll flag"
412 );
413 vertex.setState(GridVertex::State::Refined);
414 _statistics.setCoarseningHasBeenVetoed(true);
415 _statistics.setStationarySweeps(0);
416 } else {
417 logDebug(
418 "updateVertexAfterLoad(...)", "erase vertex " << vertex.toString() << " outside of domain on tree " << _id
419 );
420 vertex.setState(GridVertex::State::Erasing);
421 _statistics.setStationarySweeps(0);
422 }
423 }
424
425 // has to be here. Don't want to interfere with state splitting
426 if (
427 not isVertexAdjacentToLocalSpacetree(vertex,true,true)
428 and
429 not vertex.getHasBeenAntecessorOfRefinedVertexInPreviousTreeSweep()
430 and
431 vertex.getState()==GridVertex::State::Refined
432 ) {
433 logDebug(
434 "updateVertexAfterLoad(GridVertex&)", "would like to erase " << vertex.toString() << " in spacetree " << _id
435 );
436 vertex.setState(GridVertex::State::EraseTriggered);
437 }
438 }
439
440 if (_spacetreeState == SpacetreeState::Joining and isVertexAdjacentToLocalSpacetree(vertex, true, true)) {
442 logDebug(
443 "updateVertexAfterLoad(GridVertex&)",
444 "stream vertex "
445 << vertex.toString() << " from tree " << _id << " to master " << _masterId << " through stack " << stackNo
446 );
447 _vertexStack.getForPush(_id, stackNo)->push(vertex);
448 }
449
450 logTraceOutWith1Argument("updateVertexAfterLoad(GridVertex&)", vertex.toString());
451}
452
454 const tarch::la::Vector<Dimensions, int>& coarseVertexPosition,
455 const tarch::la::Vector<Dimensions, int>& fineVertexPosition
456) {
457 bool result = true;
458 for (int d = 0; d < Dimensions; d++) {
459 assertion2(coarseVertexPosition(d) >= 0, coarseVertexPosition, fineVertexPosition);
460 assertion2(coarseVertexPosition(d) <= 1, coarseVertexPosition, fineVertexPosition);
461
462 assertion2(fineVertexPosition(d) >= 0, coarseVertexPosition, fineVertexPosition);
463 assertion2(fineVertexPosition(d) <= 3, coarseVertexPosition, fineVertexPosition);
464
465 result
466 &= ((coarseVertexPosition(d) == 1 and fineVertexPosition(d) > 0) or (coarseVertexPosition(d) == 0 and fineVertexPosition(d) < 3));
467 }
468
469 return result;
470}
471
473 GridVertex& vertex,
474 GridVertex coarseGridVertices[TwoPowerD],
475 const tarch::la::Vector<Dimensions, int>& fineVertexPositionWithinPatch
476) {
477 logTraceInWith2Arguments("updateVertexBeforeStore()", vertex.toString(), _id);
478
479 if (_spacetreeState != SpacetreeState::EmptyRun) {
480 if (vertex.getState() == GridVertex::State::New) {
482 }
483
484 if (
485 _spacetreeState==SpacetreeState::Running
486 and
488 and
490 ) {
492 logDebug(
493 "updateVertexBeforeStore(...)",
494 "have to post-refine vertex "
495 << vertex.toString() << " as it surrounded by 2^d refined cells on tree " << _id << " x "
496 << peano4::grid::toString(_spacetreeState)
497 );
498 }
499
500 /*
501 @todo Do we want to avoid hanging vertices along boundary? I think this would make sense
502
503 if (
504 vertex.getState()==GridVertex::State::Unrefined
505 and
506 vertex.
507 ) {
508 vertex.setState( GridVertex::State::RefinementTriggered );
509 logDebug( "updateVertexBeforeStore(...)", "have to post-refine vertex " << vertex.toString() );
510 }
511 */
512
513 bool restrictIsAntecessorOfRefinedVertex = vertex.getIsAntecessorOfRefinedVertexInCurrentTreeSweep();
514
516 restrictIsAntecessorOfRefinedVertex = true;
517 } else if (vertex.getState() == GridVertex::State::Refining) {
519 restrictIsAntecessorOfRefinedVertex = true;
520 } else if (vertex.getState() == GridVertex::State::EraseTriggered) {
521 restrictIsAntecessorOfRefinedVertex = true;
522 } else if (vertex.getState() == GridVertex::State::Erasing) {
524 }
525
526 sendGridVertex(vertex);
527
528 if (restrictIsAntecessorOfRefinedVertex) {
529 dfor2(k) if (restrictToCoarseGrid(k, fineVertexPositionWithinPatch)) {
530 logDebug(
531 "updateVertexBeforeStore(...)",
532 "set antecessor flag (veto coarsenign) on vertex " << coarseGridVertices[kScalar].toString(
533 ) << " due to vertex " << vertex.toString()
534 );
535 coarseGridVertices[kScalar].setIsAntecessorOfRefinedVertexInCurrentTreeSweep(true);
536 coarseGridVertices[kScalar].setIsParentOfSubtreeVertexInCurrentTreeSweep(
537 coarseGridVertices[kScalar].getIsParentOfSubtreeVertexInCurrentTreeSweep()
539 );
540 }
542 }
543
544 if (shouldEraseAdjacencyInformation(vertex, coarseGridVertices, fineVertexPositionWithinPatch)) {
546 }
547 }
548
549 logTraceOutWith2Arguments("updateVertexBeforeStore()", vertex.toString(), _id);
550}
551
553 const GridVertex& vertex,
554 GridVertex coarseGridVertices[TwoPowerD],
555 tarch::la::Vector<Dimensions, int> fineVertexPositionWithinPatch
556) const {
557 if (isVertexAdjacentToLocalSpacetree(vertex, true, true) or vertex.getState() != GridVertex::State::Unrefined) {
558 return false;
559 }
560
561 logTraceInWith2Arguments("shouldEraseAdjacencyInformation(...)", vertex.toString(), fineVertexPositionWithinPatch);
562 for (int d = 0; d < Dimensions; d++) {
563 if (fineVertexPositionWithinPatch(d) != 0 and fineVertexPositionWithinPatch(d) != 3) {
564 tarch::la::Vector<Dimensions, int> positionA = fineVertexPositionWithinPatch;
565 tarch::la::Vector<Dimensions, int> positionB = fineVertexPositionWithinPatch;
566
567 positionA(d) = 0;
568 positionB(d) = 3;
569
570 bool result = shouldEraseAdjacencyInformation(vertex, coarseGridVertices, positionA)
571 and shouldEraseAdjacencyInformation(vertex, coarseGridVertices, positionB);
572
573 logTraceOutWith1Argument("shouldEraseAdjacencyInformation(...)", result);
574 return result;
575 }
576 }
577
578 fineVertexPositionWithinPatch = fineVertexPositionWithinPatch / 3;
579
580 bool result = not tarch::la::contains(
581 coarseGridVertices[peano4::utils::dLinearised(fineVertexPositionWithinPatch, 2)].getAdjacentRanks(), _id
582 );
583 logTraceOutWith1Argument("shouldEraseAdjacencyInformation(...)", result);
584 return result;
585}
586
588 GridVertex coarseGridVertices[TwoPowerD], const tarch::la::Vector<Dimensions, int>& vertexPositionWithin3x3Patch
589) const {
591
592 dfor2(k) std::bitset<Dimensions> vertexToInherit;
593 std::bitset<Dimensions> indexToInherit;
594 for (int d = 0; d < Dimensions; d++) {
595 if (vertexPositionWithin3x3Patch(d) <= 1) {
596 vertexToInherit.set(d, false);
597 indexToInherit.set(d, k(d) > 0 or vertexPositionWithin3x3Patch(d) > 0);
598 } else {
599 vertexToInherit.set(d, true);
600 indexToInherit.set(d, not(k(d) < 1 or vertexPositionWithin3x3Patch(d) < 3));
601 }
602 }
603 logDebug(
604 "createNewPersistentVertex(...)",
605 "inherit "
606 << indexToInherit.to_ulong() << "th index from coarse vertex " << vertexToInherit << " into local index "
607 << kScalar
608 );
609 adjacentRanks(kScalar) = coarseGridVertices[vertexToInherit.to_ulong()].getAdjacentRanks(indexToInherit.to_ulong());
611
612 return adjacentRanks;
613}
614
616 const AutomatonState& fineGridStatesState,
617 GridVertex coarseGridVertices[TwoPowerD],
618 GridVertex fineGridVertices[TwoPowerD],
619 const tarch::la::Vector<Dimensions, int>& cellPositionWithin3x3Patch,
620 TraversalObserver& observer
621) {
622 logTraceInWith3Arguments("loadVertices(...)", fineGridStatesState.toString(), cellPositionWithin3x3Patch, _id);
623
624 const std::bitset<Dimensions> coordinates = PeanoCurve::getFirstVertexIndex(fineGridStatesState);
625 for (int i = 0; i < TwoPowerD; i++) {
626 const std::bitset<Dimensions> vertexIndex(coordinates ^ std::bitset<Dimensions>(i));
628 vertexPositionWithinPatch = cellPositionWithin3x3Patch + convertToIntegerVector(vertexIndex);
629
631 x = fineGridStatesState.getX()
633 tarch::la::convertScalar<double>(convertToIntegerVector(vertexIndex)), fineGridStatesState.getH()
634 );
635
636 VertexType type = _gridTraversalEventGenerator.getVertexType(coarseGridVertices, vertexPositionWithinPatch);
637 int stackNumber = PeanoCurve::getVertexReadStackNumber(fineGridStatesState, vertexIndex);
638
639 // reset to persistent, as new vertex already has been generated
640 if (not PeanoCurve::isInOutStack(stackNumber) and type == VertexType::New) {
642 logDebug(
643 "loadVertices(...)",
644 "reset stack flag for local vertex " << vertexPositionWithinPatch << " from new/hanging to persistent"
645 );
646 }
647
648 switch (type) {
649 case VertexType::New:
651 fineGridVertices[peano4::utils::dLinearised(vertexIndex)] = createVertex(
653 x,
654 fineGridStatesState.getLevel(),
655 getAdjacentRanksForNewVertex(coarseGridVertices, vertexPositionWithinPatch),
656 true
657 );
658 break;
660 fineGridVertices[peano4::utils::dLinearised(vertexIndex)] = createVertex(
662 x,
663 fineGridStatesState.getLevel(),
664 getAdjacentRanksForNewVertex(coarseGridVertices, vertexPositionWithinPatch),
665 true
666 );
667 break;
669 logDebug("readVertices(...)", "read vertex from stack " << stackNumber);
670
671 if (PeanoCurve::isInOutStack(stackNumber)) {
672 assertion3(not _vertexStack.getForPop(_id, stackNumber)->empty(), _id, stackNumber, vertexIndex);
673 fineGridVertices[peano4::utils::dLinearised(vertexIndex)] = _vertexStack.getForPop(_id, stackNumber)->pop();
674
675 updateVertexAfterLoad(
676 fineGridVertices[peano4::utils::dLinearised(vertexIndex)],
677 coarseGridVertices,
678 vertexPositionWithinPatch,
679 observer
680 );
681 } else {
682 assertion3(not _vertexStack.getForPop(_id, stackNumber)->empty(), _id, stackNumber, vertexIndex);
683 fineGridVertices[peano4::utils::dLinearised(vertexIndex)] = _vertexStack.getForPop(_id, stackNumber)->pop();
684 }
685 } break;
686 case VertexType::Delete: {
687 logDebug("readVertices(...)", "read vertex from stack " << stackNumber);
688
689 if (PeanoCurve::isInOutStack(stackNumber)) {
690 assertion2(not _vertexStack.getForPop(_id, stackNumber)->empty(), stackNumber, _id);
691 fineGridVertices[peano4::utils::dLinearised(vertexIndex)] = _vertexStack.getForPop(_id, stackNumber)->pop();
692
693 updateVertexAfterLoad(
694 fineGridVertices[peano4::utils::dLinearised(vertexIndex)],
695 coarseGridVertices,
696 vertexPositionWithinPatch,
697 observer
698 );
699 fineGridVertices[peano4::utils::dLinearised(vertexIndex)].setState(GridVertex::State::Delete);
700 } else {
701 assertion2(not _vertexStack.getForPop(_id, stackNumber)->empty(), stackNumber, _id);
702 fineGridVertices[peano4::utils::dLinearised(vertexIndex)] = _vertexStack.getForPop(_id, stackNumber)->pop();
703 }
704 } break;
705 }
706 logDebug(
707 "loadVertices(...)",
708 "handled "
709 << peano4::grid::toString(type) << " vertex " << vertexIndex << " at " << vertexPositionWithinPatch << ": "
710 << fineGridVertices[peano4::utils::dLinearised(vertexIndex)].toString()
711 );
712
714 fineGridVertices[peano4::utils::dLinearised(vertexIndex)].getX(),
715 x,
716 fineGridVertices[peano4::utils::dLinearised(vertexIndex)].toString(),
717 fineGridStatesState.toString(),
718 vertexIndex,
719 toString(),
720 _id
721 );
723 fineGridVertices[peano4::utils::dLinearised(vertexIndex)].getLevel(),
724 fineGridStatesState.getLevel(),
725 fineGridVertices[peano4::utils::dLinearised(vertexIndex)].toString(),
726 fineGridStatesState.toString(),
727 vertexIndex,
728 toString(),
729 _id
730 );
731 }
732
733 logTraceOutWith1Argument("loadVertices(...)", fineGridStatesState.toString());
734}
735
737 [[maybe_unused]] const AutomatonState& fineGridStatesState,
738 [[maybe_unused]] GridVertex coarseGridVertices[TwoPowerD],
739 [[maybe_unused]] GridVertex fineGridVertices[TwoPowerD],
740 [[maybe_unused]] const tarch::la::Vector<Dimensions, int>& cellPositionWithin3x3Patch,
741 [[maybe_unused]] TraversalObserver& observer
742) {
743 logTraceInWith1Argument("storeVertices(...)", fineGridStatesState.toString());
744
745 const std::bitset<Dimensions> coordinates = PeanoCurve::getFirstVertexIndex(fineGridStatesState);
746 for (int i = 0; i < TwoPowerD; i++) {
747 const std::bitset<Dimensions> vertexIndex(coordinates ^ std::bitset<Dimensions>(i));
749 vertexPositionWithinPatch = cellPositionWithin3x3Patch + convertToIntegerVector(vertexIndex);
750
751 // const tarch::la::Vector<Dimensions,double> x = fineGridStatesState.getX()
752 // + tarch::la::multiplyComponents(
753 // tarch::la::convertScalar<double>( convertToIntegerVector(vertexIndex) ),
754 // fineGridStatesState.getH()
755 // );
756
757 const int stackNumber = PeanoCurve::getVertexWriteStackNumber(fineGridStatesState, vertexIndex);
758 VertexType type = _gridTraversalEventGenerator.getVertexType(coarseGridVertices, vertexPositionWithinPatch);
759
760 if (not PeanoCurve::isInOutStack(stackNumber) and type == VertexType::Delete) {
762 logDebug(
763 "storeVertices(...)",
764 "reset stack flag for local vertex " << vertexPositionWithinPatch << " from new/hanging to persistent"
765 );
766 }
767
768 switch (type) {
769 case VertexType::New:
771 logDebug(
772 "storeVertices(...)",
773 "write vertex "
774 << fineGridVertices[peano4::utils::dLinearised(vertexIndex)].toString() << " to stack " << stackNumber
775 );
776 if (PeanoCurve::isInOutStack(stackNumber)) {
777 updateVertexBeforeStore(
778 fineGridVertices[peano4::utils::dLinearised(vertexIndex)], coarseGridVertices, vertexPositionWithinPatch
779 );
780 }
781 _vertexStack.getForPush(_id, stackNumber)->push(fineGridVertices[peano4::utils::dLinearised(vertexIndex)]);
782 } break;
784 logDebug(
785 "storeVertices(...)", "discard vertex " << fineGridVertices[peano4::utils::dLinearised(vertexIndex)].toString()
786 );
787 break;
789 logDebug(
790 "storeVertices(...)", "delete vertex " << fineGridVertices[peano4::utils::dLinearised(vertexIndex)].toString()
791 );
793 break;
794 }
795 }
796
797 logTraceOutWith1Argument("storeVertices(...)", fineGridStatesState.toString());
798}
799
801 const {
802 const bool receiverCriteria = (_joining.count(rank) == 0) and (_splitting.count(rank) == 0);
803 const bool senderCriteria = (_joining.count(rank) == 0) and (_splitTriggered.count(rank) == 0)
804 and _spacetreeState != SpacetreeState::Joining;
805
806 const bool mandatoryCriteria = rank != _id and rank != InvalidRank and rank != RankOfPeriodicBoundaryCondition;
807
808 return calledByReceivingProcess ? (mandatoryCriteria and receiverCriteria) : (mandatoryCriteria and senderCriteria);
809}
810
812 GridVertex fineGridVertices[TwoPowerD], int faceNumber, bool calledByReceivingProcess
813) const {
814 logTraceInWith2Arguments("isFaceAlongPeriodicBoundaryCondition(...)", faceNumber, calledByReceivingProcess);
815
816 tarch::la::Vector<TwoPowerD, int> adjacentRanksOfFace = _gridTraversalEventGenerator.getAdjacentRanksOfFace(
817 fineGridVertices, faceNumber, calledByReceivingProcess
818 );
819
820 bool isAdjacentToLocalRank = false;
821 bool holdsPeriodicBoundaryConditionFlag = false; // semantics is either has been local or will be local
822 for (int i = 0; i < TwoPowerD; i++) {
823 isAdjacentToLocalRank |= adjacentRanksOfFace(i) == _id;
824 holdsPeriodicBoundaryConditionFlag |= adjacentRanksOfFace(i) == RankOfPeriodicBoundaryCondition;
825 }
826
827 holdsPeriodicBoundaryConditionFlag &= isAdjacentToLocalRank;
828
830 "isFaceAlongPeriodicBoundaryCondition(...)", holdsPeriodicBoundaryConditionFlag, isAdjacentToLocalRank
831 );
832 return holdsPeriodicBoundaryConditionFlag;
833}
834
836 GridVertex fineGridVertices[TwoPowerD], int faceNumber, bool calledByReceivingProcess
837) const {
838 logTraceInWith3Arguments("getNeighbourTrees(...)", faceNumber, calledByReceivingProcess, _id);
839
840 tarch::la::Vector<TwoPowerD, int> adjacentRanksOfFace = _gridTraversalEventGenerator.getAdjacentRanksOfFace(
841 fineGridVertices, faceNumber, calledByReceivingProcess
842 );
843
844 logDebug("getNeighbourTrees(...)", "face adjacency list=" << adjacentRanksOfFace);
845
846 // Study whether face is local and who neighbours it. See routine
847 // documentation of our particular flavour of localness in this
848 // case.
849 // --------------------------------------------------------------
850 bool isAdjacentToLocalRank = false; // semantics is either has been local or will be local
851 int neighbour = TraversalObserver::NoData;
852 for (int i = 0; i < TwoPowerD; i++) {
853 const bool mandatoryCriteria = adjacentRanksOfFace(i) != _id and adjacentRanksOfFace(i) != InvalidRank
854 and adjacentRanksOfFace(i) != RankOfPeriodicBoundaryCondition
855 and _spacetreeState != SpacetreeState::EmptyRun;
856
857 if (calledByReceivingProcess) {
858 isAdjacentToLocalRank |= adjacentRanksOfFace(i) == _id or _splitTriggered.count(adjacentRanksOfFace(i)) == 1
859 or _splitting.count(adjacentRanksOfFace(i)) == 1;
860
861 const bool receiverCriteria = _splitTriggered.count(adjacentRanksOfFace(i)) == 0
862 and _splitting.count(adjacentRanksOfFace(i)) == 0
863 and _spacetreeState != SpacetreeState::NewFromSplit;
864
865 if (mandatoryCriteria and receiverCriteria) {
866 neighbour = adjacentRanksOfFace(i);
867 }
868 } else {
869 isAdjacentToLocalRank |= adjacentRanksOfFace(i) == _id or _splitTriggered.count(adjacentRanksOfFace(i)) == 1;
870
871 const bool senderCriteria = _splitTriggered.count(adjacentRanksOfFace(i)) == 0;
872
873 if (mandatoryCriteria and senderCriteria) {
874 neighbour = adjacentRanksOfFace(i);
875 }
876 }
877 }
878
879 if (not isAdjacentToLocalRank) {
880 neighbour = TraversalObserver::NoData;
881 }
882
883 logTraceOutWith1Argument("getNeighbourTrees(...)", neighbour);
884 return neighbour;
885}
886
887std::set<int> peano4::grid::Spacetree::getNeighbourTrees(const GridVertex& vertex, bool calledByReceivingProcess)
888 const {
889 std::set<int> neighbourIds;
890
891 const bool isLocalVertex = calledByReceivingProcess ? isVertexAdjacentToLocalSpacetree(vertex, true, false)
892 : isVertexAdjacentToLocalSpacetree(vertex, false, true);
893
894 if (isLocalVertex) {
895 auto adjacentRanks = calledByReceivingProcess ? vertex.getBackupOfAdjacentRanks() : vertex.getAdjacentRanks();
896
897 for (int i = 0; i < TwoPowerD; i++) {
898 if (doesRankIndexIdentifyHorizontalDataExchange(adjacentRanks(i), calledByReceivingProcess)) {
899 neighbourIds.insert(adjacentRanks(i));
900 }
901 }
902 }
903
904 return neighbourIds;
905}
906
908 GridVertex& vertex, const GridVertex& inVertex, int neighbour
909) {
910 //
911 // Merge adjacency lists. The neighbour owns some entries
912 //
913 for (int i = 0; i < TwoPowerD; i++) {
914 if (vertex.getAdjacentRanks(i) == neighbour and neighbour != InvalidRank) {
915 if (inVertex.getAdjacentRanks(i) != vertex.getAdjacentRanks(i)) {
916 logDebug(
917 "mergeGridVertexAdjacencyListsAtHorizontalDomainBoundary(...)",
918 "update "
919 << i << "th entry of adjacency data of vertex " << vertex.toString() << " with neighbouring vertex "
920 << inVertex.toString() << " on tree " << _id
921 );
922 }
923 vertex.setAdjacentRanks(i, inVertex.getAdjacentRanks(i));
924 }
925 }
926}
927
929 [[maybe_unused]] GridVertex& vertex, [[maybe_unused]] const GridVertex& inVertex, [[maybe_unused]] int neighbour
930) {
932 vertex.getState() != GridVertex::State::HangingVertex, inVertex.toString(), vertex.toString(), _id, neighbour
933 );
935 inVertex.getState() != GridVertex::State::HangingVertex, inVertex.toString(), vertex.toString(), _id, neighbour
936 );
938 tarch::la::equals(vertex.getX(), inVertex.getX())
939 or
940 (
941 tarch::la::contains(vertex.getAdjacentRanks(),RankOfPeriodicBoundaryCondition)
942 and
943 (_periodicBC.count()>1 or tarch::la::countEqualEntries(vertex.getX(), inVertex.getX())==Dimensions-static_cast<int>(_periodicBC.count()))
944 ),
945 inVertex.toString(), vertex.toString(), _id, neighbour,
946 tarch::la::countEqualEntries(vertex.getX(), inVertex.getX()), _periodicBC
947 );
948 assertionEquals4(vertex.getLevel(), inVertex.getLevel(), inVertex.toString(), vertex.toString(), _id, neighbour);
950 not(vertex.getState() == GridVertex::State::Refined and inVertex.getState() == GridVertex::State::Erasing),
951 inVertex.toString(),
952 vertex.toString(),
953 _id,
954 neighbour
955 );
957 not(vertex.getState() == GridVertex::State::Refined and inVertex.getState() == GridVertex::State::Unrefined),
958 inVertex.toString(),
959 vertex.toString(),
960 _id,
961 neighbour
962 );
963
964 //
965 // Merge helper flags
966 //
967 vertex.setIsAntecessorOfRefinedVertexInCurrentTreeSweep(
968 vertex.getIsAntecessorOfRefinedVertexInCurrentTreeSweep()
969 or inVertex.getIsAntecessorOfRefinedVertexInCurrentTreeSweep()
970 );
971
972 //
973 // Update refinement flags
974 //
975 assertion3(vertex.getState() != GridVertex::State::Erasing, vertex.toString(), inVertex.toString(), _id);
976 assertion3(vertex.getState() != GridVertex::State::Refining, vertex.toString(), inVertex.toString(), _id);
977
978 const bool OnlyNeighbourHasTriggeredRefinement
979 = inVertex.getState() == GridVertex::State::RefinementTriggered
980 && (vertex.getState() == GridVertex::State::Unrefined or vertex.getState() == GridVertex::State::New or vertex.getState() == GridVertex::State::Delete);
981 const bool OnlyLocalHasTriggeredRefinement =
982 vertex.getState()==GridVertex::State::RefinementTriggered &&
983 (inVertex.getState()==GridVertex::State::Unrefined or inVertex.getState()==GridVertex::State::New or inVertex.getState()==GridVertex::State::Delete);
984 const bool OnlyNeighbourHasTriggeredErase = inVertex.getState() == GridVertex::State::EraseTriggered
985 && vertex.getState() == GridVertex::State::Refined;
986 const bool OnlyLocalHasTriggeredErase = vertex.getState() == GridVertex::State::EraseTriggered
987 && inVertex.getState() == GridVertex::State::Refined;
988
989 if (OnlyNeighbourHasTriggeredRefinement || OnlyLocalHasTriggeredRefinement) {
991 logDebug(
992 "mergeGridVertexRefinementStateAtHorizontalDomainBoundary( GridVertex )",
993 "set state to " << vertex.toString() << " on tree " << _id << " due to merge with neighbour"
994 );
995 } else if (OnlyNeighbourHasTriggeredErase || OnlyLocalHasTriggeredErase) {
996 vertex.setState(GridVertex::State::EraseTriggered);
997 logDebug(
998 "mergeGridVertexRefinementStateAtHorizontalDomainBoundary( GridVertex )",
999 "set state to " << vertex.toString() << " on tree " << _id << " due to merge with neighbour"
1000 );
1001 } else {
1002 assertion4(vertex.getState() == inVertex.getState(), inVertex.toString(), vertex.toString(), _id, neighbour);
1003 }
1004}
1005
1007 assertion(_spacetreeState != SpacetreeState::NewFromSplit and _spacetreeState != SpacetreeState::EmptyRun);
1008
1009 logTraceInWith1Argument("receiveAndMergeGridVertexAtHorizontalBoundary(...)", vertex.toString());
1010
1011 //
1012 // Backup adjacency lists
1013 //
1015
1016 std::set<int> neighbourIds = getNeighbourTrees(vertex, true);
1017 for (auto neighbour : neighbourIds) {
1018 assertion1(neighbour >= 0, neighbour);
1020
1021 assertion4(_vertexStack.holdsStack(_id, inStack), _id, inStack, neighbour, vertex.toString());
1022 assertion4(not _vertexStack.getForPop(_id, inStack)->empty(), _id, inStack, neighbour, vertex.toString());
1023 GridVertex inVertex = _vertexStack.getForPop(_id, inStack)->pop();
1024
1025 mergeGridVertexRefinementStateAtHorizontalDomainBoundary(vertex, inVertex, neighbour);
1026 mergeGridVertexAdjacencyListsAtHorizontalDomainBoundary(vertex, inVertex, neighbour);
1027 }
1028
1029 std::set<peano4::parallel::Node::PeriodicBoundaryStackIdentifier>
1030 periodicBCOutputStacks = _id == 0 ? peano4::parallel::Node::getInstance()
1032 : std::set<peano4::parallel::Node::PeriodicBoundaryStackIdentifier>();
1033 std::set<peano4::parallel::Node::PeriodicBoundaryStackIdentifier> periodicBCInputStacks;
1034 for (auto& p : periodicBCOutputStacks) {
1037 ));
1038 }
1039
1040 for (auto stackNo : periodicBCInputStacks) {
1041 assertion4(_id == 0, _id, stackNo.first, stackNo.second, vertex.toString());
1042 assertion3(not _vertexStack.getForPop(_id, stackNo.first)->empty(), stackNo.first, stackNo.second, _id);
1043 GridVertex inVertex = _vertexStack.getForPop(_id, stackNo.first)->pop();
1044 logDebug(
1045 "receiveAndMergeGridVertexAtHorizontalBoundary(...)",
1046 "read periodic BC data from stack " << stackNo.first << ": " << inVertex.toString()
1047 );
1048 logDebug(
1049 "receiveAndMergeGridVertexAtHorizontalBoundary(...)", "normals of involved symmetry axes: " << stackNo.second
1050 );
1051 mergeGridVertexRefinementStateAtHorizontalDomainBoundary(vertex, inVertex, _id);
1052
1053 dfor2(k) assertion3(
1054 vertex.getAdjacentRanks(kScalar) == RankOfPeriodicBoundaryCondition or vertex.getAdjacentRanks(kScalar) == _id
1055 or vertex.getAdjacentRanks(kScalar) == InvalidRank,
1056 vertex.toString(),
1057 inVertex.toString(),
1058 _id
1059 );
1060 enddforx
1061 }
1062
1063 logTraceOut("receiveAndMergeGridVertexAtHorizontalBoundary(...)");
1064}
1065
1067 logTraceInWith2Arguments("sendGridVertex(GridVertex)", vertex.toString(), _id);
1068
1069 assertion2(_spacetreeState != SpacetreeState::EmptyRun, _id, peano4::grid::toString(_spacetreeState));
1070
1071 std::set<int> outRanks = getNeighbourTrees(vertex, false);
1072
1073 for (auto p : outRanks) {
1074 //
1075 // Boundary exchange
1076 //
1078
1079 GridVertex vertexCopy = vertex;
1080 for (int i = 0; i < TwoPowerD; i++) {
1081 int targetRank = vertexCopy.getAdjacentRanks(i);
1082 if (_spacetreeState == SpacetreeState::JoinTriggered and targetRank == _id and p != _masterId) {
1083 vertexCopy.setAdjacentRanks(i, _masterId);
1084 }
1085 }
1086
1087 _vertexStack.getForPush(_id, stackNo)->push(vertexCopy);
1088 }
1089
1090 std::set<peano4::parallel::Node::PeriodicBoundaryStackIdentifier>
1091 periodicBCStacks = _id == 0 ? peano4::parallel::Node::getInstance()
1093 : std::set<peano4::parallel::Node::PeriodicBoundaryStackIdentifier>();
1094
1095 for (auto stackNo : periodicBCStacks) {
1096 _vertexStack.getForPush(_id, stackNo.first)->push(vertex);
1097 logDebug(
1098 "sendGridVertex(GridVertex)",
1099 "vertex "
1100 << vertex.toString() << " on tree " << _id << " goes to stack " << stackNo.first << " to realise periodic BC"
1101 );
1102 }
1103
1104 logTraceOutWith1Argument("sendGridVertex(GridVertex)", isVertexAdjacentToLocalSpacetree(vertex, true, true));
1105}
1106
1108 dfor2(k) vertices[kScalar].setNumberOfAdjacentRefinedLocalCells(
1109 vertices[kScalar].getNumberOfAdjacentRefinedLocalCells() + 1
1110 );
1111 logDebug(
1112 "incrementNumberOfAdjacentRefinedLocalCells(...)", "incremented counter of " << vertices[kScalar].toString()
1113 );
1114 enddforx
1115}
1116
1118 dfor2(k) fineGridVertices[kScalar].setAdjacentRanks(TwoPowerD - kScalar - 1, newId);
1119 enddforx
1120}
1121
1123 const AutomatonState& state, GridVertex coarseGridVertices[TwoPowerD], GridVertex fineGridVertices[TwoPowerD]
1124) {
1125 if (not _gridControlEvents.empty()) {
1126 logTraceInWith2Arguments("evaluateGridControlEvents(...)", state.toString(), _gridControlEvents.size());
1127
1128 assertion1(
1129 _spacetreeState != SpacetreeState::EmptyRun and _spacetreeState != SpacetreeState::NewFromSplit
1130 and _spacetreeState != SpacetreeState::Joining,
1131 toString()
1132 );
1133
1134 bool mayChangeGrid = true;
1135 for (int i = 0; i < TwoPowerD; i++) {
1136 // excluding refinement triggered and refining ensures that we have no immediate
1137 // refine anymore. This is important for the adjacency lists. We have to allow
1138 // erase triggered, as the grid control events are evaluated top-down, i.e. data
1139 // might be set.
1140 mayChangeGrid &= (
1141 coarseGridVertices[i].getState()==GridVertex::State::HangingVertex
1142 or
1143 coarseGridVertices[i].getState()==GridVertex::State::Unrefined
1144 or
1145 coarseGridVertices[i].getState()==GridVertex::State::Refined
1146 or
1147 coarseGridVertices[i].getState()==GridVertex::State::EraseTriggered
1148 );
1149 }
1150
1151 bool refine = false;
1152 bool erase = false;
1153 if (mayChangeGrid) {
1154 for (auto p : _gridControlEvents) {
1155 if (
1156 overlaps(state,p)
1157 and
1158 p.getRefinementControl()==GridControlEvent::RefinementControl::Refine
1159 and
1161 ) {
1162 refine = true;
1163 }
1164
1165 if (
1166 isContained(state,p,3.0)
1167 and
1168 p.getRefinementControl()==GridControlEvent::RefinementControl::Erase
1169 and
1170 tarch::la::allSmaller( state.getH(), p.getH() )
1171 ) {
1172 erase = true;
1173 }
1174 }
1175 }
1176
1177 logDebug(
1178 "evaluateGridControlEvents(...)",
1179 _gridControlEvents.size(
1180 ) << " event(s) in state "
1181 << state.toString() << " trigger change=" << mayChangeGrid << ", refine=" << refine << ", erase=" << erase
1182 );
1183
1184 if (refine) {
1185 bool haveTriggeredRefinementForAtLeastOneVertex = false;
1186 dfor2(i
1187 ) if (isVertexAdjacentToLocalSpacetree(fineGridVertices[iScalar], true, true) and fineGridVertices[iScalar].getState() == GridVertex::State::Unrefined) {
1188 fineGridVertices[iScalar].setState(GridVertex::State::RefinementTriggered);
1189 haveTriggeredRefinementForAtLeastOneVertex = true;
1190 }
1191 enddforx
1192
1193 if (not haveTriggeredRefinementForAtLeastOneVertex) {
1194 logDebug("evaluate...", "wanted to refine cell " << state.toString() << " but no vertex is refinable");
1195 }
1196 } else if (erase) {
1197 for (int i = 0; i < TwoPowerD; i++) {
1198 if (isVertexAdjacentToLocalSpacetree(fineGridVertices[i], true, true) and fineGridVertices[i].getState() == GridVertex::State::Refined) {
1199 fineGridVertices[i].setState(GridVertex::State::EraseTriggered);
1200 }
1201 }
1202 }
1203
1204 logTraceOutWith3Arguments("evaluateGridControlEvents(...)", state.toString(), refine, erase);
1205 }
1206}
1207
1209 const AutomatonState& state, GridVertex vertices[TwoPowerD], TraversalObserver& observer
1210) {
1212 logTraceInWith2Arguments("descend(...)", state.toString(), _id);
1213
1214#if PeanoDebug >= 2
1215 dfor2(k) logDebug("descend(...)", "-" << vertices[kScalar].toString());
1216 enddforx
1217#endif
1218
1219 peano4::utils::LoopDirection loopDirection
1221
1222 //
1223 // Construct the 3^d new children states
1224 //
1225 AutomatonState fineGridStates[ThreePowerD];
1226 refineState(state, fineGridStates);
1227
1228#if PeanoDebug >= 2
1229 dfor3(k) logDebug("descend(...)", "-" << fineGridStates[kScalar].toString());
1230 enddforx
1231#endif
1232
1233 //
1234 // Loop over children
1235 //
1236 zfor3(k, loopDirection)
1237 //
1238 // Load cell's vertices
1239 //
1240 GridVertex fineGridVertices[TwoPowerD];
1241 loadVertices(fineGridStates[peano4::utils::dLinearised(k, 3)], vertices, fineGridVertices, k, observer);
1242
1243 mergeCellFromWorkerWithMasterThroughoutJoin(vertices, fineGridVertices);
1244
1245 //
1246 // Enter cell
1247 //
1248
1249 // flag areas which fork off further
1250 if (isSpacetreeNodeLocal(fineGridVertices, false, false) and not isSpacetreeNodeLocal(vertices, false, false)) {
1251 markVerticesAroundForkedCell(vertices, fineGridVertices);
1252 } else if (not isSpacetreeNodeLocal(fineGridVertices, false, false) and isSpacetreeNodeLocal(vertices, false, false)) {
1253 markVerticesAroundForkedCell(vertices, fineGridVertices);
1254 }
1255
1256 // refinement control
1257 if (isSpacetreeNodeLocal(fineGridVertices, false, false)) {
1258 evaluateGridControlEvents(fineGridStates[peano4::utils::dLinearised(k, 3)], vertices, fineGridVertices);
1259 }
1260
1261 splitCellTopDown(vertices, fineGridVertices);
1262
1263 GridTraversalEvent enterCellTraversalEvent = _gridTraversalEventGenerator.createEnterCellTraversalEvent(
1264 vertices,
1265 fineGridVertices,
1266 fineGridStates[peano4::utils::dLinearised(k, 3)],
1267 _splitTriggered,
1268 _splitting,
1269 _joinTriggered,
1270 _joining,
1271 _hasSplit,
1272 k,
1273 _spacetreeState == SpacetreeState::Running
1274 );
1275
1276 observer.loadCell(
1277 _gridTraversalEventGenerator.createPrunedEnterCellTraversalEvent(_spacetreeState, enterCellTraversalEvent)
1278 );
1279
1280 if (_spacetreeState != SpacetreeState::EmptyRun and _spacetreeState != SpacetreeState::NewFromSplit and _spacetreeState != SpacetreeState::Joined) {
1281 receiveAndMergeUserData(
1282 fineGridStates[peano4::utils::dLinearised(k, 3)], observer, enterCellTraversalEvent, fineGridVertices
1283 );
1284 }
1285
1286 observer.enterCell(
1287 _gridTraversalEventGenerator.createPrunedEnterCellTraversalEvent(_spacetreeState, enterCellTraversalEvent)
1288 );
1289
1290 _statistics.setMinH(tarch::la::min(_statistics.getMinH(), 1.0 / 3.0 * state.getH()));
1291
1292 //
1293 // DFS
1294 //
1295 if (isSpacetreeNodeRefined(fineGridVertices)) {
1296 if (isSpacetreeNodeLocal(fineGridVertices, false, false)) {
1297 _statistics.setNumberOfLocalRefinedCells(_statistics.getNumberOfLocalRefinedCells() + 1);
1298 incrementNumberOfAdjacentRefinedLocalCells(fineGridVertices);
1299 } else {
1300 _statistics.setNumberOfRemoteRefinedCells(_statistics.getNumberOfRemoteRefinedCells() + 1);
1301 }
1302 descend(fineGridStates[peano4::utils::dLinearised(k, 3)], fineGridVertices, observer);
1303 } else {
1304 if (isSpacetreeNodeLocal(fineGridVertices, true, true)) {
1305 _statistics.setNumberOfLocalUnrefinedCells(_statistics.getNumberOfLocalUnrefinedCells() + 1);
1306 } else {
1307 _statistics.setNumberOfRemoteUnrefinedCells(_statistics.getNumberOfRemoteUnrefinedCells() + 1);
1308 }
1309 }
1310
1311 //
1312 // Leave cell
1313 //
1314 GridTraversalEvent leaveCellTraversalEvent = _gridTraversalEventGenerator.createLeaveCellTraversalEvent(
1315 vertices,
1316 fineGridVertices,
1317 fineGridStates[peano4::utils::dLinearised(k, 3)],
1318 _splitTriggered,
1319 _splitting,
1320 _joinTriggered,
1321 _joining,
1322 _hasSplit,
1323 k,
1324 _spacetreeState == SpacetreeState::Running
1325 );
1326
1327 observer.leaveCell(
1328 _gridTraversalEventGenerator.createPrunedLeaveCellTraversalEvent(_spacetreeState, leaveCellTraversalEvent)
1329 );
1330
1331 if (_spacetreeState != SpacetreeState::EmptyRun and _spacetreeState != SpacetreeState::Joined) {
1332 sendUserData(fineGridStates[peano4::utils::dLinearised(k, 3)], observer, leaveCellTraversalEvent, fineGridVertices);
1333 }
1334
1335 observer.storeCell(
1336 _gridTraversalEventGenerator.createPrunedLeaveCellTraversalEvent(_spacetreeState, leaveCellTraversalEvent)
1337 );
1338
1339 splitOrJoinCellBottomUp(vertices, fineGridVertices);
1340
1341 //
1342 // Store vertices
1343 //
1344 storeVertices(fineGridStates[peano4::utils::dLinearised(k, 3)], vertices, fineGridVertices, k, observer);
1345 endzfor
1346
1347 logTraceOut("descend(...)");
1348}
1349
1351 const AutomatonState& state,
1352 TraversalObserver& observer,
1353 const GridTraversalEvent& enterCellTraversalEvent,
1354 GridVertex fineGridVertices[TwoPowerD]
1355) {
1356 logTraceInWith3Arguments("receiveAndMergeUserData(...)", state.toString(), enterCellTraversalEvent.toString(), _id);
1357
1358 assertion3(
1359 _spacetreeState != SpacetreeState::EmptyRun and _spacetreeState != SpacetreeState::NewFromSplit
1360 and _spacetreeState != SpacetreeState::Joined,
1361 state.toString(),
1362 peano4::grid::toString(_spacetreeState),
1363 _id
1364 );
1365
1366 for (int i = 0; i < TwoPowerD; i++) {
1367 int inVertexStack = enterCellTraversalEvent.getVertexDataFrom(i);
1368 int inVertexPositionWithinCell = enterCellTraversalEvent.getVertexDataTo(i);
1369
1370 if (peano4::grid::PeanoCurve::isInOutStack(inVertexStack)) {
1373
1374 if (enterCellTraversalEvent.getIsVertexLocal(inVertexPositionWithinCell)) {
1375 std::set<int> neighbours = getNeighbourTrees(fineGridVertices[inVertexPositionWithinCell], true);
1376 for (auto p : neighbours) {
1377 logDebug(
1378 "receiveAndMergeUserData(...)",
1379 "receive neighbour data from neighbour "
1380 << p << " for vertex " << fineGridVertices[inVertexPositionWithinCell].toString()
1381 );
1383 observer.receiveAndMergeVertex(
1384 inVertexPositionWithinCell,
1385 fromStack, // Rank
1387 enterCellTraversalEvent
1388 );
1389 }
1390
1391 std::set<peano4::parallel::Node::PeriodicBoundaryStackIdentifier>
1392 periodicBCOutputStacks = _id == 0
1394 fineGridVertices[inVertexPositionWithinCell].getAdjacentRanks()
1395 )
1396 : std::set<peano4::parallel::Node::PeriodicBoundaryStackIdentifier>();
1397
1398 std::set<peano4::parallel::Node::PeriodicBoundaryStackIdentifier> periodicBCInputStacks;
1399 for (auto& p : periodicBCOutputStacks) {
1400 periodicBCInputStacks.insert(
1402 );
1403 }
1404
1405 for (auto p : periodicBCInputStacks) {
1406 observer.receiveAndMergeVertex(
1407 inVertexPositionWithinCell,
1408 p.first, // Rank
1410 enterCellTraversalEvent
1411 );
1412 }
1413 }
1414 }
1415 }
1416
1417 for (int i = 0; i < 2 * Dimensions; i++) {
1418 int inFaceStack = enterCellTraversalEvent.getFaceDataFrom(i);
1419 int inFacePositionWithinCell = enterCellTraversalEvent.getFaceDataTo(i);
1420 if (peano4::grid::PeanoCurve::isInOutStack(inFaceStack)) {
1423
1424 if (enterCellTraversalEvent.getIsFaceLocal(inFacePositionWithinCell)) {
1425 int neighbour = getNeighbourTrees(fineGridVertices, inFacePositionWithinCell, true);
1426 if (neighbour >= 0) {
1428 observer.receiveAndMergeFace(
1429 inFacePositionWithinCell,
1430 fromStack,
1432 enterCellTraversalEvent
1433 );
1434 }
1435
1436 if (isFaceAlongPeriodicBoundaryCondition(fineGridVertices, inFacePositionWithinCell, true)) {
1439 );
1440
1441 peano4::datamanagement::FaceMarker marker(enterCellTraversalEvent, inFacePositionWithinCell /*oppositeFace*/);
1442 logDebug(
1443 "receiveAndMergeUserData(...)",
1444 "will merge face from periodic BC stack #"
1445 << fromStack << " with local face. Cell marker=" << marker.toString()
1446 << ". in-face=" << inFacePositionWithinCell
1447 );
1448
1449 observer.receiveAndMergeFace(
1450 inFacePositionWithinCell,
1451 fromStack,
1453 enterCellTraversalEvent
1454 );
1455 }
1456 }
1457 }
1458 }
1459
1460 logTraceOut("receiveAndMergeUserData(...)");
1461}
1462
1464 [[maybe_unused]] const AutomatonState& state,
1465 [[maybe_unused]] TraversalObserver& observer,
1466 [[maybe_unused]] const GridTraversalEvent& leaveCellTraversalEvent,
1467 [[maybe_unused]] GridVertex fineGridVertices[TwoPowerD]
1468) {
1469 logTraceInWith3Arguments("sendUserData(...)", state.toString(), leaveCellTraversalEvent.toString(), _id);
1470 assertion4(
1471 _spacetreeState != SpacetreeState::EmptyRun and _spacetreeState != SpacetreeState::Joined,
1472 peano4::grid::toString(_spacetreeState),
1473 state.toString(),
1474 leaveCellTraversalEvent.toString(),
1475 _id
1476 );
1477
1478 for (int i = 0; i < TwoPowerD; i++) {
1479 int outVertexStack = leaveCellTraversalEvent.getVertexDataTo(i);
1480 int outVertexPositionWithinCell = leaveCellTraversalEvent.getVertexDataFrom(i);
1481
1482 if (peano4::grid::PeanoCurve::isInOutStack(outVertexStack)) {
1485
1486 if (leaveCellTraversalEvent.getIsVertexLocal(outVertexPositionWithinCell)) {
1487 std::set<int> neighbours = getNeighbourTrees(fineGridVertices[outVertexPositionWithinCell], false);
1488
1489 for (auto p : neighbours) {
1490 logDebug(
1491 "sendUserData(...)",
1492 "send local vertex data of "
1493 << fineGridVertices[outVertexPositionWithinCell].toString() << " from stack " << outVertexStack
1494 << " on tree " << _id << " to neighbour " << p << ". Position within cell=" << outVertexPositionWithinCell
1495 );
1497 observer.sendVertex(
1498 outVertexPositionWithinCell,
1499 toStack,
1501 leaveCellTraversalEvent
1502 );
1503 }
1504
1505 std::set<peano4::parallel::Node::PeriodicBoundaryStackIdentifier>
1507 fineGridVertices[outVertexPositionWithinCell].getAdjacentRanks()
1508 )
1509 : std::set<peano4::parallel::Node::PeriodicBoundaryStackIdentifier>();
1510
1511 for (auto stackNo : periodicBCStacks) {
1512 logDebug(
1513 "sendUserData(...)",
1514 "vertex "
1515 << fineGridVertices[outVertexPositionWithinCell].toString() << " on tree " << _id << " goes to stack "
1516 << stackNo.first << " to realise periodic BC"
1517 );
1518
1519 observer.sendVertex(
1520 outVertexPositionWithinCell,
1521 stackNo.first,
1523 leaveCellTraversalEvent
1524 );
1525 }
1526 }
1527
1528 for (auto p : _splitting) {
1529 if (tarch::la::contains(fineGridVertices[outVertexPositionWithinCell].getBackupOfAdjacentRanks(), p)) {
1530 logDebug(
1531 "sendUserData(...)",
1532 "stream local vertex data of "
1533 << fineGridVertices[outVertexPositionWithinCell].toString() << " from stack " << outVertexStack
1534 << " on tree " << _id << " to upcoming worker " << p << ". Position within cell="
1535 << outVertexPositionWithinCell << ". event=" << leaveCellTraversalEvent.toString()
1536 );
1538 observer.sendVertex(
1539 outVertexPositionWithinCell,
1540 toStack,
1542 leaveCellTraversalEvent
1543 );
1544 } else {
1545 logDebug(
1546 "sendUserData(...)",
1547 "skip vertex data of " << fineGridVertices[outVertexPositionWithinCell].toString() << " on tree " << _id
1548 );
1549 }
1550 }
1551 }
1552 }
1553
1554 for (int i = 0; i < 2 * Dimensions; i++) {
1555 int outFaceStack = leaveCellTraversalEvent.getFaceDataTo(i);
1556 int outFacePositionWithinCell = leaveCellTraversalEvent.getFaceDataFrom(i);
1557
1558 if (peano4::grid::PeanoCurve::isInOutStack(outFaceStack)) {
1561 if (leaveCellTraversalEvent.getIsFaceLocal(outFacePositionWithinCell)) {
1562 int neighbour = getNeighbourTrees(fineGridVertices, outFacePositionWithinCell, false);
1563 if (neighbour >= 0) {
1564 logDebug(
1565 "sendUserData(...)",
1566 "send local face from stack "
1567 << outFaceStack << " of tree " << _id << " to neighbour " << neighbour
1568 << ". Position within cell=" << outFacePositionWithinCell
1569 );
1570
1572 observer.sendFace(
1573 outFacePositionWithinCell,
1574 toStack,
1576 leaveCellTraversalEvent
1577 );
1578 }
1579
1580 if (isFaceAlongPeriodicBoundaryCondition(fineGridVertices, outFacePositionWithinCell, false)) {
1582 outFacePositionWithinCell
1583 );
1584
1585 logDebug(
1586 "sendUserData(...)",
1587 "send local face from stack " << outFaceStack << " of tree " << _id << " to periodic BC stack #" << toStack
1588 );
1589
1590 observer.sendFace(
1591 outFacePositionWithinCell,
1592 toStack,
1594 leaveCellTraversalEvent
1595 );
1596 }
1597 }
1598
1599 for (auto p : _splitting) {
1601 _gridTraversalEventGenerator.getAdjacentRanksOfFace(fineGridVertices, outFacePositionWithinCell, false), p
1602 )) {
1603 logDebug(
1604 "sendUserData(...)",
1605 "stream local face from stack "
1606 << outFaceStack << " of tree " << _id << " to new worker " << p
1607 << ". Position within cell=" << outFacePositionWithinCell
1608 );
1609
1611 observer.sendFace(
1612 outFacePositionWithinCell,
1613 toStack,
1615 leaveCellTraversalEvent
1616 );
1617 }
1618 }
1619 }
1620 }
1621
1622 [[maybe_unused]] int outCellStack = leaveCellTraversalEvent.getCellData();
1623 for (auto p : _splitting) {
1624 if (_gridTraversalEventGenerator.getTreeOwningSpacetreeNode(fineGridVertices, _splitTriggered, _splitting, _joinTriggered, _joining) == p) {
1625 logDebug(
1626 "sendUserData(...)",
1627 "stream local cell of tree "
1628 << _id << " to new worker " << p << ". Left bottom vertex=" << fineGridVertices[0].toString()
1629 );
1630
1632 observer.sendCell(toStack, TraversalObserver::SendReceiveContext::ForkDomain, leaveCellTraversalEvent);
1633 }
1634 }
1635 logTraceOutWith3Arguments("sendUserData(...)", state.toString(), leaveCellTraversalEvent.toString(), _id);
1636}
1637
1639 GridVertex coarseGridVertices[TwoPowerD], GridVertex fineGridVertices[TwoPowerD]
1640) const {
1641 bool isOneVertexAdjacentToPeriodicBC = false;
1642 bool isOneVertexParentOfForkedTree = false;
1643 dfor2(k)
1644 isOneVertexAdjacentToPeriodicBC |= tarch::la::contains(
1645 fineGridVertices[kScalar].getAdjacentRanks(), RankOfPeriodicBoundaryCondition
1646 );
1647 isOneVertexParentOfForkedTree |= fineGridVertices[kScalar].getHasBeenParentOfSubtreeVertexInPreviousTreeSweep();
1648 enddforx
1649
1650 bool result = isSpacetreeNodeLocal(fineGridVertices, false, false)
1651 and isSpacetreeNodeLocal(coarseGridVertices, false, false) and areAllVerticesNonHanging(fineGridVertices)
1652 and not isOneVertexAdjacentToPeriodicBC and (not isOneVertexParentOfForkedTree);
1653
1654 return result;
1655}
1656
1658 GridVertex coarseGridVertices[TwoPowerD], GridVertex fineGridVertices[TwoPowerD]
1659) {
1660 [[maybe_unused]] constexpr int NoSplit = -1;
1661
1662 if (not _splitTriggered.empty() and _splitTriggered.begin()->second.mode == peano4::SplitInstruction::Mode::BottomUp) {
1663 const bool isSplitCandidate = isCellSplitCandidate(coarseGridVertices, fineGridVertices);
1664 const bool isRefined = isSpacetreeNodeRefined(fineGridVertices);
1665
1666 logDebug(
1667 "splitOrJoinCellBottomUp(...)",
1668 "checked cell for bottom-up splits (first target tree=" << _splitTriggered.begin()->first
1669 << "). is-refined=" << isRefined << ", is-split-candidate=" << isSplitCandidate
1670 << " / " << fineGridVertices[0].toString()
1671 );
1672
1673 if (isSplitCandidate and isRefined) {
1674 int reducedMarker = _splittedCells.back();
1675 for (int i = 0; i < ThreePowerD; i++) {
1676 int topMarker = _splittedCells.back();
1677 _splittedCells.pop_back();
1678 if (topMarker != reducedMarker) {
1679 reducedMarker = NoSplit;
1680 }
1681 }
1682
1683 if (reducedMarker >= 0) {
1684 updateVertexRanksWithinCell(fineGridVertices, reducedMarker);
1685 }
1686
1687 _splittedCells.push_back(reducedMarker);
1688 } else if (not isSplitCandidate and isRefined) {
1689 for (int i = 0; i < ThreePowerD; i++) {
1690 _splittedCells.pop_back();
1691 }
1692 _splittedCells.push_back(NoSplit);
1693 } else if (isSplitCandidate and not isRefined) {
1694 int targetSpacetreeId = getSplittingTree();
1695 if (targetSpacetreeId >= 0) {
1696 updateVertexRanksWithinCell(fineGridVertices, targetSpacetreeId);
1697 updateSplittingCounter(targetSpacetreeId);
1698 }
1699 _splittedCells.push_back(targetSpacetreeId);
1700 } else if (not isSplitCandidate and not isRefined) {
1701 _splittedCells.push_back(NoSplit);
1702 } else {
1703 assertionMsg(false, "should not be entered as all combination are covered already");
1704 }
1705 }
1706 else if (
1707 not _splitTriggered.empty()
1708 and
1709 _splitTriggered.begin()->second.mode == peano4::SplitInstruction::Mode::AggressiveTopDown
1710 and
1711 not _splittedCells.empty()
1712 ) {
1713 int targetSpacetreeId = _splittedCells.back();
1714 _splittedCells.pop_back();
1715
1716 logDebug(
1717 "splitOrJoinCellBottomUp(...)",
1718 "checked cell for top-down splits (first split " << _splitTriggered.begin()->first << ")"
1719 );
1720 assertion(isSpacetreeNodeLocal(fineGridVertices, false, false));
1721 assertion(isSpacetreeNodeLocal(coarseGridVertices, false, false));
1722 updateVertexRanksWithinCell(fineGridVertices, targetSpacetreeId);
1723 }
1724}
1725
1727 GridVertex coarseGridVertices[TwoPowerD], GridVertex fineGridVertices[TwoPowerD]
1728) {
1729 [[maybe_unused]] constexpr int NoSplit = -1;
1730
1731 if (not _splitTriggered.empty() and _splitTriggered.begin()->second.mode == peano4::SplitInstruction::Mode::AggressiveTopDown) {
1732 const bool isParentSplit = not _splittedCells.empty();
1733 const int targetSpacetreeId = getSplittingTree();
1734 const bool isSplitCandidate = targetSpacetreeId >= 0 and isCellSplitCandidate(coarseGridVertices, fineGridVertices);
1735 const bool isRefined = isSpacetreeNodeRefined(fineGridVertices);
1736
1737 if (isParentSplit and isRefined) {
1738 assertion(isSpacetreeNodeLocal(fineGridVertices, false, false));
1739 assertion(isSpacetreeNodeLocal(coarseGridVertices, false, false));
1740 int parentId = _splittedCells.back();
1741 _splittedCells.push_back(parentId);
1742 } else if (isParentSplit and not isRefined) {
1743 assertion(isSpacetreeNodeLocal(fineGridVertices, false, false));
1744 assertion(isSpacetreeNodeLocal(coarseGridVertices, false, false));
1745 updateSplittingCounter(targetSpacetreeId);
1746 int parentId = _splittedCells.back();
1747 _splittedCells.push_back(parentId);
1748 } else if (not isParentSplit and isSplitCandidate and isRefined) {
1749 assertion(isSpacetreeNodeLocal(fineGridVertices, false, false));
1750 assertion(isSpacetreeNodeLocal(coarseGridVertices, false, false));
1751 logDebug(
1752 "splitCellTopDown(...)",
1753 "refined cell at "
1754 << fineGridVertices[0].toString() << " should go with all children to tree " << targetSpacetreeId
1755 );
1756 _splittedCells.push_back(targetSpacetreeId);
1757 } else if (not isParentSplit and isSplitCandidate and not isRefined) {
1758 updateSplittingCounter(targetSpacetreeId);
1759 assertion(isSpacetreeNodeLocal(fineGridVertices, false, false));
1760 assertion(isSpacetreeNodeLocal(coarseGridVertices, false, false));
1761 _splittedCells.push_back(targetSpacetreeId);
1762 }
1763 logDebug("splitOrJoinCellBottomUp(...)", "#splitted-cells=" << _splittedCells.size());
1764 }
1765}
1766
1768 GridVertex coarseGridVertices[TwoPowerD], GridVertex fineGridVertices[TwoPowerD]
1769) {
1770 for (auto worker : _joining) {
1771 if (isSpacetreeNodeLocal(coarseGridVertices, false, false) and _gridTraversalEventGenerator.getTreeOwningSpacetreeNode(fineGridVertices, _splitTriggered, _splitting, _joinTriggered, _joining) == worker) {
1772 logDebug(
1773 "mergeCellFromWorkerWithMasterThroughoutJoin(...)",
1774 "cell from worker " << worker << " is merged into master " << _id
1775 );
1776 updateVertexRanksWithinCell(fineGridVertices, _id);
1777 } else {
1778 for (int i = 0; i < TwoPowerD; i++) {
1779 logDebug("mergeCellFromWorkerWithMasterThroughoutJoin(...)", "- " << coarseGridVertices[i].toString());
1780 }
1781 for (int i = 0; i < TwoPowerD; i++) {
1782 logDebug("mergeCellFromWorkerWithMasterThroughoutJoin(...)", "- " << fineGridVertices[i].toString());
1783 }
1784 }
1785 }
1786}
1787
1789 for (auto& p : _splitTriggered) {
1790 if (p.first == treeId) {
1791 p.second.numberOfFineGridCells = std::max(p.second.numberOfFineGridCells - 1, 0);
1792 break;
1793 }
1794 }
1795}
1796
1798 for (auto& p : _splitTriggered) {
1799 if (p.second.numberOfFineGridCells > 0) {
1800 return p.first;
1801 }
1802 }
1803 return -1;
1804}
1805
1807
1809 GridVertex coarseGridVertices[TwoPowerD], GridVertex fineGridVertices[TwoPowerD]
1810) const {
1811 dfor2(k) assertion1(
1812 coarseGridVertices[kScalar].getState() != GridVertex::State::HangingVertex, coarseGridVertices[kScalar].toString()
1813 );
1814 coarseGridVertices[kScalar].setIsAntecessorOfRefinedVertexInCurrentTreeSweep(true);
1815 coarseGridVertices[kScalar].setIsParentOfSubtreeVertexInCurrentTreeSweep(true);
1816 fineGridVertices[kScalar].setIsParentOfSubtreeVertexInCurrentTreeSweep(true);
1817 enddforx
1818}
1819
1820void peano4::grid::Spacetree::split(int newSpacetreeId, const SplitInstruction& instruction) {
1821 assertion3(
1822 instruction.numberOfFineGridCells == std::numeric_limits<int>::max() or maySplit(),
1823 newSpacetreeId,
1824 instruction,
1825 toString()
1826 );
1827 assertion3(
1828 instruction.numberOfFineGridCells != std::numeric_limits<int>::max(), newSpacetreeId, instruction, toString()
1829 );
1830 assertion3(instruction.numberOfFineGridCells >= 1, newSpacetreeId, instruction, toString());
1831
1832 _splitTriggered.insert(std::pair<int, SplitInstruction>(newSpacetreeId, instruction));
1833
1834 auto firstMode = _splitTriggered.begin()->second.mode;
1835 for (auto& p : _splitTriggered) {
1836 if (p.second.mode != firstMode) {
1837 logWarning(
1838 "split(...)",
1839 "split of tree "
1840 << p.first << " is of type " << p.second.mode << " while other splits have mode " << firstMode
1841 << ". Switch all splits to " << firstMode
1842 );
1843 p.second.mode = firstMode;
1844 }
1845 }
1846}
1847
1849 std::ostringstream msg;
1850 msg << "(id=" << _id << ",master=" << _masterId << ",state=" << peano4::grid::toString(_spacetreeState)
1851 << ",statistics=" << _statistics.toString();
1852 if (_joinTriggered.empty()) {
1853 msg << ",no-join-triggered-with-any-tree";
1854 } else {
1855 msg << ",join-triggered={";
1856 for (const auto& p : _joinTriggered) {
1857 msg << "(" << p << ")";
1858 }
1859 msg << "}";
1860 }
1861 if (_joining.empty()) {
1862 msg << ",not-joining";
1863 } else {
1864 msg << ",joining={";
1865 for (const auto& p : _joining) {
1866 msg << "(" << p << ")";
1867 }
1868 msg << "}";
1869 }
1870 /*
1871 if (_hasJoined.empty()) {
1872 msg << ",noone-has-joined-recently";
1873 }
1874 else {
1875 msg << ",has-joined-recently={";
1876 for (const auto& p: _hasJoined) {
1877 msg << "(" << p << ")";
1878 }
1879 msg << "}";
1880 }
1881 */
1882 if (_splitTriggered.empty()) {
1883 msg << ",no-split-triggered";
1884 } else {
1885 msg << ",split-triggered={";
1886 for (const auto& p : _splitTriggered) {
1887 msg << "(" << p.first << "," << p.second << ")";
1888 }
1889 msg << "}";
1890 }
1891 if (_splitting.empty()) {
1892 msg << ",not-splitting";
1893 } else {
1894 msg << ",splitting={";
1895 for (const auto& p : _splitting) {
1896 msg << "(" << p << ")";
1897 }
1898 msg << "}";
1899 }
1900 msg << ",stacks:" << _vertexStack.toString() << ")";
1901 return msg.str();
1902}
1903
1905 return _spacetreeState == SpacetreeState::Running and _joinTriggered.empty() and _joining.empty()
1906 and _splitting.empty() and _statistics.getNumberOfLocalUnrefinedCells() > 0
1907 and (_splitTriggered.empty() or _splitTriggered.begin()->second.numberOfFineGridCells < std::numeric_limits<int>::max());
1908}
1909
1911 return _spacetreeState == SpacetreeState::Running and _splitTriggered.empty() and _joining.empty()
1912 and _splitting.empty() and _joinTriggered.empty();
1913}
1914
1916 return _spacetreeState == SpacetreeState::Running and _masterId >= 0
1917 and _statistics.getStationarySweeps() > NumberOfStationarySweepsToWaitAtLeastTillJoin
1918 and _splitTriggered.empty() and _splitting.empty() and _joinTriggered.empty() and _joining.empty()
1919 and _statistics.getNumberOfLocalRefinedCells() == 0;
1920}
1921
1923 assertion1(mayJoinWithMaster(), _id);
1924 _spacetreeState = SpacetreeState::JoinTriggered;
1925 assertion(_splitTriggered.empty());
1926 assertion(_splitting.empty());
1927 assertion(_splittedCells.empty());
1928 assertion(_joining.empty());
1929}
1930
1932 logInfo("joinWithWorker(int)", "merge tree " << id << " into tree " << _id);
1933 assertion2(_joinTriggered.count(id) == 0, id, _id);
1934 _joinTriggered.insert(id);
1935 assertion2(_splitTriggered.empty(), id, toString());
1936 assertion2(_splitting.empty(), id, toString());
1937}
1938
1940 return not _joinTriggered.empty() or not _joining.empty() or not _splitTriggered.empty() or not _splitting.empty();
1941}
#define assertion2(expr, param0, param1)
#define assertion4(expr, param0, param1, param2, param3)
#define assertionVectorNumericalEquals3(lhs, rhs, param0, param1, param2)
#define assertionNumericalEquals5(lhs, rhs, a, b, c, d, e)
#define assertion3(expr, param0, param1, param2)
#define assertion1(expr, param)
#define assertionMsg(expr, message)
#define assertion(expr)
#define assertionEquals5(lhs, rhs, larg, rarg, three, four, five)
#define assertionEquals4(lhs, rhs, larg, rarg, three, four)
#define assertion6(expr, param0, param1, param2, param3, param4, param5)
#define TwoTimesD
Definition Globals.h:30
#define ThreePowerD
Definition Globals.h:24
#define TwoPowerD
Definition Globals.h:19
#define DimensionsTimesTwo
Definition Globals.h:17
AutomatonState state
#define logDebug(methodName, logMacroMessageStream)
Definition Log.h:50
#define logTraceOutWith1Argument(methodName, argument0)
Definition Log.h:380
#define logTraceOut(methodName)
Definition Log.h:379
#define logWarning(methodName, logMacroMessageStream)
Wrapper macro around tarch::tarch::logging::Log to improve logging.
Definition Log.h:440
#define logTraceOutWith3Arguments(methodName, argument0, argument1, argument2)
Definition Log.h:382
#define logTraceInWith3Arguments(methodName, argument0, argument1, argument2)
Definition Log.h:372
#define logTraceOutWith2Arguments(methodName, argument0, argument1)
Definition Log.h:381
#define logTraceIn(methodName)
Definition Log.h:369
#define logTraceInWith1Argument(methodName, argument0)
Definition Log.h:370
#define logTraceInWith2Arguments(methodName, argument0, argument1)
Definition Log.h:371
#define logInfo(methodName, logMacroMessageStream)
Wrapper macro around tarch::tarch::logging::Log to improve logging.
Definition Log.h:411
#define endzfor
Definition Loop.h:1049
#define dfor2(counter)
Shortcut For dfor(counter,2)
Definition Loop.h:911
#define dfor3(counter)
Shortcut For dfor(counter,3)
Definition Loop.h:647
#define zfor3(counter, direction)
Definition Loop.h:1044
#define enddforx
I prefer to use this macro for dforx instead of a closing bracket as many syntax parser fail otherwis...
Definition Loop.h:933
std::bitset< Dimensions > periodicBC
Definition main.cpp:19
static int getVertexWriteStackNumber(const AutomatonState &state, const std::bitset< Dimensions > &vertex)
static void invertEvenFlag(AutomatonState &cell, int axis)
static bool isInOutStack(int number)
static int getVertexReadStackNumber(const AutomatonState &state, const std::bitset< Dimensions > &vertex)
static peano4::utils::LoopDirection getLoopDirection(const AutomatonState &state)
Holds a set bit for each dimension along which the traversal is positive.
static void setEntryFace(AutomatonState &cell, int axis)
static bool isTraversePositiveAlongAxis(const AutomatonState &state, int axis)
Definition PeanoCurve.cpp:9
static std::bitset< Dimensions > getFirstVertexIndex(const AutomatonState &cell)
Looks into a cell of the spacetree and gives the index of the first local vertex.
static void setExitFace(AutomatonState &cell, int axis)
static bool restrictToCoarseGrid(const tarch::la::Vector< Dimensions, int > &coarseVertexPosition, const tarch::la::Vector< Dimensions, int > &fineVertexPosition)
Determines whether to restrict a vertex to the coarser level or not.
void split(int treeId, const SplitInstruction &instruction)
Add a split instruction.
static tarch::logging::Log _log
Definition Spacetree.h:58
void mergeGridVertexAdjacencyListsAtHorizontalDomainBoundary(GridVertex &vertex, const GridVertex &inVertex, int neighbour)
void storeVertices(const AutomatonState &fineGridState, GridVertex coarseGridVertices[TwoPowerD], GridVertex fineGridVertices[TwoPowerD], const tarch::la::Vector< Dimensions, int > &cellPositionWithin3x3Patch, TraversalObserver &observer)
GridStatistics getGridStatistics() const
void sendUserData(const AutomatonState &state, TraversalObserver &observer, const GridTraversalEvent &enterCellTraversalEvent, GridVertex fineGridVertices[TwoPowerD])
Send user data.
bool isInvolvedInJoinOrFork() const
void updateVertexAfterLoad(GridVertex &vertex, GridVertex fineGridVertices[TwoPowerD], const tarch::la::Vector< Dimensions, int > &fineVertexPositionWithinPatch, TraversalObserver &observer)
This operation has multiple purposes.
static GridVertexStackMap _vertexStack
Definition Spacetree.h:152
static void refineState(const AutomatonState &coarseGrid, AutomatonState fineGrid[ThreePowerD], tarch::la::Vector< Dimensions, int > fineGridPosition=tarch::la::Vector< Dimensions, int >(0), int axis=Dimensions-1)
Takes a state (describing a node in the tree) and returns the states on the next finer level along t...
void markVerticesAroundForkedCell(GridVertex coarseGridVertices[TwoPowerD], GridVertex fineGridVertices[TwoPowerD]) const
setIsAntecessorOfRefinedVertexInCurrentTreeSweep()
bool areAllVerticesRefined(GridVertex vertices[TwoPowerD]) const
void loadVertices(const AutomatonState &fineGridState, GridVertex coarseGridVertices[TwoPowerD], GridVertex fineGridVertices[TwoPowerD], const tarch::la::Vector< Dimensions, int > &cellPositionWithin3x3Patch, TraversalObserver &observer)
Load the vertices of one cell.
bool mayJoinWithMaster() const
Only ranks that have no kids are allowed to join.
std::string toString() const
void joinWithWorker(int id)
GridStatistics _statistics
Definition Spacetree.h:99
static void incrementNumberOfAdjacentRefinedLocalCells(GridVertex vertices[TwoPowerD])
Every local refined cell should call this routine.
void receiveAndMergeUserData(const AutomatonState &state, TraversalObserver &observer, const GridTraversalEvent &enterCellTraversalEvent, GridVertex fineGridVertices[TwoPowerD])
bool areAllVerticesUnrefined(GridVertex vertices[TwoPowerD]) const
bool isFaceAlongPeriodicBoundaryCondition(GridVertex vertex[TwoPowerD], int faceNumber, bool calledByReceivingProcess) const
void descend(const AutomatonState &state, GridVertex vertices[TwoPowerD], TraversalObserver &observer)
bool isSpacetreeNodeLocal(GridVertex vertices[TwoPowerD], bool splittingIsConsideredLocal, bool joiningIsConsideredLocal) const
Wrapper around GridTraversalEventGenerator::isSpacetreeNodeLocal()
const std::bitset< Dimensions > _periodicBC
Indicate per axis whether we have periodic boundary conditions.
Definition Spacetree.h:115
Spacetree(int newId, int masterId, const tarch::la::Vector< Dimensions, double > &offset, const tarch::la::Vector< Dimensions, double > &width, bool traversalInverted)
Only used by SpacetreeSet to create children of the original tree.
Definition Spacetree.cpp:48
static tarch::la::Vector< Dimensions, int > convertToIntegerVector(const std::bitset< Dimensions > &in)
Little helper.
std::set< int > getNeighbourTrees(const GridVertex &vertex, bool calledByReceivingProcess) const
Get the ids of the surrounding cells of a vertex.
void splitOrJoinCellBottomUp(GridVertex vertex[TwoPowerD], GridVertex fineGridVertices[TwoPowerD])
Realise the splits and joins.
void joinWithMaster()
Join with master.
static constexpr int NumberOfStationarySweepsToWaitAtLeastTillJoin
Definition Spacetree.h:55
void sendGridVertex(const GridVertex &vertex)
This one is to be invoked if and only if a vertex goes to the in/out stacks.
AutomatonState _root
The root of a spacetree corresponds to the initial state of the tree traversal automaton.
Definition Spacetree.h:97
void evaluateGridControlEvents(const AutomatonState &fineGridState, GridVertex coarseGridVertices[TwoPowerD], GridVertex fineGridVertices[TwoPowerD])
Should only be called for inner cells.
bool isVertexAdjacentToLocalSpacetree(GridVertex vertex, bool splittingIsConsideredLocal, bool joiningIsConsideredLocal) const
Returns if a vertex is local to adjacent tree.
Definition Spacetree.cpp:82
static void updateVertexRanksWithinCell(GridVertex fineGridVertices[TwoPowerD], int newId)
If a cell gets a new id, we have to update its vertices.
void mergeGridVertexRefinementStateAtHorizontalDomainBoundary(GridVertex &vertex, const GridVertex &inVertex, int neighbour)
Called by receiveAndMergeGridVertexAtHorizontalBoundary().
void updateVertexBeforeStore(GridVertex &vertex, GridVertex fineGridVertices[TwoPowerD], const tarch::la::Vector< Dimensions, int > &fineVertexPositionWithinPatch)
bool maySplit() const
Is the tree in principle allowed to split.
bool doesRankIndexIdentifyHorizontalDataExchange(int rank, bool calledByReceivingProcess) const
You may exchange data horizontally with rank if and only if.
void traverse(TraversalObserver &observer, bool calledFromSpacetreeSet=false)
bool mayJoinWithWorker() const
We allow at most one join at a time and not while we split.
void receiveAndMergeGridVertexAtVerticalBoundary(GridVertex &vertex)
This is a merge routine for vertical data exchange.
void receiveAndMergeGridVertexAtHorizontalBoundary(GridVertex &vertex)
Manage the data exchange after a vertex is loaded for the first time.
bool shouldEraseAdjacencyInformation(const GridVertex &vertex, GridVertex coarseGridVertices[TwoPowerD], tarch::la::Vector< Dimensions, int > fineVertexPositionWithinPatch) const
void updateSplittingCounter(int treeId)
Reduce splitting counter.
void mergeCellFromWorkerWithMasterThroughoutJoin(GridVertex vertex[TwoPowerD], GridVertex fineGridVertices[TwoPowerD])
Merge data from worker with master data throughout join.
void splitCellTopDown(GridVertex vertex[TwoPowerD], GridVertex fineGridVertices[TwoPowerD])
Split cell in a top down fashion.
tarch::la::Vector< TwoPowerD, int > getAdjacentRanksForNewVertex(GridVertex coarseGridVertices[TwoPowerD], const tarch::la::Vector< Dimensions, int > &vertexPositionWithin3x3Patch) const
bool areAllVerticesNonHanging(GridVertex vertices[TwoPowerD]) const
Could also be called areAllVerticesPersistent() in the Peano terminology.
Definition Spacetree.cpp:97
bool isCellSplitCandidate(GridVertex coarseGridVertices[TwoPowerD], GridVertex fineGridVertices[TwoPowerD]) const
Can a cell be split (deployed to another rank)
virtual void receiveAndMergeVertex(int, int, SendReceiveContext, const GridTraversalEvent &)
static constexpr int CreateOrDestroyHangingGridEntity
Implies that the data will then be local or had been local.
static constexpr int CreateOrDestroyPersistentGridEntity
Implies that the data will then be local or had been local.
virtual void loadCell(const GridTraversalEvent &event)=0
virtual void storeCell(const GridTraversalEvent &event)=0
virtual void beginTraversal(const tarch::la::Vector< Dimensions, double > &x, const tarch::la::Vector< Dimensions, double > &h)=0
Begin the traversal.
virtual void endTraversal(const tarch::la::Vector< Dimensions, double > &x, const tarch::la::Vector< Dimensions, double > &h)=0
static constexpr int NoData
Can this grid entity hold data.
virtual std::vector< GridControlEvent > getGridControlEvents() const =0
virtual void leaveCell(const GridTraversalEvent &event)=0
virtual void enterCell(const GridTraversalEvent &event)=0
Event is invoked per cell.
virtual void receiveAndMergeFace(int, int, SendReceiveContext, const GridTraversalEvent &)
static int getOutputStackForPeriodicBoundaryExchange(int faceNumber)
Identify output stack for periodic boundary data written by face.
Definition Node.cpp:250
static int getOutputStackNumberForHorizontalDataExchange(int id)
Hand in a spacetree id and get back the number that we should use to send something to this tree.
Definition Node.cpp:211
static int getInputStackNumberForHorizontalDataExchange(int id)
Counterpart of getOutputStackNumberOfBoundaryExchange(int)
Definition Node.cpp:216
std::pair< int, int > PeriodicBoundaryStackIdentifier
A periodic boundary stack is basically a stack (an integer), but I do augment it by a bitset which id...
Definition Node.h:216
static int getOutputStackNumberForVerticalDataExchange(int id)
Definition Node.cpp:221
static std::set< PeriodicBoundaryStackIdentifier > getOutputStacksForPeriodicBoundaryExchange(const tarch::la::Vector< TwoPowerD, int > &flags)
You hand in a the flags of a vertex and you get the boundary stack identifiers including their direct...
Definition Node.cpp:282
static int getPeriodicBoundaryExchangeInputStackNumberForOutputStack(int outputStackNumber)
Hand in an output stack number of a face and you get back the input stack number.
Definition Node.cpp:355
static int getInputStackNumberForVerticalDataExchange(int id)
Get the input stack where a tree writes all of its vertical data to/from when it exchanges informatio...
Definition Node.cpp:226
static Node & getInstance()
This operation returns the singleton instance.
Definition Node.cpp:108
Log Device.
Definition Log.h:516
void log(const std::string &identifier, double value, bool disableSampling=false)
Definition Statistics.h:105
static Statistics & getInstance()
This is not the canonical realisation of singletons as I use it usually for stats in Peano.
bool isSpacetreeNodeRefined(GridVertex vertices[TwoPowerD])
A spacetree node is refined if any of its adjacent vertices holds one of the following flags:
Definition grid.cpp:241
std::string toString(VertexType type)
Definition grid.cpp:276
bool isSpacetreeNodeLocal(GridVertex vertices[TwoPowerD], bool splittingIsConsideredLocal, bool joiningIsConsideredLocal, int id)
A spacetree node as 2^d adjacent vertices.
void clear(GridStatistics &statistics, bool isGlobalMasterTree)
The term clear() is not 100% correct, as the number of stationary traversals is not reset to a dummy ...
Definition grid.cpp:230
GridVertex createVertex(GridVertex::State state, const tarch::la::Vector< Dimensions, double > &x, int level, const tarch::la::Vector< TwoPowerD, int > &adjacentRanks, bool isNewFineGridVertex)
Factory mechanism.
Definition grid.cpp:61
@ NewFromSplit
Set if this tree results from a split and if this is the first grid sweep when the former owner actua...
@ JoinTriggered
Join has been triggered for this tree.
@ EmptyRun
Not yet a new root.
bool overlaps(const tarch::la::Vector< Dimensions, double > &x, const GridControlEvent &event)
Definition grid.cpp:56
constexpr int InvalidRank(-1)
std::vector< GridControlEvent > merge(std::vector< GridControlEvent > events, const double Tolerance=0.1)
Merge set of refinement/coarsening commands.
Definition grid.cpp:112
bool isContained(const AutomatonState &x, const GridControlEvent &event, double upscaleAutomatonState=1.0)
isContained() is defined over the closed interval, i.e.
Definition grid.cpp:40
std::bitset< Dimensions > LoopDirection
Is used by the z-loop.
Definition Loop.h:70
CPUGPUMethod int dLinearised(const tarch::la::Vector< Dimensions, int > &counter, int max)
Map d-dimensional vector onto integer index.
Definition Loop.cpp:106
bool allGreaterEquals(const Vector< Size, Scalar > &lhs, const Scalar &cmp, const Scalar tolerance=NUMERICAL_ZERO_DIFFERENCE)
int countEqualEntries(const Vector< Size, int > &lhs, const Vector< Size, int > &rhs)
Run through both vectors and count how many entries are the same.
bool allSmaller(const Vector< Size, Scalar > &lhs, const Scalar &cmp, const Scalar tolerance=NUMERICAL_ZERO_DIFFERENCE)
bool equals(const Matrix< Rows, Cols, Scalar > &lhs, const Matrix< Rows, Cols, Scalar > &rhs, const Scalar &tolerance=NUMERICAL_ZERO_DIFFERENCE)
Compares to matrices on equality by means of a numerical accuracy.
Matrix< Rows, Cols, Scalar > multiplyComponents(const Matrix< Rows, X, Scalar > &lhs, const Matrix< X, Cols, Scalar > &rhs)
bool contains(const Vector< Size, Scalar > &vector, const Scalar &value)
Scalar min(const Vector< Size, Scalar > &vector)
Returns the element with minimal value (NOT absolute value).
Instruction to split.
Definition grid.h:34
Provide information about selected face.
Definition FaceMarker.h:35
tarch::la::Vector< Dimensions, double > getX() const
void setAccessNumber(const tarch::la::Vector< DimensionsTimesTwo, int > &value)
tarch::la::Vector< Dimensions, double > getH() const
void setH(const tarch::la::Vector< Dimensions, double > &value)
void setEvenFlags(const std::bitset< Dimensions > &value)
void setX(const tarch::la::Vector< Dimensions, double > &value)
std::bitset< TwoTimesD > getIsFaceLocal() const
tarch::la::Vector< TwoTimesD, int > getFaceDataFrom() const
tarch::la::Vector< TwoPowerD, int > getVertexDataFrom() const
tarch::la::Vector< TwoTimesD, int > getFaceDataTo() const
tarch::la::Vector< TwoPowerD, int > getVertexDataTo() const
std::bitset< TwoPowerD > getIsVertexLocal() const
bool getIsParentOfSubtreeVertexInCurrentTreeSweep() const
tarch::la::Vector< TwoPowerD, int > getAdjacentRanks() const
int getNumberOfAdjacentRefinedLocalCells() const
void setBackupOfAdjacentRanks(const tarch::la::Vector< TwoPowerD, int > &value)
tarch::la::Vector< TwoPowerD, int > getBackupOfAdjacentRanks() const
std::string toString() const
bool getIsAntecessorOfRefinedVertexInCurrentTreeSweep() const
void setHasBeenParentOfSubtreeVertexInPreviousTreeSweep(bool value)
void setState(State value)
void setAdjacentRanks(const tarch::la::Vector< TwoPowerD, int > &value)
peano4::grid::GridVertex::State getState() const
Simple vector class.
Definition Vector.h:134