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