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 : // Local includes
21 : #include "libmesh/mesh_communication.h"
22 :
23 : // libMesh includes
24 : #include "libmesh/libmesh_config.h"
25 : #include "libmesh/libmesh_common.h"
26 : #include "libmesh/libmesh_logging.h"
27 : #include "libmesh/mesh_base.h"
28 : #include "libmesh/mesh_tools.h"
29 : #include "libmesh/parallel_hilbert.h"
30 : #include "libmesh/parallel_sort.h"
31 : #include "libmesh/elem.h"
32 : #include "libmesh/elem_range.h"
33 : #include "libmesh/node_range.h"
34 :
35 : // TIMPI includes
36 : #include "timpi/parallel_implementation.h"
37 : #include "timpi/parallel_sync.h"
38 :
39 : // C/C++ includes
40 : #ifdef LIBMESH_HAVE_LIBHILBERT
41 : # include "hilbert.h"
42 : #endif
43 :
44 :
45 : #if defined(LIBMESH_HAVE_LIBHILBERT) && defined(LIBMESH_HAVE_MPI)
46 :
47 : namespace { // anonymous namespace for helper functions
48 :
49 : using namespace libMesh;
50 :
51 :
52 : // Trying to divide per mesh, not per point
53 27486 : Point invert_bbox (const BoundingBox & bbox)
54 : {
55 13831 : Point p;
56 :
57 55148 : p(0) = (bbox.first(0) == bbox.second(0)) ? 0. :
58 41317 : 1/(bbox.second(0)-bbox.first(0));
59 :
60 : #if LIBMESH_DIM > 1
61 54268 : p(1) = (bbox.first(1) == bbox.second(1)) ? 0. :
62 38677 : 1/(bbox.second(1)-bbox.first(1));
63 : #endif
64 :
65 : #if LIBMESH_DIM > 2
66 55257 : p(2) = (bbox.first(2) == bbox.second(2)) ? 0. :
67 20848 : 1/(bbox.second(2)-bbox.first(2));
68 : #endif
69 :
70 27486 : return p;
71 : }
72 :
73 :
74 :
75 : // Utility function to map (x,y,z) in [bbox.min, bbox.max]^3 into
76 : // [0,max_inttype]^3 for computing Hilbert keys
77 18999394 : void get_hilbert_coords (const Point & p,
78 : const BoundingBox & bbox,
79 : const Point & bboxinv,
80 : CFixBitVec icoords[3])
81 : {
82 : static const Hilbert::inttype max_inttype = static_cast<Hilbert::inttype>(-1);
83 :
84 : const Real // put (x,y,z) in [0,1]^3 (don't divide by 0)
85 18999394 : x = (p(0)-bbox.first(0)) * bboxinv(0),
86 :
87 : #if LIBMESH_DIM > 1
88 18999394 : y = (p(1)-bbox.first(1)) * bboxinv(1),
89 : #else
90 : y = 0.,
91 : #endif
92 :
93 : #if LIBMESH_DIM > 2
94 18999394 : z = (p(2)-bbox.first(2)) * bboxinv(2);
95 : #else
96 : z = 0.;
97 : #endif
98 :
99 : // (icoords) in [0,max_inttype]^3
100 18999394 : icoords[0] = static_cast<Hilbert::inttype>(x*max_inttype);
101 18999394 : icoords[1] = static_cast<Hilbert::inttype>(y*max_inttype);
102 18999394 : icoords[2] = static_cast<Hilbert::inttype>(z*max_inttype);
103 18999394 : }
104 :
105 :
106 :
107 : Parallel::DofObjectKey
108 12031696 : get_dofobject_key (const Elem & e,
109 : const BoundingBox & bbox,
110 : const Point & bboxinv)
111 : {
112 : static const unsigned int sizeof_inttype = sizeof(Hilbert::inttype);
113 :
114 4034830 : Hilbert::HilbertIndices index;
115 48126784 : CFixBitVec icoords[3];
116 4034830 : Hilbert::BitVecType bv;
117 12031696 : get_hilbert_coords (e.vertex_average(), bbox, bboxinv, icoords);
118 4034830 : Hilbert::coordsToIndex (icoords, 8*sizeof_inttype, 3, bv);
119 12031696 : index = bv;
120 :
121 : #ifdef LIBMESH_ENABLE_UNIQUE_ID
122 16066526 : return std::make_pair(index, e.unique_id());
123 : #else
124 : return index;
125 : #endif
126 : }
127 :
128 :
129 :
130 : // Compute the hilbert index
131 : Parallel::DofObjectKey
132 6967698 : get_dofobject_key (const Node & n,
133 : const BoundingBox & bbox,
134 : const Point & bboxinv)
135 : {
136 : static const unsigned int sizeof_inttype = sizeof(Hilbert::inttype);
137 :
138 2303395 : Hilbert::HilbertIndices index;
139 27870792 : CFixBitVec icoords[3];
140 2303395 : Hilbert::BitVecType bv;
141 6967698 : get_hilbert_coords (n, bbox, bboxinv, icoords);
142 2303395 : Hilbert::coordsToIndex (icoords, 8*sizeof_inttype, 3, bv);
143 6967698 : index = bv;
144 :
145 : #ifdef LIBMESH_ENABLE_UNIQUE_ID
146 9271093 : return std::make_pair(index, n.unique_id());
147 : #else
148 : return index;
149 : #endif
150 : }
151 :
152 : // Helper class for threaded Hilbert key computation
153 : class ComputeHilbertKeys
154 : {
155 : public:
156 1132 : ComputeHilbertKeys (const BoundingBox & bbox,
157 : const Point & bboxinv,
158 3416 : std::vector<Parallel::DofObjectKey> & keys) :
159 1152 : _bbox(bbox),
160 1152 : _bboxinv(bboxinv),
161 3416 : _keys(keys)
162 1132 : {}
163 :
164 : // computes the hilbert index for a node
165 2320 : void operator() (const ConstNodeRange & range) const
166 : {
167 1540 : std::size_t pos = range.first_idx();
168 1405254 : for (const auto & node : range)
169 : {
170 460679 : libmesh_assert(node);
171 460679 : libmesh_assert_less (pos, _keys.size());
172 1402934 : _keys[pos++] = get_dofobject_key (*node, _bbox, _bboxinv);
173 : }
174 2320 : }
175 :
176 : // computes the hilbert index for an element
177 2320 : void operator() (const ConstElemRange & range) const
178 : {
179 1540 : std::size_t pos = range.first_idx();
180 1725374 : for (const auto & elem : range)
181 : {
182 571372 : libmesh_assert(elem);
183 571372 : libmesh_assert_less (pos, _keys.size());
184 1723054 : _keys[pos++] = get_dofobject_key (*elem, _bbox, _bboxinv);
185 : }
186 2320 : }
187 :
188 : private:
189 : const BoundingBox _bbox;
190 : const Point _bboxinv;
191 : std::vector<Parallel::DofObjectKey> & _keys;
192 : };
193 :
194 : }
195 : #endif // defined(LIBMESH_HAVE_LIBHILBERT) && defined(LIBMESH_HAVE_MPI)
196 :
197 :
198 : namespace libMesh
199 : {
200 :
201 : // ------------------------------------------------------------
202 : // MeshCommunication class members
203 : #if defined(LIBMESH_HAVE_LIBHILBERT) && defined(LIBMESH_HAVE_MPI)
204 1708 : void MeshCommunication::assign_global_indices (MeshBase & mesh) const
205 : {
206 1698 : LOG_SCOPE ("assign_global_indices()", "MeshCommunication");
207 :
208 : // This method determines partition-agnostic global indices
209 : // for nodes and elements.
210 :
211 : // Algorithm:
212 : // (1) compute the Hilbert key for each local node/element
213 : // (2) perform a parallel sort of the Hilbert key
214 : // (3) get the min/max value on each processor
215 : // (4) determine the position in the global ranking for
216 : // each local object
217 :
218 1132 : const Parallel::Communicator & communicator (mesh.comm());
219 :
220 : #ifdef DEBUG
221 : // This is going to be a mess if geometry is out of sync
222 566 : MeshTools::libmesh_assert_equal_points(mesh);
223 566 : MeshTools::libmesh_assert_equal_connectivity(mesh);
224 : #endif
225 :
226 : // Global bounding box. We choose the nodal bounding box for
227 : // backwards compatibility; the element bounding box may be looser
228 : // on curved elements.
229 : const BoundingBox bbox =
230 1708 : MeshTools::create_nodal_bounding_box (mesh);
231 :
232 1142 : const Point bboxinv = invert_bbox(bbox);
233 :
234 : //-------------------------------------------------------------
235 : // (1) compute Hilbert keys
236 : std::vector<Parallel::DofObjectKey>
237 1132 : node_keys, elem_keys;
238 :
239 : {
240 : // Nodes first
241 : {
242 1708 : const ConstNodeRange & nr = mesh.const_local_node_stored_range();
243 2274 : node_keys.resize (nr.size());
244 1708 : Threads::parallel_for (nr, ComputeHilbertKeys (bbox, bboxinv, node_keys));
245 :
246 : // // It's O(N^2) to check that these keys don't duplicate before the
247 : // // sort...
248 : //
249 : // MeshBase::const_node_iterator nodei = mesh.local_nodes_begin();
250 : // for (std::size_t i = 0; i != node_keys.size(); ++i, ++nodei)
251 : // {
252 : // MeshBase::const_node_iterator nodej = mesh.local_nodes_begin();
253 : // for (std::size_t j = 0; j != i; ++j, ++nodej)
254 : // {
255 : // if (node_keys[i] == node_keys[j])
256 : // {
257 : // CFixBitVec icoords[3], jcoords[3];
258 : // get_hilbert_coords(**nodej, bbox, bboxinv, jcoords);
259 : // libMesh::err << "node " << (*nodej)->id() << ", " << static_cast<Point &>(**nodej) << " has HilbertIndices " << node_keys[j] << std::endl;
260 : // get_hilbert_coords(**nodei, bbox, bboxinv, icoords);
261 : // libMesh::err << "node " << (*nodei)->id() << ", " << static_cast<Point &>(**nodei) << " has HilbertIndices " << node_keys[i] << std::endl;
262 : // libmesh_error_msg("Error: nodes with duplicate Hilbert keys!");
263 : // }
264 : // }
265 : // }
266 : }
267 :
268 : // Elements next
269 : {
270 1708 : const ConstElemRange & er = mesh.const_local_element_stored_range();
271 2274 : elem_keys.resize (er.size());
272 1708 : Threads::parallel_for (er, ComputeHilbertKeys (bbox, bboxinv, elem_keys));
273 :
274 : // // For elements, the keys can be (and in the case of TRI, are
275 : // // expected to be) duplicates, but only if the elements are at
276 : // // different levels
277 : // MeshBase::const_element_iterator elemi = mesh.local_elements_begin();
278 : // for (std::size_t i = 0; i != elem_keys.size(); ++i, ++elemi)
279 : // {
280 : // MeshBase::const_element_iterator elemj = mesh.local_elements_begin();
281 : // for (std::size_t j = 0; j != i; ++j, ++elemj)
282 : // {
283 : // if ((elem_keys[i] == elem_keys[j]) &&
284 : // ((*elemi)->level() == (*elemj)->level()))
285 : // {
286 : // libMesh::err << "level " << (*elemj)->level()
287 : // << " elem\n" << (**elemj)
288 : // << " vertex average " << (*elemj)->vertex_average()
289 : // << " has HilbertIndices " << elem_keys[j]
290 : // << " or " << get_dofobject_key((**elemj), bbox, bboxinv)
291 : // << std::endl;
292 : // libMesh::err << "level " << (*elemi)->level()
293 : // << " elem\n" << (**elemi)
294 : // << " vertex average " << (*elemi)->vertex_average()
295 : // << " has HilbertIndices " << elem_keys[i]
296 : // << " or " << get_dofobject_key((**elemi), bbox, bboxinv)
297 : // << std::endl;
298 : // libmesh_error_msg("Error: level " << (*elemi)->level() << " elements with duplicate Hilbert keys!");
299 : // }
300 : // }
301 : // }
302 : }
303 : } // done computing Hilbert keys
304 :
305 :
306 :
307 : //-------------------------------------------------------------
308 : // (2) parallel sort the Hilbert keys
309 : Parallel::Sort<Parallel::DofObjectKey> node_sorter (communicator,
310 2840 : node_keys);
311 1708 : node_sorter.sort(); /* done with node_keys */ //node_keys.clear();
312 :
313 : const std::vector<Parallel::DofObjectKey> & my_node_bin =
314 1708 : node_sorter.bin();
315 :
316 : Parallel::Sort<Parallel::DofObjectKey> elem_sorter (communicator,
317 2840 : elem_keys);
318 1708 : elem_sorter.sort(); /* done with elem_keys */ //elem_keys.clear();
319 :
320 : const std::vector<Parallel::DofObjectKey> & my_elem_bin =
321 1708 : elem_sorter.bin();
322 :
323 :
324 :
325 : //-------------------------------------------------------------
326 : // (3) get the max value on each processor
327 : std::vector<Parallel::DofObjectKey>
328 2274 : node_upper_bounds(communicator.size()),
329 2274 : elem_upper_bounds(communicator.size());
330 :
331 : { // limit scope of temporaries
332 2274 : std::vector<Parallel::DofObjectKey> recvbuf(2*communicator.size());
333 : std::vector<unsigned short int> /* do not use a vector of bools here since it is not always so! */
334 2274 : empty_nodes (communicator.size()),
335 2274 : empty_elem (communicator.size());
336 2274 : std::vector<Parallel::DofObjectKey> my_max(2);
337 :
338 2274 : communicator.allgather (static_cast<unsigned short int>(my_node_bin.empty()), empty_nodes);
339 1708 : communicator.allgather (static_cast<unsigned short int>(my_elem_bin.empty()), empty_elem);
340 :
341 1708 : if (!my_node_bin.empty()) my_max[0] = my_node_bin.back();
342 1708 : if (!my_elem_bin.empty()) my_max[1] = my_elem_bin.back();
343 :
344 1708 : communicator.allgather (my_max, /* identical_buffer_sizes = */ true);
345 :
346 : // Be careful here. The *_upper_bounds will be used to find the processor
347 : // a given object belongs to. So, if a processor contains no objects (possible!)
348 : // then copy the bound from the lower processor id.
349 5108 : for (auto p : make_range(communicator.size()))
350 : {
351 4532 : node_upper_bounds[p] = my_max[2*p+0];
352 4532 : elem_upper_bounds[p] = my_max[2*p+1];
353 :
354 3400 : if (p > 0) // default hilbert index value is the OK upper bound for processor 0.
355 : {
356 2258 : if (empty_nodes[p]) node_upper_bounds[p] = node_upper_bounds[p-1];
357 2258 : if (empty_elem[p]) elem_upper_bounds[p] = elem_upper_bounds[p-1];
358 : }
359 : }
360 : }
361 :
362 :
363 :
364 : //-------------------------------------------------------------
365 : // (4) determine the position in the global ranking for
366 : // each local object
367 : {
368 : //----------------------------------------------
369 : // Nodes first -- all nodes, not just local ones
370 : {
371 : // Request sets to send to each processor
372 : std::map<processor_id_type, std::vector<Parallel::DofObjectKey>>
373 1132 : requested_ids;
374 : // Results to gather from each processor - kept in a map so we
375 : // do only one loop over nodes after all receives are done.
376 : std::map<dof_id_type, std::vector<dof_id_type>>
377 1132 : filled_request;
378 :
379 : // build up list of requests
380 3724898 : for (const auto & node : mesh.node_ptr_range())
381 : {
382 921358 : libmesh_assert(node);
383 : const Parallel::DofObjectKey hi =
384 2782382 : get_dofobject_key (*node, bbox, bboxinv);
385 : const processor_id_type pid =
386 : cast_int<processor_id_type>
387 2782382 : (std::distance (node_upper_bounds.begin(),
388 : std::lower_bound(node_upper_bounds.begin(),
389 : node_upper_bounds.end(),
390 2782382 : hi)));
391 :
392 921358 : libmesh_assert_less (pid, communicator.size());
393 :
394 2782382 : requested_ids[pid].push_back(hi);
395 576 : }
396 :
397 : // The number of objects in my_node_bin on each processor
398 2274 : std::vector<dof_id_type> node_bin_sizes(communicator.size());
399 2274 : communicator.allgather (static_cast<dof_id_type>(my_node_bin.size()), node_bin_sizes);
400 :
401 : // The offset of my first global index
402 566 : dof_id_type my_offset = 0;
403 2554 : for (auto pid : make_range(communicator.rank()))
404 1129 : my_offset += node_bin_sizes[pid];
405 :
406 : auto gather_functor =
407 1136 : [
408 : #ifndef NDEBUG
409 : & node_upper_bounds,
410 : & communicator,
411 : #endif
412 : & my_node_bin,
413 : my_offset
414 : ]
415 : (processor_id_type,
416 : const std::vector<Parallel::DofObjectKey> & keys,
417 9234152 : std::vector<dof_id_type> & global_ids)
418 : {
419 : // Fill the requests
420 2264 : const std::size_t keys_size = keys.size();
421 3400 : global_ids.reserve(keys_size);
422 2785782 : for (std::size_t idx=0; idx != keys_size; idx++)
423 : {
424 1842716 : const Parallel::DofObjectKey & hi = keys[idx];
425 921358 : libmesh_assert_less_equal (hi, node_upper_bounds[communicator.rank()]);
426 :
427 : // find the requested index in my node bin
428 : std::vector<Parallel::DofObjectKey>::const_iterator pos =
429 2782382 : std::lower_bound (my_node_bin.begin(), my_node_bin.end(), hi);
430 921358 : libmesh_assert (pos != my_node_bin.end());
431 921358 : libmesh_assert_equal_to (*pos, hi);
432 :
433 : // Finally, assign the global index based off the position of the index
434 : // in my array, properly offset.
435 4625098 : global_ids.push_back(cast_int<dof_id_type>(std::distance(my_node_bin.begin(), pos) + my_offset));
436 : }
437 4542 : };
438 :
439 : auto action_functor =
440 1136 : [&filled_request]
441 : (processor_id_type pid,
442 : const std::vector<Parallel::DofObjectKey> &,
443 2268 : const std::vector<dof_id_type> & global_ids)
444 : {
445 3400 : filled_request[pid] = global_ids;
446 3976 : };
447 :
448 : // Trade requests with other processors
449 566 : const dof_id_type * ex = nullptr;
450 : Parallel::pull_parallel_vector_data
451 1708 : (communicator, requested_ids, gather_functor, action_functor, ex);
452 :
453 : // We now have all the filled requests, so we can loop through our
454 : // nodes once and assign the global index to each one.
455 : {
456 : std::map<dof_id_type, std::vector<dof_id_type>::const_iterator>
457 1132 : next_obj_on_proc;
458 5108 : for (auto & p : filled_request)
459 3400 : next_obj_on_proc[p.first] = p.second.begin();
460 :
461 2808718 : for (auto & node : mesh.node_ptr_range())
462 : {
463 921358 : libmesh_assert(node);
464 : const Parallel::DofObjectKey hi =
465 2782382 : get_dofobject_key (*node, bbox, bboxinv);
466 : const processor_id_type pid =
467 : cast_int<processor_id_type>
468 2782382 : (std::distance (node_upper_bounds.begin(),
469 : std::lower_bound(node_upper_bounds.begin(),
470 : node_upper_bounds.end(),
471 1866202 : hi)));
472 :
473 921358 : libmesh_assert_less (pid, communicator.size());
474 921358 : libmesh_assert (next_obj_on_proc[pid] != filled_request[pid].end());
475 :
476 2782382 : const dof_id_type global_index = *next_obj_on_proc[pid];
477 921358 : libmesh_assert_less (global_index, mesh.n_nodes());
478 2782382 : node->set_id() = global_index;
479 :
480 2782382 : ++next_obj_on_proc[pid];
481 576 : }
482 : }
483 : }
484 :
485 : //---------------------------------------------------
486 : // elements next -- all elements, not just local ones
487 : {
488 : // Request sets to send to each processor
489 : std::map<processor_id_type, std::vector<Parallel::DofObjectKey>>
490 1132 : requested_ids;
491 : // Results to gather from each processor - kept in a map so we
492 : // do only one loop over elements after all receives are done.
493 : std::map<dof_id_type, std::vector<dof_id_type>>
494 1132 : filled_request;
495 :
496 4586054 : for (const auto & elem : mesh.element_ptr_range())
497 : {
498 1142744 : libmesh_assert(elem);
499 : const Parallel::DofObjectKey hi =
500 3434346 : get_dofobject_key (*elem, bbox, bboxinv);
501 : const processor_id_type pid =
502 : cast_int<processor_id_type>
503 3434346 : (std::distance (elem_upper_bounds.begin(),
504 : std::lower_bound(elem_upper_bounds.begin(),
505 : elem_upper_bounds.end(),
506 3434346 : hi)));
507 :
508 1142744 : libmesh_assert_less (pid, communicator.size());
509 :
510 3434346 : requested_ids[pid].push_back(hi);
511 576 : }
512 :
513 : // The number of objects in my_elem_bin on each processor
514 2274 : std::vector<dof_id_type> elem_bin_sizes(communicator.size());
515 2274 : communicator.allgather (static_cast<dof_id_type>(my_elem_bin.size()), elem_bin_sizes);
516 :
517 : // The offset of my first global index
518 566 : dof_id_type my_offset = 0;
519 2554 : for (auto pid : make_range(communicator.rank()))
520 1129 : my_offset += elem_bin_sizes[pid];
521 :
522 : auto gather_functor =
523 1136 : [
524 : #ifndef NDEBUG
525 : & elem_upper_bounds,
526 : & communicator,
527 : #endif
528 : & my_elem_bin,
529 : my_offset
530 : ]
531 : (processor_id_type,
532 : const std::vector<Parallel::DofObjectKey> & keys,
533 11435818 : std::vector<dof_id_type> & global_ids)
534 : {
535 : // Fill the requests
536 2264 : const std::size_t keys_size = keys.size();
537 3400 : global_ids.reserve(keys_size);
538 3437746 : for (std::size_t idx=0; idx != keys_size; idx++)
539 : {
540 2285488 : const Parallel::DofObjectKey & hi = keys[idx];
541 1142744 : libmesh_assert_less_equal (hi, elem_upper_bounds[communicator.rank()]);
542 :
543 : // find the requested index in my elem bin
544 : std::vector<Parallel::DofObjectKey>::const_iterator pos =
545 3434346 : std::lower_bound (my_elem_bin.begin(), my_elem_bin.end(), hi);
546 1142744 : libmesh_assert (pos != my_elem_bin.end());
547 1142744 : libmesh_assert_equal_to (*pos, hi);
548 :
549 : // Finally, assign the global index based off the position of the index
550 : // in my array, properly offset.
551 5719834 : global_ids.push_back (cast_int<dof_id_type>(std::distance(my_elem_bin.begin(), pos) + my_offset));
552 : }
553 4542 : };
554 :
555 : auto action_functor =
556 1136 : [&filled_request]
557 : (processor_id_type pid,
558 : const std::vector<Parallel::DofObjectKey> &,
559 2268 : const std::vector<dof_id_type> & global_ids)
560 : {
561 3400 : filled_request[pid] = global_ids;
562 3976 : };
563 :
564 : // Trade requests with other processors
565 566 : const dof_id_type * ex = nullptr;
566 : Parallel::pull_parallel_vector_data
567 1708 : (communicator, requested_ids, gather_functor, action_functor, ex);
568 :
569 : // We now have all the filled requests, so we can loop through our
570 : // elements once and assign the global index to each one.
571 : {
572 : std::vector<std::vector<dof_id_type>::const_iterator>
573 2274 : next_obj_on_proc; next_obj_on_proc.reserve(communicator.size());
574 5108 : for (auto pid : make_range(communicator.size()))
575 5668 : next_obj_on_proc.push_back(filled_request[pid].begin());
576 :
577 4586054 : for (auto & elem : mesh.element_ptr_range())
578 : {
579 1142744 : libmesh_assert(elem);
580 : const Parallel::DofObjectKey hi =
581 3434346 : get_dofobject_key (*elem, bbox, bboxinv);
582 : const processor_id_type pid =
583 : cast_int<processor_id_type>
584 3434346 : (std::distance (elem_upper_bounds.begin(),
585 : std::lower_bound(elem_upper_bounds.begin(),
586 : elem_upper_bounds.end(),
587 1142744 : hi)));
588 :
589 1142744 : libmesh_assert_less (pid, communicator.size());
590 1142744 : libmesh_assert (next_obj_on_proc[pid] != filled_request[pid].end());
591 :
592 3434346 : const dof_id_type global_index = *next_obj_on_proc[pid];
593 1142744 : libmesh_assert_less (global_index, mesh.n_elem());
594 3434346 : elem->set_id() = global_index;
595 :
596 1142744 : ++next_obj_on_proc[pid];
597 576 : }
598 : }
599 : }
600 : }
601 2284 : }
602 : #else // LIBMESH_HAVE_LIBHILBERT, LIBMESH_HAVE_MPI
603 : void MeshCommunication::assign_global_indices (MeshBase &) const
604 : {
605 : }
606 : #endif // LIBMESH_HAVE_LIBHILBERT, LIBMESH_HAVE_MPI
607 :
608 :
609 : #if defined(LIBMESH_HAVE_LIBHILBERT) && defined(LIBMESH_HAVE_MPI)
610 0 : void MeshCommunication::check_for_duplicate_global_indices (MeshBase & mesh) const
611 : {
612 0 : LOG_SCOPE ("check_for_duplicate_global_indices()", "MeshCommunication");
613 :
614 : // Global bounding box. We choose the nodal bounding box for
615 : // backwards compatibility; the element bounding box may be looser
616 : // on curved elements.
617 : const BoundingBox bbox =
618 0 : MeshTools::create_nodal_bounding_box (mesh);
619 :
620 0 : const Point bboxinv = invert_bbox(bbox);
621 :
622 : std::vector<Parallel::DofObjectKey>
623 0 : node_keys, elem_keys;
624 :
625 : {
626 : // Nodes first
627 : {
628 0 : const ConstNodeRange & nr = mesh.const_local_node_stored_range();
629 0 : Threads::parallel_for (nr, ComputeHilbertKeys (bbox, bboxinv, node_keys));
630 :
631 : // It's O(N^2) to check that these keys don't duplicate before the
632 : // sort...
633 0 : MeshBase::const_node_iterator nodei = mesh.local_nodes_begin();
634 0 : for (std::size_t i = 0; i != node_keys.size(); ++i, ++nodei)
635 : {
636 0 : MeshBase::const_node_iterator nodej = mesh.local_nodes_begin();
637 0 : for (std::size_t j = 0; j != i; ++j, ++nodej)
638 : {
639 0 : if (node_keys[i] == node_keys[j])
640 : {
641 0 : CFixBitVec icoords[3], jcoords[3];
642 0 : get_hilbert_coords(**nodej, bbox, bboxinv, jcoords);
643 : libMesh::err <<
644 0 : "node " << (*nodej)->id() << ", " <<
645 0 : *(const Point *)(*nodej) << " has HilbertIndices " <<
646 0 : node_keys[j] << std::endl;
647 0 : get_hilbert_coords(**nodei, bbox, bboxinv, icoords);
648 : libMesh::err <<
649 0 : "node " << (*nodei)->id() << ", " <<
650 0 : *(const Point *)(*nodei) << " has HilbertIndices " <<
651 0 : node_keys[i] << std::endl;
652 0 : libmesh_error_msg("Error: nodes with duplicate Hilbert keys!");
653 : }
654 : }
655 : }
656 : }
657 :
658 : // Elements next
659 : {
660 0 : const ConstElemRange & er = mesh.const_local_element_stored_range();
661 0 : elem_keys.resize (er.size());
662 0 : Threads::parallel_for (er, ComputeHilbertKeys (bbox, bboxinv, elem_keys));
663 :
664 : // For elements, the keys can be (and in the case of TRI, are
665 : // expected to be) duplicates, but only if the elements are at
666 : // different levels
667 0 : MeshBase::const_element_iterator elemi = mesh.local_elements_begin();
668 0 : for (std::size_t i = 0; i != elem_keys.size(); ++i, ++elemi)
669 : {
670 0 : MeshBase::const_element_iterator elemj = mesh.local_elements_begin();
671 0 : for (std::size_t j = 0; j != i; ++j, ++elemj)
672 : {
673 0 : if ((elem_keys[i] == elem_keys[j]) &&
674 0 : ((*elemi)->level() == (*elemj)->level()))
675 : {
676 : libMesh::err <<
677 0 : "level " << (*elemj)->level() << " elem\n" <<
678 0 : (**elemj) << " vertex average " <<
679 0 : (*elemj)->vertex_average() << " has HilbertIndices " <<
680 0 : elem_keys[j] << " or " <<
681 0 : get_dofobject_key((**elemj), bbox, bboxinv) <<
682 0 : std::endl;
683 : libMesh::err <<
684 0 : "level " << (*elemi)->level() << " elem\n" <<
685 0 : (**elemi) << " vertex average " <<
686 0 : (*elemi)->vertex_average() << " has HilbertIndices " <<
687 0 : elem_keys[i] << " or " <<
688 0 : get_dofobject_key((**elemi), bbox, bboxinv) <<
689 0 : std::endl;
690 0 : libmesh_error_msg("Error: level " << (*elemi)->level() << " elements with duplicate Hilbert keys!");
691 : }
692 : }
693 : }
694 : }
695 : } // done checking Hilbert keys
696 0 : }
697 : #else // LIBMESH_HAVE_LIBHILBERT, LIBMESH_HAVE_MPI
698 : void MeshCommunication::check_for_duplicate_global_indices (MeshBase &) const
699 : {
700 : }
701 : #endif // LIBMESH_HAVE_LIBHILBERT, LIBMESH_HAVE_MPI
702 :
703 : #if defined(LIBMESH_HAVE_LIBHILBERT) && defined(LIBMESH_HAVE_MPI)
704 : template <typename ForwardIterator>
705 2340 : void MeshCommunication::find_local_indices (const BoundingBox & bbox,
706 : const ForwardIterator & begin,
707 : const ForwardIterator & end,
708 : std::unordered_map<dof_id_type, dof_id_type> & index_map) const
709 : {
710 2340 : LOG_SCOPE ("find_local_indices()", "MeshCommunication");
711 :
712 : // This method determines id-agnostic local indices
713 : // for nodes and elements by sorting Hilbert keys.
714 :
715 780 : index_map.clear();
716 :
717 1560 : const Point bboxinv = invert_bbox(bbox);
718 :
719 : //-------------------------------------------------------------
720 : // (1) compute Hilbert keys
721 : // These aren't trivial to compute, and we will need them again.
722 : // But the binsort will sort the input vector, trashing the order
723 : // that we'd like to rely on. So, two vectors...
724 1560 : std::map<Parallel::DofObjectKey, dof_id_type> hilbert_keys;
725 : {
726 2340 : LOG_SCOPE("local_hilbert_indices", "MeshCommunication");
727 73344 : for (ForwardIterator it=begin; it!=end; ++it)
728 : {
729 71004 : const Parallel::DofObjectKey hi(get_dofobject_key ((**it), bbox, bboxinv));
730 71004 : hilbert_keys.emplace(hi, (*it)->id());
731 : }
732 : }
733 :
734 : {
735 780 : dof_id_type cnt = 0;
736 73344 : for (auto key_val : hilbert_keys)
737 71004 : index_map[key_val.second] = cnt++;
738 : }
739 2340 : }
740 :
741 :
742 : template <typename ForwardIterator>
743 37269 : void MeshCommunication::find_global_indices (const Parallel::Communicator & communicator,
744 : const BoundingBox & bbox,
745 : const ForwardIterator & begin,
746 : const ForwardIterator & end,
747 : std::vector<dof_id_type> & index_map) const
748 : {
749 37455 : LOG_SCOPE ("find_global_indices()", "MeshCommunication");
750 :
751 : // This method determines partition-agnostic global indices
752 : // for nodes and elements.
753 :
754 : // Algorithm:
755 : // (1) compute the Hilbert key for each local node/element
756 : // (2) perform a parallel sort of the Hilbert key
757 : // (3) get the min/max value on each processor
758 : // (4) determine the position in the global ranking for
759 : // each local object
760 12485 : index_map.clear();
761 37269 : std::size_t n_objects = std::distance (begin, end);
762 37269 : index_map.reserve(n_objects);
763 :
764 24784 : const Point bboxinv = invert_bbox(bbox);
765 :
766 : //-------------------------------------------------------------
767 : // (1) compute Hilbert keys
768 : // These aren't trivial to compute, and we will need them again.
769 : // But the binsort will sort the input vector, trashing the order
770 : // that we'd like to rely on. So, two vectors...
771 : std::vector<Parallel::DofObjectKey>
772 24970 : sorted_hilbert_keys,
773 24970 : hilbert_keys;
774 37269 : sorted_hilbert_keys.reserve(n_objects);
775 37269 : hilbert_keys.reserve(n_objects);
776 : {
777 37455 : LOG_SCOPE("compute_hilbert_indices()", "MeshCommunication");
778 24970 : const processor_id_type my_pid = communicator.rank();
779 4466557 : for (ForwardIterator it=begin; it!=end; ++it)
780 : {
781 3368946 : const Parallel::DofObjectKey hi(get_dofobject_key (**it, bbox, bboxinv));
782 3368946 : hilbert_keys.push_back(hi);
783 :
784 3368946 : const processor_id_type pid = (*it)->processor_id();
785 :
786 3368946 : if (pid == my_pid)
787 1680587 : sorted_hilbert_keys.push_back(hi);
788 :
789 : // someone needs to take care of unpartitioned objects!
790 4523248 : if ((my_pid == 0) &&
791 2214644 : (pid == DofObject::invalid_processor_id))
792 9762 : sorted_hilbert_keys.push_back(hi);
793 : }
794 : }
795 :
796 : //-------------------------------------------------------------
797 : // (2) parallel sort the Hilbert keys
798 24970 : START_LOG ("parallel_sort()", "MeshCommunication");
799 62239 : Parallel::Sort<Parallel::DofObjectKey> sorter (communicator,
800 : sorted_hilbert_keys);
801 37269 : sorter.sort();
802 24970 : STOP_LOG ("parallel_sort()", "MeshCommunication");
803 37269 : const std::vector<Parallel::DofObjectKey> & my_bin = sorter.bin();
804 :
805 : // The number of objects in my_bin on each processor
806 49754 : std::vector<unsigned int> bin_sizes(communicator.size());
807 49754 : communicator.allgather (static_cast<unsigned int>(my_bin.size()), bin_sizes);
808 :
809 : // The offset of my first global index
810 12485 : unsigned int my_offset = 0;
811 55899 : for (auto pid : make_range(communicator.rank()))
812 24872 : my_offset += bin_sizes[pid];
813 :
814 : //-------------------------------------------------------------
815 : // (3) get the max value on each processor
816 : std::vector<Parallel::DofObjectKey>
817 49754 : upper_bounds(1);
818 :
819 37269 : if (!my_bin.empty())
820 24970 : upper_bounds[0] = my_bin.back();
821 :
822 37269 : communicator.allgather (upper_bounds, /* identical_buffer_sizes = */ true);
823 :
824 : // Be careful here. The *_upper_bounds will be used to find the processor
825 : // a given object belongs to. So, if a processor contains no objects (possible!)
826 : // then copy the bound from the lower processor id.
827 74529 : for (auto p : IntRange<processor_id_type>(1, communicator.size()))
828 49744 : if (!bin_sizes[p]) upper_bounds[p] = upper_bounds[p-1];
829 :
830 :
831 : //-------------------------------------------------------------
832 : // (4) determine the position in the global ranking for
833 : // each local object
834 : {
835 : //----------------------------------------------
836 : // all objects, not just local ones
837 :
838 : // Request sets to send to each processor
839 : std::map<processor_id_type, std::vector<Parallel::DofObjectKey>>
840 24970 : requested_ids;
841 : // Results to gather from each processor
842 : std::map<processor_id_type, std::vector<dof_id_type>>
843 24970 : filled_request;
844 :
845 : // build up list of requests
846 12485 : std::vector<Parallel::DofObjectKey>::const_iterator hi =
847 12485 : hilbert_keys.begin();
848 :
849 3406332 : for (ForwardIterator it = begin; it != end; ++it)
850 : {
851 1154302 : libmesh_assert (hi != hilbert_keys.end());
852 :
853 : std::vector<Parallel::DofObjectKey>::iterator lb =
854 3368946 : std::lower_bound(upper_bounds.begin(), upper_bounds.end(),
855 1154302 : *hi);
856 :
857 3368946 : const processor_id_type pid =
858 : cast_int<processor_id_type>
859 1154302 : (std::distance (upper_bounds.begin(), lb));
860 :
861 1154302 : libmesh_assert_less (pid, communicator.size());
862 :
863 3368946 : requested_ids[pid].push_back(*hi);
864 :
865 1154302 : ++hi;
866 : // go ahead and put pid in index_map, that way we
867 : // don't have to repeat the std::lower_bound()
868 3368946 : index_map.push_back(pid);
869 : }
870 :
871 3550111 : auto gather_functor =
872 1084932 : [
873 : #ifndef NDEBUG
874 : & upper_bounds,
875 : & communicator,
876 : #endif
877 : & bbox,
878 : & my_bin,
879 : my_offset
880 : ]
881 : (processor_id_type, const std::vector<Parallel::DofObjectKey> & keys,
882 49936 : std::vector<dof_id_type> & global_ids)
883 : {
884 : // Ignore unused lambda capture warnings in devel mode
885 24968 : libmesh_ignore(bbox);
886 :
887 : // Fill the requests
888 49936 : const std::size_t keys_size = keys.size();
889 24968 : global_ids.clear();
890 74526 : global_ids.reserve(keys_size);
891 3443472 : for (std::size_t idx=0; idx != keys_size; idx++)
892 : {
893 2308604 : const Parallel::DofObjectKey & hilbert_indices = keys[idx];
894 1154302 : libmesh_assert_less_equal (hilbert_indices, upper_bounds[communicator.rank()]);
895 :
896 : // find the requested index in my node bin
897 : std::vector<Parallel::DofObjectKey>::const_iterator pos =
898 3368946 : std::lower_bound (my_bin.begin(), my_bin.end(), hilbert_indices);
899 1154302 : libmesh_assert (pos != my_bin.end());
900 : #ifdef DEBUG
901 : // If we could not find the requested Hilbert index in
902 : // my_bin, something went terribly wrong, possibly the
903 : // Mesh was displaced differently on different processors,
904 : // and therefore the Hilbert indices don't agree.
905 1154302 : if (*pos != hilbert_indices)
906 : {
907 : // The input will be hilbert_indices. We convert it
908 : // to BitVecType using the operator= provided by the
909 : // BitVecType class. BitVecType is a CBigBitVec!
910 0 : Hilbert::BitVecType input;
911 : #ifdef LIBMESH_ENABLE_UNIQUE_ID
912 0 : input = hilbert_indices.first;
913 : #else
914 : input = hilbert_indices;
915 : #endif
916 :
917 : // Get output in a vector of CBigBitVec
918 0 : std::vector<CBigBitVec> output(3);
919 :
920 : // Call the indexToCoords function
921 0 : Hilbert::indexToCoords(output.data(), 8*sizeof(Hilbert::inttype), 3, input);
922 :
923 : // The entries in the output racks are integers in the
924 : // range [0, Hilbert::inttype::max] which can be
925 : // converted to floating point values in [0,1] and
926 : // finally to actual values using the bounding box.
927 0 : const Real max_int_as_real =
928 : static_cast<Real>(std::numeric_limits<Hilbert::inttype>::max());
929 :
930 : // Get the points in [0,1]^3. The zeroth rack of each entry in
931 : // 'output' maps to the normalized x, y, and z locations,
932 : // respectively.
933 0 : Point p_hat(static_cast<Real>(output[0].racks()[0]) / max_int_as_real,
934 0 : static_cast<Real>(output[1].racks()[0]) / max_int_as_real,
935 0 : static_cast<Real>(output[2].racks()[0]) / max_int_as_real);
936 :
937 : // Convert the points from [0,1]^3 to their actual (x,y,z) locations
938 : Real
939 0 : xmin = bbox.first(0),
940 0 : xmax = bbox.second(0),
941 0 : ymin = bbox.first(1),
942 0 : ymax = bbox.second(1),
943 0 : zmin = bbox.first(2),
944 0 : zmax = bbox.second(2);
945 :
946 : // Convert the points from [0,1]^3 to their actual (x,y,z) locations
947 0 : Point p(xmin + (xmax-xmin)*p_hat(0),
948 0 : ymin + (ymax-ymin)*p_hat(1),
949 0 : zmin + (zmax-zmin)*p_hat(2));
950 :
951 0 : libmesh_error_msg("Could not find hilbert indices: "
952 : << hilbert_indices
953 : << " corresponding to point " << p);
954 : }
955 : #endif
956 :
957 : // Finally, assign the global index based off the position of the index
958 : // in my array, properly offset.
959 5677550 : global_ids.push_back (cast_int<dof_id_type>(std::distance(my_bin.begin(), pos) + my_offset));
960 : }
961 : };
962 :
963 87205 : auto action_functor =
964 49180 : [&filled_request]
965 : (processor_id_type pid,
966 : const std::vector<Parallel::DofObjectKey> &,
967 24968 : const std::vector<dof_id_type> & global_ids)
968 : {
969 74526 : filled_request[pid] = global_ids;
970 : };
971 :
972 12485 : const dof_id_type * ex = nullptr;
973 : Parallel::pull_parallel_vector_data
974 37269 : (communicator, requested_ids, gather_functor, action_functor, ex);
975 :
976 : // We now have all the filled requests, so we can loop through our
977 : // nodes once and assign the global index to each one.
978 : {
979 : std::vector<std::vector<dof_id_type>::const_iterator>
980 49754 : next_obj_on_proc; next_obj_on_proc.reserve(communicator.size());
981 111798 : for (auto pid : make_range(communicator.size()))
982 124089 : next_obj_on_proc.push_back(filled_request[pid].begin());
983 :
984 12485 : unsigned int cnt=0;
985 4560517 : for (ForwardIterator it = begin; it != end; ++it, cnt++)
986 : {
987 1154302 : const processor_id_type pid = cast_int<processor_id_type>
988 3368946 : (index_map[cnt]);
989 :
990 1154302 : libmesh_assert_less (pid, communicator.size());
991 1154302 : libmesh_assert (next_obj_on_proc[pid] != filled_request[pid].end());
992 :
993 3368946 : const dof_id_type global_index = *next_obj_on_proc[pid];
994 3368946 : index_map[cnt] = global_index;
995 :
996 1154302 : ++next_obj_on_proc[pid];
997 : }
998 : }
999 : }
1000 :
1001 12485 : libmesh_assert_equal_to(index_map.size(), n_objects);
1002 49568 : }
1003 : #else // LIBMESH_HAVE_LIBHILBERT, LIBMESH_HAVE_MPI
1004 : template <typename ForwardIterator>
1005 : void MeshCommunication::find_local_indices (const libMesh::BoundingBox &,
1006 : const ForwardIterator & begin,
1007 : const ForwardIterator & end,
1008 : std::unordered_map<dof_id_type, dof_id_type> & index_map) const
1009 : {
1010 : index_map.clear();
1011 : dof_id_type index = 0;
1012 : for (ForwardIterator it=begin; it!=end; ++it)
1013 : index_map[(*it)->id()] = (index++);
1014 : }
1015 :
1016 : template <typename ForwardIterator>
1017 : void MeshCommunication::find_global_indices (const Parallel::Communicator &,
1018 : const libMesh::BoundingBox &,
1019 : const ForwardIterator & begin,
1020 : const ForwardIterator & end,
1021 : std::vector<dof_id_type> & index_map) const
1022 : {
1023 : index_map.clear();
1024 : index_map.reserve(std::distance (begin, end));
1025 : unsigned int index = 0;
1026 : for (ForwardIterator it=begin; it!=end; ++it)
1027 : index_map.push_back(index++);
1028 : }
1029 : #endif // LIBMESH_HAVE_LIBHILBERT, LIBMESH_HAVE_MPI
1030 :
1031 :
1032 :
1033 : //------------------------------------------------------------------
1034 : template LIBMESH_EXPORT void MeshCommunication::find_global_indices<MeshBase::const_node_iterator> (const Parallel::Communicator &,
1035 : const libMesh::BoundingBox &,
1036 : const MeshBase::const_node_iterator &,
1037 : const MeshBase::const_node_iterator &,
1038 : std::vector<dof_id_type> &) const;
1039 :
1040 : template LIBMESH_EXPORT void MeshCommunication::find_global_indices<MeshBase::const_element_iterator> (const Parallel::Communicator &,
1041 : const libMesh::BoundingBox &,
1042 : const MeshBase::const_element_iterator &,
1043 : const MeshBase::const_element_iterator &,
1044 : std::vector<dof_id_type> &) const;
1045 : template LIBMESH_EXPORT void MeshCommunication::find_global_indices<MeshBase::node_iterator> (const Parallel::Communicator &,
1046 : const libMesh::BoundingBox &,
1047 : const MeshBase::node_iterator &,
1048 : const MeshBase::node_iterator &,
1049 : std::vector<dof_id_type> &) const;
1050 :
1051 : template LIBMESH_EXPORT void MeshCommunication::find_global_indices<MeshBase::element_iterator> (const Parallel::Communicator &,
1052 : const libMesh::BoundingBox &,
1053 : const MeshBase::element_iterator &,
1054 : const MeshBase::element_iterator &,
1055 : std::vector<dof_id_type> &) const;
1056 : template LIBMESH_EXPORT void MeshCommunication::find_local_indices<MeshBase::const_element_iterator> (const libMesh::BoundingBox &,
1057 : const MeshBase::const_element_iterator &,
1058 : const MeshBase::const_element_iterator &,
1059 : std::unordered_map<dof_id_type, dof_id_type> &) const;
1060 :
1061 : } // namespace libMesh
|