Reference documentation for deal.II version 9.6.0
\(\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\}}\)
Loading...
Searching...
No Matches
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
17#include <deal.II/base/partitioner.templates.h>
18
19#include <boost/serialization/utility.hpp>
20
21#include <limits>
22
24
25#ifndef DOXYGEN
26namespace Utilities
27{
28 namespace MPI
29 {
31 : global_size(0)
32 , local_range_data(
33 std::pair<types::global_dof_index, types::global_dof_index>(0, 0))
34 , n_ghost_indices_data(0)
35 , n_import_indices_data(0)
36 , n_ghost_indices_in_larger_set(0)
37 , my_pid(0)
38 , n_procs(1)
39 , communicator(MPI_COMM_SELF)
40 , have_ghost_indices(false)
41 {}
42
43
44
45 Partitioner::Partitioner(const unsigned int size)
46 : global_size(size)
47 , locally_owned_range_data(size)
48 , local_range_data(
49 std::pair<types::global_dof_index, types::global_dof_index>(0, size))
50 , n_ghost_indices_data(0)
51 , n_import_indices_data(0)
52 , n_ghost_indices_in_larger_set(0)
53 , my_pid(0)
54 , n_procs(1)
55 , communicator(MPI_COMM_SELF)
56 , have_ghost_indices(false)
57 {
58 locally_owned_range_data.add_range(0, size);
59 locally_owned_range_data.compress();
60 ghost_indices_data.set_size(size);
61 }
62
63
64
65 Partitioner::Partitioner(const types::global_dof_index local_size,
66 const types::global_dof_index ghost_size,
67 const MPI_Comm communicator)
68 : global_size(Utilities::MPI::sum<types::global_dof_index>(local_size,
69 communicator))
70 , locally_owned_range_data(global_size)
71 , local_range_data{0, local_size}
72 , n_ghost_indices_data(ghost_size)
73 , n_import_indices_data(0)
74 , n_ghost_indices_in_larger_set(0)
75 , my_pid(Utilities::MPI::this_mpi_process(communicator))
76 , n_procs(Utilities::MPI::n_mpi_processes(communicator))
77 , communicator(communicator)
78 , have_ghost_indices(true)
79 {
80 types::global_dof_index prefix_sum = 0;
81
82# ifdef DEAL_II_WITH_MPI
83 const int ierr =
84 MPI_Exscan(&local_size,
85 &prefix_sum,
86 1,
87 Utilities::MPI::mpi_type_id_for_type<decltype(prefix_sum)>,
88 MPI_SUM,
89 communicator);
90 AssertThrowMPI(ierr);
91# endif
92
93 local_range_data = {prefix_sum, prefix_sum + local_size};
94
95 locally_owned_range_data.add_range(prefix_sum, prefix_sum + local_size);
96 locally_owned_range_data.compress();
97 }
98
99
100
101 Partitioner::Partitioner(const IndexSet &locally_owned_indices,
102 const IndexSet &ghost_indices_in,
103 const MPI_Comm communicator_in)
104 : global_size(
105 static_cast<types::global_dof_index>(locally_owned_indices.size()))
106 , n_ghost_indices_data(0)
107 , n_import_indices_data(0)
108 , n_ghost_indices_in_larger_set(0)
109 , my_pid(0)
110 , n_procs(1)
111 , communicator(communicator_in)
112 , have_ghost_indices(false)
113 {
114 set_owned_indices(locally_owned_indices);
115 set_ghost_indices(ghost_indices_in);
116 }
117
118
119
120 Partitioner::Partitioner(const IndexSet &locally_owned_indices,
121 const MPI_Comm communicator_in)
122 : global_size(
123 static_cast<types::global_dof_index>(locally_owned_indices.size()))
124 , n_ghost_indices_data(0)
125 , n_import_indices_data(0)
126 , n_ghost_indices_in_larger_set(0)
127 , my_pid(0)
128 , n_procs(1)
129 , communicator(communicator_in)
130 , have_ghost_indices(false)
131 {
132 set_owned_indices(locally_owned_indices);
133 }
134
135
136
137 void
138 Partitioner::reinit(const IndexSet &locally_owned_indices,
139 const IndexSet &ghost_indices,
140 const MPI_Comm communicator_in)
141 {
142 have_ghost_indices = false;
143 communicator = communicator_in;
144 set_owned_indices(locally_owned_indices);
145 set_ghost_indices(ghost_indices);
146 }
147
148
149
150 void
151 Partitioner::set_owned_indices(const IndexSet &locally_owned_indices)
152 {
153 my_pid = Utilities::MPI::this_mpi_process(communicator);
154 n_procs = Utilities::MPI::n_mpi_processes(communicator);
155
156 // set the local range
157 Assert(locally_owned_indices.is_contiguous() == true,
158 ExcMessage("The index set specified in locally_owned_indices "
159 "is not contiguous."));
160 locally_owned_indices.compress();
161 if (locally_owned_indices.n_elements() > 0)
162 local_range_data =
163 std::pair<types::global_dof_index, types::global_dof_index>(
164 locally_owned_indices.nth_index_in_set(0),
165 locally_owned_indices.nth_index_in_set(0) +
166 locally_owned_indices.n_elements());
168 local_range_data.second - local_range_data.first <
169 static_cast<types::global_dof_index>(
170 std::numeric_limits<unsigned int>::max()),
172 "Index overflow: This class supports at most 2^32-1 locally owned vector entries"));
173 locally_owned_range_data.set_size(locally_owned_indices.size());
174 locally_owned_range_data.add_range(local_range_data.first,
175 local_range_data.second);
176 locally_owned_range_data.compress();
177
178 ghost_indices_data.set_size(locally_owned_indices.size());
179 }
180
181
182
183 void
184 Partitioner::set_ghost_indices(const IndexSet &ghost_indices_in,
185 const IndexSet &larger_ghost_index_set)
186 {
187 // Set ghost indices from input. To be sure that no entries from the
188 // locally owned range are present, subtract the locally owned indices
189 // in any case.
190 Assert(ghost_indices_in.n_elements() == 0 ||
191 ghost_indices_in.size() == locally_owned_range_data.size(),
192 ExcDimensionMismatch(ghost_indices_in.size(),
193 locally_owned_range_data.size()));
194
195 ghost_indices_data = ghost_indices_in;
196 if (ghost_indices_data.size() != locally_owned_range_data.size())
197 ghost_indices_data.set_size(locally_owned_range_data.size());
198 ghost_indices_data.subtract_set(locally_owned_range_data);
199 ghost_indices_data.compress();
201 ghost_indices_data.n_elements() <
202 static_cast<types::global_dof_index>(
203 std::numeric_limits<unsigned int>::max()),
205 "Index overflow: This class supports at most 2^32-1 ghost elements"));
206 n_ghost_indices_data = ghost_indices_data.n_elements();
207
208 have_ghost_indices =
209 Utilities::MPI::max(n_ghost_indices_data, communicator) > 0;
210
211 // In the rest of this function, we determine the point-to-point
212 // communication pattern of the partitioner. We make up a list with both
213 // the processors the ghost indices actually belong to, and the indices
214 // that are locally held but ghost indices of other processors. This
215 // allows then to import and export data very easily.
216
217 // find out the end index for each processor and communicate it (this
218 // implies the start index for the next processor)
219# ifdef DEAL_II_WITH_MPI
220 if (n_procs < 2)
221 {
222 Assert(ghost_indices_data.n_elements() == 0, ExcInternalError());
223 Assert(n_import_indices_data == 0, ExcInternalError());
224 Assert(n_ghost_indices_data == 0, ExcInternalError());
225 return;
226 }
227
228 types::global_dof_index my_size = locally_owned_size();
229
230 // Allow non-zero start index for the vector. Part 1:
231 // Assume for now that the index set of rank 0 starts with 0
232 // and therefore has an increased size.
233 if (my_pid == 0)
234 my_size += local_range_data.first;
235
236 types::global_dof_index my_shift = 0;
237 {
238 const int ierr = MPI_Exscan(&my_size,
239 &my_shift,
240 1,
242 MPI_SUM,
243 communicator);
244 AssertThrowMPI(ierr);
245 }
246
247 // Allow non-zero start index for the vector. Part 2:
248 // We correct the assumption made above and let the
249 // index set of rank 0 actually start from the
250 // correct value, i.e. we correct the shift to
251 // its start.
252 if (my_pid == 0)
253 my_shift = local_range_data.first;
254
255 // Fix the index start in case the index set could not give us that
256 // information.
257 if (local_range_data.first == 0 && my_shift != 0)
258 {
259 const types::global_dof_index old_locally_owned_size =
260 locally_owned_size();
261 local_range_data.first = my_shift;
262 local_range_data.second = my_shift + old_locally_owned_size;
263 }
264
265 std::vector<unsigned int> owning_ranks_of_ghosts(
266 ghost_indices_data.n_elements());
267
268 // set up dictionary
269 internal::ComputeIndexOwner::ConsensusAlgorithmsPayload process(
270 locally_owned_range_data,
271 ghost_indices_data,
272 communicator,
273 owning_ranks_of_ghosts,
274 /* track origins of ghosts*/ true);
275
276 // read dictionary by communicating with the process who owns the index
277 // in the static partition (i.e. in the dictionary). This process
278 // returns the actual owner of the index.
279 ConsensusAlgorithms::Selector<
280 std::vector<
281 std::pair<types::global_dof_index, types::global_dof_index>>,
282 std::vector<unsigned int>>
283 consensus_algorithm;
284 consensus_algorithm.run(process, communicator);
285
286 {
287 ghost_targets_data = {};
288
289 if (owning_ranks_of_ghosts.size() > 0)
290 {
291 ghost_targets_data.emplace_back(owning_ranks_of_ghosts[0], 0);
292 for (auto i : owning_ranks_of_ghosts)
293 {
294 Assert(i >= ghost_targets_data.back().first,
296 "Expect result of ConsensusAlgorithms::Process to be "
297 "sorted."));
298 if (i == ghost_targets_data.back().first)
299 ghost_targets_data.back().second++;
300 else
301 ghost_targets_data.emplace_back(i, 1);
302 }
303 }
304 }
305
306 // find how much the individual processes that want import from me
307 std::map<unsigned int, IndexSet> import_data = process.get_requesters();
308
309 // count import requests and set up the compressed indices
310 n_import_indices_data = 0;
311 import_targets_data = {};
312 import_targets_data.reserve(import_data.size());
313 import_indices_chunks_by_rank_data = {};
314 import_indices_chunks_by_rank_data.reserve(import_data.size());
315 import_indices_chunks_by_rank_data.resize(1);
316 for (const auto &i : import_data)
317 if (i.second.n_elements() > 0)
318 {
319 import_targets_data.emplace_back(i.first, i.second.n_elements());
320 n_import_indices_data += i.second.n_elements();
321 import_indices_chunks_by_rank_data.push_back(
322 import_indices_chunks_by_rank_data.back() +
323 i.second.n_intervals());
324 }
325
326 // transform import indices to local index space
327 import_indices_data = {};
328 import_indices_data.reserve(import_indices_chunks_by_rank_data.back());
329 for (const auto &i : import_data)
330 {
331 Assert((i.second & locally_owned_range_data) == i.second,
332 ExcInternalError("Requested indices must be in local range"));
333 for (auto interval = i.second.begin_intervals();
334 interval != i.second.end_intervals();
335 ++interval)
336 import_indices_data.emplace_back(*interval->begin() -
337 local_range_data.first,
338 interval->last() + 1 -
339 local_range_data.first);
340 }
341
342# ifdef DEBUG
343
344 // simple check: the number of processors to which we want to send
345 // ghosts and the processors to which ghosts reference should be the
346 // same
348 Utilities::MPI::sum(import_targets_data.size(), communicator),
349 Utilities::MPI::sum(ghost_targets_data.size(), communicator));
350
351 // simple check: the number of indices to exchange should match from the
352 // ghost indices side and the import indices side
353 AssertDimension(Utilities::MPI::sum(n_import_indices_data, communicator),
354 Utilities::MPI::sum(n_ghost_indices_data, communicator));
355
356 // expensive check that the communication channel is sane -> do a ghost
357 // exchange step and see whether the ghost indices sent to us by other
358 // processes (ghost_indices) are the same as we hold locally
359 // (ghost_indices_ref).
360 const std::vector<types::global_dof_index> ghost_indices_ref =
361 ghost_indices_data.get_index_vector();
362 AssertDimension(ghost_indices_ref.size(), n_ghost_indices());
363 std::vector<types::global_dof_index> indices_to_send(n_import_indices());
364 std::vector<types::global_dof_index> ghost_indices(n_ghost_indices());
365
366 const std::vector<types::global_dof_index> my_indices =
367 locally_owned_range_data.get_index_vector();
368 std::vector<MPI_Request> requests;
369 n_ghost_indices_in_larger_set = n_ghost_indices_data;
370 export_to_ghosted_array_start(127,
372 my_indices.data(), my_indices.size()),
373 make_array_view(indices_to_send),
374 make_array_view(ghost_indices),
375 requests);
376 export_to_ghosted_array_finish(make_array_view(ghost_indices), requests);
377 int flag = 0;
378 const int ierr = MPI_Testall(requests.size(),
379 requests.data(),
380 &flag,
381 MPI_STATUSES_IGNORE);
382 AssertThrowMPI(ierr);
383 Assert(flag == 1,
385 "MPI found unfinished requests. Check communication setup"));
386
387 for (unsigned int i = 0; i < ghost_indices.size(); ++i)
388 AssertDimension(ghost_indices[i], ghost_indices_ref[i]);
389
390# endif
391
392# endif // #ifdef DEAL_II_WITH_MPI
393
394 if (larger_ghost_index_set.size() == 0)
395 {
396 ghost_indices_subset_chunks_by_rank_data.clear();
397 ghost_indices_subset_data.emplace_back(0, n_ghost_indices());
398 n_ghost_indices_in_larger_set = n_ghost_indices_data;
399 }
400 else
401 {
402 AssertDimension(larger_ghost_index_set.size(),
403 ghost_indices_data.size());
404 Assert(
405 (larger_ghost_index_set & locally_owned_range_data).n_elements() ==
406 0,
407 ExcMessage("Ghost index set should not overlap with owned set."));
408 Assert((larger_ghost_index_set & ghost_indices_data) ==
409 ghost_indices_data,
410 ExcMessage("Larger ghost index set must contain the tight "
411 "ghost index set."));
412
413 n_ghost_indices_in_larger_set = larger_ghost_index_set.n_elements();
414
415 // first translate tight ghost indices into indices within the large
416 // set:
417 std::vector<unsigned int> expanded_numbering;
418 for (const ::IndexSet::size_type index : ghost_indices_data)
419 {
420 Assert(larger_ghost_index_set.is_element(index),
421 ExcMessage("The given larger ghost index set must contain "
422 "all indices in the actual index set."));
423 Assert(
424 larger_ghost_index_set.index_within_set(index) <
425 static_cast<types::global_dof_index>(
426 std::numeric_limits<unsigned int>::max()),
428 "Index overflow: This class supports at most 2^32-1 ghost elements"));
429 expanded_numbering.push_back(
430 larger_ghost_index_set.index_within_set(index));
431 }
432
433 // now rework expanded_numbering into ranges and store in:
434 std::vector<std::pair<unsigned int, unsigned int>>
435 ghost_indices_subset;
436 ghost_indices_subset_chunks_by_rank_data.resize(
437 ghost_targets_data.size() + 1);
438 // also populate ghost_indices_subset_chunks_by_rank_data
439 ghost_indices_subset_chunks_by_rank_data[0] = 0;
440 unsigned int shift = 0;
441 for (unsigned int p = 0; p < ghost_targets_data.size(); ++p)
442 {
443 unsigned int last_index = numbers::invalid_unsigned_int - 1;
444 for (unsigned int ii = 0; ii < ghost_targets_data[p].second; ++ii)
445 {
446 const unsigned int i = shift + ii;
447 if (expanded_numbering[i] == last_index + 1)
448 // if contiguous, increment the end of last range:
449 ghost_indices_subset.back().second++;
450 else
451 // otherwise start a new range
452 ghost_indices_subset.emplace_back(expanded_numbering[i],
453 expanded_numbering[i] +
454 1);
455 last_index = expanded_numbering[i];
456 }
457 shift += ghost_targets_data[p].second;
458 ghost_indices_subset_chunks_by_rank_data[p + 1] =
459 ghost_indices_subset.size();
460 }
461 ghost_indices_subset_data = ghost_indices_subset;
462 }
463 }
464
465
466
467 bool
468 Partitioner::is_compatible(const Partitioner &part) const
469 {
470 // if the partitioner points to the same memory location as the calling
471 // processor
472 if (&part == this)
473 return true;
474# ifdef DEAL_II_WITH_MPI
476 {
477 int communicators_same = 0;
478 const int ierr = MPI_Comm_compare(part.communicator,
479 communicator,
480 &communicators_same);
481 AssertThrowMPI(ierr);
482 if (!(communicators_same == MPI_IDENT ||
483 communicators_same == MPI_CONGRUENT))
484 return false;
485 }
486# endif
487 return (global_size == part.global_size &&
488 local_range_data == part.local_range_data &&
489 ghost_indices_data == part.ghost_indices_data);
490 }
491
492
493
494 bool
495 Partitioner::is_globally_compatible(const Partitioner &part) const
496 {
497 return Utilities::MPI::min(static_cast<int>(is_compatible(part)),
498 communicator) == 1;
499 }
500
501
502
503 std::size_t
504 Partitioner::memory_consumption() const
505 {
506 std::size_t memory = MemoryConsumption::memory_consumption(global_size);
507 memory += locally_owned_range_data.memory_consumption();
508 memory += MemoryConsumption::memory_consumption(local_range_data);
509 memory += ghost_indices_data.memory_consumption();
510 memory += sizeof(n_ghost_indices_data);
511 memory += MemoryConsumption::memory_consumption(ghost_targets_data);
512 memory += MemoryConsumption::memory_consumption(import_indices_data);
513 memory += sizeof(import_indices_plain_dev) +
514 sizeof(*import_indices_plain_dev.begin()) *
515 import_indices_plain_dev.capacity();
516 memory += MemoryConsumption::memory_consumption(n_import_indices_data);
517 memory += MemoryConsumption::memory_consumption(import_targets_data);
519 import_indices_chunks_by_rank_data);
520 memory +=
521 MemoryConsumption::memory_consumption(n_ghost_indices_in_larger_set);
523 ghost_indices_subset_chunks_by_rank_data);
524 memory +=
525 MemoryConsumption::memory_consumption(ghost_indices_subset_data);
527 memory += MemoryConsumption::memory_consumption(n_procs);
528 memory += MemoryConsumption::memory_consumption(communicator);
529 memory += MemoryConsumption::memory_consumption(have_ghost_indices);
530 return memory;
531 }
532
533
534
535 void
536 Partitioner::initialize_import_indices_plain_dev() const
537 {
538 const unsigned int n_import_targets = import_targets_data.size();
539 import_indices_plain_dev.reserve(n_import_targets);
540 for (unsigned int i = 0; i < n_import_targets; ++i)
541 {
542 // Expand the indices on the host
543 std::vector<std::pair<unsigned int, unsigned int>>::const_iterator
544 my_imports = import_indices_data.begin() +
545 import_indices_chunks_by_rank_data[i],
546 end_my_imports = import_indices_data.begin() +
547 import_indices_chunks_by_rank_data[i + 1];
548 std::vector<unsigned int> import_indices_plain_host;
549 for (; my_imports != end_my_imports; ++my_imports)
550 {
551 const unsigned int chunk_size =
552 my_imports->second - my_imports->first;
553 for (unsigned int j = 0; j < chunk_size; ++j)
554 import_indices_plain_host.push_back(my_imports->first + j);
555 }
556
557 // Move the indices to the device
558 const auto chunk_size = import_indices_plain_host.size();
559 import_indices_plain_dev.emplace_back("import_indices_plain_dev" +
560 std::to_string(i),
561 chunk_size);
562 Kokkos::deep_copy(import_indices_plain_dev.back(),
563 Kokkos::View<unsigned int *, Kokkos::HostSpace>(
564 import_indices_plain_host.data(), chunk_size));
565 }
566 }
567
568 } // namespace MPI
569
570} // end of namespace Utilities
571
572#endif
573
574// explicit instantiations from .templates.h file
575#include "partitioner.inst"
576
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:949
bool is_contiguous() const
Definition index_set.h:1917
size_type size() const
Definition index_set.h:1776
size_type index_within_set(const size_type global_index) const
Definition index_set.h:2001
size_type n_elements() const
Definition index_set.h:1934
bool is_element(const size_type index) const
Definition index_set.h:1894
void set_size(const size_type size)
Definition index_set.h:1764
size_type nth_index_in_set(const size_type local_index) const
Definition index_set.h:1982
void compress() const
Definition index_set.h:1784
#define DEAL_II_NAMESPACE_OPEN
Definition config.h:503
#define DEAL_II_NAMESPACE_CLOSE
Definition config.h:504
Point< 2 > second
Definition grid_out.cc:4624
#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)
constexpr int chunk_size
Definition cuda_size.h:34
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)
T sum(const T &t, const MPI_Comm mpi_communicator)
unsigned int n_mpi_processes(const MPI_Comm mpi_communicator)
Definition mpi.cc:92
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:107
bool job_supports_mpi()
Definition mpi.cc:697
const MPI_Datatype mpi_type_id_for_type
Definition mpi.h:1674
static const unsigned int invalid_unsigned_int
Definition types.h:220
STL namespace.
Definition types.h:32
#define DEAL_II_DOF_INDEX_MPI_TYPE
Definition types.h:102