Line data Source code
1 : // The libMesh Finite Element Library.
2 : // Copyright (C) 2002-2026 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 653708 : 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 12887 : Partitioner (const Partitioner &) = default;
65 : Partitioner (Partitioner &&) = default;
66 : Partitioner & operator= (const Partitioner &) = default;
67 : Partitioner & operator= (Partitioner &&) = default;
68 48066 : 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 : * As above, but \p spatial_indexing selects how the elements are mapped onto the
170 : * partitions. With \p true they are ordered along a space-filling curve, so that each
171 : * partition gets a spatially compact set; this costs a parallel sort. With \p false
172 : * their position in the traversal of the range is used, which is free but is only
173 : * consistent across processors for a replicated mesh.
174 : */
175 : static void partition_unpartitioned_elements (MeshBase & mesh,
176 : const unsigned int n,
177 : const bool spatial_indexing);
178 :
179 : /**
180 : * This function is called after partitioning to set the processor IDs
181 : * for the inactive parent elements. A parent's processor ID is the same
182 : * as its first child.
183 : */
184 : static void set_parent_processor_ids(MeshBase & mesh);
185 :
186 : /**
187 : * This function is called after partitioning to set the processor IDs
188 : * for the nodes. By definition, a Node's processor ID is the minimum
189 : * processor ID for all of the elements which share the node.
190 : */
191 : static void set_node_processor_ids(MeshBase & mesh);
192 :
193 : /**
194 : * On the partitioning interface, a surface is shared by two and only two processors.
195 : * Try to find which pair of processors corresponds to which surfaces, and store their
196 : * nodes.
197 : */
198 : 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);
199 :
200 : /**
201 : * Nodes on the partitioning interface is linearly assigned to
202 : * each pair of processors
203 : */
204 : static void set_interface_node_processor_ids_linear(MeshBase & mesh);
205 :
206 : /**
207 : * Nodes on the partitioning interface is clustered into two groups BFS (Breadth First Search)scheme
208 : * for per pair of processors
209 : */
210 : static void set_interface_node_processor_ids_BFS(MeshBase & mesh);
211 :
212 :
213 : /**
214 : * Nodes on the partitioning interface is partitioned into two groups using a PETSc partitioner
215 : * for each pair of processors
216 : */
217 : static void set_interface_node_processor_ids_petscpartitioner(MeshBase & mesh);
218 :
219 : /**
220 : * Attach weights that can be used for partitioning. This ErrorVector should be
221 : * _exactly_ the same on every processor and should have mesh->max_elem_id()
222 : * entries.
223 : */
224 0 : virtual void attach_weights(ErrorVector * /*weights*/) { libmesh_not_implemented(); }
225 :
226 : /**
227 : * \returns Whether this partitioner computes its partitioning without reference to the
228 : * partitioning the mesh already carries.
229 : *
230 : * A partitioner that instead refines what it is handed is sensitive to the temporary
231 : * assignment partition_unpartitioned_elements() gives to unpartitioned elements, and so
232 : * should have that assignment be spatially coherent rather than merely consistent across
233 : * processors.
234 : *
235 : * The base-class default is conservative, so that a sub-class partitioner which has not
236 : * considered whether to override this virtual keeps a spatially coherent temporary
237 : * partitioning assignment. Overriding it to return \p true buys a cheaper temporary
238 : * partitioning on a replicated mesh.
239 : *
240 : * \todo Make this pure virtual, so that every partitioner has to state which kind it is,
241 : * once the partitioners outside the library have been given an override.
242 : */
243 0 : virtual bool partitions_from_scratch () const { return false; }
244 :
245 : protected:
246 :
247 : /**
248 : * Trivially "partitions" the mesh for one processor.
249 : * Simply loops through the elements and assigns all of them
250 : * to processor 0. Is is provided as a separate function
251 : * so that derived classes may use it without reimplementing it.
252 : *
253 : * Returns \p true iff any processor id was changed.
254 : */
255 : bool single_partition (MeshBase & mesh);
256 :
257 : /**
258 : * Slightly generalized version of single_partition which acts on a
259 : * range of elements defined by the pair of iterators (it, end).
260 : *
261 : * Returns \p true iff any processor id was changed.
262 : */
263 : bool single_partition_range(MeshBase::element_iterator it,
264 : MeshBase::element_iterator end);
265 :
266 : /**
267 : * This is the actual partitioning method which must be overridden
268 : * in derived classes. It is called via the public partition()
269 : * method above by the user.
270 : */
271 : virtual void _do_partition(MeshBase & mesh,
272 : const unsigned int n) = 0;
273 :
274 : /**
275 : * This is the actual re-partitioning method which can be overridden
276 : * in derived classes.
277 : *
278 : * \note The default behavior is to simply call the partition
279 : * function.
280 : */
281 0 : virtual void _do_repartition (MeshBase & mesh,
282 0 : const unsigned int n) { this->_do_partition (mesh, n); }
283 :
284 : /**
285 : * The blocksize to use when doing blocked parallel communication. This limits the
286 : * maximum vector size which can be used in a single communication step.
287 : */
288 : static const dof_id_type communication_blocksize;
289 :
290 : /**
291 : * Construct contiguous global indices for the current partitioning. The global indices
292 : * are ordered part-by-part
293 : */
294 : virtual void _find_global_index_by_pid_map(const MeshBase & mesh);
295 :
296 :
297 : /**
298 : * Build a dual graph for partitioner
299 : *
300 : */
301 : virtual void build_graph(const MeshBase & mesh);
302 :
303 : /**
304 : * Assign the computed partitioning to the mesh.
305 : */
306 : void assign_partitioning (MeshBase & mesh, const std::vector<dof_id_type> & parts);
307 :
308 : /**
309 : * The weights that might be used for partitioning.
310 : */
311 : ErrorVector * _weights;
312 :
313 : /**
314 : * Maps active element ids into a contiguous range, as needed by parallel partitioner.
315 : */
316 : std::unordered_map<dof_id_type, dof_id_type> _global_index_by_pid_map;
317 :
318 : /**
319 : * The number of active elements on each processor.
320 : *
321 : * \note ParMETIS requires that each processor have some active
322 : * elements; it will abort if any processor passes a nullptr _part
323 : * array.
324 : */
325 : std::vector<dof_id_type> _n_active_elem_on_proc;
326 :
327 : /**
328 : * A dual graph corresponds to the mesh, and it is typically used
329 : * in paritioner. A vertex represents an element, and its neighbors are the
330 : * element neighbors.
331 : */
332 : std::vector<std::vector<dof_id_type>> _dual_graph;
333 :
334 :
335 : std::vector<Elem *> _local_id_to_elem;
336 : };
337 :
338 : } // namespace libMesh
339 :
340 : #endif // LIBMESH_PARTITIONER_H
|
