Line data Source code
1 : // The libMesh Finite Element Library.
2 : // Copyright (C) 2002-2025 Benjamin S. Kirk, John W. Peterson, Roy H. Stogner
3 :
4 : // This library is free software; you can redistribute it and/or
5 : // modify it under the terms of the GNU Lesser General Public
6 : // License as published by the Free Software Foundation; either
7 : // version 2.1 of the License, or (at your option) any later version.
8 :
9 : // This library is distributed in the hope that it will be useful,
10 : // but WITHOUT ANY WARRANTY; without even the implied warranty of
11 : // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
12 : // Lesser General Public License for more details.
13 :
14 : // You should have received a copy of the GNU Lesser General Public
15 : // License along with this library; if not, write to the Free Software
16 : // Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
17 :
18 :
19 :
20 : #ifndef LIBMESH_PARTITIONER_H
21 : #define LIBMESH_PARTITIONER_H
22 :
23 : // Local Includes
24 : #include "libmesh/libmesh.h"
25 : #include "libmesh/id_types.h"
26 : #include "libmesh/mesh_base.h" // for MeshBase::element_iterator
27 :
28 : // C++ Includes
29 : #include <cstddef>
30 : #include <memory>
31 : #include <unordered_map>
32 : #include <queue>
33 :
34 : namespace libMesh
35 : {
36 :
37 : // Forward Declarations
38 : class ErrorVector;
39 : enum PartitionerType : int;
40 :
41 : /**
42 : * The \p Partitioner class provides a uniform interface for
43 : * partitioning algorithms. It takes a reference to a \p MeshBase
44 : * object as input, which it will partition into a number of
45 : * subdomains.
46 : *
47 : * \author Benjamin S. Kirk
48 : * \date 2003
49 : * \brief Base class for all concrete Partitioner instantiations.
50 : */
51 : class Partitioner
52 : {
53 : public:
54 :
55 : /**
56 : * Constructor.
57 : */
58 474495 : Partitioner () : _weights(nullptr) {}
59 :
60 : /**
61 : * Copy/move ctor, copy/move assignment operator, and destructor are
62 : * all explicitly defaulted for this class.
63 : */
64 12807 : Partitioner (const Partitioner &) = default;
65 : Partitioner (Partitioner &&) = default;
66 : Partitioner & operator= (const Partitioner &) = default;
67 : Partitioner & operator= (Partitioner &&) = default;
68 47713 : virtual ~Partitioner() = default;
69 :
70 : virtual PartitionerType type () const;
71 :
72 : /**
73 : * Builds a \p Partitioner of the type specified by
74 : * \p partitioner_type
75 : */
76 : static std::unique_ptr<Partitioner>
77 : build(const PartitionerType solver_package);
78 :
79 : /**
80 : * \returns A copy of this partitioner wrapped in a smart pointer.
81 : *
82 : * This is used when copying meshes, and must be overridden in the
83 : * derived classes.
84 : */
85 : virtual std::unique_ptr<Partitioner> clone () const = 0;
86 :
87 : /**
88 : * Partitions the \p MeshBase into \p n parts by setting
89 : * processor_id() on Nodes and Elems.
90 : *
91 : * \note If you are implementing a new type of Partitioner, you most
92 : * likely do \e not want to override the partition() function, see
93 : * instead the protected virtual _do_partition() method below. The
94 : * partition() function is responsible for doing a lot of
95 : * libmesh-internals-specific setup and finalization before and
96 : * after the _do_partition() function is called. The only
97 : * responsibility of the _do_partition() function, on the other
98 : * hand, is to set the processor IDs of the elements according to a
99 : * specific partitioning algorithm. See, e.g. MetisPartitioner for
100 : * an example.
101 : */
102 : virtual void partition (MeshBase & mesh,
103 : const unsigned int n);
104 :
105 : /**
106 : * Partitions the \p MeshBase into \p mesh.n_processors() by setting
107 : * processor_id() on Nodes and Elems.
108 : *
109 : * \note If you are implementing a new type of Partitioner, you most
110 : * likely do \e not want to override the partition() function, see
111 : * instead the protected virtual _do_partition() method below. The
112 : * partition() function is responsible for doing a lot of
113 : * libmesh-internals-specific setup and finalization before and
114 : * after the _do_partition() function is called. The only
115 : * responsibility of the _do_partition() function, on the other
116 : * hand, is to set the processor IDs of the elements according to a
117 : * specific partitioning algorithm. See, e.g. MetisPartitioner for
118 : * an example.
119 : */
120 : virtual void partition (MeshBase & mesh);
121 :
122 : /**
123 : * Partitions elements in the range (it, end) into n parts.
124 : * The mesh from which the iterators are created must also be passed
125 : * in, since it is a parallel object and has other useful
126 : * information in it.
127 : *
128 : * Although partition_range() is part of the public Partitioner
129 : * interface, it should not generally be called by applications.
130 : * Its main purpose is to support the SubdomainPartitioner, which
131 : * uses it internally to individually partition ranges of elements
132 : * before combining them into the final partitioning. Most of the
133 : * time, the protected _do_partition() function is implemented in
134 : * terms of partition_range() by passing a range which includes all
135 : * the elements of the Mesh.
136 : */
137 0 : virtual void partition_range (MeshBase & /*mesh*/,
138 : MeshBase::element_iterator /*beg*/,
139 : MeshBase::element_iterator /*end*/,
140 : const unsigned int /*n_parts*/)
141 0 : { libmesh_not_implemented(); }
142 :
143 : /**
144 : * Repartitions the \p MeshBase into \p n parts. (Some partitioning
145 : * algorithms can repartition more efficiently than computing a new
146 : * partitioning from scratch.) The default behavior is to simply
147 : * call this->partition(mesh,n).
148 : */
149 : void repartition (MeshBase & mesh,
150 : const unsigned int n);
151 :
152 : /**
153 : * Repartitions the \p MeshBase into \p mesh.n_processors() parts. This
154 : * is required since some partitioning algorithms can repartition
155 : * more efficiently than computing a new partitioning from scratch.
156 : */
157 : void repartition (MeshBase & mesh);
158 :
159 : /**
160 : * These functions assign processor IDs to newly-created elements
161 : * (in parallel) which are currently assigned to processor 0.
162 : */
163 : static void partition_unpartitioned_elements (MeshBase & mesh);
164 :
165 : static void partition_unpartitioned_elements (MeshBase & mesh,
166 : const unsigned int n);
167 :
168 : /**
169 : * This function is called after partitioning to set the processor IDs
170 : * for the inactive parent elements. A parent's processor ID is the same
171 : * as its first child.
172 : */
173 : static void set_parent_processor_ids(MeshBase & mesh);
174 :
175 : /**
176 : * This function is called after partitioning to set the processor IDs
177 : * for the nodes. By definition, a Node's processor ID is the minimum
178 : * processor ID for all of the elements which share the node.
179 : */
180 : static void set_node_processor_ids(MeshBase & mesh);
181 :
182 : /**
183 : * On the partitioning interface, a surface is shared by two and only two processors.
184 : * Try to find which pair of processors corresponds to which surfaces, and store their
185 : * nodes.
186 : */
187 : static void processor_pairs_to_interface_nodes(MeshBase & mesh, std::map<std::pair<processor_id_type, processor_id_type>, std::set<dof_id_type>> & processor_pair_to_nodes);
188 :
189 : /**
190 : * Nodes on the partitioning interface is linearly assigned to
191 : * each pair of processors
192 : */
193 : static void set_interface_node_processor_ids_linear(MeshBase & mesh);
194 :
195 : /**
196 : * Nodes on the partitioning interface is clustered into two groups BFS (Breadth First Search)scheme
197 : * for per pair of processors
198 : */
199 : static void set_interface_node_processor_ids_BFS(MeshBase & mesh);
200 :
201 :
202 : /**
203 : * Nodes on the partitioning interface is partitioned into two groups using a PETSc partitioner
204 : * for each pair of processors
205 : */
206 : static void set_interface_node_processor_ids_petscpartitioner(MeshBase & mesh);
207 :
208 : /**
209 : * Attach weights that can be used for partitioning. This ErrorVector should be
210 : * _exactly_ the same on every processor and should have mesh->max_elem_id()
211 : * entries.
212 : */
213 0 : virtual void attach_weights(ErrorVector * /*weights*/) { libmesh_not_implemented(); }
214 :
215 : protected:
216 :
217 : /**
218 : * Trivially "partitions" the mesh for one processor.
219 : * Simply loops through the elements and assigns all of them
220 : * to processor 0. Is is provided as a separate function
221 : * so that derived classes may use it without reimplementing it.
222 : *
223 : * Returns \p true iff any processor id was changed.
224 : */
225 : bool single_partition (MeshBase & mesh);
226 :
227 : /**
228 : * Slightly generalized version of single_partition which acts on a
229 : * range of elements defined by the pair of iterators (it, end).
230 : *
231 : * Returns \p true iff any processor id was changed.
232 : */
233 : bool single_partition_range(MeshBase::element_iterator it,
234 : MeshBase::element_iterator end);
235 :
236 : /**
237 : * This is the actual partitioning method which must be overridden
238 : * in derived classes. It is called via the public partition()
239 : * method above by the user.
240 : */
241 : virtual void _do_partition(MeshBase & mesh,
242 : const unsigned int n) = 0;
243 :
244 : /**
245 : * This is the actual re-partitioning method which can be overridden
246 : * in derived classes.
247 : *
248 : * \note The default behavior is to simply call the partition
249 : * function.
250 : */
251 0 : virtual void _do_repartition (MeshBase & mesh,
252 0 : const unsigned int n) { this->_do_partition (mesh, n); }
253 :
254 : /**
255 : * The blocksize to use when doing blocked parallel communication. This limits the
256 : * maximum vector size which can be used in a single communication step.
257 : */
258 : static const dof_id_type communication_blocksize;
259 :
260 : /**
261 : * Construct contiguous global indices for the current partitioning. The global indices
262 : * are ordered part-by-part
263 : */
264 : virtual void _find_global_index_by_pid_map(const MeshBase & mesh);
265 :
266 :
267 : /**
268 : * Build a dual graph for partitioner
269 : *
270 : */
271 : virtual void build_graph(const MeshBase & mesh);
272 :
273 : /**
274 : * Assign the computed partitioning to the mesh.
275 : */
276 : void assign_partitioning (MeshBase & mesh, const std::vector<dof_id_type> & parts);
277 :
278 : /**
279 : * The weights that might be used for partitioning.
280 : */
281 : ErrorVector * _weights;
282 :
283 : /**
284 : * Maps active element ids into a contiguous range, as needed by parallel partitioner.
285 : */
286 : std::unordered_map<dof_id_type, dof_id_type> _global_index_by_pid_map;
287 :
288 : /**
289 : * The number of active elements on each processor.
290 : *
291 : * \note ParMETIS requires that each processor have some active
292 : * elements; it will abort if any processor passes a nullptr _part
293 : * array.
294 : */
295 : std::vector<dof_id_type> _n_active_elem_on_proc;
296 :
297 : /**
298 : * A dual graph corresponds to the mesh, and it is typically used
299 : * in paritioner. A vertex represents an element, and its neighbors are the
300 : * element neighbors.
301 : */
302 : std::vector<std::vector<dof_id_type>> _dual_graph;
303 :
304 :
305 : std::vector<Elem *> _local_id_to_elem;
306 : };
307 :
308 : } // namespace libMesh
309 :
310 : #endif // LIBMESH_PARTITIONER_H
|
