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 : #include "libmesh/partitioner.h"
21 :
22 : // libMesh includes
23 : #include "libmesh/compare_elems_by_level.h"
24 : #include "libmesh/elem.h"
25 : #include "libmesh/enum_to_string.h"
26 : #include "libmesh/int_range.h"
27 : #include "libmesh/libmesh_logging.h"
28 : #include "libmesh/mesh_base.h"
29 : #include "libmesh/mesh_tools.h"
30 : #include "libmesh/mesh_communication.h"
31 : #include "libmesh/node_range.h"
32 : #include "libmesh/parallel_ghost_sync.h"
33 : #include "libmesh/wrapped_petsc.h"
34 : #include "libmesh/boundary_info.h"
35 :
36 : // Subclasses to build()
37 : #include "libmesh/enum_partitioner_type.h"
38 : #include "libmesh/centroid_partitioner.h"
39 : #include "libmesh/hilbert_sfc_partitioner.h"
40 : #include "libmesh/linear_partitioner.h"
41 : #include "libmesh/mapped_subdomain_partitioner.h"
42 : #include "libmesh/metis_partitioner.h"
43 : #include "libmesh/morton_sfc_partitioner.h"
44 : #include "libmesh/parmetis_partitioner.h"
45 : #include "libmesh/sfc_partitioner.h"
46 : #include "libmesh/subdomain_partitioner.h"
47 :
48 : // TIMPI includes
49 : #include "timpi/parallel_implementation.h"
50 : #include "timpi/parallel_sync.h"
51 :
52 : // C/C++ includes
53 : #ifdef LIBMESH_HAVE_PETSC
54 : #include "libmesh/ignore_warnings.h"
55 : #include "petscmat.h"
56 : #include "libmesh/restore_warnings.h"
57 : #include "libmesh/petsc_solver_exception.h"
58 : #endif
59 :
60 :
61 : namespace {
62 :
63 : using namespace libMesh;
64 :
65 : struct CorrectProcIds
66 : {
67 : typedef processor_id_type datum;
68 :
69 146 : CorrectProcIds(MeshBase & _mesh,
70 92169 : std::unordered_set<dof_id_type> & _bad_pids) :
71 92169 : mesh(_mesh), bad_pids(_bad_pids) {}
72 :
73 : MeshBase & mesh;
74 : std::unordered_set<dof_id_type> & bad_pids;
75 :
76 : // ------------------------------------------------------------
77 1612328 : void gather_data (const std::vector<dof_id_type> & ids,
78 : std::vector<datum> & data)
79 : {
80 : // Find the processor id of each requested node
81 1612328 : data.resize(ids.size());
82 :
83 138520837 : for (auto i : index_range(ids))
84 : {
85 : // Look for this point in the mesh and make sure we have a
86 : // good pid for it before sending that on
87 136994438 : if (ids[i] != DofObject::invalid_id &&
88 136888667 : !bad_pids.count(ids[i]))
89 : {
90 136867863 : Node & node = mesh.node_ref(ids[i]);
91 :
92 : // Return the node's correct processor id,
93 136867863 : data[i] = node.processor_id();
94 : }
95 : else
96 40646 : data[i] = DofObject::invalid_processor_id;
97 : }
98 1612328 : }
99 :
100 : // ------------------------------------------------------------
101 1612328 : bool act_on_data (const std::vector<dof_id_type> & ids,
102 : const std::vector<datum> proc_ids)
103 : {
104 468 : bool data_changed = false;
105 :
106 : // Set the ghost node processor ids we've now been informed of
107 138520837 : for (auto i : index_range(ids))
108 : {
109 136908509 : Node & node = mesh.node_ref(ids[i]);
110 :
111 85929 : processor_id_type & proc_id = node.processor_id();
112 136908509 : const processor_id_type new_proc_id = proc_ids[i];
113 :
114 136908509 : if (const auto it = bad_pids.find(ids[i]);
115 136908509 : (new_proc_id != proc_id || it != bad_pids.end()) &&
116 : new_proc_id != DofObject::invalid_processor_id)
117 : {
118 636962 : if (it != bad_pids.end())
119 : {
120 274866 : proc_id = new_proc_id;
121 106 : bad_pids.erase(it);
122 : }
123 : else
124 362096 : proc_id = node.choose_processor_id(proc_id, new_proc_id);
125 :
126 636962 : if (proc_id == new_proc_id)
127 106 : data_changed = true;
128 : }
129 : }
130 :
131 1612328 : return data_changed;
132 : }
133 : };
134 :
135 : }
136 :
137 : namespace libMesh
138 : {
139 :
140 :
141 :
142 : // ------------------------------------------------------------
143 : // Partitioner static data
144 : const dof_id_type Partitioner::communication_blocksize =
145 : dof_id_type(1000000);
146 :
147 :
148 :
149 : // ------------------------------------------------------------
150 : // Partitioner implementation
151 :
152 :
153 0 : PartitionerType Partitioner::type() const
154 : {
155 0 : return INVALID_PARTITIONER;
156 : }
157 :
158 :
159 : std::unique_ptr<Partitioner>
160 499149 : Partitioner::build (const PartitionerType partitioner_type)
161 : {
162 499149 : switch (partitioner_type)
163 : {
164 71 : case CENTROID_PARTITIONER:
165 71 : return std::make_unique<CentroidPartitioner>();
166 213 : case LINEAR_PARTITIONER:
167 213 : return std::make_unique<LinearPartitioner>();
168 0 : case MAPPED_SUBDOMAIN_PARTITIONER:
169 0 : return std::make_unique<MappedSubdomainPartitioner>();
170 79471 : case METIS_PARTITIONER:
171 79471 : return std::make_unique<MetisPartitioner>();
172 419181 : case PARMETIS_PARTITIONER:
173 419181 : return std::make_unique<ParmetisPartitioner>();
174 71 : case HILBERT_SFC_PARTITIONER:
175 71 : return std::make_unique<HilbertSFCPartitioner>();
176 71 : case MORTON_SFC_PARTITIONER:
177 71 : return std::make_unique<MortonSFCPartitioner>();
178 71 : case SFC_PARTITIONER:
179 71 : return std::make_unique<SFCPartitioner>();
180 0 : case SUBDOMAIN_PARTITIONER:
181 0 : return std::make_unique<SubdomainPartitioner>();
182 0 : default:
183 0 : libmesh_error_msg("Invalid partitioner type: " <<
184 : Utility::enum_to_string(partitioner_type));
185 : }
186 : }
187 :
188 :
189 :
190 0 : void Partitioner::partition (MeshBase & mesh)
191 : {
192 0 : this->partition(mesh,mesh.n_processors());
193 0 : }
194 :
195 :
196 :
197 891448 : void Partitioner::partition (MeshBase & mesh,
198 : const unsigned int n)
199 : {
200 18525 : libmesh_parallel_only(mesh.comm());
201 :
202 : // BSK - temporary fix while redistribution is integrated 6/26/2008
203 : // Uncomment this to not repartition in parallel
204 : // if (!mesh.is_serial())
205 : // return;
206 :
207 : // we cannot partition into more pieces than we have
208 : // active elements!
209 : const unsigned int n_parts =
210 : static_cast<unsigned int>
211 891448 : (std::min(mesh.n_active_elem(), static_cast<dof_id_type>(n)));
212 :
213 : // Set the number of partitions in the mesh
214 891448 : mesh.set_n_partitions()=n_parts;
215 :
216 891448 : if (n_parts == 1)
217 : {
218 209515 : this->single_partition (mesh);
219 :
220 : // Give derived Mesh classes a chance to update any cached data
221 : // to reflect the new partitioning
222 209515 : mesh.update_post_partitioning();
223 :
224 209515 : return;
225 : }
226 :
227 : // First assign a temporary partitioning to any unpartitioned elements. A spatially
228 : // coherent assignment is only worth its parallel sort for a partitioner that refines what
229 : // it is handed; the other partitioners just need one that is consistent across processors,
230 : // which the cheap traversal-order assignment already is on a replicated mesh.
231 : Partitioner::partition_unpartitioned_elements
232 681933 : (mesh, n_parts,
233 681933 : /*spatial_indexing=*/!(mesh.is_replicated() && this->partitions_from_scratch()));
234 :
235 : // Call the partitioning function
236 681933 : this->_do_partition(mesh,n_parts);
237 :
238 : // Set the parent's processor ids
239 681933 : Partitioner::set_parent_processor_ids(mesh);
240 :
241 : // Ghosting functors may iterate over local elements while we
242 : // redistribute, so cached local ranges must reflect the new element
243 : // processor ids
244 681933 : mesh.update_post_partitioning();
245 :
246 : // Redistribute elements if necessary, before setting node processor
247 : // ids, to make sure those will be set consistently
248 681933 : mesh.redistribute();
249 :
250 : #ifdef DEBUG
251 12055 : MeshTools::libmesh_assert_valid_remote_elems(mesh);
252 :
253 : // Messed up elem processor_id()s can leave us without the child
254 : // elements we need to restrict vectors on a distributed mesh
255 12055 : MeshTools::libmesh_assert_valid_procids<Elem>(mesh);
256 : #endif
257 :
258 : // Set the node's processor ids
259 681933 : Partitioner::set_node_processor_ids(mesh);
260 :
261 : #ifdef DEBUG
262 12055 : MeshTools::libmesh_assert_valid_procids<Elem>(mesh);
263 : #endif
264 :
265 : // Give derived Mesh classes a chance to update any cached data to
266 : // reflect the new partitioning
267 681933 : mesh.update_post_partitioning();
268 : }
269 :
270 :
271 :
272 0 : void Partitioner::repartition (MeshBase & mesh)
273 : {
274 0 : this->repartition(mesh,mesh.n_processors());
275 0 : }
276 :
277 :
278 :
279 0 : void Partitioner::repartition (MeshBase & mesh,
280 : const unsigned int n)
281 : {
282 : // we cannot partition into more pieces than we have
283 : // active elements!
284 : const unsigned int n_parts =
285 : static_cast<unsigned int>
286 0 : (std::min(mesh.n_active_elem(), static_cast<dof_id_type>(n)));
287 :
288 : // Set the number of partitions in the mesh
289 0 : mesh.set_n_partitions()=n_parts;
290 :
291 0 : if (n_parts == 1)
292 : {
293 0 : this->single_partition (mesh);
294 0 : return;
295 : }
296 :
297 : // First assign a temporary partitioning to any unpartitioned elements; see partition()
298 : // for why the indexing is chosen this way.
299 : Partitioner::partition_unpartitioned_elements
300 0 : (mesh, n_parts,
301 0 : /*spatial_indexing=*/!(mesh.is_replicated() && this->partitions_from_scratch()));
302 :
303 : // Call the partitioning function
304 0 : this->_do_repartition(mesh,n_parts);
305 :
306 : // Set the parent's processor ids
307 0 : Partitioner::set_parent_processor_ids(mesh);
308 :
309 : // Set the node's processor ids
310 0 : Partitioner::set_node_processor_ids(mesh);
311 :
312 : // Give derived Mesh classes a chance to update any cached data to
313 : // reflect the new partitioning
314 0 : mesh.update_post_partitioning();
315 : }
316 :
317 :
318 :
319 :
320 :
321 209515 : bool Partitioner::single_partition (MeshBase & mesh)
322 : {
323 : bool changed_pid =
324 412560 : this->single_partition_range(mesh.elements_begin(),
325 615941 : mesh.elements_end());
326 :
327 : // If we have a distributed mesh with an empty rank (or where rank
328 : // 0 has only its own component of a disconnected mesh, I guess),
329 : // that rank might need to be informed of a change.
330 209515 : mesh.comm().max(changed_pid);
331 :
332 209515 : if (changed_pid)
333 : {
334 : // Ghosting functors may iterate over local elements while we
335 : // redistribute, so cached local ranges must reflect the new
336 : // element processor ids
337 201510 : mesh.update_post_partitioning();
338 :
339 : // We may need to redistribute, in case someone (like our unit
340 : // tests) is doing something silly (like moving a whole
341 : // already-distributed mesh back onto rank 0).
342 201510 : mesh.redistribute();
343 :
344 : // Even single_partition can be a change, if we're starting with
345 : // any unpartitioned elements or nodes
346 201510 : mesh.update_post_partitioning();
347 : }
348 :
349 209515 : return changed_pid;
350 : }
351 :
352 :
353 :
354 209515 : bool Partitioner::single_partition_range (MeshBase::element_iterator it,
355 : MeshBase::element_iterator end)
356 : {
357 12604 : LOG_SCOPE("single_partition_range()", "Partitioner");
358 :
359 6470 : bool changed_pid = false;
360 :
361 3497220 : for (auto & elem : as_range(it, end))
362 : {
363 1556455 : if (elem->processor_id())
364 14878 : changed_pid = true;
365 1556455 : elem->processor_id() = 0;
366 :
367 : // Assign all this element's nodes to processor 0 as well.
368 13358132 : for (Node & node : elem->node_ref_range())
369 : {
370 11801677 : if (node.processor_id())
371 58969 : changed_pid = true;
372 11801677 : node.processor_id() = 0;
373 : }
374 196911 : }
375 :
376 215985 : return changed_pid;
377 : }
378 :
379 0 : void Partitioner::partition_unpartitioned_elements (MeshBase & mesh)
380 : {
381 0 : Partitioner::partition_unpartitioned_elements(mesh, mesh.n_processors());
382 0 : }
383 :
384 :
385 :
386 0 : void Partitioner::partition_unpartitioned_elements (MeshBase & mesh,
387 : const unsigned int n_subdomains)
388 : {
389 0 : Partitioner::partition_unpartitioned_elements(mesh, n_subdomains,
390 : /*spatial_indexing=*/true);
391 0 : }
392 :
393 :
394 :
395 681933 : void Partitioner::partition_unpartitioned_elements (MeshBase & mesh,
396 : const unsigned int n_subdomains,
397 : const bool spatial_indexing)
398 : {
399 681933 : MeshBase::element_iterator it = mesh.unpartitioned_elements_begin();
400 681933 : const MeshBase::element_iterator end = mesh.unpartitioned_elements_end();
401 :
402 1351811 : const dof_id_type n_unpartitioned_elements = MeshTools::n_elem (it, end);
403 :
404 : // the unpartitioned elements must exist on all processors. If the range is empty on one
405 : // it is empty on all, and we can quit right here.
406 681933 : if (!n_unpartitioned_elements)
407 3843 : return;
408 :
409 : // find the target subdomain sizes
410 298016 : std::vector<dof_id_type> subdomain_bounds(mesh.n_processors());
411 :
412 3100516 : for (auto pid : make_range(mesh.n_processors()))
413 : {
414 16424 : dof_id_type tgt_subdomain_size = 0;
415 :
416 : // watch out for the case that n_subdomains < n_processors
417 2818924 : if (pid < n_subdomains)
418 : {
419 1549269 : tgt_subdomain_size = n_unpartitioned_elements/n_subdomains;
420 :
421 1549269 : if (pid < n_unpartitioned_elements%n_subdomains)
422 440511 : tgt_subdomain_size++;
423 :
424 : }
425 :
426 : //libMesh::out << "pid, #= " << pid << ", " << tgt_subdomain_size << std::endl;
427 2818924 : if (pid == 0)
428 281592 : subdomain_bounds[0] = tgt_subdomain_size;
429 : else
430 2553756 : subdomain_bounds[pid] = subdomain_bounds[pid-1] + tgt_subdomain_size;
431 : }
432 :
433 8212 : libmesh_assert_equal_to (subdomain_bounds.back(), n_unpartitioned_elements);
434 :
435 : // create the unique mapping for all unpartitioned elements independent of partitioning
436 : // determine the global indexing for all the unpartitioned elements
437 16424 : std::vector<dof_id_type> global_indices;
438 :
439 : // Calling this on all processors a unique range in [0,n_unpartitioned_elements) is constructed.
440 : // Only the indices for the elements we pass in are returned in the array.
441 : // Without the spatial indexing an element's position in the traversal of the range is used
442 : // instead, which a replicated mesh reaches in the same order on every processor and which
443 : // therefore indexes [0, n_unpartitioned_elements) just as uniquely, at no cost.
444 281592 : if (spatial_indexing)
445 242034 : MeshCommunication().find_global_indices (mesh.comm(),
446 484068 : MeshTools::create_bounding_box(mesh), it, end,
447 : global_indices);
448 : else
449 7990 : libmesh_assert (mesh.is_replicated());
450 :
451 8212 : dof_id_type cnt=0;
452 14280200 : for (auto & elem : as_range(it, end))
453 : {
454 381202 : libmesh_assert (!spatial_indexing || cnt < global_indices.size());
455 : const dof_id_type global_index =
456 13725228 : spatial_indexing ? global_indices[cnt++] : cnt++;
457 :
458 381202 : libmesh_assert_less (global_index, subdomain_bounds.back());
459 381202 : libmesh_assert_less (global_index, n_unpartitioned_elements);
460 :
461 : const processor_id_type subdomain_id =
462 : cast_int<processor_id_type>
463 13344026 : (std::distance(subdomain_bounds.begin(),
464 : std::upper_bound(subdomain_bounds.begin(),
465 : subdomain_bounds.end(),
466 381202 : global_index)));
467 381202 : libmesh_assert_less (subdomain_id, n_subdomains);
468 :
469 13725228 : elem->processor_id() = subdomain_id;
470 : //libMesh::out << "assigning " << global_index << " to " << subdomain_id << std::endl;
471 265168 : }
472 :
473 : // Even a temporary partitioning may invalidate some mesh caches
474 281592 : mesh.update_post_partitioning();
475 : }
476 :
477 :
478 :
479 681933 : void Partitioner::set_parent_processor_ids(MeshBase & mesh)
480 : {
481 : // Ignore the parameter when !LIBMESH_ENABLE_AMR
482 12055 : libmesh_ignore(mesh);
483 :
484 36165 : LOG_SCOPE("set_parent_processor_ids()", "Partitioner");
485 :
486 : #ifdef LIBMESH_ENABLE_AMR
487 :
488 : // If the mesh is serial we have access to all the elements,
489 : // in particular all the active ones. We can therefore set
490 : // the parent processor ids indirectly through their children, and
491 : // set the subactive processor ids while examining their active
492 : // ancestors.
493 : // By convention a parent is assigned to the minimum processor
494 : // of all its children, and a subactive is assigned to the processor
495 : // of its active ancestor.
496 681933 : if (mesh.is_serial())
497 : {
498 53428673 : for (auto & elem : mesh.active_element_ptr_range())
499 : {
500 : // First set descendents
501 2289324 : std::vector<Elem *> subactive_family;
502 27263307 : elem->total_family_tree(subactive_family);
503 55778862 : for (const auto & f : subactive_family)
504 28515555 : f->processor_id() = elem->processor_id();
505 :
506 : // Then set ancestors
507 27263307 : Elem * parent = elem->parent();
508 :
509 60072858 : while (parent)
510 : {
511 : // invalidate the parent id, otherwise the min below
512 : // will not work if the current parent id is less
513 : // than all the children!
514 1988172 : parent->invalidate_processor_id();
515 :
516 170469589 : for (auto & child : parent->child_ref_range())
517 : {
518 9496996 : libmesh_assert(!child.is_remote());
519 9496996 : libmesh_assert_not_equal_to (child.processor_id(), DofObject::invalid_processor_id);
520 137660038 : parent->processor_id() = std::min(parent->processor_id(),
521 9496996 : child.processor_id());
522 : }
523 3976344 : parent = parent->parent();
524 : }
525 577807 : }
526 : }
527 :
528 : // When the mesh is parallel we cannot guarantee that parents have access to
529 : // all their children.
530 : else
531 : {
532 : // Setting subactive processor ids is easy: we can guarantee
533 : // that children have access to all their parents.
534 :
535 : // Loop over all the active elements in the mesh
536 11038344 : for (auto & child : mesh.active_element_ptr_range())
537 : {
538 22788 : std::vector<Elem *> subactive_family;
539 5450352 : child->total_family_tree(subactive_family);
540 10904445 : for (const auto & f : subactive_family)
541 5454093 : f->processor_id() = child->processor_id();
542 80016 : }
543 :
544 : // When the mesh is parallel we cannot guarantee that parents have access to
545 : // all their children.
546 :
547 : // We will use a brute-force approach here. Each processor finds its parent
548 : // elements and sets the parent pid to the minimum of its
549 : // semilocal descendants.
550 : // A global reduction is then performed to make sure the true minimum is found.
551 : // As noted, this is required because we cannot guarantee that a parent has
552 : // access to all its children on any single processor.
553 132 : libmesh_parallel_only(mesh.comm());
554 132 : libmesh_assert(MeshTools::n_elem(mesh.unpartitioned_elements_begin(),
555 : mesh.unpartitioned_elements_end()) == 0);
556 :
557 80280 : const dof_id_type max_elem_id = mesh.max_elem_id();
558 :
559 : std::vector<processor_id_type>
560 264 : parent_processor_ids (std::min(communication_blocksize,
561 80412 : max_elem_id));
562 :
563 160560 : for (dof_id_type blk=0, last_elem_id=0; last_elem_id<max_elem_id; blk++)
564 : {
565 80280 : last_elem_id =
566 80412 : std::min(static_cast<dof_id_type>((blk+1)*communication_blocksize),
567 132 : max_elem_id);
568 80280 : const dof_id_type first_elem_id = blk*communication_blocksize;
569 :
570 132 : std::fill (parent_processor_ids.begin(),
571 : parent_processor_ids.end(),
572 : DofObject::invalid_processor_id);
573 :
574 : // first build up local contributions to parent_processor_ids
575 132 : bool have_parent_in_block = false;
576 :
577 161420 : for (auto & parent : as_range(mesh.ancestor_elements_begin(),
578 1696412 : mesh.ancestor_elements_end()))
579 : {
580 688274 : const dof_id_type parent_idx = parent->id();
581 992 : libmesh_assert_less (parent_idx, max_elem_id);
582 :
583 689266 : if ((parent_idx >= first_elem_id) &&
584 688274 : (parent_idx < last_elem_id))
585 : {
586 992 : have_parent_in_block = true;
587 688274 : processor_id_type parent_pid = DofObject::invalid_processor_id;
588 :
589 992 : std::vector<const Elem *> active_family;
590 688274 : parent->active_family_tree(active_family);
591 7915583 : for (const auto & f : active_family)
592 8014165 : parent_pid = std::min (parent_pid, f->processor_id());
593 :
594 688274 : const dof_id_type packed_idx = parent_idx - first_elem_id;
595 992 : libmesh_assert_less (packed_idx, parent_processor_ids.size());
596 :
597 689266 : parent_processor_ids[packed_idx] = parent_pid;
598 : }
599 80016 : }
600 :
601 : // then find the global minimum
602 80280 : mesh.comm().min (parent_processor_ids);
603 :
604 : // and assign the ids, if we have a parent in this block.
605 80280 : if (have_parent_in_block)
606 50626 : for (auto & parent : as_range(mesh.ancestor_elements_begin(),
607 1474824 : mesh.ancestor_elements_end()))
608 : {
609 688274 : const dof_id_type parent_idx = parent->id();
610 :
611 689266 : if ((parent_idx >= first_elem_id) &&
612 687282 : (parent_idx < last_elem_id))
613 : {
614 688274 : const dof_id_type packed_idx = parent_idx - first_elem_id;
615 992 : libmesh_assert_less (packed_idx, parent_processor_ids.size());
616 :
617 : const processor_id_type parent_pid =
618 688274 : parent_processor_ids[packed_idx];
619 :
620 992 : libmesh_assert_not_equal_to (parent_pid, DofObject::invalid_processor_id);
621 :
622 688274 : parent->processor_id() = parent_pid;
623 : }
624 24739 : }
625 : }
626 : }
627 :
628 : #endif // LIBMESH_ENABLE_AMR
629 681933 : }
630 :
631 : void
632 0 : Partitioner::processor_pairs_to_interface_nodes(MeshBase & mesh,
633 : std::map<std::pair<processor_id_type, processor_id_type>, std::set<dof_id_type>> & processor_pair_to_nodes)
634 : {
635 : // This function must be run on all processors at once
636 0 : libmesh_parallel_only(mesh.comm());
637 :
638 0 : processor_pair_to_nodes.clear();
639 :
640 0 : std::set<dof_id_type> mynodes;
641 0 : std::set<dof_id_type> neighbor_nodes;
642 0 : std::vector<dof_id_type> common_nodes;
643 :
644 : // Loop over all the active elements
645 0 : for (auto & elem : mesh.active_element_ptr_range())
646 : {
647 0 : libmesh_assert(elem);
648 :
649 0 : libmesh_assert_not_equal_to (elem->processor_id(), DofObject::invalid_processor_id);
650 :
651 0 : auto n_nodes = elem->n_nodes();
652 :
653 : // prepare data for this element
654 0 : mynodes.clear();
655 0 : neighbor_nodes.clear();
656 0 : common_nodes.clear();
657 :
658 0 : for (unsigned int inode = 0; inode < n_nodes; inode++)
659 0 : mynodes.insert(elem->node_id(inode));
660 :
661 0 : for (auto i : elem->side_index_range())
662 : {
663 0 : auto neigh = elem->neighbor_ptr(i);
664 0 : if (neigh && !neigh->is_remote() && neigh->processor_id() != elem->processor_id())
665 : {
666 0 : neighbor_nodes.clear();
667 0 : common_nodes.clear();
668 0 : auto neigh_n_nodes = neigh->n_nodes();
669 0 : for (unsigned int inode = 0; inode < neigh_n_nodes; inode++)
670 0 : neighbor_nodes.insert(neigh->node_id(inode));
671 :
672 0 : std::set_intersection(mynodes.begin(), mynodes.end(),
673 : neighbor_nodes.begin(), neighbor_nodes.end(),
674 0 : std::back_inserter(common_nodes));
675 :
676 0 : auto & map_set = processor_pair_to_nodes[std::make_pair(std::min(elem->processor_id(), neigh->processor_id()),
677 0 : std::max(elem->processor_id(), neigh->processor_id()))];
678 0 : for (auto global_node_id : common_nodes)
679 0 : map_set.insert(global_node_id);
680 : }
681 : }
682 0 : }
683 0 : }
684 :
685 0 : void Partitioner::set_interface_node_processor_ids_linear(MeshBase & mesh)
686 : {
687 : // This function must be run on all processors at once
688 0 : libmesh_parallel_only(mesh.comm());
689 :
690 0 : std::map<std::pair<processor_id_type, processor_id_type>, std::set<dof_id_type>> processor_pair_to_nodes;
691 :
692 0 : processor_pairs_to_interface_nodes(mesh, processor_pair_to_nodes);
693 :
694 0 : for (auto & pmap : processor_pair_to_nodes)
695 : {
696 0 : std::size_t n_own_nodes = pmap.second.size()/2, i = 0;
697 :
698 0 : for (dof_id_type id : pmap.second)
699 : {
700 0 : auto & node = mesh.node_ref(id);
701 0 : if (i <= n_own_nodes)
702 0 : node.processor_id() = pmap.first.first;
703 : else
704 0 : node.processor_id() = pmap.first.second;
705 0 : i++;
706 : }
707 : }
708 0 : }
709 :
710 0 : void Partitioner::set_interface_node_processor_ids_BFS(MeshBase & mesh)
711 : {
712 : // This function must be run on all processors at once
713 0 : libmesh_parallel_only(mesh.comm());
714 :
715 : // I see occasional consistency failures when using this on a
716 : // distributed mesh
717 : libmesh_experimental();
718 :
719 0 : std::map<std::pair<processor_id_type, processor_id_type>, std::set<dof_id_type>> processor_pair_to_nodes;
720 :
721 0 : processor_pairs_to_interface_nodes(mesh, processor_pair_to_nodes);
722 :
723 0 : std::unordered_map<dof_id_type, std::vector<const Elem *>> nodes_to_elem_map;
724 :
725 0 : MeshTools::build_nodes_to_elem_map(mesh, nodes_to_elem_map);
726 :
727 0 : std::vector<const Node *> neighbors;
728 0 : std::set<dof_id_type> neighbors_order;
729 0 : std::vector<dof_id_type> common_nodes;
730 0 : std::queue<dof_id_type> nodes_queue;
731 0 : std::set<dof_id_type> visted_nodes;
732 :
733 0 : for (auto & pmap : processor_pair_to_nodes)
734 : {
735 0 : std::size_t n_own_nodes = pmap.second.size()/2;
736 :
737 : // Initialize node assignment
738 0 : for (dof_id_type id : pmap.second)
739 0 : mesh.node_ref(id).processor_id() = pmap.first.second;
740 :
741 0 : visted_nodes.clear();
742 0 : for (dof_id_type id : pmap.second)
743 : {
744 0 : mesh.node_ref(id).processor_id() = pmap.first.second;
745 :
746 0 : if (visted_nodes.count(id))
747 0 : continue;
748 : else
749 : {
750 0 : nodes_queue.push(id);
751 0 : visted_nodes.insert(id);
752 0 : if (visted_nodes.size() >= n_own_nodes)
753 0 : break;
754 : }
755 :
756 0 : while (!nodes_queue.empty())
757 : {
758 0 : auto & node = mesh.node_ref(nodes_queue.front());
759 0 : nodes_queue.pop();
760 :
761 0 : neighbors.clear();
762 0 : MeshTools::find_nodal_neighbors(mesh, node, nodes_to_elem_map, neighbors);
763 0 : neighbors_order.clear();
764 0 : for (auto & neighbor : neighbors)
765 0 : neighbors_order.insert(neighbor->id());
766 :
767 0 : common_nodes.clear();
768 0 : std::set_intersection(pmap.second.begin(), pmap.second.end(),
769 : neighbors_order.begin(), neighbors_order.end(),
770 0 : std::back_inserter(common_nodes));
771 :
772 0 : for (auto c_node : common_nodes)
773 0 : if (!visted_nodes.count(c_node))
774 : {
775 0 : nodes_queue.push(c_node);
776 0 : visted_nodes.insert(c_node);
777 0 : if (visted_nodes.size() >= n_own_nodes)
778 0 : goto queue_done;
779 : }
780 :
781 0 : if (visted_nodes.size() >= n_own_nodes)
782 0 : goto queue_done;
783 : }
784 : }
785 0 : queue_done:
786 0 : for (auto node : visted_nodes)
787 0 : mesh.node_ref(node).processor_id() = pmap.first.first;
788 : }
789 0 : }
790 :
791 0 : void Partitioner::set_interface_node_processor_ids_petscpartitioner(MeshBase & mesh)
792 : {
793 0 : libmesh_ignore(mesh); // Only used if LIBMESH_HAVE_PETSC
794 :
795 : // This function must be run on all processors at once
796 0 : libmesh_parallel_only(mesh.comm());
797 :
798 : #ifdef LIBMESH_HAVE_PETSC
799 0 : std::map<std::pair<processor_id_type, processor_id_type>, std::set<dof_id_type>> processor_pair_to_nodes;
800 :
801 0 : processor_pairs_to_interface_nodes(mesh, processor_pair_to_nodes);
802 :
803 0 : std::vector<std::vector<const Elem *>> nodes_to_elem_map;
804 :
805 0 : MeshTools::build_nodes_to_elem_map(mesh, nodes_to_elem_map);
806 :
807 0 : std::vector<const Node *> neighbors;
808 0 : std::set<dof_id_type> neighbors_order;
809 0 : std::vector<dof_id_type> common_nodes;
810 :
811 0 : std::vector<dof_id_type> rows;
812 0 : std::vector<dof_id_type> cols;
813 :
814 0 : std::map<dof_id_type, dof_id_type> global_to_local;
815 :
816 0 : for (auto & pmap : processor_pair_to_nodes)
817 : {
818 0 : unsigned int i = 0;
819 :
820 0 : rows.clear();
821 0 : rows.resize(pmap.second.size()+1);
822 0 : cols.clear();
823 0 : for (dof_id_type id : pmap.second)
824 0 : global_to_local[id] = i++;
825 :
826 0 : i = 0;
827 0 : for (auto id : pmap.second)
828 : {
829 0 : auto & node = mesh.node_ref(id);
830 0 : neighbors.clear();
831 0 : MeshTools::find_nodal_neighbors(mesh, node, nodes_to_elem_map, neighbors);
832 0 : neighbors_order.clear();
833 0 : for (auto & neighbor : neighbors)
834 0 : neighbors_order.insert(neighbor->id());
835 :
836 0 : common_nodes.clear();
837 0 : std::set_intersection(pmap.second.begin(), pmap.second.end(),
838 : neighbors_order.begin(), neighbors_order.end(),
839 0 : std::back_inserter(common_nodes));
840 :
841 0 : rows[i+1] = rows[i] + cast_int<dof_id_type>(common_nodes.size());
842 :
843 0 : for (auto c_node : common_nodes)
844 0 : cols.push_back(global_to_local[c_node]);
845 :
846 0 : i++;
847 : }
848 :
849 : // Next we construct an IS from a MatPartitioning
850 0 : WrappedPetsc<IS> is;
851 : {
852 : PetscInt *adj_i, *adj_j;
853 0 : LibmeshPetscCall2(mesh.comm(), PetscCalloc1(rows.size(), &adj_i));
854 0 : LibmeshPetscCall2(mesh.comm(), PetscCalloc1(cols.size(), &adj_j));
855 0 : PetscInt rows_size = cast_int<PetscInt>(rows.size());
856 0 : for (PetscInt ii=0; ii<rows_size; ii++)
857 0 : adj_i[ii] = rows[ii];
858 :
859 0 : PetscInt cols_size = cast_int<PetscInt>(cols.size());
860 0 : for (PetscInt ii=0; ii<cols_size; ii++)
861 0 : adj_j[ii] = cols[ii];
862 :
863 0 : const PetscInt sz = cast_int<PetscInt>(pmap.second.size());
864 :
865 : // Create sparse matrix representing an adjacency list
866 0 : WrappedPetsc<Mat> adj;
867 0 : LibmeshPetscCall2(mesh.comm(), MatCreateMPIAdj(PETSC_COMM_SELF, sz, sz, adj_i, adj_j, nullptr, adj.get()));
868 :
869 : // Create MatPartitioning object
870 0 : WrappedPetsc<MatPartitioning> part;
871 0 : LibmeshPetscCall2(mesh.comm(), MatPartitioningCreate(PETSC_COMM_SELF, part.get()));
872 :
873 : // Apply MatPartitioning, storing results in "is"
874 0 : LibmeshPetscCall2(mesh.comm(), MatPartitioningSetAdjacency(part, adj));
875 0 : LibmeshPetscCall2(mesh.comm(), MatPartitioningSetNParts(part, 2));
876 0 : LibmeshPetscCall2(mesh.comm(), PetscObjectSetOptionsPrefix((PetscObject)(*part), "balance_"));
877 0 : LibmeshPetscCall2(mesh.comm(), MatPartitioningSetFromOptions(part));
878 0 : LibmeshPetscCall2(mesh.comm(), MatPartitioningApply(part, is.get()));
879 : }
880 :
881 : PetscInt local_size;
882 : const PetscInt *indices;
883 0 : LibmeshPetscCall2(mesh.comm(), ISGetLocalSize(is, &local_size));
884 0 : LibmeshPetscCall2(mesh.comm(), ISGetIndices(is, &indices));
885 :
886 0 : i = 0;
887 0 : for (auto id : pmap.second)
888 : {
889 0 : auto & node = mesh.node_ref(id);
890 0 : if (indices[i])
891 0 : node.processor_id() = pmap.first.second;
892 : else
893 0 : node.processor_id() = pmap.first.first;
894 :
895 0 : i++;
896 : }
897 0 : LibmeshPetscCall2(mesh.comm(), ISRestoreIndices(is, &indices));
898 : }
899 : #else
900 0 : libmesh_error_msg("PETSc is required");
901 : #endif
902 0 : }
903 :
904 :
905 720613 : void Partitioner::set_node_processor_ids(MeshBase & mesh)
906 : {
907 42165 : LOG_SCOPE("set_node_processor_ids()","Partitioner");
908 :
909 : // This function must be run on all processors at once
910 14055 : libmesh_parallel_only(mesh.comm());
911 :
912 : // If we have any unpartitioned elements at this
913 : // stage there is a problem
914 14055 : libmesh_assert (MeshTools::n_elem(mesh.unpartitioned_elements_begin(),
915 : mesh.unpartitioned_elements_end()) == 0);
916 :
917 : // Start from scratch here: nodes we used to own may not be
918 : // eligible for us to own any more.
919 : Threads::parallel_for_each
920 720613 : (mesh.node_stored_range(), [](Node * node)
921 96318723 : { node->processor_id() = DofObject::invalid_processor_id; });
922 :
923 : // Loop over all the active elements
924 79883911 : for (auto & elem : mesh.active_element_ptr_range())
925 : {
926 1790652 : libmesh_assert(elem);
927 :
928 1790652 : libmesh_assert_not_equal_to (elem->processor_id(), DofObject::invalid_processor_id);
929 :
930 : // Consider updating the processor id on this element's nodes
931 360654386 : for (Node & node : elem->node_ref_range())
932 : {
933 12792791 : processor_id_type & pid = node.processor_id();
934 317844712 : pid = node.choose_processor_id(pid, elem->processor_id());
935 : }
936 692503 : }
937 :
938 : // How we finish off the node partitioning depends on our command
939 : // line options.
940 :
941 : const bool load_balanced_nodes_linear =
942 720613 : libMesh::on_command_line ("--load-balanced-nodes-linear");
943 :
944 : const bool load_balanced_nodes_bfs =
945 720613 : libMesh::on_command_line ("--load-balanced-nodes-bfs");
946 :
947 : const bool load_balanced_nodes_petscpartition =
948 720613 : libMesh::on_command_line ("--load-balanced-nodes-petscpartitioner");
949 :
950 720613 : unsigned int n_load_balance_options = load_balanced_nodes_linear;
951 720613 : n_load_balance_options += load_balanced_nodes_bfs;
952 720613 : n_load_balance_options += load_balanced_nodes_petscpartition;
953 720613 : libmesh_error_msg_if(n_load_balance_options > 1,
954 : "Cannot perform more than one load balancing type at a time");
955 :
956 720613 : if (load_balanced_nodes_linear)
957 0 : set_interface_node_processor_ids_linear(mesh);
958 720613 : else if (load_balanced_nodes_bfs)
959 0 : set_interface_node_processor_ids_BFS(mesh);
960 720613 : else if (load_balanced_nodes_petscpartition)
961 0 : set_interface_node_processor_ids_petscpartitioner(mesh);
962 :
963 : // Node balancing algorithm will response to assign owned nodes.
964 : // We still need to sync PIDs
965 : {
966 : // For inactive elements, we will have already gotten most of
967 : // these nodes, *except* for the case of a parent with a subset
968 : // of active descendants which are remote elements. In that
969 : // case some of the parent nodes will not have been properly
970 : // handled yet on our processor.
971 : //
972 : // We don't want to inadvertently give one of them an incorrect
973 : // processor id, but if we're not in serial then we have to
974 : // assign them temporary pids to make querying work, so we'll
975 : // save our *valid* pids before assigning temporaries.
976 : //
977 : // Even in serial we'll want to check and make sure we're not
978 : // overwriting valid active node pids with pids from subactive
979 : // elements.
980 28110 : std::unordered_set<dof_id_type> bad_pids;
981 28110 : Threads::spin_mutex pid_mtx;
982 :
983 : Threads::parallel_for
984 720613 : (mesh.node_stored_range(),
985 2149190 : [&bad_pids, &pid_mtx](const NodeRange & range)
986 : {
987 28522 : std::unordered_set<dof_id_type> my_bad_pids;
988 99737246 : for (const Node * node : range)
989 99016033 : if (node->processor_id() == DofObject::invalid_processor_id)
990 1962176 : my_bad_pids.insert(node->id());
991 :
992 28522 : Threads::spin_mutex::scoped_lock lock(pid_mtx);
993 :
994 14261 : bad_pids.merge(my_bad_pids);
995 721213 : });
996 :
997 : // If we assign our temporary ids by looping from finer elements
998 : // to coarser elements, we'll always get an id from the finest
999 : // ghost element we can see, which will usually be "closer" to
1000 : // the true processor we want to query and so will reduce query
1001 : // cycles that don't reach that processor.
1002 :
1003 : // But we can still end up with a query cycle that dead-ends, so
1004 : // we need to prepare a "push" communication step here.
1005 :
1006 720613 : const bool is_serial = mesh.is_serial();
1007 : std::unordered_map
1008 : <processor_id_type,
1009 : std::unordered_map<dof_id_type, processor_id_type>>
1010 28110 : potential_pids;
1011 :
1012 720613 : const unsigned int n_levels = MeshTools::n_levels(mesh);
1013 1664882 : for (unsigned int level = n_levels; level > 0; --level)
1014 : {
1015 4046021 : for (auto & elem : as_range(mesh.level_elements_begin(level-1),
1016 98653394 : mesh.level_elements_end(level-1)))
1017 : {
1018 2180180 : libmesh_assert_not_equal_to (elem->processor_id(),
1019 : DofObject::invalid_processor_id);
1020 :
1021 48550946 : const processor_id_type elem_pid = elem->processor_id();
1022 :
1023 : // Consider updating the processor id on this element's nodes
1024 401564116 : for (Node & node : elem->node_ref_range())
1025 : {
1026 14739533 : processor_id_type & pid = node.processor_id();
1027 353013170 : if (bad_pids.count(node.id()))
1028 5335487 : pid = node.choose_processor_id(pid, elem_pid);
1029 347677683 : else if (!is_serial)
1030 62282688 : potential_pids[elem_pid][node.id()] = pid;
1031 : }
1032 898875 : }
1033 : }
1034 :
1035 720613 : if (!is_serial)
1036 : {
1037 : std::unordered_map
1038 : <processor_id_type,
1039 : std::vector<std::pair<dof_id_type, processor_id_type>>>
1040 146 : potential_pids_vecs;
1041 :
1042 676576 : for (auto & pair : potential_pids)
1043 584407 : potential_pids_vecs[pair.first].assign(pair.second.begin(), pair.second.end());
1044 :
1045 : auto pids_action_functor =
1046 583863 : [& mesh, & bad_pids]
1047 : (processor_id_type /* src_pid */,
1048 24224239 : const std::vector<std::pair<dof_id_type, processor_id_type>> & data)
1049 : {
1050 24702721 : for (auto pair : data)
1051 : {
1052 24118314 : Node & node = mesh.node_ref(pair.first);
1053 35209 : processor_id_type & pid = node.processor_id();
1054 24118314 : if (const auto it = bad_pids.find(pair.first);
1055 35209 : it != bad_pids.end())
1056 : {
1057 15803 : pid = pair.second;
1058 26 : bad_pids.erase(it);
1059 : }
1060 : else
1061 24102511 : pid = node.choose_processor_id(pid, pair.second);
1062 : }
1063 92567 : };
1064 :
1065 : Parallel::push_parallel_vector_data
1066 92169 : (mesh.comm(), potential_pids_vecs, pids_action_functor);
1067 :
1068 : // Using default libMesh options, we'll just need to sync
1069 : // between processors now. The catch here is that we can't
1070 : // initially trust Node::choose_processor_id() because some
1071 : // of those node processor ids are the temporary ones.
1072 146 : CorrectProcIds correct_pids(mesh, bad_pids);
1073 : Parallel::sync_node_data_by_element_id
1074 276215 : (mesh, mesh.elements_begin(), mesh.elements_end(),
1075 92023 : Parallel::SyncEverything(), Parallel::SyncEverything(),
1076 : correct_pids);
1077 :
1078 : // But once we've got all the non-temporary pids synced, we
1079 : // may need to sync again to get any pids on nodes only
1080 : // connected to subactive elements, for which *only*
1081 : // "temporary" pids are possible.
1082 146 : bad_pids.clear();
1083 : Parallel::sync_node_data_by_element_id
1084 184338 : (mesh,
1085 276653 : mesh.elements_begin(), mesh.elements_end(),
1086 92169 : Parallel::SyncEverything(), Parallel::SyncEverything(),
1087 : correct_pids);
1088 : }
1089 : }
1090 :
1091 : // We can't assert that all nodes are connected to elements, because
1092 : // a DistributedMesh with NodeConstraints might have pulled in some
1093 : // remote nodes solely for evaluating those constraints.
1094 : // MeshTools::libmesh_assert_connected_nodes(mesh);
1095 :
1096 : #ifdef DEBUG
1097 14055 : MeshTools::libmesh_assert_valid_procids<Node>(mesh);
1098 : //MeshTools::libmesh_assert_canonical_node_procids(mesh);
1099 : #endif
1100 720613 : }
1101 :
1102 :
1103 :
1104 : struct SyncLocalIDs
1105 : {
1106 : typedef dof_id_type datum;
1107 :
1108 : typedef std::unordered_map<dof_id_type, dof_id_type> map_type;
1109 :
1110 671178 : SyncLocalIDs(map_type & _id_map) : id_map(_id_map) {}
1111 :
1112 : map_type & id_map;
1113 :
1114 3436876 : void gather_data (const std::vector<dof_id_type> & ids,
1115 : std::vector<datum> & local_ids) const
1116 : {
1117 3437642 : local_ids.resize(ids.size());
1118 :
1119 32896790 : for (auto i : index_range(ids))
1120 29459914 : local_ids[i] = id_map[ids[i]];
1121 3436876 : }
1122 :
1123 3436876 : void act_on_data (const std::vector<dof_id_type> & ids,
1124 : const std::vector<datum> & local_ids)
1125 : {
1126 32896790 : for (auto i : index_range(local_ids))
1127 29475834 : id_map[ids[i]] = local_ids[i];
1128 3436876 : }
1129 : };
1130 :
1131 671178 : void Partitioner::_find_global_index_by_pid_map(const MeshBase & mesh)
1132 : {
1133 671178 : const dof_id_type n_active_local_elem = mesh.n_active_local_elem();
1134 :
1135 : // Find the number of active elements on each processor. We cannot use
1136 : // mesh.n_active_elem_on_proc(pid) since that only returns the number of
1137 : // elements assigned to pid which are currently stored on the calling
1138 : // processor. This will not in general be correct for parallel meshes
1139 : // when (pid!=mesh.processor_id()).
1140 1560 : auto n_proc = mesh.n_processors();
1141 671178 : _n_active_elem_on_proc.resize(n_proc);
1142 671178 : mesh.comm().allgather(n_active_local_elem, _n_active_elem_on_proc);
1143 :
1144 672738 : std::vector<dof_id_type> n_active_elem_before_proc(mesh.n_processors());
1145 :
1146 7213110 : for (auto i : make_range(n_proc-1))
1147 6541932 : n_active_elem_before_proc[i+1] =
1148 6543492 : n_active_elem_before_proc[i] + _n_active_elem_on_proc[i];
1149 :
1150 : libMesh::BoundingBox bbox =
1151 671178 : MeshTools::create_bounding_box(mesh);
1152 :
1153 780 : _global_index_by_pid_map.clear();
1154 :
1155 : // create the mapping which is contiguous by processor
1156 671178 : MeshCommunication().find_local_indices (bbox,
1157 1342356 : mesh.active_local_elements_begin(),
1158 1341576 : mesh.active_local_elements_end(),
1159 671178 : _global_index_by_pid_map);
1160 :
1161 780 : SyncLocalIDs sync(_global_index_by_pid_map);
1162 :
1163 : Parallel::sync_dofobject_data_by_id
1164 1341576 : (mesh.comm(), mesh.active_elements_begin(), mesh.active_elements_end(), sync);
1165 :
1166 36478606 : for (const auto & elem : mesh.active_element_ptr_range())
1167 : {
1168 35137030 : const processor_id_type pid = elem->processor_id();
1169 39588 : libmesh_assert_less (_global_index_by_pid_map[elem->id()], _n_active_elem_on_proc[pid]);
1170 :
1171 35176618 : _global_index_by_pid_map[elem->id()] += n_active_elem_before_proc[pid];
1172 669618 : }
1173 671178 : }
1174 :
1175 335589 : void Partitioner::build_graph (const MeshBase & mesh)
1176 : {
1177 1170 : LOG_SCOPE("build_graph()", "Partitioner");
1178 :
1179 390 : const dof_id_type n_active_local_elem = mesh.n_active_local_elem();
1180 :
1181 : // If we have boundary elements in this mesh, we want to account for
1182 : // the connectivity between them and interior elements. We can find
1183 : // interior elements from boundary elements, but we need to build up
1184 : // a lookup map to do the reverse.
1185 : typedef std::unordered_multimap<const Elem *, const Elem *> map_type;
1186 780 : map_type interior_to_boundary_map;
1187 :
1188 : // If we have spline nodes in this mesh, we want to account for the
1189 : // connectivity between them and integration elements. We can find
1190 : // spline nodes from integration elements, but need a reverse map
1191 : // {integration_elements} = elems_constrained_by[spline_nodeelem]
1192 780 : map_type elems_constrained_by;
1193 :
1194 390 : const auto & mesh_constrained_nodes = mesh.get_constraint_rows();
1195 :
1196 53316951 : for (const Elem * elem : mesh.active_element_ptr_range())
1197 : {
1198 17568515 : if (!mesh_constrained_nodes.empty()) // quick test for non-IGA cases
1199 : {
1200 0 : const auto end_it = mesh_constrained_nodes.end();
1201 :
1202 : // Use a set to avoid duplicates. Use a well-defined method
1203 : // of ordering that set to make debugging easier.
1204 0 : std::set<const Elem *, CompareElemIdsByLevel> constraining_elems;
1205 1209774 : for (const Node & node : elem->node_ref_range())
1206 : {
1207 980847 : if (const auto row_it = mesh_constrained_nodes.find(&node);
1208 0 : row_it != end_it)
1209 3947007 : for (const auto & [pr, coef] : row_it->second)
1210 : {
1211 0 : libmesh_ignore(coef); // avoid gcc 7 warning
1212 3093135 : constraining_elems.insert(pr.first);
1213 : }
1214 : }
1215 1584515 : for (const Elem * constraining_elem : constraining_elems)
1216 0 : elems_constrained_by.emplace(constraining_elem, elem);
1217 : }
1218 :
1219 : // If we don't have an interior_parent and we don't have any
1220 : // constrained nodes then there's nothing else to look up.
1221 17568515 : if (elem->interior_parent())
1222 : {
1223 : // get all relevant interior elements
1224 0 : std::set<const Elem *> neighbor_set;
1225 1094 : elem->find_interior_neighbors(neighbor_set);
1226 :
1227 2188 : for (const auto & neighbor : neighbor_set)
1228 0 : interior_to_boundary_map.emplace(neighbor, elem);
1229 : }
1230 334809 : }
1231 :
1232 : #ifdef LIBMESH_ENABLE_AMR
1233 780 : std::vector<const Elem *> neighbors_offspring;
1234 : #endif
1235 :
1236 : // This is costly, and we only need to do it if the mesh has
1237 : // changed since we last partitioned... but the mesh probably has
1238 : // changed since we last partitioned, and if it hasn't we don't
1239 : // have a reliable way to be sure of that.
1240 335589 : _find_global_index_by_pid_map(mesh);
1241 :
1242 390 : dof_id_type first_local_elem = 0;
1243 1971072 : for (auto pid : make_range(mesh.processor_id()))
1244 1635678 : first_local_elem += _n_active_elem_on_proc[pid];
1245 :
1246 335199 : _dual_graph.clear();
1247 335589 : _dual_graph.resize(n_active_local_elem);
1248 335589 : _local_id_to_elem.resize(n_active_local_elem);
1249 :
1250 : // We may need to communicate constraint-row-based connections
1251 : // between processors
1252 : std::unordered_map<processor_id_type,
1253 780 : std::vector<std::pair<dof_id_type, dof_id_type>>> connections_to_push;
1254 :
1255 6324236 : for (const auto & elem : mesh.active_local_element_ptr_range())
1256 : {
1257 11834 : libmesh_assert (_global_index_by_pid_map.count(elem->id()));
1258 : const dof_id_type global_index_by_pid =
1259 2838558 : _global_index_by_pid_map[elem->id()];
1260 :
1261 2838558 : const dof_id_type local_index =
1262 11834 : global_index_by_pid - first_local_elem;
1263 11834 : libmesh_assert_less (local_index, n_active_local_elem);
1264 :
1265 23668 : std::vector<dof_id_type> & graph_row = _dual_graph[local_index];
1266 :
1267 : // Save this off to make it easy to index later
1268 2838558 : _local_id_to_elem[local_index] = const_cast<Elem*>(elem);
1269 :
1270 : // Loop over the element's neighbors. An element
1271 : // adjacency corresponds to a face neighbor
1272 14969400 : for (auto neighbor : elem->neighbor_ptr_range())
1273 : {
1274 12119008 : if (neighbor != nullptr)
1275 : {
1276 : // If the neighbor is active treat it
1277 : // as a connection
1278 50897 : if (neighbor->active())
1279 : {
1280 50770 : libmesh_assert(_global_index_by_pid_map.count(neighbor->id()));
1281 : const dof_id_type neighbor_global_index_by_pid =
1282 10949833 : _global_index_by_pid_map[neighbor->id()];
1283 :
1284 10949833 : graph_row.push_back(neighbor_global_index_by_pid);
1285 : }
1286 :
1287 : #ifdef LIBMESH_ENABLE_AMR
1288 :
1289 : // Otherwise we need to find all of the
1290 : // neighbor's children that are connected to
1291 : // us and add them
1292 : else
1293 : {
1294 : // The side of the neighbor to which
1295 : // we are connected
1296 : const unsigned int ns =
1297 44637 : neighbor->which_neighbor_am_i (elem);
1298 127 : libmesh_assert_less (ns, neighbor->n_neighbors());
1299 :
1300 : // Get all the active children (& grandchildren, etc...)
1301 : // of the neighbor
1302 :
1303 : // FIXME - this is the wrong thing, since we
1304 : // should be getting the active family tree on
1305 : // our side only. But adding too many graph
1306 : // links may cause hanging nodes to tend to be
1307 : // on partition interiors, which would reduce
1308 : // communication overhead for constraint
1309 : // equations, so we'll leave it.
1310 :
1311 44637 : neighbor->active_family_tree (neighbors_offspring);
1312 :
1313 : // Get all the neighbor's children that
1314 : // live on that side and are thus connected
1315 : // to us
1316 296630 : for (const auto & child : neighbors_offspring)
1317 : {
1318 : // This does not assume a level-1 mesh.
1319 : // Note that since children have sides numbered
1320 : // coincident with the parent then this is a sufficient test.
1321 252582 : if (child->neighbor_ptr(ns) == elem)
1322 : {
1323 254 : libmesh_assert (child->active());
1324 254 : libmesh_assert (_global_index_by_pid_map.count(child->id()));
1325 : const dof_id_type child_global_index_by_pid =
1326 119483 : _global_index_by_pid_map[child->id()];
1327 :
1328 119483 : graph_row.push_back(child_global_index_by_pid);
1329 : }
1330 : }
1331 : }
1332 :
1333 : #endif /* ifdef LIBMESH_ENABLE_AMR */
1334 :
1335 :
1336 : }
1337 : }
1338 :
1339 3738339 : if ((elem->dim() < LIBMESH_DIM) &&
1340 899781 : elem->interior_parent())
1341 : {
1342 : // get all relevant interior elements
1343 0 : std::set<const Elem *> neighbor_set;
1344 896 : elem->find_interior_neighbors(neighbor_set);
1345 :
1346 1792 : for (const auto & neighbor : neighbor_set)
1347 : {
1348 : const dof_id_type neighbor_global_index_by_pid =
1349 896 : _global_index_by_pid_map[neighbor->id()];
1350 :
1351 896 : graph_row.push_back(neighbor_global_index_by_pid);
1352 : }
1353 : }
1354 :
1355 : // Check for any boundary neighbors
1356 2839454 : for (const auto & pr : as_range(interior_to_boundary_map.equal_range(elem)))
1357 : {
1358 896 : const Elem * neighbor = pr.second;
1359 :
1360 : const dof_id_type neighbor_global_index_by_pid =
1361 896 : _global_index_by_pid_map[neighbor->id()];
1362 :
1363 896 : graph_row.push_back(neighbor_global_index_by_pid);
1364 : }
1365 :
1366 : // Check for any constraining elements
1367 2838558 : if (!mesh_constrained_nodes.empty()) // quick test for non-IGA cases
1368 : {
1369 0 : const auto end_it = mesh_constrained_nodes.end();
1370 :
1371 : // Use a set to avoid duplicates. Use a well-defined method
1372 : // of ordering that set to make debugging easier.
1373 0 : std::set<const Elem *, CompareElemIdsByLevel> constraining_elems;
1374 146426 : for (const Node & node : elem->node_ref_range())
1375 : {
1376 118510 : if (const auto row_it = mesh_constrained_nodes.find(&node);
1377 0 : row_it != end_it)
1378 555331 : for (const auto & [pr, coef] : row_it->second)
1379 : {
1380 0 : libmesh_ignore(coef); // avoid gcc 7 warning
1381 451458 : constraining_elems.insert(pr.first);
1382 : }
1383 : }
1384 240912 : for (const Elem * constraining_elem : constraining_elems)
1385 : {
1386 : const dof_id_type constraining_global_index_by_pid =
1387 212996 : _global_index_by_pid_map[constraining_elem->id()];
1388 :
1389 212996 : graph_row.push_back(constraining_global_index_by_pid);
1390 :
1391 : // We can't be sure if the constraining element's owner sees
1392 : // the assembly element, so to get a symmetric connectivity
1393 : // graph we'll need to tell them about us to be safe.
1394 212996 : if (constraining_elem->processor_id() != mesh.processor_id())
1395 237106 : connections_to_push[constraining_elem->processor_id()].emplace_back
1396 118553 : (global_index_by_pid, constraining_global_index_by_pid);
1397 : }
1398 : }
1399 :
1400 : // Check for any constrained elements
1401 3015071 : for (const auto & pr : as_range(elems_constrained_by.equal_range(elem)))
1402 : {
1403 176513 : const Elem * constrained = pr.second;
1404 : const dof_id_type constrained_global_index_by_pid =
1405 176513 : _global_index_by_pid_map[constrained->id()];
1406 :
1407 176513 : graph_row.push_back(constrained_global_index_by_pid);
1408 :
1409 : // We can't be sure if the constrained element's owner sees
1410 : // the assembly element, so to get a symmetric connectivity
1411 : // graph we'll need to tell them about us to be safe.
1412 176513 : if (constrained->processor_id() != mesh.processor_id())
1413 164140 : connections_to_push[constrained->processor_id()].emplace_back
1414 82070 : (global_index_by_pid, constrained_global_index_by_pid);
1415 : }
1416 334809 : }
1417 :
1418 : // Partitioners like Parmetis require a symmetric adjacency matrix,
1419 : // but if we have an assembly element constrained by a spline
1420 : // NodeElem owned by another processor, it's possible that that
1421 : // processor doesn't see our assembly element. Let's push those
1422 : // entries, to ensure they're counted on both sides.
1423 : auto symmetrize_entries =
1424 4111 : [this, first_local_elem]
1425 : (processor_id_type /*src_pid*/,
1426 200623 : const std::vector<std::pair<dof_id_type, dof_id_type>> & incoming_entries)
1427 : {
1428 204734 : for (auto [i, j] : incoming_entries)
1429 : {
1430 0 : libmesh_assert_greater_equal(j, first_local_elem);
1431 200623 : const std::size_t jl = j - first_local_elem;
1432 0 : libmesh_assert_less(jl, _dual_graph.size());
1433 0 : std::vector<dof_id_type> & graph_row = _dual_graph[jl];
1434 200623 : if (std::find(graph_row.begin(), graph_row.end(), i) == graph_row.end())
1435 : {
1436 : // std::cerr << "Pushing back (" << j << ", " << i << ") from " << src_pid << std::endl;
1437 36483 : graph_row.push_back(i);
1438 : }
1439 : }
1440 335199 : };
1441 :
1442 335589 : Parallel::push_parallel_vector_data(mesh.comm(),
1443 : connections_to_push,
1444 : symmetrize_entries);
1445 :
1446 : // *Now* we should have a symmetric adjacency matrix. Let's check
1447 : // that, so any failures get caught before they e.g. confuse
1448 : // Parmetis in hard-to-debug ways. That's a global communication so
1449 : // we'll only do it in debug mode.
1450 : #ifdef DEBUG
1451 390 : auto n_proc = mesh.n_processors();
1452 780 : std::vector<dof_id_type> first_local_index_on_proc(n_proc, 0);
1453 780 : for (auto pid : make_range(1u,n_proc))
1454 390 : first_local_index_on_proc[pid] = first_local_index_on_proc[pid-1] + _n_active_elem_on_proc[pid-1];
1455 :
1456 390 : libmesh_assert_equal_to(first_local_index_on_proc[mesh.processor_id()],
1457 : first_local_elem);
1458 :
1459 780 : std::unordered_map<processor_id_type, std::vector<std::pair<dof_id_type, dof_id_type>>> entries_to_send;
1460 12224 : for (auto il : index_range(_dual_graph))
1461 : {
1462 11834 : const std::vector<dof_id_type> & graph_row = _dual_graph[il];
1463 :
1464 11834 : const auto i = il + first_local_elem;
1465 :
1466 62858 : for (auto j : graph_row)
1467 : {
1468 : // Stupid graph rows aren't sorted yet...
1469 51024 : processor_id_type target_pid = 0;
1470 127340 : while (target_pid+1 < n_proc &&
1471 51024 : j >= first_local_index_on_proc[target_pid+1])
1472 25292 : ++target_pid;
1473 :
1474 51024 : entries_to_send[target_pid].emplace_back(i,j);
1475 : }
1476 : }
1477 :
1478 780 : std::vector<std::tuple<processor_id_type, dof_id_type, dof_id_type>> bad_entries;
1479 :
1480 : auto check_incoming_entries =
1481 : [this, first_local_elem, &bad_entries]
1482 : (processor_id_type src_pid,
1483 204824 : const std::vector<std::pair<dof_id_type, dof_id_type>> & incoming_entries)
1484 : {
1485 51752 : for (auto [i, j] : incoming_entries)
1486 : {
1487 51024 : if (j < first_local_elem)
1488 : {
1489 0 : bad_entries.emplace_back(src_pid,i,j);
1490 0 : continue;
1491 : }
1492 102048 : const std::size_t jl = j - first_local_elem;
1493 51024 : if (jl >= _dual_graph.size())
1494 : {
1495 0 : bad_entries.emplace_back(src_pid,i,j);
1496 0 : continue;
1497 : }
1498 51024 : const std::vector<dof_id_type> & graph_row = _dual_graph[jl];
1499 51024 : if (std::find(graph_row.begin(), graph_row.end(), i) ==
1500 102048 : graph_row.end())
1501 : {
1502 0 : bad_entries.emplace_back(src_pid,i,j);
1503 0 : continue;
1504 : }
1505 : }
1506 728 : };
1507 :
1508 : // Keep any failures in sync in parallel, for easier debugging in
1509 : // unit tests where the failure exception will be caught.
1510 : Parallel::push_parallel_vector_data
1511 390 : (mesh.comm(), entries_to_send, check_incoming_entries);
1512 390 : bool bad_entries_exist = !bad_entries.empty();
1513 390 : mesh.comm().max(bad_entries_exist);
1514 390 : if (bad_entries_exist)
1515 : {
1516 : #if 0 // Optional verbosity for if this breaks again...
1517 : if (!bad_entries.empty())
1518 : {
1519 : std::cerr << "Bad entries on processor " << mesh.processor_id() << ": ";
1520 : for (auto [p, i, j] : bad_entries)
1521 : std::cerr << '(' << p << ", " << i << ", " << j << "), ";
1522 : std::cerr << std::endl;
1523 : }
1524 : #endif
1525 0 : libmesh_error_msg("Asymmetric partitioner graph detected");
1526 : }
1527 : #endif
1528 335589 : }
1529 :
1530 56251 : void Partitioner::assign_partitioning (MeshBase & mesh, const std::vector<dof_id_type> & parts)
1531 : {
1532 882 : LOG_SCOPE("assign_partitioning()", "Partitioner");
1533 :
1534 : // This function must be run on all processors at once
1535 294 : libmesh_parallel_only(mesh.comm());
1536 :
1537 294 : dof_id_type first_local_elem = 0;
1538 283068 : for (auto pid : make_range(mesh.processor_id()))
1539 226964 : first_local_elem += _n_active_elem_on_proc[pid];
1540 :
1541 : #ifndef NDEBUG
1542 294 : const dof_id_type n_active_local_elem = mesh.n_active_local_elem();
1543 : #endif
1544 :
1545 : std::map<processor_id_type, std::vector<dof_id_type>>
1546 588 : requested_ids;
1547 :
1548 : // Results to gather from each processor - kept in a map so we
1549 : // do only one loop over elements after all receives are done.
1550 : std::map<processor_id_type, std::vector<processor_id_type>>
1551 588 : filled_request;
1552 :
1553 14502345 : for (auto & elem : mesh.active_element_ptr_range())
1554 : {
1555 : // we need to get the index from the owning processor
1556 : // (note we cannot assign it now -- we are iterating
1557 : // over elements again and this will be bad!)
1558 14409329 : requested_ids[elem->processor_id()].push_back(elem->id());
1559 55663 : }
1560 :
1561 : auto gather_functor =
1562 455857 : [this,
1563 : & parts,
1564 : #ifndef NDEBUG
1565 : & mesh,
1566 : n_active_local_elem,
1567 : #endif
1568 : first_local_elem]
1569 : (processor_id_type, const std::vector<dof_id_type> & ids,
1570 28877410 : std::vector<processor_id_type> & data)
1571 : {
1572 1176 : const std::size_t ids_size = ids.size();
1573 457033 : data.resize(ids.size());
1574 :
1575 14847170 : for (std::size_t i=0; i != ids_size; i++)
1576 : {
1577 14409329 : const dof_id_type requested_elem_index = ids[i];
1578 :
1579 19192 : libmesh_assert(_global_index_by_pid_map.count(requested_elem_index));
1580 :
1581 : const dof_id_type global_index_by_pid =
1582 14390137 : _global_index_by_pid_map[requested_elem_index];
1583 :
1584 14390137 : const dof_id_type local_index =
1585 19192 : global_index_by_pid - first_local_elem;
1586 :
1587 19192 : libmesh_assert_less (local_index, parts.size());
1588 19192 : libmesh_assert_less (local_index, n_active_local_elem);
1589 :
1590 : const processor_id_type elem_procid =
1591 14390137 : cast_int<processor_id_type>(parts[local_index]);
1592 :
1593 19192 : libmesh_assert_less (elem_procid, mesh.n_partitions());
1594 :
1595 14409329 : data[i] = elem_procid;
1596 : }
1597 512990 : };
1598 :
1599 : auto action_functor =
1600 455857 : [&filled_request]
1601 : (processor_id_type pid,
1602 : const std::vector<dof_id_type> &,
1603 456445 : const std::vector<processor_id_type> & new_procids)
1604 : {
1605 457033 : filled_request[pid] = new_procids;
1606 56839 : };
1607 :
1608 : // Trade requests with other processors
1609 294 : const processor_id_type * ex = nullptr;
1610 : Parallel::pull_parallel_vector_data
1611 56251 : (mesh.comm(), requested_ids, gather_functor, action_functor, ex);
1612 :
1613 : // and finally assign the partitioning.
1614 : // note we are iterating in exactly the same order
1615 : // used to build up the request, so we can expect the
1616 : // required entries to be in the proper sequence.
1617 56839 : std::vector<unsigned int> counters(mesh.n_processors(), 0);
1618 14502345 : for (auto & elem : mesh.active_element_ptr_range())
1619 : {
1620 14390137 : const processor_id_type current_pid = elem->processor_id();
1621 :
1622 19192 : libmesh_assert_less (counters[current_pid], requested_ids[current_pid].size());
1623 :
1624 : const processor_id_type elem_procid =
1625 14390137 : filled_request[current_pid][counters[current_pid]++];
1626 :
1627 19192 : libmesh_assert_less (elem_procid, mesh.n_partitions());
1628 14390137 : elem->processor_id() = elem_procid;
1629 55663 : }
1630 56251 : }
1631 :
1632 :
1633 : } // namespace libMesh
|