mpi_compute_index_owner_internal.h

Go to the documentation of this file.

// ------------------------------------------------------------------------
//
// SPDX-License-Identifier: LGPL-2.1-or-later
// Copyright (C) 2019 - 2024 by the deal.II authors
//
// This file is part of the deal.II library.
//
// Part of the source code is dual licensed under Apache-2.0 WITH
// LLVM-exception OR LGPL-2.1-or-later. Detailed license information
// governing the source code and code contributions can be found in
// LICENSE.md and CONTRIBUTING.md at the top level directory of deal.II.
//
// ------------------------------------------------------------------------
 
#ifndef dealii_base_mpi_compute_index_owner_internal_h
#define dealii_base_mpi_compute_index_owner_internal_h
 
#include <deal.II/base/config.h>
 
#include <deal.II/base/mpi_consensus_algorithms.h>
#include <deal.II/base/mpi_stub.h>
 
DEAL_II_NAMESPACE_OPEN
 
namespace Utilities
{
  namespace MPI
  {
    namespace internal
    {
      namespace ComputeIndexOwner
      {
        class FlexibleIndexStorage
        {
        public:
          using index_type = unsigned int;
          static const index_type invalid_index_value =
            numbers::invalid_unsigned_int;
 
          FlexibleIndexStorage(const bool use_vector = true);
 
          void
          reinit(const bool        use_vector,
                 const bool        index_range_contiguous,
                 const std::size_t size);
 
          void
          fill(const std::size_t start,
               const std::size_t end,
               const index_type &value);
 
          index_type &
          operator[](const std::size_t index);
 
          index_type
          operator[](const std::size_t index) const;
 
          bool
          entry_has_been_set(const std::size_t index) const;
 
        private:
          bool                              use_vector;
          std::size_t                       size;
          std::vector<index_type>           data;
          std::map<std::size_t, index_type> data_map;
        };
 
 
 
        struct Dictionary
        {
          static constexpr unsigned int range_minimum_grain_size = 64;
 
          static constexpr unsigned int sparsity_factor = 4;
 
          FlexibleIndexStorage actually_owning_ranks;
 
          std::vector<unsigned int> actually_owning_rank_list;
 
          types::global_dof_index dofs_per_process;
 
          std::pair<types::global_dof_index, types::global_dof_index>
            local_range;
 
          types::global_dof_index locally_owned_size;
 
          types::global_dof_index size;
 
          unsigned int n_dict_procs_in_owned_indices;
 
          unsigned int stride_small_size;
 
          void
          reinit(const IndexSet &owned_indices, const MPI_Comm comm);
 
          unsigned int
          dof_to_dict_rank(const types::global_dof_index i);
 
          types::global_dof_index
          get_index_offset(const unsigned int rank);
 
          unsigned int
          get_owning_rank_index(const unsigned int rank_in_owned_indices,
                                const unsigned int guess = 0);
 
        private:
          void
          partition(const IndexSet &owned_indices, const MPI_Comm comm);
        };
 
 
 
        class ConsensusAlgorithmsPayload
          : public ConsensusAlgorithms::Process<
              std::vector<
                std::pair<types::global_dof_index, types::global_dof_index>>,
              std::vector<unsigned int>>
        {
        public:
          ConsensusAlgorithmsPayload(const IndexSet &owned_indices,
                                     const IndexSet &indices_to_look_up,
                                     const MPI_Comm  comm,
                                     std::vector<unsigned int> &owning_ranks,
                                     const bool track_index_requests = false);
 
          const IndexSet &owned_indices;
 
          const IndexSet &indices_to_look_up;
 
          const MPI_Comm comm;
 
          const unsigned int my_rank;
 
          const unsigned int n_procs;
 
          const bool track_index_requests;
 
          std::vector<unsigned int> &owning_ranks;
 
          std::vector<std::vector<
            std::pair<unsigned int,
                      std::vector<std::pair<types::global_dof_index,
                                            types::global_dof_index>>>>>
            requesters;
 
          Dictionary dict;
 
          std::map<unsigned int,
                   std::pair<std::vector<types::global_dof_index>,
                             std::vector<unsigned int>>>
            indices_to_look_up_by_dict_rank;
 
          virtual void
          answer_request(
            const unsigned int                                     other_rank,
            const std::vector<std::pair<types::global_dof_index,
                                        types::global_dof_index>> &buffer_recv,
            std::vector<unsigned int> &request_buffer) override;
 
          virtual std::vector<unsigned int>
          compute_targets() override;
 
          virtual void
          create_request(const unsigned int other_rank,
                         std::vector<std::pair<types::global_dof_index,
                                               types::global_dof_index>>
                           &send_buffer) override;
 
          virtual void
          read_answer(const unsigned int               other_rank,
                      const std::vector<unsigned int> &recv_buffer) override;
 
          std::map<unsigned int, IndexSet>
          get_requesters();
 
        private:
          void
          append_index_origin(
            const types::global_dof_index index_within_dictionary,
            const unsigned int            rank_of_request,
            const unsigned int            rank_of_owner,
            unsigned int                 &owner_index_guess);
        };
 
        /* ------------------------- inline functions ----------------------- */
 
        inline unsigned int
        Dictionary::dof_to_dict_rank(const types::global_dof_index i)
        {
          // note: this formula is also explicitly used in
          // get_index_offset(), so keep the two in sync
          return (i / dofs_per_process) * stride_small_size;
        }
 
 
        inline types::global_dof_index
        Dictionary::get_index_offset(const unsigned int rank)
        {
          return std::min(dofs_per_process *
                            static_cast<types::global_dof_index>(
                              (rank + stride_small_size - 1) /
                              stride_small_size),
                          size);
        }
 
 
 
        inline unsigned int
        Dictionary::get_owning_rank_index(
          const unsigned int rank_in_owned_indices,
          const unsigned int guess)
        {
          AssertIndexRange(guess, actually_owning_rank_list.size());
          if (actually_owning_rank_list[guess] == rank_in_owned_indices)
            return guess;
          else
            {
              auto it = std::lower_bound(actually_owning_rank_list.begin(),
                                         actually_owning_rank_list.end(),
                                         rank_in_owned_indices);
              Assert(it != actually_owning_rank_list.end(), ExcInternalError());
              Assert(*it == rank_in_owned_indices, ExcInternalError());
              return it - actually_owning_rank_list.begin();
            }
        }
 
 
      } // namespace ComputeIndexOwner
    }   // namespace internal
  }     // namespace MPI
} // namespace Utilities
 
DEAL_II_NAMESPACE_CLOSE
 
#endif