From 6b631c5ad0a9b2d665ce61e425b15f18c19822b8 Mon Sep 17 00:00:00 2001 From: Peter Munch Date: Wed, 27 Nov 2019 12:19:08 +0100 Subject: [PATCH] Relax assumpitions in GridTools::partition_triangulation_zorder --- include/deal.II/grid/grid_tools.h | 18 +++-- source/grid/grid_tools.cc | 66 +++++++++-------- source/grid/grid_tools.inst.in | 3 +- .../grid/partition_triangulation_zorder_01.cc | 73 +++++++++++++++++++ .../partition_triangulation_zorder_01.output | 5 ++ 5 files changed, 127 insertions(+), 38 deletions(-) create mode 100644 tests/grid/partition_triangulation_zorder_01.cc create mode 100644 tests/grid/partition_triangulation_zorder_01.output diff --git a/include/deal.II/grid/grid_tools.h b/include/deal.II/grid/grid_tools.h index 6d5b276837..d46660c284 100644 --- a/include/deal.II/grid/grid_tools.h +++ b/include/deal.II/grid/grid_tools.h @@ -2006,15 +2006,23 @@ namespace GridTools /** * Generates a partitioning of the active cells making up the entire domain - * using the same partitioning scheme as in the p4est library. After calling - * this function, the subdomain ids of all active cells will have values - * between zero and @p n_partitions-1. You can access the subdomain id of a - * cell by using cell-@>subdomain_id(). + * using the same partitioning scheme as in the p4est library if the flag + * @p group_siblings is set to true (default behavior of this function). + * After calling this function, the subdomain ids of all active cells will + * have values between zero and @p n_partitions-1. You can access the + * subdomain id of a cell by using cell-@>subdomain_id(). + * + * @note If the flag @p group_siblings is set to false, children of a + * cell might be placed on different processors even though they are all + * active, which is an assumption made by p4est. By relaxing this, we + * can can create partitions owning a single cell (also for refined + * meshes). */ template void partition_triangulation_zorder(const unsigned int n_partitions, - Triangulation &triangulation); + Triangulation &triangulation, + const bool group_siblings = true); /** * Partitions the cells of a multigrid hierarchy by assigning level subdomain diff --git a/source/grid/grid_tools.cc b/source/grid/grid_tools.cc index a328fcfe64..607772013f 100644 --- a/source/grid/grid_tools.cc +++ b/source/grid/grid_tools.cc @@ -3037,7 +3037,8 @@ namespace GridTools template void partition_triangulation_zorder(const unsigned int n_partitions, - Triangulation &triangulation) + Triangulation &triangulation, + const bool group_siblings) { Assert((dynamic_cast *>( &triangulation) == nullptr), @@ -3100,40 +3101,41 @@ namespace GridTools // the processor with the largest number of children // (ties are broken by picking the lower rank). // Duplicate this logic here. - { - typename Triangulation::cell_iterator - cell = triangulation.begin(), - endc = triangulation.end(); - for (; cell != endc; ++cell) - { - if (cell->active()) - continue; - bool all_children_active = true; - std::map map_cpu_n_cells; - for (unsigned int n = 0; n < cell->n_children(); ++n) - if (!cell->child(n)->active()) - { - all_children_active = false; - break; - } - else - ++map_cpu_n_cells[cell->child(n)->subdomain_id()]; + if (group_siblings) + { + typename Triangulation::cell_iterator + cell = triangulation.begin(), + endc = triangulation.end(); + for (; cell != endc; ++cell) + { + if (cell->active()) + continue; + bool all_children_active = true; + std::map map_cpu_n_cells; + for (unsigned int n = 0; n < cell->n_children(); ++n) + if (!cell->child(n)->active()) + { + all_children_active = false; + break; + } + else + ++map_cpu_n_cells[cell->child(n)->subdomain_id()]; - if (!all_children_active) - continue; + if (!all_children_active) + continue; - unsigned int new_owner = cell->child(0)->subdomain_id(); - for (std::map::iterator it = - map_cpu_n_cells.begin(); - it != map_cpu_n_cells.end(); - ++it) - if (it->second > map_cpu_n_cells[new_owner]) - new_owner = it->first; + unsigned int new_owner = cell->child(0)->subdomain_id(); + for (std::map::iterator it = + map_cpu_n_cells.begin(); + it != map_cpu_n_cells.end(); + ++it) + if (it->second > map_cpu_n_cells[new_owner]) + new_owner = it->first; - for (unsigned int n = 0; n < cell->n_children(); ++n) - cell->child(n)->set_subdomain_id(new_owner); - } - } + for (unsigned int n = 0; n < cell->n_children(); ++n) + cell->child(n)->set_subdomain_id(new_owner); + } + } } diff --git a/source/grid/grid_tools.inst.in b/source/grid/grid_tools.inst.in index 78ff47ec8b..ff06ead6ba 100644 --- a/source/grid/grid_tools.inst.in +++ b/source/grid/grid_tools.inst.in @@ -297,7 +297,8 @@ for (deal_II_dimension : DIMENSIONS; deal_II_space_dimension : SPACE_DIMENSIONS) template void partition_triangulation_zorder( const unsigned int, - Triangulation &); + Triangulation &, + const bool); template void partition_multigrid_levels( diff --git a/tests/grid/partition_triangulation_zorder_01.cc b/tests/grid/partition_triangulation_zorder_01.cc new file mode 100644 index 0000000000..1e1b843f0e --- /dev/null +++ b/tests/grid/partition_triangulation_zorder_01.cc @@ -0,0 +1,73 @@ +// --------------------------------------------------------------------- +// +// Copyright (C) 2019 by the deal.II authors +// +// This file is part of the deal.II library. +// +// The deal.II library is free software; you can use it, redistribute +// it, and/or modify it under the terms of the GNU Lesser General +// Public License as published by the Free Software Foundation; either +// version 2.1 of the License, or (at your option) any later version. +// The full text of the license can be found in the file LICENSE.md at +// the top level directory of deal.II. +// +// --------------------------------------------------------------------- + + +// Test GridTools::partition_triangulation_zorder + +#include +#include +#include +#include + +#include "../tests.h" + +using namespace dealii; + +template +void +test(const int n_refinements, const int n_partitions, const bool blocked) +{ + // create serial triangulation + Triangulation tria; + GridGenerator::hyper_cube(tria); + tria.refine_global(n_refinements); + + GridTools::partition_triangulation_zorder(n_partitions, tria, blocked); + + for (const auto &cell : tria.active_cell_iterators()) + deallog << cell->subdomain_id() << " "; + deallog << std::endl; +} + +int +main(int argc, char *argv[]) +{ + initlog(); + + if (true) + { + deallog.push("2d"); + test<2>(1, 4, false); + deallog.pop(); + } + if (true) + { + deallog.push("2d-pdt"); + test<2>(1, 4, true); + deallog.pop(); + } + if (true) + { + deallog.push("3d"); + test<3>(1, 8, false); + deallog.pop(); + } + if (true) + { + deallog.push("3d-pdt"); + test<3>(1, 8, true); + deallog.pop(); + } +} diff --git a/tests/grid/partition_triangulation_zorder_01.output b/tests/grid/partition_triangulation_zorder_01.output new file mode 100644 index 0000000000..50dd0f8216 --- /dev/null +++ b/tests/grid/partition_triangulation_zorder_01.output @@ -0,0 +1,5 @@ + +DEAL:2d::0 1 2 3 +DEAL:2d-pdt::0 0 0 0 +DEAL:3d::0 1 2 3 4 5 6 7 +DEAL:3d-pdt::0 0 0 0 0 0 0 0 -- 2.39.5