Path: blob/main/tutorials/general/t8_step4_partition_balance_ghost.cxx
906 views
/*
This file is part of t8code.
t8code is a C library to manage a collection (a forest) of multiple
connected adaptive space-trees of general element types in parallel.
Copyright (C) 2015 the developers
t8code is free software; you can redistribute it and/or modify
it under the terms of the GNU General Public License as published by
the Free Software Foundation; either version 2 of the License, or
(at your option) any later version.
t8code is distributed in the hope that it will be useful,
but WITHOUT ANY WARRANTY; without even the implied warranty of
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
GNU General Public License for more details.
You should have received a copy of the GNU General Public License
along with t8code; if not, write to the Free Software Foundation, Inc.,
51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
*/
/* See also: https://github.com/DLR-AMR/t8code/wiki/Step-4---Partition,-Balance,-Ghost
*
* This is step4 of the t8code tutorials.
* After generating a coarse mesh (step1), building a uniform forest
* on it (step2) and adapting this forest (step3)
* we will now learn how to control the forest creation in more detail,
* how to partition and balance a forest and how to generate a layer of ghost elements.
*
* Partition: Each forest is distributed among the MPI processes. Partitioning a forest means
* to change this distribution in order to maintain a load balance. After we
* applied partition to a forest the new forest will have equal numbers of elements
* on each process (+- 1).
* In our example we start with a uniform forest from a cmesh. This forest is constructed
* such that each process has the same number of elements.
* We then adapt this forest, thus refining and coarsening its elements. This changes the
* number of elements on each process and will almost always result in a load imbalance.
* You can verify this yourself by printing the process local number on each process for the
* adapted forest (for example with t8_productionf).
* In order to reestablish a load balance, we will construct a new forest from the adapted
* one via the partition feature.
*
* Ghost: Many applications require a layer of ghost elements. Ghost element of a process are
* those elements that are not local to this process but have a (face) neighbor element that is.
* Telling a forest to create a ghost layer will gather all necessary information and give
* us access to the ghost elements.
* t8code does not create a layer of ghost elements by default, thus our initial uniform forest
* and the adapted forest will not have one.
*
* Balance: A forest fulfills the balance property if (and only if) for each element its (face) neighbors
* have refinement level at most +1 or -1 in comparison to the element's level.
* The balance property is often broken after adaptation. The Balance algorithm iterates through
* the mesh and restores the balance property by refining elements if necessary.
* Balance will never coarsen any elements.
* t8code does not balance a forest by default.
* Our initial uniform forest is balanced since every element has the same refinement level l.
* Our adaptation criterion is such that (usually) after one step of adaptation the forest will still be balanced,
* since we have level l+1 elements in the inner sphere, level l elements in the middle and level l+1 elements
* outside. This may not be the case for very small initial refinement levels levels or with different radius thresholds (why don't you try it out?).
* Therefore, in this example we will apply the adaptation two times, resulting in level l+2 elements
* in the inner sphere, level l elements in the middle and level l - 2 element in the outer sphere
* (and probably some, but not many, level l-1 and level l+1 elements in between).
* This forest will be unbalanced and we will then apply the balance routine to it.
* Note that balance changes the local number of elements and thus may also change the load balance
* and hence require repartitioning.
* Balance is usually the most expensive of t8code's mesh manipulation algorithms.
*
* How you can experiment here:
* Partition:
* - Test the program with different numbers of processes and compare the local
* number of elements before and after partitioning.
* - Open the vtu files before and after partitioning and color them by mpirank in order
* to see how the distribution of elements changes.
* Ghost:
* - We actually print the ghost elements in the vtu files and you can look at them.
* Ghost elements have treeid = -1 in the vtu files. To view the ghosts of a single process (say process 1)
* you can set a threshold on mpirank to view only the elements of process 1 and then set a threshold
* on treeid to only view those elements with treeid = -1.
* Balance:
* - View the unbalanced and balanced forest vtu files and compare them.
* You can color the elements by level.
* - Exercise: Apply balance to forest_adapt and not to the twice adapted forest.
* - Set the no_repartition flag of t8_forest_set_balance to true and observe how the
* partition of the resulting forest changes.
* */
#include <t8.h> /* General t8code header, always include this. */
#include <t8_cmesh/t8_cmesh.h> /* cmesh definition and basic interface. */
#include <t8_cmesh/t8_cmesh_examples.h> /* A collection of exemplary cmeshes */
#include <t8_forest/t8_forest_general.h> /* forest definition and basic interface. */
#include <t8_forest/t8_forest_io.h> /* save forest */
#include <t8_schemes/t8_default/t8_default.hxx> /* default refinement scheme. */
#include <tutorials/general/t8_step3.h>
T8_EXTERN_C_BEGIN ();
/* So far we have seen t8_forest_new_* functions to create forests.
* These directly returned a new forest.
* However, t8code offers us more control over the creation of forests.
* For example we can control whether or not a forest should have a ghost layer,
* be balanced/partitioned from another forest, etc.
*
* Usually, there are three steps involved in creating a forest:
* 1. Initialize the forest with t8_forest_init.
* This function will prepare a forest by setting default values for its members and
* initializing necessary structures.
* 2. Set all properties that the forest should have.
* Here we can for example set a cmesh and refinement scheme or specify that the
* forest should be adapted/partitioned/balanced from another forest etc.
* See the t8_forest_set functions in t8_forest.h
* The order in which you call the set functions does not matter.
* 3. Commit the forest with t8_forest_commit.
* In this step the forest is actually created after setting all
* desired properties. The forest cannot be changed after it was committed.
*
* The t8_forest_new functions are just wrappers around this process.
*/
/* In this function we create a new forest that repartitions a given forest
* and has a layer of ghost elements.
*/
static t8_forest_t
t8_step4_partition_ghost (t8_forest_t forest)
{
t8_forest_t new_forest;
/* Check that forest is a committed, that is valid and usable, forest. */
T8_ASSERT (t8_forest_is_committed (forest));
/* Initialize */
t8_forest_init (&new_forest);
/* Tell the new_forest that it should partition the existing forest.
* This will change the distribution of the forest elements among the processes
* in such a way that afterwards each process has the same number of elements
* (+- 1 if the number of elements is not divisible by the number of processes).
*
* The third 0 argument is the flag 'set_for_coarsening'. Setting it non-zero ensures
* that a family of (same-level) siblings will not be split across multiple processes;
* this way, coarsening by one level is never prevented by the partitioning
* (see also the comments on coarsening in t8_step3).
*/
t8_forest_set_partition (new_forest, forest, 0);
/* Tell the new_forest to create a ghost layer.
* This will gather those face neighbor elements of process local element that reside
* on a different process.
*
* We currently support ghost mode T8_GHOST_FACES that creates face neighbor ghost elements
* and will in future also support other modes for edge/vertex neighbor ghost elements.
*/
t8_forest_set_ghost (new_forest, 1, T8_GHOST_FACES);
/* Commit the forest, this step will perform the partitioning and ghost layer creation. */
t8_forest_commit (new_forest);
return new_forest;
}
/* In this function we adapt a forest as in step3 and balance it.
* In our main program the input forest is already adapted and then the resulting twice adapted forest will be balanced.
*/
static t8_forest_t
t8_step4_balance (t8_forest_t forest)
{
t8_forest_t balanced_forest;
/* Adapt the input forest. */
t8_forest_t unbalanced_forest = t8_step3_adapt_forest (forest);
/* Output to vtk. */
t8_forest_write_vtk (unbalanced_forest, "t8_step4_unbalanced_forest");
t8_global_productionf (" [step4] Wrote unbalanced forest to vtu files: %s*\n", "t8_step4_unbalanced_forest");
/* Initialize new forest. */
t8_forest_init (&balanced_forest);
/* Specify that this forest should result from balancing unbalanced_forest.
* The last argument is the flag 'no_repartition'.
* Since balancing will refine elements, the load-balance will be broken afterwards.
* Setting this flag to false (no_repartition = false -> yes repartition) will repartition
* the forest after balance, such that every process has the same number of elements afterwards.
*/
t8_forest_set_balance (balanced_forest, unbalanced_forest, 0);
/* Commit the forest. */
t8_forest_commit (balanced_forest);
return balanced_forest;
}
int
t8_step4_main (int argc, char **argv)
{
int mpiret;
sc_MPI_Comm comm;
t8_cmesh_t cmesh;
t8_forest_t forest;
/* The prefix for our output files. */
const char *prefix_uniform = "t8_step4_uniform_forest";
const char *prefix_adapt = "t8_step4_adapted_forest";
const char *prefix_partition_ghost = "t8_step4_partitioned_ghost_forest";
const char *prefix_balance = "t8_step4_balanced_forest";
/* The uniform refinement level of the forest. */
const int level = 3;
/* Initialize MPI. This has to happen before we initialize sc or t8code. */
mpiret = sc_MPI_Init (&argc, &argv);
/* Error check the MPI return value. */
SC_CHECK_MPI (mpiret);
/* Initialize the sc library, has to happen before we initialize t8code. */
sc_init (sc_MPI_COMM_WORLD, 1, 1, NULL, SC_LP_ESSENTIAL);
/* Initialize t8code with log level SC_LP_PRODUCTION. See sc.h for more info on the log levels. */
t8_init (SC_LP_PRODUCTION);
/* Print a message on the root process. */
t8_global_productionf (" [step4] \n");
t8_global_productionf (" [step4] Hello, this is the step4 example of t8code.\n");
t8_global_productionf (" [step4] In this example we will explain the forest creation in more details.\n");
t8_global_productionf (
" [step4] We will partition a forest and create a ghost layer and we will also balance a forest.\n");
t8_global_productionf (" [step4] \n");
/* We will use MPI_COMM_WORLD as a communicator. */
comm = sc_MPI_COMM_WORLD;
/*
* Setup.
* Build cmesh and uniform forest.
*/
t8_global_productionf (" [step4] \n");
t8_global_productionf (" [step4] Creating an adapted forest as in step3.\n");
t8_global_productionf (" [step4] \n");
/* Build a cube cmesh with tet, hex, and prism trees. */
cmesh = t8_cmesh_new_hypercube_hybrid (comm, 0, 0);
t8_global_productionf (" [step4] Created coarse mesh.\n");
forest = t8_forest_new_uniform (cmesh, t8_scheme_new_default (), level, 0, comm);
/* Print information of the forest. */
t8_step3_print_forest_information (forest);
/* Write forest to vtu files. */
t8_forest_write_vtk (forest, prefix_uniform);
t8_global_productionf (" [step4] Wrote uniform level %i forest to vtu files: %s*\n", level, prefix_uniform);
/*
* Adapt the forest.
*/
/* Adapt the forest. We can reuse the forest variable, since the new adapted
* forest will take ownership of the old forest and destroy it.
* Note that the adapted forest is a new forest, though. */
forest = t8_step3_adapt_forest (forest);
/* Print information of our new forest. */
t8_step3_print_forest_information (forest);
/* Write forest to vtu files. */
t8_forest_write_vtk (forest, prefix_adapt);
t8_global_productionf (" [step4] Wrote adapted forest to vtu files: %s*\n", prefix_adapt);
/*
* Partition and create ghost elements.
*/
t8_global_productionf (" [step4] \n");
t8_global_productionf (" [step4] Repartitioning this forest and creating a ghost layer.\n");
t8_global_productionf (" [step4] \n");
forest = t8_step4_partition_ghost (forest);
t8_global_productionf (" [step4] Repartitioned forest and built ghost layer.\n");
t8_step3_print_forest_information (forest);
/* Write forest to vtu files. */
t8_forest_write_vtk_ext (forest, prefix_partition_ghost, 1, 1, 1, 1, 1, 0, 1, 0, NULL);
t8_global_productionf (" [step4] Wrote repartitioned forest with ghost layer to vtu files: %s*\n",
prefix_partition_ghost);
/*
* Balance
*/
t8_global_productionf (" [step4] \n");
t8_global_productionf (" [step4] Creating an unbalanced forest and balancing it.\n");
t8_global_productionf (" [step4] \n");
forest = t8_step4_balance (forest);
t8_global_productionf (" [step4] Balanced forest.\n");
t8_step3_print_forest_information (forest);
/* Write forest to vtu files. */
t8_forest_write_vtk (forest, prefix_balance);
t8_global_productionf (" [step4] Wrote balanced forest to vtu files: %s*\n", prefix_balance);
/*
* clean-up
*/
/* Destroy the forest. */
t8_forest_unref (&forest);
t8_global_productionf (" [step4] Destroyed forest.\n");
sc_finalize ();
mpiret = sc_MPI_Finalize ();
SC_CHECK_MPI (mpiret);
return 0;
}
T8_EXTERN_C_END ();