Loading [MathJax]/extensions/TeX/newcommand.js
 deal.II version GIT relicensing-3104-g8c3bc2e695 2025-04-21 18:40:00+00:00
\newcommand{\dealvcentcolon}{\mathrel{\mathop{:}}} \newcommand{\dealcoloneq}{\dealvcentcolon\mathrel{\mkern-1.2mu}=} \newcommand{\jump}[1]{\left[\!\left[ #1 \right]\!\right]} \newcommand{\average}[1]{\left\{\!\left\{ #1 \right\}\!\right\}}
All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Modules Pages Concepts
partitioner.cc
Go to the documentation of this file.
1// ------------------------------------------------------------------------
2//
3// SPDX-License-Identifier: LGPL-2.1-or-later
4// Copyright (C) 2012 - 2023 by the deal.II authors
5//
6// This file is part of the deal.II library.
7//
8// Part of the source code is dual licensed under Apache-2.0 WITH
9// LLVM-exception OR LGPL-2.1-or-later. Detailed license information
10// governing the source code and code contributions can be found in
11// LICENSE.md and CONTRIBUTING.md at the top level directory of deal.II.
12//
13// ------------------------------------------------------------------------
14
16#include <deal.II/base/mpi.h>
18#include <deal.II/base/partitioner.templates.h>
19
20#include <boost/serialization/utility.hpp>
21
22#include <Kokkos_Core.hpp>
23
24#include <limits>
25
27
28#ifndef DOXYGEN
29namespace Utilities
30{
31 namespace MPI
32 {
34 : global_size(0)
35 , local_range_data(
37 , n_ghost_indices_data(0)
38 , n_import_indices_data(0)
39 , n_ghost_indices_in_larger_set(0)
40 , my_pid(0)
41 , n_procs(1)
42 , communicator(MPI_COMM_SELF)
43 , have_ghost_indices(false)
44 {}
45
46
47
48 Partitioner::Partitioner(const unsigned int size)
49 : global_size(size)
50 , locally_owned_range_data(size)
51 , local_range_data(
53 , n_ghost_indices_data(0)
54 , n_import_indices_data(0)
55 , n_ghost_indices_in_larger_set(0)
56 , my_pid(0)
57 , n_procs(1)
58 , communicator(MPI_COMM_SELF)
59 , have_ghost_indices(false)
60 {
61 locally_owned_range_data.add_range(0, size);
62 locally_owned_range_data.compress();
63 ghost_indices_data.set_size(size);
64 }
65
66
67
68 Partitioner::Partitioner(const types::global_dof_index local_size,
69 const types::global_dof_index ghost_size,
70 const MPI_Comm communicator)
71 : global_size(Utilities::MPI::sum<types::global_dof_index>(local_size,
72 communicator))
73 , locally_owned_range_data(global_size)
74 , local_range_data{0, local_size}
75 , n_ghost_indices_data(ghost_size)
76 , n_import_indices_data(0)
77 , n_ghost_indices_in_larger_set(0)
78 , my_pid(Utilities::MPI::this_mpi_process(communicator))
79 , n_procs(Utilities::MPI::n_mpi_processes(communicator))
80 , communicator(communicator)
81 , have_ghost_indices(true)
82 {
83 types::global_dof_index prefix_sum = 0;
84
85# ifdef DEAL_II_WITH_MPI
86 const int ierr =
87 MPI_Exscan(&local_size,
88 &prefix_sum,
89 1,
90 Utilities::MPI::mpi_type_id_for_type<decltype(prefix_sum)>,
91 MPI_SUM,
92 communicator);
93 AssertThrowMPI(ierr);
94# endif
95
96 local_range_data = {prefix_sum, prefix_sum + local_size};
97
98 locally_owned_range_data.add_range(prefix_sum, prefix_sum + local_size);
99 locally_owned_range_data.compress();
100 }
101
102
103
104 Partitioner::Partitioner(const IndexSet &locally_owned_indices,
105 const IndexSet &ghost_indices_in,
106 const MPI_Comm communicator_in)
107 : global_size(
108 static_cast<types::global_dof_index>(locally_owned_indices.size()))
109 , n_ghost_indices_data(0)
110 , n_import_indices_data(0)
111 , n_ghost_indices_in_larger_set(0)
112 , my_pid(0)
113 , n_procs(1)
114 , communicator(communicator_in)
115 , have_ghost_indices(false)
116 {
117 set_owned_indices(locally_owned_indices);
118 set_ghost_indices(ghost_indices_in);
119 }
120
121
122
123 Partitioner::Partitioner(const IndexSet &locally_owned_indices,
124 const MPI_Comm communicator_in)
125 : global_size(
126 static_cast<types::global_dof_index>(locally_owned_indices.size()))
127 , n_ghost_indices_data(0)
128 , n_import_indices_data(0)
129 , n_ghost_indices_in_larger_set(0)
130 , my_pid(0)
131 , n_procs(1)
132 , communicator(communicator_in)
133 , have_ghost_indices(false)
134 {
135 set_owned_indices(locally_owned_indices);
136 }
137
138
139
140 void
141 Partitioner::reinit(const IndexSet &locally_owned_indices,
142 const IndexSet &ghost_indices,
143 const MPI_Comm communicator_in)
144 {
145 have_ghost_indices = false;
146 communicator = communicator_in;
147 set_owned_indices(locally_owned_indices);
148 set_ghost_indices(ghost_indices);
149 }
150
151
152
153 void
154 Partitioner::set_owned_indices(const IndexSet &locally_owned_indices)
155 {
156 my_pid = Utilities::MPI::this_mpi_process(communicator);
158
159 // set the local range
160 Assert(locally_owned_indices.is_contiguous() == true,
161 ExcMessage("The index set specified in locally_owned_indices "
162 "is not contiguous."));
163 locally_owned_indices.compress();
164 if (locally_owned_indices.n_elements() > 0)
165 local_range_data =
166 std::pair<types::global_dof_index, types::global_dof_index>(
167 locally_owned_indices.nth_index_in_set(0),
168 locally_owned_indices.nth_index_in_set(0) +
169 locally_owned_indices.n_elements());
171 local_range_data.second - local_range_data.first <
172 static_cast<types::global_dof_index>(
173 std::numeric_limits<unsigned int>::max()),
175 "Index overflow: This class supports at most 2^32-1 locally owned vector entries"));
176 locally_owned_range_data.set_size(locally_owned_indices.size());
177 locally_owned_range_data.add_range(local_range_data.first,
178 local_range_data.second);
179 locally_owned_range_data.compress();
180
181 ghost_indices_data.set_size(locally_owned_indices.size());
182 }
183
184
185
186 void
187 Partitioner::set_ghost_indices(const IndexSet &ghost_indices_in,
188 const IndexSet &larger_ghost_index_set)
189 {
190 // Set ghost indices from input. To be sure that no entries from the
191 // locally owned range are present, subtract the locally owned indices
192 // in any case.
193 Assert(ghost_indices_in.n_elements() == 0 ||
194 ghost_indices_in.size() == locally_owned_range_data.size(),
195 ExcDimensionMismatch(ghost_indices_in.size(),
196 locally_owned_range_data.size()));
197
198 ghost_indices_data = ghost_indices_in;
199 if (ghost_indices_data.size() != locally_owned_range_data.size())
200 ghost_indices_data.set_size(locally_owned_range_data.size());
201 ghost_indices_data.subtract_set(locally_owned_range_data);
202 ghost_indices_data.compress();
204 ghost_indices_data.n_elements() <
205 static_cast<types::global_dof_index>(
206 std::numeric_limits<unsigned int>::max()),
208 "Index overflow: This class supports at most 2^32-1 ghost elements"));
209 n_ghost_indices_data = ghost_indices_data.n_elements();
210
211 have_ghost_indices =
212 Utilities::MPI::max(n_ghost_indices_data, communicator) > 0;
213
214 // In the rest of this function, we determine the point-to-point
215 // communication pattern of the partitioner. We make up a list with both
216 // the processors the ghost indices actually belong to, and the indices
217 // that are locally held but ghost indices of other processors. This
218 // allows then to import and export data very easily.
219
220 // find out the end index for each processor and communicate it (this
221 // implies the start index for the next processor)
222# ifdef DEAL_II_WITH_MPI
223 if (n_procs < 2)
224 {
225 Assert(ghost_indices_data.n_elements() == 0, ExcInternalError());
226 Assert(n_import_indices_data == 0, ExcInternalError());
227 Assert(n_ghost_indices_data == 0, ExcInternalError());
228 return;
229 }
230
232
233 // Allow non-zero start index for the vector. Part 1:
234 // Assume for now that the index set of rank 0 starts with 0
235 // and therefore has an increased size.
236 if (my_pid == 0)
237 my_size += local_range_data.first;
238
239 types::global_dof_index my_shift = 0;
240 {
241 const int ierr = MPI_Exscan(
242 &my_size,
243 &my_shift,
244 1,
245 Utilities::MPI::mpi_type_id_for_type<types::global_dof_index>,
246 MPI_SUM,
247 communicator);
248 AssertThrowMPI(ierr);
249 }
250
251 // Allow non-zero start index for the vector. Part 2:
252 // We correct the assumption made above and let the
253 // index set of rank 0 actually start from the
254 // correct value, i.e. we correct the shift to
255 // its start.
256 if (my_pid == 0)
257 my_shift = local_range_data.first;
258
259 // Fix the index start in case the index set could not give us that
260 // information.
261 if (local_range_data.first == 0 && my_shift != 0)
262 {
263 const types::global_dof_index old_locally_owned_size =
265 local_range_data.first = my_shift;
266 local_range_data.second = my_shift + old_locally_owned_size;
267 }
268
269 const auto [owning_ranks_of_ghosts, import_data] =
271 locally_owned_range_data, ghost_indices_data, communicator);
272
273
274 {
275 ghost_targets_data = {};
276
277 if (owning_ranks_of_ghosts.size() > 0)
278 {
279 ghost_targets_data.emplace_back(owning_ranks_of_ghosts[0], 0);
280 for (auto i : owning_ranks_of_ghosts)
281 {
282 Assert(i >= ghost_targets_data.back().first,
284 "Expect result of ConsensusAlgorithms::Process to be "
285 "sorted."));
286 if (i == ghost_targets_data.back().first)
287 ghost_targets_data.back().second++;
288 else
289 ghost_targets_data.emplace_back(i, 1);
290 }
291 }
292 }
293
294 // count import requests and set up the compressed indices
295 n_import_indices_data = 0;
296 import_targets_data = {};
297 import_targets_data.reserve(import_data.size());
298 import_indices_chunks_by_rank_data = {};
299 import_indices_chunks_by_rank_data.reserve(import_data.size());
300 import_indices_chunks_by_rank_data.resize(1);
301 for (const auto &i : import_data)
302 if (i.second.n_elements() > 0)
303 {
304 import_targets_data.emplace_back(i.first, i.second.n_elements());
305 n_import_indices_data += i.second.n_elements();
306 import_indices_chunks_by_rank_data.push_back(
307 import_indices_chunks_by_rank_data.back() +
308 i.second.n_intervals());
309 }
310
311 // transform import indices to local index space
312 import_indices_data = {};
313 import_indices_data.reserve(import_indices_chunks_by_rank_data.back());
314 for (const auto &i : import_data)
315 {
316 Assert((i.second & locally_owned_range_data) == i.second,
317 ExcInternalError("Requested indices must be in local range"));
318 for (auto interval = i.second.begin_intervals();
319 interval != i.second.end_intervals();
320 ++interval)
321 import_indices_data.emplace_back(*interval->begin() -
322 local_range_data.first,
323 interval->last() + 1 -
324 local_range_data.first);
325 }
326
327 if constexpr (running_in_debug_mode())
328 {
329 // simple check: the number of processors to which we want to send
330 // ghosts and the processors to which ghosts reference should be the
331 // same
333 Utilities::MPI::sum(import_targets_data.size(), communicator),
334 Utilities::MPI::sum(ghost_targets_data.size(), communicator));
335
336 // simple check: the number of indices to exchange should match from
337 // the ghost indices side and the import indices side
339 Utilities::MPI::sum(n_import_indices_data, communicator),
340 Utilities::MPI::sum(n_ghost_indices_data, communicator));
341
342 // expensive check that the communication channel is sane -> do a
343 // ghost exchange step and see whether the ghost indices sent to us by
344 // other processes (ghost_indices) are the same as we hold locally
345 // (ghost_indices_ref).
346 const std::vector<types::global_dof_index> ghost_indices_ref =
347 ghost_indices_data.get_index_vector();
348 AssertDimension(ghost_indices_ref.size(), n_ghost_indices());
349 std::vector<types::global_dof_index> indices_to_send(
350 n_import_indices());
351 std::vector<types::global_dof_index> ghost_indices(n_ghost_indices());
352
353 const std::vector<types::global_dof_index> my_indices =
354 locally_owned_range_data.get_index_vector();
355 std::vector<MPI_Request> requests;
356 n_ghost_indices_in_larger_set = n_ghost_indices_data;
357 export_to_ghosted_array_start(
358 127,
360 my_indices.size()),
361 make_array_view(indices_to_send),
362 make_array_view(ghost_indices),
363 requests);
364 export_to_ghosted_array_finish(make_array_view(ghost_indices),
365 requests);
366 int flag = 0;
367 const int ierr = MPI_Testall(requests.size(),
368 requests.data(),
369 &flag,
370 MPI_STATUSES_IGNORE);
371 AssertThrowMPI(ierr);
372 Assert(flag == 1,
374 "MPI found unfinished requests. Check communication setup"));
375
376 for (unsigned int i = 0; i < ghost_indices.size(); ++i)
377 AssertDimension(ghost_indices[i], ghost_indices_ref[i]);
378 }
379
380# endif // #ifdef DEAL_II_WITH_MPI
381
382 if (larger_ghost_index_set.size() == 0)
383 {
384 ghost_indices_subset_chunks_by_rank_data.clear();
385 ghost_indices_subset_data.emplace_back(0, n_ghost_indices());
386 n_ghost_indices_in_larger_set = n_ghost_indices_data;
387 }
388 else
389 {
390 AssertDimension(larger_ghost_index_set.size(),
391 ghost_indices_data.size());
392 Assert(
393 (larger_ghost_index_set & locally_owned_range_data).n_elements() ==
394 0,
395 ExcMessage("Ghost index set should not overlap with owned set."));
396 Assert((larger_ghost_index_set & ghost_indices_data) ==
397 ghost_indices_data,
398 ExcMessage("Larger ghost index set must contain the tight "
399 "ghost index set."));
400
401 n_ghost_indices_in_larger_set = larger_ghost_index_set.n_elements();
402
403 // first translate tight ghost indices into indices within the large
404 // set:
405 std::vector<unsigned int> expanded_numbering;
406 for (const ::IndexSet::size_type index : ghost_indices_data)
407 {
408 Assert(larger_ghost_index_set.is_element(index),
409 ExcMessage("The given larger ghost index set must contain "
410 "all indices in the actual index set."));
411 Assert(
412 larger_ghost_index_set.index_within_set(index) <
413 static_cast<types::global_dof_index>(
414 std::numeric_limits<unsigned int>::max()),
416 "Index overflow: This class supports at most 2^32-1 ghost elements"));
417 expanded_numbering.push_back(
418 larger_ghost_index_set.index_within_set(index));
419 }
420
421 // now rework expanded_numbering into ranges and store in:
422 std::vector<std::pair<unsigned int, unsigned int>>
423 ghost_indices_subset;
424 ghost_indices_subset_chunks_by_rank_data.resize(
425 ghost_targets_data.size() + 1);
426 // also populate ghost_indices_subset_chunks_by_rank_data
427 ghost_indices_subset_chunks_by_rank_data[0] = 0;
428 unsigned int shift = 0;
429 for (unsigned int p = 0; p < ghost_targets_data.size(); ++p)
430 {
431 unsigned int last_index = numbers::invalid_unsigned_int - 1;
432 for (unsigned int ii = 0; ii < ghost_targets_data[p].second; ++ii)
433 {
434 const unsigned int i = shift + ii;
435 if (expanded_numbering[i] == last_index + 1)
436 // if contiguous, increment the end of last range:
437 ghost_indices_subset.back().second++;
438 else
439 // otherwise start a new range
440 ghost_indices_subset.emplace_back(expanded_numbering[i],
441 expanded_numbering[i] +
442 1);
443 last_index = expanded_numbering[i];
444 }
445 shift += ghost_targets_data[p].second;
446 ghost_indices_subset_chunks_by_rank_data[p + 1] =
447 ghost_indices_subset.size();
448 }
449 ghost_indices_subset_data = ghost_indices_subset;
450 }
451 }
452
453
454
455 bool
456 Partitioner::is_compatible(const Partitioner &part) const
457 {
458 // if the partitioner points to the same memory location as the calling
459 // processor
460 if (&part == this)
461 return true;
462# ifdef DEAL_II_WITH_MPI
464 {
465 int communicators_same = 0;
466 const int ierr = MPI_Comm_compare(part.communicator,
467 communicator,
468 &communicators_same);
469 AssertThrowMPI(ierr);
470 if (!(communicators_same == MPI_IDENT ||
471 communicators_same == MPI_CONGRUENT))
472 return false;
473 }
474# endif
475 return (global_size == part.global_size &&
476 local_range_data == part.local_range_data &&
477 ghost_indices_data == part.ghost_indices_data);
478 }
479
480
481
482 bool
483 Partitioner::is_globally_compatible(const Partitioner &part) const
484 {
485 return Utilities::MPI::min(static_cast<int>(is_compatible(part)),
486 communicator) == 1;
487 }
488
489
490
491 std::size_t
492 Partitioner::memory_consumption() const
493 {
494 std::size_t memory = MemoryConsumption::memory_consumption(global_size);
495 memory += locally_owned_range_data.memory_consumption();
496 memory += MemoryConsumption::memory_consumption(local_range_data);
497 memory += ghost_indices_data.memory_consumption();
498 memory += sizeof(n_ghost_indices_data);
499 memory += MemoryConsumption::memory_consumption(ghost_targets_data);
500 memory += MemoryConsumption::memory_consumption(import_indices_data);
501 memory += sizeof(import_indices_plain_dev) +
502 sizeof(*import_indices_plain_dev.begin()) *
503 import_indices_plain_dev.capacity();
504 memory += MemoryConsumption::memory_consumption(n_import_indices_data);
505 memory += MemoryConsumption::memory_consumption(import_targets_data);
507 import_indices_chunks_by_rank_data);
508 memory +=
509 MemoryConsumption::memory_consumption(n_ghost_indices_in_larger_set);
511 ghost_indices_subset_chunks_by_rank_data);
512 memory +=
513 MemoryConsumption::memory_consumption(ghost_indices_subset_data);
516 memory += MemoryConsumption::memory_consumption(communicator);
517 memory += MemoryConsumption::memory_consumption(have_ghost_indices);
518 return memory;
519 }
520
521
522
523 void
524 Partitioner::initialize_import_indices_plain_dev() const
525 {
526 const unsigned int n_import_targets = import_targets_data.size();
527 import_indices_plain_dev.reserve(n_import_targets);
528 for (unsigned int i = 0; i < n_import_targets; ++i)
529 {
530 // Expand the indices on the host
531 std::vector<std::pair<unsigned int, unsigned int>>::const_iterator
532 my_imports = import_indices_data.begin() +
533 import_indices_chunks_by_rank_data[i],
534 end_my_imports = import_indices_data.begin() +
535 import_indices_chunks_by_rank_data[i + 1];
536 std::vector<unsigned int> import_indices_plain_host;
537 for (; my_imports != end_my_imports; ++my_imports)
538 {
539 const unsigned int chunk_size =
540 my_imports->second - my_imports->first;
541 for (unsigned int j = 0; j < chunk_size; ++j)
542 import_indices_plain_host.push_back(my_imports->first + j);
543 }
544
545 // Move the indices to the device
546 const auto chunk_size = import_indices_plain_host.size();
547 import_indices_plain_dev.emplace_back("import_indices_plain_dev" +
548 std::to_string(i),
549 chunk_size);
550 Kokkos::deep_copy(import_indices_plain_dev.back(),
551 Kokkos::View<unsigned int *, Kokkos::HostSpace>(
552 import_indices_plain_host.data(), chunk_size));
553 }
554 }
555
556 } // namespace MPI
557
558} // end of namespace Utilities
559
560#endif
561
562// explicit instantiations from .templates.h file
563#include "base/partitioner.inst"
564
ArrayView< std::remove_reference_t< typename std::iterator_traits< Iterator >::reference >, MemorySpaceType > make_array_view(const Iterator begin, const Iterator end)
Definition array_view.h:954
bool is_contiguous() const
Definition index_set.h:1928
size_type size() const
Definition index_set.h:1787
size_type index_within_set(const size_type global_index) const
Definition index_set.h:2013
size_type n_elements() const
Definition index_set.h:1945
bool is_element(const size_type index) const
Definition index_set.h:1905
void set_size(const size_type size)
Definition index_set.h:1775
size_type nth_index_in_set(const size_type local_index) const
Definition index_set.h:1994
void compress() const
Definition index_set.h:1795
#define DEAL_II_NAMESPACE_OPEN
Definition config.h:35
constexpr bool running_in_debug_mode()
Definition config.h:73
#define DEAL_II_NAMESPACE_CLOSE
Definition config.h:36
Point< 2 > second
Definition grid_out.cc:4633
#define Assert(cond, exc)
#define AssertDimension(dim1, dim2)
#define AssertThrowMPI(error_code)
static ::ExceptionBase & ExcInternalError()
static ::ExceptionBase & ExcDimensionMismatch(std::size_t arg1, std::size_t arg2)
static ::ExceptionBase & ExcMessage(std::string arg1)
#define AssertThrow(cond, exc)
std::size_t size
Definition mpi.cc:745
types::global_dof_index locally_owned_size
Definition mpi.cc:833
const unsigned int n_procs
Definition mpi.cc:935
void shift(const Tensor< 1, spacedim > &shift_vector, Triangulation< dim, spacedim > &triangulation)
std::enable_if_t< std::is_fundamental_v< T >, std::size_t > memory_consumption(const T &t)
std::pair< std::vector< unsigned int >, std::map< unsigned int, IndexSet > > compute_index_owner_and_requesters(const IndexSet &owned_indices, const IndexSet &indices_to_look_up, const MPI_Comm &comm)
Definition mpi.cc:1886
T sum(const T &t, const MPI_Comm mpi_communicator)
unsigned int n_mpi_processes(const MPI_Comm mpi_communicator)
Definition mpi.cc:99
T max(const T &t, const MPI_Comm mpi_communicator)
T min(const T &t, const MPI_Comm mpi_communicator)
unsigned int this_mpi_process(const MPI_Comm mpi_communicator)
Definition mpi.cc:114
bool job_supports_mpi()
Definition mpi.cc:692
const MPI_Datatype mpi_type_id_for_type
Definition mpi.h:1634
constexpr unsigned int invalid_unsigned_int
Definition types.h:238
STL namespace.
Definition types.h:32
unsigned int global_dof_index
Definition types.h:94