Reference documentation for deal.II version Git 932f7faded 2020-11-28 20:02:43 +0100
\(\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\}}\)
partitioner.cc
Go to the documentation of this file.
1 // ---------------------------------------------------------------------
2 //
3 // Copyright (C) 1999 - 2020 by the deal.II authors
4 //
5 // This file is part of the deal.II library.
6 //
7 // The deal.II library is free software; you can use it, redistribute
8 // it, and/or modify it under the terms of the GNU Lesser General
9 // Public License as published by the Free Software Foundation; either
10 // version 2.1 of the License, or (at your option) any later version.
11 // The full text of the license can be found in the file LICENSE.md at
12 // the top level directory of deal.II.
13 //
14 // ---------------------------------------------------------------------
15 
18 #include <deal.II/base/partitioner.templates.h>
19 
21 
22 namespace Utilities
23 {
24  namespace MPI
25  {
27  : global_size(0)
28  , local_range_data(
30  , n_ghost_indices_data(0)
31  , n_import_indices_data(0)
32  , n_ghost_indices_in_larger_set(0)
33  , my_pid(0)
34  , n_procs(1)
35  , communicator(MPI_COMM_SELF)
36  , have_ghost_indices(false)
37  {}
38 
39 
40 
41  Partitioner::Partitioner(const unsigned int size)
42  : global_size(size)
45  std::pair<types::global_dof_index, types::global_dof_index>(0, size))
49  , my_pid(0)
50  , n_procs(1)
51  , communicator(MPI_COMM_SELF)
52  , have_ghost_indices(false)
53  {
57  }
58 
59 
60 
62  const types::global_dof_index ghost_size,
63  const MPI_Comm & communicator)
64  : global_size(Utilities::MPI::sum<types::global_dof_index>(local_size,
65  communicator))
67  , local_range_data{0, local_size}
68  , n_ghost_indices_data(ghost_size)
74  , have_ghost_indices(true)
75  {
76  types::global_dof_index prefix_sum = 0;
77 
78 #ifdef DEAL_II_WITH_MPI
79  MPI_Exscan(&local_size,
80  &prefix_sum,
81  1,
82  Utilities::MPI::internal::mpi_type_id(&prefix_sum),
83  MPI_SUM,
84  communicator);
85 #endif
86 
87  local_range_data = {prefix_sum, prefix_sum + local_size};
88 
89  locally_owned_range_data.add_range(prefix_sum, prefix_sum + local_size);
91  }
92 
93 
94 
95  Partitioner::Partitioner(const IndexSet &locally_owned_indices,
96  const IndexSet &ghost_indices_in,
97  const MPI_Comm &communicator_in)
98  : global_size(
99  static_cast<types::global_dof_index>(locally_owned_indices.size()))
103  , my_pid(0)
104  , n_procs(1)
105  , communicator(communicator_in)
106  , have_ghost_indices(false)
107  {
108  set_owned_indices(locally_owned_indices);
109  set_ghost_indices(ghost_indices_in);
110  }
111 
112 
113 
114  Partitioner::Partitioner(const IndexSet &locally_owned_indices,
115  const MPI_Comm &communicator_in)
116  : global_size(
117  static_cast<types::global_dof_index>(locally_owned_indices.size()))
121  , my_pid(0)
122  , n_procs(1)
123  , communicator(communicator_in)
124  , have_ghost_indices(false)
125  {
126  set_owned_indices(locally_owned_indices);
127  }
128 
129 
130 
131  void
132  Partitioner::reinit(const IndexSet &vector_space_vector_index_set,
133  const IndexSet &read_write_vector_index_set,
134  const MPI_Comm &communicator_in)
135  {
136  have_ghost_indices = false;
137  communicator = communicator_in;
138  set_owned_indices(vector_space_vector_index_set);
139  set_ghost_indices(read_write_vector_index_set);
140  }
141 
142 
143 
144  void
145  Partitioner::set_owned_indices(const IndexSet &locally_owned_indices)
146  {
147  if (Utilities::MPI::job_supports_mpi() == true)
148  {
151  }
152  else
153  {
154  my_pid = 0;
155  n_procs = 1;
156  }
157 
158  // set the local range
159  Assert(locally_owned_indices.is_contiguous() == true,
160  ExcMessage("The index set specified in locally_owned_indices "
161  "is not contiguous."));
162  locally_owned_indices.compress();
163  if (locally_owned_indices.n_elements() > 0)
165  std::pair<types::global_dof_index, types::global_dof_index>(
166  locally_owned_indices.nth_index_in_set(0),
167  locally_owned_indices.nth_index_in_set(0) +
168  locally_owned_indices.n_elements());
169  AssertThrow(
170  local_range_data.second - local_range_data.first <
171  static_cast<types::global_dof_index>(
173  ExcMessage(
174  "Index overflow: This class supports at most 2^32-1 locally owned vector entries"));
175  locally_owned_range_data.set_size(locally_owned_indices.size());
177  local_range_data.second);
179 
180  ghost_indices_data.set_size(locally_owned_indices.size());
181  }
182 
183 
184 
185  void
186  Partitioner::set_ghost_indices(const IndexSet &ghost_indices_in,
187  const IndexSet &larger_ghost_index_set)
188  {
189  // Set ghost indices from input. To be sure that no entries from the
190  // locally owned range are present, subtract the locally owned indices
191  // in any case.
192  Assert(ghost_indices_in.n_elements() == 0 ||
193  ghost_indices_in.size() == locally_owned_range_data.size(),
194  ExcDimensionMismatch(ghost_indices_in.size(),
196 
197  ghost_indices_data = ghost_indices_in;
202  AssertThrow(
204  static_cast<types::global_dof_index>(
206  ExcMessage(
207  "Index overflow: This class supports at most 2^32-1 ghost elements"));
209 
211  Utilities::MPI::max(n_ghost_indices_data, communicator) > 0;
212 
213  // In the rest of this function, we determine the point-to-point
214  // communication pattern of the partitioner. We make up a list with both
215  // the processors the ghost indices actually belong to, and the indices
216  // that are locally held but ghost indices of other processors. This
217  // allows then to import and export data very easily.
218 
219  // find out the end index for each processor and communicate it (this
220  // implies the start index for the next processor)
221 #ifdef DEAL_II_WITH_MPI
222  if (n_procs < 2)
223  {
226  Assert(n_ghost_indices_data == 0, ExcInternalError());
227  return;
228  }
229 
231 
232  // Allow non-zero start index for the vector. Part 1:
233  // Assume for now that the index set of rank 0 starts with 0
234  // and therefore has an increased size.
235  if (my_pid == 0)
236  my_size += local_range_data.first;
237 
238  types::global_dof_index my_shift = 0;
239  {
240  const int ierr = MPI_Exscan(&my_size,
241  &my_shift,
242  1,
244  MPI_SUM,
245  communicator);
246  AssertThrowMPI(ierr);
247  }
248 
249  // Allow non-zero start index for the vector. Part 2:
250  // We correct the assumption made above and let the
251  // index set of rank 0 actually start from the
252  // correct value, i.e. we correct the shift to
253  // its start.
254  if (my_pid == 0)
255  my_shift = local_range_data.first;
256 
257  // Fix the index start in case the index set could not give us that
258  // information.
259  if (local_range_data.first == 0 && my_shift != 0)
260  {
261  const types::global_dof_index old_local_size = local_size();
262  local_range_data.first = my_shift;
263  local_range_data.second = my_shift + old_local_size;
264  }
265 
266  std::vector<unsigned int> owning_ranks_of_ghosts(
268 
269  // set up dictionary
273  communicator,
274  owning_ranks_of_ghosts,
275  /* track origins of ghosts*/ true);
276 
277  // read dictionary by communicating with the process who owns the index
278  // in the static partition (i.e. in the dictionary). This process
279  // returns the actual owner of the index.
281  std::pair<types::global_dof_index, types::global_dof_index>,
282  unsigned int>
283  consensus_algorithm(process, communicator);
284  consensus_algorithm.run();
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 ConsensusAlgorithmsProcess 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 setup the compressed indices
311  import_targets_data = {};
312  import_targets_data.reserve(import_data.size());
314  import_indices_chunks_by_rank_data.reserve(import_data.size());
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();
323  i.second.n_intervals());
324  }
325 
326  // transform import indices to local index space
327  import_indices_data = {};
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
350 
351  // simple check: the number of indices to exchange should match from the
352  // ghost indices side and the import indices side
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  std::vector<types::global_dof_index> ghost_indices_ref;
361  ghost_indices_data.fill_index_vector(ghost_indices_ref);
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  std::vector<types::global_dof_index> my_indices;
367  std::vector<MPI_Request> requests;
371  my_indices.data(), my_indices.size()),
372  make_array_view(indices_to_send),
373  make_array_view(ghost_indices),
374  requests);
375  export_to_ghosted_array_finish(make_array_view(ghost_indices), requests);
376  int flag = 0;
377  const int ierr = MPI_Testall(requests.size(),
378  requests.data(),
379  &flag,
380  MPI_STATUSES_IGNORE);
381  AssertThrowMPI(ierr);
382  Assert(flag == 1,
383  ExcMessage(
384  "MPI found unfinished requests. Check communication setup"));
385 
386  for (unsigned int i = 0; i < ghost_indices.size(); ++i)
387  AssertDimension(ghost_indices[i], ghost_indices_ref[i]);
388 
389 # endif
390 
391 #endif // #ifdef DEAL_II_WITH_MPI
392 
393  if (larger_ghost_index_set.size() == 0)
394  {
396  ghost_indices_subset_data.emplace_back(0, n_ghost_indices());
398  }
399  else
400  {
401  AssertDimension(larger_ghost_index_set.size(),
403  Assert(
404  (larger_ghost_index_set & locally_owned_range_data).n_elements() ==
405  0,
406  ExcMessage("Ghost index set should not overlap with owned set."));
407  Assert((larger_ghost_index_set & ghost_indices_data) ==
408  ghost_indices_data,
409  ExcMessage("Larger ghost index set must contain the tight "
410  "ghost index set."));
411 
412  n_ghost_indices_in_larger_set = larger_ghost_index_set.n_elements();
413 
414  // first translate tight ghost indices into indices within the large
415  // set:
416  std::vector<unsigned int> expanded_numbering;
417  for (::IndexSet::size_type index : ghost_indices_data)
418  {
419  Assert(larger_ghost_index_set.is_element(index),
420  ExcMessage("The given larger ghost index set must contain "
421  "all indices in the actual index set."));
422  Assert(
423  larger_ghost_index_set.index_within_set(index) <
424  static_cast<types::global_dof_index>(
426  ExcMessage(
427  "Index overflow: This class supports at most 2^32-1 ghost elements"));
428  expanded_numbering.push_back(
429  larger_ghost_index_set.index_within_set(index));
430  }
431 
432  // now rework expanded_numbering into ranges and store in:
433  std::vector<std::pair<unsigned int, unsigned int>>
434  ghost_indices_subset;
436  ghost_targets_data.size() + 1);
437  // also populate ghost_indices_subset_chunks_by_rank_data
439  unsigned int shift = 0;
440  for (unsigned int p = 0; p < ghost_targets_data.size(); ++p)
441  {
442  unsigned int last_index = numbers::invalid_unsigned_int - 1;
443  for (unsigned int ii = 0; ii < ghost_targets_data[p].second; ii++)
444  {
445  const unsigned int i = shift + ii;
446  if (expanded_numbering[i] == last_index + 1)
447  // if contiguous, increment the end of last range:
448  ghost_indices_subset.back().second++;
449  else
450  // otherwise start a new range
451  ghost_indices_subset.emplace_back(expanded_numbering[i],
452  expanded_numbering[i] +
453  1);
454  last_index = expanded_numbering[i];
455  }
456  shift += ghost_targets_data[p].second;
458  ghost_indices_subset.size();
459  }
460  ghost_indices_subset_data = ghost_indices_subset;
461  }
462  }
463 
464 
465 
466  bool
468  {
469  // if the partitioner points to the same memory location as the calling
470  // processor
471  if (&part == this)
472  return true;
473 #ifdef DEAL_II_WITH_MPI
475  {
476  int communicators_same = 0;
477  const int ierr = MPI_Comm_compare(part.communicator,
478  communicator,
479  &communicators_same);
480  AssertThrowMPI(ierr);
481  if (!(communicators_same == MPI_IDENT ||
482  communicators_same == MPI_CONGRUENT))
483  return false;
484  }
485 #endif
486  return (global_size == part.global_size &&
489  }
490 
491 
492 
493  bool
495  {
496  return Utilities::MPI::min(static_cast<int>(is_compatible(part)),
497  communicator) == 1;
498  }
499 
500 
501 
502  std::size_t
504  {
505  std::size_t memory = (3 * sizeof(types::global_dof_index) +
506  4 * sizeof(unsigned int) + sizeof(MPI_Comm));
515  memory +=
518  return memory;
519  }
520 
521  } // namespace MPI
522 
523 } // end of namespace Utilities
524 
525 
526 
527 // explicit instantiations from .templates.h file
528 #include "partitioner.inst"
529 
std::vector< std::pair< unsigned int, unsigned int > > import_indices_data
Definition: partitioner.h:706
bool is_globally_compatible(const Partitioner &part) const
Definition: partitioner.cc:494
static const unsigned int invalid_unsigned_int
Definition: types.h:196
#define AssertDimension(dim1, dim2)
Definition: exceptions.h:1623
bool is_compatible(const Partitioner &part) const
Definition: partitioner.cc:467
unsigned int local_size() const
types::global_dof_index global_size
Definition: partitioner.h:668
#define DEAL_II_DOF_INDEX_MPI_TYPE
Definition: types.h:86
unsigned int n_ghost_indices_data
Definition: partitioner.h:692
STL namespace.
#define AssertThrow(cond, exc)
Definition: exceptions.h:1576
void set_owned_indices(const IndexSet &locally_owned_indices)
Definition: partitioner.cc:145
std::vector< unsigned int > ghost_indices_subset_chunks_by_rank_data
Definition: partitioner.h:750
std::vector< unsigned int > import_indices_chunks_by_rank_data
Definition: partitioner.h:738
size_type size() const
Definition: index_set.h:1632
static ::ExceptionBase & ExcMessage(std::string arg1)
const IndexSet & ghost_indices() const
unsigned int n_ghost_indices() const
Definition: types.h:31
T sum(const T &t, const MPI_Comm &mpi_communicator)
void subtract_set(const IndexSet &other)
Definition: index_set.cc:258
#define Assert(cond, exc)
Definition: exceptions.h:1466
static ::ExceptionBase & ExcDimensionMismatch(std::size_t arg1, std::size_t arg2)
size_type index_within_set(const size_type global_index) const
Definition: index_set.h:1919
ArrayView< typename std::remove_reference< typename std::iterator_traits< Iterator >::reference >::type, MemorySpaceType > make_array_view(const Iterator begin, const Iterator end)
Definition: array_view.h:665
#define DEAL_II_NAMESPACE_CLOSE
Definition: config.h:372
std::vector< std::pair< unsigned int, unsigned int > > ghost_indices_subset_data
Definition: partitioner.h:758
unsigned int n_mpi_processes(const MPI_Comm &mpi_communicator)
Definition: mpi.cc:117
void fill_index_vector(std::vector< size_type > &indices) const
Definition: index_set.cc:507
void add_range(const size_type begin, const size_type end)
Definition: index_set.h:1671
void set_size(const size_type size)
Definition: index_set.h:1620
unsigned int global_dof_index
Definition: types.h:76
Definition: cuda.h:32
types::global_dof_index size() const
void compress() const
Definition: index_set.h:1640
std::size_t memory_consumption() const
Definition: partitioner.cc:503
#define AssertThrowMPI(error_code)
Definition: exceptions.h:1747
bool is_contiguous() const
Definition: index_set.h:1813
#define DEAL_II_NAMESPACE_OPEN
Definition: config.h:371
T min(const T &t, const MPI_Comm &mpi_communicator)
std::vector< std::pair< unsigned int, unsigned int > > import_targets_data
Definition: partitioner.h:732
std::pair< types::global_dof_index, types::global_dof_index > local_range_data
Definition: partitioner.h:680
std::vector< std::pair< unsigned int, unsigned int > > ghost_targets_data
Definition: partitioner.h:698
void export_to_ghosted_array_start(const unsigned int communication_channel, const ArrayView< const Number, MemorySpaceType > &locally_owned_array, const ArrayView< Number, MemorySpaceType > &temporary_storage, const ArrayView< Number, MemorySpaceType > &ghost_array, std::vector< MPI_Request > &requests) const
unsigned int this_mpi_process(const MPI_Comm &mpi_communicator)
Definition: mpi.cc:128
void export_to_ghosted_array_finish(const ArrayView< Number, MemorySpaceType > &ghost_array, std::vector< MPI_Request > &requests) const
bool is_element(const size_type index) const
Definition: index_set.h:1763
bool job_supports_mpi()
Definition: mpi.cc:1058
unsigned int n_import_indices() const
unsigned int n_import_indices_data
Definition: partitioner.h:726
virtual void reinit(const IndexSet &vector_space_vector_index_set, const IndexSet &read_write_vector_index_set, const MPI_Comm &communicator) override
Definition: partitioner.cc:132
size_type n_elements() const
Definition: index_set.h:1830
size_type nth_index_in_set(const size_type local_index) const
Definition: index_set.h:1878
T max(const T &t, const MPI_Comm &mpi_communicator)
void shift(const Tensor< 1, spacedim > &shift_vector, Triangulation< dim, spacedim > &triangulation)
Definition: grid_tools.cc:931
std::enable_if< std::is_fundamental< T >::value, std::size_t >::type memory_consumption(const T &t)
unsigned int n_ghost_indices_in_larger_set
Definition: partitioner.h:744
static ::ExceptionBase & ExcInternalError()
void set_ghost_indices(const IndexSet &ghost_indices, const IndexSet &larger_ghost_index_set=IndexSet())
Definition: partitioner.cc:186