Debian Codegraph @

include/deal.II/distributed/shared_tria.h

raw
1 // ------------------------------------------------------------------------
2 //
3 // SPDX-License-Identifier: LGPL-2.1-or-later
4 // Copyright (C) 2015 - 2024 by the deal.II authors
5 //
6 // This file is part of the deal.II library.
7 //
8 // Part of the source code is dual licensed under Apache-2.0 WITH
9 // LLVM-exception OR LGPL-2.1-or-later. Detailed license information
10 // governing the source code and code contributions can be found in
11 // LICENSE.md and CONTRIBUTING.md at the top level directory of deal.II.
12 //
13 // ------------------------------------------------------------------------
14
15 #ifndef dealii_distributed_shared_tria_h
16 #define dealii_distributed_shared_tria_h
17
18
19 #include <deal.II/base/config.h>
20
21 #include <deal.II/base/enable_observer_pointer.h>
22 #include <deal.II/base/mpi_stub.h>
23 #include <deal.II/base/observer_pointer.h>
24 #include <deal.II/base/template_constraints.h>
25
26 #include <deal.II/distributed/tria_base.h>
27
28 #include <deal.II/grid/tria.h>
29
30 #include <functional>
31 #include <list>
32 #include <utility>
33 #include <vector>
34
35 DEAL_II_NAMESPACE_OPEN
36
37 namespace parallel
38 {
39 #ifdef DEAL_II_WITH_MPI
40
41
42 namespace shared
43 {
44 /**
45 * This class provides a parallel triangulation for which every processor
46 * knows about every cell of the global mesh (unlike for the
47 * parallel::distributed::Triangulation class) but in which cells are
48 * automatically partitioned when run with MPI so that each processor
49 * "owns" a subset of cells. The use of this class is demonstrated in
50 * step-18.
51 *
52 * Different from the parallel::distributed::Triangulation and
53 * parallel::fullydistributed::Triangulation classes, this implies
54 * that the entire mesh is stored on each processor. While this is clearly
55 * a memory bottleneck that limits the use of this class to a few dozen
56 * or hundreds of MPI processes, the partitioning of the mesh can be used
57 * to partition work such as assembly or postprocessing between
58 * participating processors, and it can also be used to partition which
59 * processor stores which parts of matrices and vectors. As a consequence,
60 * using this class is often a gentler introduction to parallelizing a
61 * code than the more involved parallel::distributed::Triangulation class
62 * in which processors only know their own part of the mesh, but nothing
63 * about cells owned by other processors with the exception of a single
64 * layer of ghost cells around their own part of the domain.
65 *
66 * Because every MPI process has a complete copy of the entire mesh
67 * as if it were stored on only this process, it needs to know for
68 * every active cell whether it is flagged for refinement or coarsening
69 * when doing mesh refinement via
70 * Triangulation::execute_coarsening_and_refinement(). In practice,
71 * each process only needs to set this information for its own
72 * "locally owned" cells; upon calling
73 * Triangulation::execute_coarsening_and_refinement(), the
74 * relevant information is then exchanged between processes
75 * internally, via MPI communication.
76 *
77 * The class is also useful in cases where compute time and memory
78 * considerations dictate that the program needs to be run in parallel,
79 * but where algorithmic concerns require that every processor knows
80 * about the entire mesh. An example could be where an application
81 * has to have both volume and surface meshes that can then both
82 * be partitioned independently, but where it is difficult to ensure
83 * that the locally owned set of surface mesh cells is adjacent to the
84 * locally owned set of volume mesh cells and the other way around. In
85 * such cases, knowing the <i>entirety</i> of both meshes ensures that
86 * assembly of coupling terms can be implemented without also
87 * implementing overly complicated schemes to transfer information about
88 * adjacent cells from processor to processor.
89 *
90 * The partitioning of cells between processors is done internally
91 * based on a number of different possibilities. By passing appropriate
92 * flags to the constructor of this class (see the
93 * parallel::shared::Triangulation::Settings
94 * enum), it is possible to select different ways of partitioning the mesh,
95 * including ways that are dictated by the application and not by the
96 * desire to minimize the length of the interface between subdomains owned
97 * by processors (as is done by the METIS and Zoltan packages, both of
98 * which are options for partitioning). The DoFHandler class knows how to
99 * enumerate degrees of freedom in ways appropriate for the partitioned
100 * mesh.
101 *
102 * @ingroup distributed
103 *
104 * @dealiiConceptRequires{(concepts::is_valid_dim_spacedim<dim, spacedim>)}
105 */
106 template <int dim, int spacedim = dim>
107 DEAL_II_CXX20_REQUIRES((concepts::is_valid_dim_spacedim<dim, spacedim>))
108 class Triangulation
109 : public dealii::parallel::TriangulationBase<dim, spacedim>
110 {
111 public:
112 using active_cell_iterator =
113 typename dealii::Triangulation<dim, spacedim>::active_cell_iterator;
114 using cell_iterator =
115 typename dealii::Triangulation<dim, spacedim>::cell_iterator;
116
117 /**
118 * Configuration flags for distributed Triangulations to be set in the
119 * constructor. Settings can be combined using bitwise OR.
120 *
121 * The constructor requires that exactly one of
122 * <code>partition_auto</code>, <code>partition_metis</code>,
123 * <code>partition_zorder</code>, <code>partition_zoltan</code> and
124 * <code>partition_custom_signal</code> is set. If
125 * <code>partition_auto</code> is chosen, it will use
126 * <code>partition_zoltan</code> (if available), then
127 * <code>partition_metis</code> (if available) and finally
128 * <code>partition_zorder</code>.
129 */
130 enum Settings
131 {
132 /**
133 * Choose the partitioner depending on the enabled
134 * dependencies that were found when configuring deal.II. In
135 * particular, if the Trilinos package Zoltan was found, then
136 * use the @p partition_zoltan strategy. If Zoltan was not
137 * found but the METIS package was found, then use the
138 * partition_metis strategy. If neither of these were found,
139 * then use the partition_zorder partitioning strategy.
140 */
141 partition_auto = 0x0,
142
143 /**
144 * Use METIS partitioner to partition active cells.
145 */
146 partition_metis = 0x1,
147
148 /**
149 * Partition active cells with the same scheme used in the
150 * p4est library.
151 *
152 * The term "Z-order" originates in the fact that cells are
153 * sorted using a space filling curve which in 2d connects the
154 * four children of a cell in the order bottom left, bottom
155 * right, top left, top right (i.e., with a curve that looks
156 * like a reverse "Z"), and does so recursively on all levels
157 * of a triangulation. This is also the order in which
158 * children are enumerated by the GeometryInfo class. The
159 * "Z-order" is also sometimes called "Morton ordering", see
160 * https://en.wikipedia.org/wiki/Z-order_curve .
161 *
162 * @see
163 * @ref GlossZOrder "Z order glossary entry".
164 */
165 partition_zorder = 0x2,
166
167 /**
168 * Use Zoltan to partition active cells.
169 */
170 partition_zoltan = 0x3,
171
172 /**
173 * Partition cells using a custom, user defined function. This is
174 * accomplished by connecting the post_refinement signal to the
175 * triangulation whenever it is first created and passing the user
176 * defined function through the signal using <code>std::bind</code>.
177 * Here is an example:
178 * @code
179 * template <int dim>
180 * void mypartition(parallel::shared::Triangulation<dim> &tria)
181 * {
182 * // user defined partitioning scheme: assign subdomain_ids
183 * // round-robin in a mostly random way:
184 * std::vector<unsigned int> assignment =
185 * {0,0,1,2,0,0,2,1,0,2,2,1,2,2,0,0};
186 * unsigned int index = 0;
187 * for (const auto &cell : tria.active_cell_iterators())
188 * cell->set_subdomain_id(assignment[(index++)%16]);
189 * }
190 *
191 * int main ()
192 * {
193 * parallel::shared::Triangulation<dim> tria(
194 * ...,
195 * parallel::shared::Triangulation<dim>::partition_custom_signal);
196 * tria.signals.post_refinement.connect(std::bind(&mypartition<dim>,
197 * std::ref(tria)));
198 * }
199 * @endcode
200 *
201 * An equivalent code using lambda functions would look like this:
202 * @code
203 * int main ()
204 * {
205 * parallel::shared::Triangulation<dim> tria(
206 * ...,
207 * parallel::shared::Triangulation<dim>::partition_custom_signal);
208 * tria.signals.post_refinement.connect (
209 * [&tria]()
210 * {
211 * // user defined partitioning scheme as above
212 * ...
213 * });
214 * }
215 * @endcode
216 *
217 * @note If you plan to use a custom partition with geometric multigrid,
218 * you must manually partition the level cells in addition to the active
219 * cells.
220 */
221 partition_custom_signal = 0x4,
222
223 /**
224 * This flag needs to be set to use the geometric multigrid
225 * functionality. This option requires additional computation and
226 * communication.
227 *
228 * Note: This flag should always be set alongside a flag for an
229 * active cell partitioning method.
230 */
231 construct_multigrid_hierarchy = 0x8,
232 };
233
234
235 /**
236 * Constructor.
237 *
238 * The flag @p allow_artificial_cells can be used to enable artificial
239 * cells. If enabled, this class will behave similarly
240 * to parallel::distributed::Triangulation and
241 * parallel::fullydistributed::Triangulation in the sense that there will
242 * be locally owned cells, a single layer of ghost cells, and
243 * artificial cells. However, one should not forget that in contrast to
244 * those parallel triangulations all cells are duplicated on all
245 * processes, leading in most cases to significantly more artificial
246 * cells.
247 *
248 * If artificial cells are disabled, all non-locally owned cells are
249 * considered ghost cells. This might lead to very expensive ghost-value
250 * update steps. While in the case of artificial cells, ghost-value
251 * updates lead to communication only with the direct process neighbors in
252 * a point-to-point fashion, these degenerate to an operation in which
253 * every process communicates with every other process (an "all-to-all"
254 * communication) if no artificial cells are available. If such
255 * ghost-value updates are the bottleneck in your code, you may want to
256 * consider enabling artificial cells.
257 */
258 Triangulation(
259 const MPI_Comm mpi_communicator,
260 const typename dealii::Triangulation<dim, spacedim>::MeshSmoothing =
261 (dealii::Triangulation<dim, spacedim>::none),
262 const bool allow_artificial_cells = false,
263 const Settings settings = partition_auto);
264
265 /**
266 * Destructor.
267 */
268 virtual ~Triangulation() override = default;
269
270 /**
271 * Return if multilevel hierarchy is supported and has been constructed.
272 */
273 virtual bool
274 is_multilevel_hierarchy_constructed() const override;
275
276 /**
277 * Coarsen and refine the mesh according to refinement and coarsening
278 * flags set.
279 *
280 * This step is equivalent to the dealii::Triangulation class with an
281 * addition of calling dealii::GridTools::partition_triangulation() at
282 * the end.
283 */
284 virtual void
285 execute_coarsening_and_refinement() override;
286
287 /**
288 * Create a triangulation.
289 *
290 * This function also partitions triangulation based on the MPI
291 * communicator provided to the constructor.
292 */
293 virtual void
294 create_triangulation(const std::vector<Point<spacedim>> &vertices,
295 const std::vector<CellData<dim>> &cells,
296 const SubCellData &subcelldata) override;
297
298 /**
299 * @copydoc Triangulation::create_triangulation()
300 *
301 * @note Not implemented yet.
302 */
303 virtual void
304 create_triangulation(
305 const TriangulationDescription::Description<dim, spacedim>
306 &construction_data) override;
307
308 /**
309 * Copy @p other_tria to this triangulation.
310 *
311 * This function also partitions triangulation based on the MPI
312 * communicator provided to the constructor.
313 *
314 * @note This function can not be used with parallel::distributed::Triangulation,
315 * since it only stores those cells that it owns, one layer of ghost cells
316 * around the ones it locally owns, and a number of artificial cells.
317 */
318 virtual void
319 copy_triangulation(
320 const dealii::Triangulation<dim, spacedim> &other_tria) override;
321
322 # ifdef DOXYGEN
323 /**
324 * Write and read the data of this object from a stream for the purpose
325 * of serialization. using the [BOOST serialization
326 * library](https://www.boost.org/doc/libs/1_74_0/libs/serialization/doc/index.html).
327 */
328 template <class Archive>
329 void
330 serialize(Archive &archive, const unsigned int version);
331 # else
332 // This macro defines the serialize() method that is compatible with
333 // the templated save() and load() method that have been implemented.
334 BOOST_SERIALIZATION_SPLIT_MEMBER()
335 # endif
336
337 /**
338 * Save the triangulation into the given file. This file needs to be
339 * reachable from all nodes in the computation on a shared network file
340 * system. See the SolutionTransfer class on how to store solution vectors
341 * into this file. Additional cell-based data can be saved using
342 * register_data_attach().
343 */
344 using parallel::TriangulationBase<dim, spacedim>::save;
345
346 /**
347 * Load the triangulation saved with save() back in. Cell-based data that
348 * was saved with register_data_attach() can be read in with
349 * notify_ready_to_unpack() after calling load().
350 */
351 using parallel::TriangulationBase<dim, spacedim>::load;
352
353 /**
354 * Read the data of this object from a stream for the purpose of
355 * serialization. Throw away the previous content.
356 *
357 * This function first does the same work as in
358 * dealii::Triangulation::load, then partitions the triangulation based on
359 * the MPI communicator provided to the constructor.
360 */
361 template <class Archive>
362 void
363 load(Archive &ar, const unsigned int version);
364
365 /**
366 * Return a vector of length Triangulation::n_active_cells() where each
367 * element stores the subdomain id of the owner of this cell. The
368 * elements of the vector are obviously the same as the subdomain ids
369 * for locally owned and ghost cells, but are also correct for
370 * artificial cells that do not store who the owner of the cell is in
371 * their subdomain_id field.
372 */
373 const std::vector<types::subdomain_id> &
374 get_true_subdomain_ids_of_cells() const;
375
376 /**
377 * Return a vector of length Triangulation::n_cells(level) where each
378 * element stores the level subdomain id of the owner of this cell. The
379 * elements of the vector are obviously the same as the level subdomain
380 * ids for locally owned and ghost cells, but are also correct for
381 * artificial cells that do not store who the owner of the cell is in
382 * their level_subdomain_id field.
383 */
384 const std::vector<types::subdomain_id> &
385 get_true_level_subdomain_ids_of_cells(const unsigned int level) const;
386
387 /**
388 * Return allow_artificial_cells, namely true if artificial cells are
389 * allowed.
390 */
391 bool
392 with_artificial_cells() const;
393
394 private:
395 /**
396 * Settings
397 */
398 const Settings settings;
399
400 /**
401 * A flag to decide whether or not artificial cells are allowed.
402 */
403 const bool allow_artificial_cells;
404
405 /**
406 * This function calls GridTools::partition_triangulation () and if
407 * requested in the constructor of the class marks artificial cells.
408 */
409 void
410 partition();
411
412 /**
413 * A vector containing subdomain IDs of cells obtained by partitioning
414 * using either zorder, METIS, or a user-defined partitioning scheme.
415 * In case allow_artificial_cells is false, this vector is
416 * consistent with IDs stored in cell->subdomain_id() of the
417 * triangulation class. When allow_artificial_cells is true, cells which
418 * are artificial will have cell->subdomain_id() == numbers::artificial;
419 *
420 * The original partition information is stored to allow using sequential
421 * DoF distribution and partitioning functions with semi-artificial
422 * cells.
423 */
424 std::vector<types::subdomain_id> true_subdomain_ids_of_cells;
425
426 /**
427 * A vector containing level subdomain IDs of cells obtained by
428 * partitioning each level.
429 *
430 * The original partition information is stored to allow using sequential
431 * DoF distribution and partitioning functions with semi-artificial
432 * cells.
433 */
434 std::vector<std::vector<types::subdomain_id>>
435 true_level_subdomain_ids_of_cells;
436 };
437
438
439
440 template <int dim, int spacedim>
441 DEAL_II_CXX20_REQUIRES((concepts::is_valid_dim_spacedim<dim, spacedim>))
442 template <class Archive>
443 void Triangulation<dim, spacedim>::load(Archive &ar,
444 const unsigned int version)
445 {
446 dealii::Triangulation<dim, spacedim>::load(ar, version);
447 partition();
448 this->update_number_cache();
449 }
450 } // namespace shared
451 #else
452
453 namespace shared
454 {
455 /**
456 * Dummy class the compiler chooses for parallel shared triangulations if
457 * we didn't actually configure deal.II with the MPI library. The
458 * existence of this class allows us to refer to
459 * parallel::shared::Triangulation objects throughout the library even if
460 * it is disabled.
461 *
462 * Since the constructor of this class is deleted, no such objects
463 * can actually be created as this would be pointless given that
464 * MPI is not available.
465 *
466 * @dealiiConceptRequires{(concepts::is_valid_dim_spacedim<dim, spacedim>)}
467 */
468 template <int dim, int spacedim = dim>
469 DEAL_II_CXX20_REQUIRES((concepts::is_valid_dim_spacedim<dim, spacedim>))
470 class Triangulation
471 : public dealii::parallel::TriangulationBase<dim, spacedim>
472 {
473 public:
474 /**
475 * Constructor. Deleted to make sure that objects of this type cannot be
476 * constructed (see also the class documentation).
477 */
478 Triangulation() = delete;
479
480 /**
481 * Return if multilevel hierarchy is supported and has been constructed.
482 */
483 virtual bool
484 is_multilevel_hierarchy_constructed() const override;
485
486 /**
487 * A dummy function to return empty vector.
488 */
489 const std::vector<types::subdomain_id> &
490 get_true_subdomain_ids_of_cells() const;
491
492 /**
493 * A dummy function to return empty vector.
494 */
495 const std::vector<types::subdomain_id> &
496 get_true_level_subdomain_ids_of_cells(const unsigned int level) const;
497
498 /**
499 * A dummy function which always returns true.
500 */
501 bool
502 with_artificial_cells() const;
503
504 private:
505 /**
506 * A dummy vector.
507 */
508 std::vector<types::subdomain_id> true_subdomain_ids_of_cells;
509
510 /**
511 * A dummy vector.
512 */
513 std::vector<types::subdomain_id> true_level_subdomain_ids_of_cells;
514 };
515 } // namespace shared
516
517
518 #endif
519 } // namespace parallel
520
521
522 namespace internal
523 {
524 namespace parallel
525 {
526 namespace shared
527 {
528 /**
529 * This class temporarily modifies the subdomain ID of all active cells to
530 * their respective "true" owner.
531 *
532 * The modification only happens on parallel::shared::Triangulation
533 * objects with artificial cells, and persists for the lifetime of an
534 * instantiation of this class.
535 *
536 * The TemporarilyRestoreSubdomainIds class should only be used for
537 * temporary read-only purposes. For example, whenever your implementation
538 * requires to treat artificial cells temporarily as locally relevant to
539 * access their dof indices.
540 *
541 * This class has effect only if artificial cells are allowed. Without
542 * artificial cells, the current subdomain IDs already correspond to the
543 * true subdomain IDs. See the
544 * @ref GlossArtificialCell "glossary"
545 * for more information about artificial cells.
546 */
547 template <int dim, int spacedim = dim>
548 class TemporarilyRestoreSubdomainIds : public EnableObserverPointer
549 {
550 public:
551 /**
552 * Constructor.
553 *
554 * Stores the subdomain ID of all active cells if the provided
555 * Triangulation is of type parallel::shared::Triangulation.
556 *
557 * Replaces them by their true subdomain ID equivalent.
558 */
559 TemporarilyRestoreSubdomainIds(
560 const Triangulation<dim, spacedim> &tria);
561
562 /**
563 * Destructor.
564 *
565 * Returns the subdomain ID of all active cells on the
566 * parallel::shared::Triangulation into their previous state.
567 */
568 ~TemporarilyRestoreSubdomainIds();
569
570 private:
571 /**
572 * The modified parallel::shared::Triangulation.
573 */
574 const ObserverPointer<
575 const dealii::parallel::shared::Triangulation<dim, spacedim>>
576 shared_tria;
577
578 /**
579 * A vector that temporarily stores the subdomain IDs on all active
580 * cells before they have been modified on the
581 * parallel::shared::Triangulation.
582 */
583 std::vector<unsigned int> saved_subdomain_ids;
584 };
585 } // namespace shared
586 } // namespace parallel
587 } // namespace internal
588
589 DEAL_II_NAMESPACE_CLOSE
590
591 #endif