3d connectivity balancing issue

[SAutum]

Description
As I created an 3D example in #237 , errors occurred during balancing. The example contains face, edge (2x) and corner (1x) connections.

Two types of errors occur using different maximum refinement level.
Case 1 - line 1042:

[libsc 0] Abort: Unreachable code
[libsc 0] Abort: ../p4est-1/src/p4est_algorithms.c:1042
[libsc 0] Abort: Obtained 10 stack frames

Case 2 - line 1062:

[libsc 0] Abort: Assertion 'p4est_quadrant_is_ancestor (tq, s) || (p4est_quadrant_is_equal (tq, s) && tq->level == P4EST_QMAXLEVEL)'
[libsc 0] Abort: ../p4est-1/src/p4est_algorithms.c:1062
[libsc 0] Abort: Obtained 10 stack frames

To Reproduce
The parameters below have been tested.

• no mpi, max_level = 2
  Case 1 - line 1042

• no mpi, max_level = 3, 4, 5
  Case 2 - line 1062

• with mpi, no_of_process = 1, max_level = 2
  Case 1 - line 1042

• with mpi, no_of_process = 1, max_level = 3, 4, 5
  Case 2 - line 1062

• with mpi, no_of_process = 2, 3, max_level = 2, 3, 4, 5
  Case 2 - line 1062

Errors persist with P8EST_CONNECT_FULL/FACE/EDGE.

[cburstedde]

Thanks for the report!

[cburstedde]

It will make sense to integrate #101 on the way to resolving this issue.

[tim-griesbach]

@hannesbrandt and I checked the issue and we think that the reason for the reported assertion failure is connected to p4est_comm_neighborhood_owned. The assertion in p4est_tree_compute_overlap fails because the binary search does not find a result due to missing quadrants in the borders array determined in p4est_balance and passed to p4est_balance_response. In p4est_tree_compute_overlap it is assumed that the tree first and last descendants can be used to check for overlap with borders.

The borders array is determined in p4est_balance in particular using p4est_comm_neighborhood_owned. Here, the problem is that some quadrants of the tree boundary are skipped, which violates the assumption in p4est_tree_compute_overlap. The decision for skipping is made by calling p4est_comm_neighborhood_owned.

Currently, in processor-local trees p4est_comm_neighborhood_owned causes skipping of all tree boundary quadrants that do not have a face neighbor across a tree boundary . Therefore, we implemented a minimal-invasive solution (https://github.com/tim-griesbach/p4est/tree/fix-balance) by introducing and using the new function p4est_comm_neighborhood_boundary_owned that does not cause skipping of any tree boundary quadrants.
This solution means that the borders array contains more quadrants than necessary for searching but satisfies the assumption in p4est_tree_compute_overlap and now in particular contains all quadrants based on edge and corner neighboring trees that are necessary for a correct balance result.

We tested our solution approach serial and parallel for the cases described by @SAutum. Moreover, we tested the balance issue described in #112. As expected this is not solved by our solution since the mentioned issue relates to missing information in the connectivity and our solution neither adds the required connectivity information nor reduces the required connectivity information in balance. However, there is still the suggestion in #136 that fixes this issue.

After we found our solution we also tested the branch referenced in the issue #101 that adds quadrants to the borders array based on any tree boundary connection types and not just on the face connections across tree boundaries. This also resolves the issue reported by @SAutum but it may not always satisfy the first/last descendant assumption in p4est_tree_compute_overlap.

[cburstedde]

Thanks for the investigation and the report!

One thing I'd like to maintain/reestablish is that BALANCE_FACE and BALANCE_EDGE work consistenly and require minimal specific information, always. This means e. g. not to store temporary corner neighbors for face/edge balance. In this sense, would it be possible to extend your fix to be sensitive to the connect_type?

(Edited: the connectivity must always connect by all codimensions.)

[tim-griesbach]

This also resolves the issue reported by @SAutum but it may not always satisfy the first/last descendant assumption in p4est_tree_compute_overlap.

After testing this again, we have seen that the changes in test-neighborhood-owned only yield correct results for full balance since only comm_neighborhood_owned is adjusted to handle different connection types but in the rest of the code it seems to be assumed that balance is only used for full connections.

One thing I'd like to maintain/reestablish is that BALANCE_FACE and BALANCE_EDGE work consistenly and require minimal specific information, always. This means e. g. not to store temporary corner neighbors for face/edge balance. In this sense, would it be possible to extend your fix to be sensitive to the connect_type?

@hannesbrandt and I think that balance always uses the full insulation layer. That is why the reported assertion failure occurs even for face balance. Because of the connection-type-agnostic insulation layer, it is not possible to only adjust comm_neighborhood_owned to all connection types without modifying the general usage and creation of the insulation layer.

I'm also curious about #112. The top picture reported violates face balance, which should not happen even if corner information is missing. What would be a good way to tighten the requirements/assumptions related to the required codimension?

Tightening the requirements in balance seems to be at least also related to the insulation layer not respecting the given balance connection type.

[cburstedde]

I think your original analysis is very much to the point, while my comment above should be considered outdated.
In particular, building the full insulation layer is reasonable even for face- and/or edge-only balance.

We have established in #112 that the edge and corner connectivity shall be complete for consistent balance, yet completeness must not be required by assertions or algorithms. In other words, the code should never crash on valid but incomplete connectivities.

Let us meet and find the best compromise to go ahead, making balance work for edge- and corner-neighbors when face neighbor trees are missing entirely.