libMesh::ParmetisPartitioner Class Reference

The ParmetisPartitioner uses the Parmetis graph partitioner to partition the elements. More...

#include <parmetis_partitioner.h>

Inheritance diagram for libMesh::ParmetisPartitioner:

Public Member Functions
	ParmetisPartitioner ()
	Default and copy ctors.
	ParmetisPartitioner (const ParmetisPartitioner &other)
ParmetisPartitioner &	operator= (const ParmetisPartitioner &)=delete
	This class contains a unique_ptr member, so it can't be default copy assigned.
	ParmetisPartitioner (ParmetisPartitioner &&)=default
	Move ctor, move assignment operator, and destructor are all explicitly inline-defaulted for this class.
ParmetisPartitioner &	operator= (ParmetisPartitioner &&)=default
virtual	~ParmetisPartitioner ()
	The destructor is out-of-line-defaulted to play nice with forward declarations.
virtual PartitionerType	type () const override
virtual std::unique_ptr< Partitioner >	clone () const override
virtual void	partition (MeshBase &mesh, const unsigned int n)
	Partitions the MeshBase into n parts by setting processor_id() on Nodes and Elems.
virtual void	partition (MeshBase &mesh)
	Partitions the MeshBase into mesh.n_processors() by setting processor_id() on Nodes and Elems.
virtual void	partition_range (MeshBase &, MeshBase::element_iterator, MeshBase::element_iterator, const unsigned int)
	Partitions elements in the range (it, end) into n parts.
void	repartition (MeshBase &mesh, const unsigned int n)
	Repartitions the MeshBase into n parts.
void	repartition (MeshBase &mesh)
	Repartitions the MeshBase into mesh.n_processors() parts.
virtual void	attach_weights (ErrorVector *)
	Attach weights that can be used for partitioning.

Static Public Member Functions
static std::unique_ptr< Partitioner >	build (const PartitionerType solver_package)
	Builds a Partitioner of the type specified by partitioner_type.
static void	partition_unpartitioned_elements (MeshBase &mesh)
	These functions assign processor IDs to newly-created elements (in parallel) which are currently assigned to processor 0.
static void	partition_unpartitioned_elements (MeshBase &mesh, const unsigned int n)
static void	set_parent_processor_ids (MeshBase &mesh)
	This function is called after partitioning to set the processor IDs for the inactive parent elements.
static void	set_node_processor_ids (MeshBase &mesh)
	This function is called after partitioning to set the processor IDs for the nodes.
static void	processor_pairs_to_interface_nodes (MeshBase &mesh, std::map< std::pair< processor_id_type, processor_id_type >, std::set< dof_id_type > > &processor_pair_to_nodes)
	On the partitioning interface, a surface is shared by two and only two processors.
static void	set_interface_node_processor_ids_linear (MeshBase &mesh)
	Nodes on the partitioning interface is linearly assigned to each pair of processors.
static void	set_interface_node_processor_ids_BFS (MeshBase &mesh)
	Nodes on the partitioning interface is clustered into two groups BFS (Breadth First Search)scheme for per pair of processors.
static void	set_interface_node_processor_ids_petscpartitioner (MeshBase &mesh)
	Nodes on the partitioning interface is partitioned into two groups using a PETSc partitioner for each pair of processors.

Protected Member Functions
virtual void	_do_repartition (MeshBase &mesh, const unsigned int n) override
	Parmetis can handle dynamically repartitioning a mesh such that the redistribution costs are minimized.
virtual void	_do_partition (MeshBase &mesh, const unsigned int n) override
	Partition the MeshBase into n subdomains.
virtual void	build_graph (const MeshBase &mesh) override
	Build the graph.
bool	single_partition (MeshBase &mesh)
	Trivially "partitions" the mesh for one processor.
bool	single_partition_range (MeshBase::element_iterator it, MeshBase::element_iterator end)
	Slightly generalized version of single_partition which acts on a range of elements defined by the pair of iterators (it, end).
virtual void	_find_global_index_by_pid_map (const MeshBase &mesh)
	Construct contiguous global indices for the current partitioning.
void	assign_partitioning (MeshBase &mesh, const std::vector< dof_id_type > &parts)
	Assign the computed partitioning to the mesh.

Protected Attributes
ErrorVector *	_weights
	The weights that might be used for partitioning.
std::unordered_map< dof_id_type, dof_id_type >	_global_index_by_pid_map
	Maps active element ids into a contiguous range, as needed by parallel partitioner.
std::vector< dof_id_type >	_n_active_elem_on_proc
	The number of active elements on each processor.
std::vector< std::vector< dof_id_type > >	_dual_graph
	A dual graph corresponds to the mesh, and it is typically used in paritioner.
std::vector< Elem * >	_local_id_to_elem

Static Protected Attributes
static const dof_id_type	communication_blocksize
	The blocksize to use when doing blocked parallel communication.

Private Member Functions
void	initialize (const MeshBase &mesh, const unsigned int n_sbdmns)
	Initialize data structures.

Private Attributes
std::unique_ptr< ParmetisHelper >	_pmetis
	Pointer to the Parmetis-specific data structures.

Detailed Description

The ParmetisPartitioner uses the Parmetis graph partitioner to partition the elements.

Author

Benjamin S. Kirk

Date

2003

Partitioner which provides an interface to ParMETIS.

Definition at line 47 of file parmetis_partitioner.h.

Constructor & Destructor Documentation

ParmetisPartitioner() [1/3]

libMesh::ParmetisPartitioner::ParmetisPartitioner

(

)

Default and copy ctors.

ParmetisPartitioner() [2/3]

libMesh::ParmetisPartitioner::ParmetisPartitioner

(

const ParmetisPartitioner &

other

)

ParmetisPartitioner() [3/3]

libMesh::ParmetisPartitioner::ParmetisPartitioner ( ParmetisPartitioner &&  )

default

Move ctor, move assignment operator, and destructor are all explicitly inline-defaulted for this class.

~ParmetisPartitioner()

virtual libMesh::ParmetisPartitioner::~ParmetisPartitioner ( )

virtual

The destructor is out-of-line-defaulted to play nice with forward declarations.

Member Function Documentation

_do_partition()

void libMesh::ParmetisPartitioner::_do_partition ( MeshBase &  mesh, const unsigned int  n  )

overrideprotectedvirtual

Partition the MeshBase into n subdomains.

Implements libMesh::Partitioner.

Definition at line 105 of file parmetis_partitioner.C.

{
  this->_do_repartition (mesh, n_sbdmns);
}

References mesh.

_do_repartition()

void libMesh::ParmetisPartitioner::_do_repartition ( MeshBase &  mesh, const unsigned int  n  )

overrideprotectedvirtual

Parmetis can handle dynamically repartitioning a mesh such that the redistribution costs are minimized.

This method takes a previously partitioned mesh (which may have then been adaptively refined) and repartitions it.

Reimplemented from libMesh::Partitioner.

Definition at line 113 of file parmetis_partitioner.C.

{
  // This function must be run on all processors at once
  libmesh_parallel_only(mesh.comm());
 
  // Check for easy returns
  if (!mesh.n_elem())
    return;
 
  if (n_sbdmns == 1)
    {
      this->single_partition(mesh);
      return;
    }
 
  libmesh_assert_greater (n_sbdmns, 0);
 
  // What to do if the Parmetis library IS NOT present
#ifndef LIBMESH_HAVE_PARMETIS
 
  libmesh_do_once(
  libMesh::out << "ERROR: The library has been built without" << std::endl
               << "Parmetis support.  Using a Metis"          << std::endl
               << "partitioner instead!"                      << std::endl;);
 
  MetisPartitioner mp;
 
  // Metis and other fallbacks only work in serial, and need to get
  // handed element ranges from an already-serialized mesh.
  mesh.allgather();
 
  // Don't just call partition() here; that would end up calling
  // post-element-partitioning work redundantly (and at the moment
  // incorrectly)
  mp.partition_range (mesh, mesh.active_elements_begin(),
                      mesh.active_elements_end(), n_sbdmns);
 
  // What to do if the Parmetis library IS present
#else
 
  // Revert to METIS on one processor.
  if (mesh.n_processors() == 1)
    {
      // Make sure the mesh knows it's serial
      mesh.allgather();
 
      MetisPartitioner mp;
      // Don't just call partition() here; that would end up calling
      // post-element-partitioning work redundantly (and at the moment
      // incorrectly)
      mp.partition_range (mesh, mesh.active_elements_begin(),
                          mesh.active_elements_end(), n_sbdmns);
      return;
    }
 
  LOG_SCOPE("repartition()", "ParmetisPartitioner");
 
  // Initialize the data structures required by ParMETIS
  this->initialize (mesh, n_sbdmns);
 
  // build the graph corresponding to the mesh
  this->build_graph (mesh);
 
  // Make sure all processors have enough active local elements and
  // enough connectivity among them.
  // Parmetis tends to die when it's given only a couple elements
  // per partition or when it can't reach elements from each other.
  {
    bool ready_for_parmetis = true;
    for (const auto & nelem : _n_active_elem_on_proc)
      if (nelem < MIN_ELEM_PER_PROC)
        ready_for_parmetis = false;
 
    std::size_t my_adjacency = _pmetis->adjncy.size();
    mesh.comm().min(my_adjacency);
    if (!my_adjacency)
      ready_for_parmetis = false;
 
    // Parmetis will not work unless each processor has some
    // elements. Specifically, it will abort when passed a nullptr
    // partition or adjacency array on *any* of the processors.
    if (!ready_for_parmetis)
      {
        // FIXME: revert to METIS, although this requires a serial mesh
        MeshSerializer serialize(mesh);
        MetisPartitioner mp;
        mp.partition (mesh, n_sbdmns);
        return;
      }
  }
 
 
  // Partition the graph
  std::vector<Parmetis::idx_t> vsize(_pmetis->vwgt.size(), 1);
  Parmetis::real_t itr = 1000000.0;
  MPI_Comm mpi_comm = mesh.comm().get();
 
  // Call the ParMETIS adaptive repartitioning method.  This respects the
  // original partitioning when computing the new partitioning so as to
  // minimize the required data redistribution.
  Parmetis::ParMETIS_V3_AdaptiveRepart(_pmetis->vtxdist.empty() ? nullptr : _pmetis->vtxdist.data(),
                                       _pmetis->xadj.empty()    ? nullptr : _pmetis->xadj.data(),
                                       _pmetis->adjncy.empty()  ? nullptr : _pmetis->adjncy.data(),
                                       _pmetis->vwgt.empty()    ? nullptr : _pmetis->vwgt.data(),
                                       vsize.empty()            ? nullptr : vsize.data(),
                                       nullptr,
                                       &_pmetis->wgtflag,
                                       &_pmetis->numflag,
                                       &_pmetis->ncon,
                                       &_pmetis->nparts,
                                       _pmetis->tpwgts.empty()  ? nullptr : _pmetis->tpwgts.data(),
                                       _pmetis->ubvec.empty()   ? nullptr : _pmetis->ubvec.data(),
                                       &itr,
                                       _pmetis->options.data(),
                                       &_pmetis->edgecut,
                                       _pmetis->part.empty()    ? nullptr : reinterpret_cast<Parmetis::idx_t *>(_pmetis->part.data()),
                                       &mpi_comm);
 
  // Assign the returned processor ids
  this->assign_partitioning (mesh, _pmetis->part);
 
#endif // #ifndef LIBMESH_HAVE_PARMETIS ... else ...
 
}

References initialize(), mesh, libMesh::MIN_ELEM_PER_PROC, libMesh::out, libMesh::Partitioner::partition(), and libMesh::MetisPartitioner::partition_range().

_find_global_index_by_pid_map()

void libMesh::Partitioner::_find_global_index_by_pid_map ( const MeshBase &  mesh )

protectedvirtualinherited

Construct contiguous global indices for the current partitioning.

The global indices are ordered part-by-part

Definition at line 1068 of file partitioner.C.

{
  const dof_id_type n_active_local_elem = mesh.n_active_local_elem();
 
  // Find the number of active elements on each processor.  We cannot use
  // mesh.n_active_elem_on_proc(pid) since that only returns the number of
  // elements assigned to pid which are currently stored on the calling
  // processor. This will not in general be correct for parallel meshes
  // when (pid!=mesh.processor_id()).
  auto n_proc = mesh.n_processors();
  _n_active_elem_on_proc.resize(n_proc);
  mesh.comm().allgather(n_active_local_elem, _n_active_elem_on_proc);
 
  std::vector<dof_id_type> n_active_elem_before_proc(mesh.n_processors());
 
  for (auto i : make_range(n_proc-1))
    n_active_elem_before_proc[i+1] =
      n_active_elem_before_proc[i] + _n_active_elem_on_proc[i];
 
  libMesh::BoundingBox bbox =
    MeshTools::create_bounding_box(mesh);
 
  _global_index_by_pid_map.clear();
 
  // create the mapping which is contiguous by processor
  MeshCommunication().find_local_indices (bbox,
                                          mesh.active_local_elements_begin(),
                                          mesh.active_local_elements_end(),
                                          _global_index_by_pid_map);
 
  SyncLocalIDs sync(_global_index_by_pid_map);
 
  Parallel::sync_dofobject_data_by_id
      (mesh.comm(), mesh.active_elements_begin(), mesh.active_elements_end(), sync);
 
  for (const auto & elem : mesh.active_element_ptr_range())
    {
      const processor_id_type pid = elem->processor_id();
      libmesh_assert_less (_global_index_by_pid_map[elem->id()], _n_active_elem_on_proc[pid]);
 
      _global_index_by_pid_map[elem->id()] += n_active_elem_before_proc[pid];
    }
}

References libMesh::Partitioner::_global_index_by_pid_map, libMesh::Partitioner::_n_active_elem_on_proc, libMesh::Parallel::Communicator::allgather(), libMesh::ParallelObject::comm(), libMesh::MeshTools::create_bounding_box(), libMesh::MeshCommunication::find_local_indices(), libMesh::make_range(), mesh, libMesh::MeshBase::n_active_local_elem(), libMesh::ParallelObject::n_processors(), and libMesh::Parallel::sync_dofobject_data_by_id().

Referenced by libMesh::Partitioner::build_graph().

assign_partitioning()

void libMesh::Partitioner::assign_partitioning ( MeshBase &  mesh, const std::vector< dof_id_type > &  parts  )

protectedinherited

Assign the computed partitioning to the mesh.

Definition at line 1467 of file partitioner.C.

{
  LOG_SCOPE("assign_partitioning()", "Partitioner");
 
  // This function must be run on all processors at once
  libmesh_parallel_only(mesh.comm());
 
  dof_id_type first_local_elem = 0;
  for (auto pid : make_range(mesh.processor_id()))
    first_local_elem += _n_active_elem_on_proc[pid];
 
#ifndef NDEBUG
  const dof_id_type n_active_local_elem = mesh.n_active_local_elem();
#endif
 
  std::map<processor_id_type, std::vector<dof_id_type>>
    requested_ids;
 
  // Results to gather from each processor - kept in a map so we
  // do only one loop over elements after all receives are done.
  std::map<processor_id_type, std::vector<processor_id_type>>
    filled_request;
 
  for (auto & elem : mesh.active_element_ptr_range())
    {
      // we need to get the index from the owning processor
      // (note we cannot assign it now -- we are iterating
      // over elements again and this will be bad!)
      requested_ids[elem->processor_id()].push_back(elem->id());
    }
 
  auto gather_functor =
    [this,
     & parts,
#ifndef NDEBUG
     & mesh,
     n_active_local_elem,
#endif
     first_local_elem]
    (processor_id_type, const std::vector<dof_id_type> & ids,
     std::vector<processor_id_type> & data)
    {
      const std::size_t ids_size = ids.size();
      data.resize(ids.size());
 
      for (std::size_t i=0; i != ids_size; i++)
        {
          const dof_id_type requested_elem_index = ids[i];
 
          libmesh_assert(_global_index_by_pid_map.count(requested_elem_index));
 
          const dof_id_type global_index_by_pid =
            _global_index_by_pid_map[requested_elem_index];
 
          const dof_id_type local_index =
            global_index_by_pid - first_local_elem;
 
          libmesh_assert_less (local_index, parts.size());
          libmesh_assert_less (local_index, n_active_local_elem);
 
          const processor_id_type elem_procid =
            cast_int<processor_id_type>(parts[local_index]);
 
          libmesh_assert_less (elem_procid, mesh.n_partitions());
 
          data[i] = elem_procid;
        }
    };
 
  auto action_functor =
    [&filled_request]
    (processor_id_type pid,
     const std::vector<dof_id_type> &,
     const std::vector<processor_id_type> & new_procids)
    {
      filled_request[pid] = new_procids;
    };
 
  // Trade requests with other processors
  const processor_id_type * ex = nullptr;
  Parallel::pull_parallel_vector_data
    (mesh.comm(), requested_ids, gather_functor, action_functor, ex);
 
  // and finally assign the partitioning.
  // note we are iterating in exactly the same order
  // used to build up the request, so we can expect the
  // required entries to be in the proper sequence.
  std::vector<unsigned int> counters(mesh.n_processors(), 0);
  for (auto & elem : mesh.active_element_ptr_range())
    {
      const processor_id_type current_pid = elem->processor_id();
 
      libmesh_assert_less (counters[current_pid], requested_ids[current_pid].size());
 
      const processor_id_type elem_procid =
        filled_request[current_pid][counters[current_pid]++];
 
      libmesh_assert_less (elem_procid, mesh.n_partitions());
      elem->processor_id() = elem_procid;
    }
}

References libMesh::Partitioner::_global_index_by_pid_map, libMesh::Partitioner::_n_active_elem_on_proc, libMesh::ParallelObject::comm(), libMesh::libmesh_assert(), libMesh::make_range(), mesh, libMesh::MeshBase::n_active_local_elem(), libMesh::MeshBase::n_partitions(), libMesh::ParallelObject::n_processors(), libMesh::ParallelObject::processor_id(), and TIMPI::pull_parallel_vector_data().

attach_weights()

virtual void libMesh::Partitioner::attach_weights ( ErrorVector *  )

inlinevirtualinherited

Attach weights that can be used for partitioning.

This ErrorVector should be exactly the same on every processor and should have mesh->max_elem_id() entries.

Reimplemented in libMesh::MetisPartitioner.

Definition at line 213 of file partitioner.h.

{ libmesh_not_implemented(); }

build()

std::unique_ptr< Partitioner > libMesh::Partitioner::build ( const PartitionerType  solver_package )

staticinherited

Builds a Partitioner of the type specified by partitioner_type.

Definition at line 159 of file partitioner.C.

{
  switch (partitioner_type)
  {
    case CENTROID_PARTITIONER:
      return std::make_unique<CentroidPartitioner>();
    case LINEAR_PARTITIONER:
      return std::make_unique<LinearPartitioner>();
    case MAPPED_SUBDOMAIN_PARTITIONER:
      return std::make_unique<MappedSubdomainPartitioner>();
    case METIS_PARTITIONER:
      return std::make_unique<MetisPartitioner>();
    case PARMETIS_PARTITIONER:
      return std::make_unique<ParmetisPartitioner>();
    case HILBERT_SFC_PARTITIONER:
      return std::make_unique<HilbertSFCPartitioner>();
    case MORTON_SFC_PARTITIONER:
      return std::make_unique<MortonSFCPartitioner>();
    case SFC_PARTITIONER:
      return std::make_unique<SFCPartitioner>();
    case SUBDOMAIN_PARTITIONER:
      return std::make_unique<SubdomainPartitioner>();
    default:
      libmesh_error_msg("Invalid partitioner type: " <<
                        Utility::enum_to_string(partitioner_type));
  }
}

References libMesh::CENTROID_PARTITIONER, libMesh::Utility::enum_to_string(), libMesh::HILBERT_SFC_PARTITIONER, libMesh::LINEAR_PARTITIONER, libMesh::MAPPED_SUBDOMAIN_PARTITIONER, libMesh::METIS_PARTITIONER, libMesh::MORTON_SFC_PARTITIONER, libMesh::PARMETIS_PARTITIONER, libMesh::SFC_PARTITIONER, and libMesh::SUBDOMAIN_PARTITIONER.

Referenced by libMesh::DistributedMesh::DistributedMesh(), libMesh::ReplicatedMesh::ReplicatedMesh(), PartitionerTest< PartitionerSubclass, MeshClass >::testBuild(), and MeshDeletionsTest::testDeleteElem().

build_graph()

void libMesh::ParmetisPartitioner::build_graph ( const MeshBase &  mesh )

overrideprotectedvirtual

Build the graph.

Reimplemented from libMesh::Partitioner.

Definition at line 433 of file parmetis_partitioner.C.

{
  LOG_SCOPE("build_graph()", "ParmetisPartitioner");
 
  // build the graph in distributed CSR format.  Note that
  // the edges in the graph will correspond to
  // face neighbors
  const dof_id_type n_active_local_elem  = mesh.n_active_local_elem();
 
  Partitioner::build_graph(mesh);
 
  dof_id_type graph_size_upper_bound = 0;
 
  for (auto & row: _dual_graph)
    graph_size_upper_bound += cast_int<dof_id_type>(row.size());
 
  // Reserve space in the adjacency array
  _pmetis->xadj.clear();
  _pmetis->xadj.reserve (n_active_local_elem + 1);
  _pmetis->adjncy.clear();
  _pmetis->adjncy.reserve (graph_size_upper_bound);
 
  const dof_id_type first_local_elem =
    _pmetis->vtxdist[mesh.processor_id()];
  std::unordered_set<dof_id_type> unique_neighbors;
 
  // ParMETIS requires a simple graph.  Preserve first-occurrence order
  // while filtering so valid graph rows remain otherwise unchanged.
  for (auto i : index_range(_dual_graph))
    {
      _pmetis->xadj.push_back(cast_int<int>(_pmetis->adjncy.size()));
 
      const dof_id_type global_index =
        first_local_elem + cast_int<dof_id_type>(i);
      const auto & graph_row = _dual_graph[i];
      unique_neighbors.clear();
 
      for (const auto neighbor : graph_row)
        if (neighbor != global_index &&
            unique_neighbors.insert(neighbor).second)
          _pmetis->adjncy.push_back(neighbor);
    }
 
  // The end of the adjacency array for the last elem
  _pmetis->xadj.push_back(cast_int<int>(_pmetis->adjncy.size()));
 
  libmesh_assert_equal_to (_pmetis->xadj.size(), n_active_local_elem+1);
  libmesh_assert_less_equal (_pmetis->adjncy.size(),
                             graph_size_upper_bound);
}

References libMesh::index_range(), and mesh.

clone()

virtual std::unique_ptr< Partitioner > libMesh::ParmetisPartitioner::clone ( ) const

inlineoverridevirtual

Returns

A copy of this partitioner wrapped in a smart pointer.

Implements libMesh::Partitioner.

Definition at line 81 of file parmetis_partitioner.h.

  {
    return std::make_unique<ParmetisPartitioner>(*this);
  }

initialize()

void libMesh::ParmetisPartitioner::initialize ( const MeshBase &  mesh, const unsigned int  n_sbdmns  )

private

Initialize data structures.

Definition at line 244 of file parmetis_partitioner.C.

{
  LOG_SCOPE("initialize()", "ParmetisPartitioner");
 
  const dof_id_type n_active_local_elem = mesh.n_active_local_elem();
  // Set parameters.
  _pmetis->wgtflag = 2;                                      // weights on vertices only
  _pmetis->ncon    = 1;                                      // one weight per vertex
  _pmetis->numflag = 0;                                      // C-style 0-based numbering
  _pmetis->nparts  = static_cast<Parmetis::idx_t>(n_sbdmns); // number of subdomains to create
  _pmetis->edgecut = 0;                                      // the numbers of edges cut by the
                                                             // partition
 
  // Initialize data structures for ParMETIS
  _pmetis->vtxdist.assign (mesh.n_processors()+1, 0);
  _pmetis->tpwgts.assign  (_pmetis->nparts, 1./_pmetis->nparts);
  _pmetis->ubvec.assign   (_pmetis->ncon, 1.05);
  _pmetis->part.assign    (n_active_local_elem, 0);
  _pmetis->options.resize (5);
  _pmetis->vwgt.resize    (n_active_local_elem);
 
  // Set the options
  _pmetis->options[0] = 1;  // don't use default options
  _pmetis->options[1] = 0;  // default (level of timing)
  _pmetis->options[2] = 15; // random seed (default)
  _pmetis->options[3] = 2;  // processor distribution and subdomain distribution are decoupled
 
  // ParMetis expects the elements to be numbered in contiguous blocks
  // by processor, i.e. [0, ne0), [ne0, ne0+ne1), ...
  // Since we only partition active elements we should have no expectation
  // that we currently have such a distribution.  So we need to create it.
  // Also, at the same time we are going to map all the active elements into a globally
  // unique range [0,n_active_elem) which is *independent* of the current partitioning.
  // This can be fed to ParMetis as the initial partitioning of the subdomains (decoupled
  // from the partitioning of the objects themselves).  This allows us to get the same
  // resultant partitioning independent of the input partitioning.
  libMesh::BoundingBox bbox =
    MeshTools::create_bounding_box(mesh);
 
  _find_global_index_by_pid_map(mesh);
 
 
  // count the total number of active elements in the mesh.  Note we cannot
  // use mesh.n_active_elem() in general since this only returns the number
  // of active elements which are stored on the calling processor.
  // We should not use n_active_elem for any allocation because that will
  // be inherently unscalable, but it can be useful for libmesh_assertions.
  dof_id_type n_active_elem=0;
 
  // Set up the vtxdist array.  This will be the same on each processor.
  // ***** Consult the Parmetis documentation. *****
  libmesh_assert_equal_to (_pmetis->vtxdist.size(),
                           cast_int<std::size_t>(mesh.n_processors()+1));
  libmesh_assert_equal_to (_pmetis->vtxdist[0], 0);
 
  for (auto pid : make_range(mesh.n_processors()))
    {
      _pmetis->vtxdist[pid+1] = _pmetis->vtxdist[pid] + _n_active_elem_on_proc[pid];
      n_active_elem += _n_active_elem_on_proc[pid];
    }
  libmesh_assert_equal_to (_pmetis->vtxdist.back(), static_cast<Parmetis::idx_t>(n_active_elem));
 
 
  // Maps active element ids into a contiguous range independent of partitioning.
  // (only needs local scope)
  std::unordered_map<dof_id_type, dof_id_type> global_index_map;
 
  {
    std::vector<dof_id_type> global_index;
 
    // create the unique mapping for all active elements independent of partitioning
    {
      MeshBase::const_element_iterator       it  = mesh.active_elements_begin();
      const MeshBase::const_element_iterator end = mesh.active_elements_end();
 
      // Calling this on all processors a unique range in [0,n_active_elem) is constructed.
      // Only the indices for the elements we pass in are returned in the array.
      MeshCommunication().find_global_indices (mesh.comm(),
                                               bbox, it, end,
                                               global_index);
 
      for (dof_id_type cnt=0; it != end; ++it)
        {
          const Elem * elem = *it;
          // vectormap::count forces a sort, which is too expensive
          // in a loop
          // libmesh_assert (!global_index_map.count(elem->id()));
          libmesh_assert_less (cnt, global_index.size());
          libmesh_assert_less (global_index[cnt], n_active_elem);
 
          global_index_map.emplace(elem->id(), global_index[cnt++]);
        }
    }
    // really, shouldn't be close!
    libmesh_assert_less_equal (global_index_map.size(), n_active_elem);
    libmesh_assert_less_equal (_global_index_by_pid_map.size(), n_active_elem);
 
    // At this point the two maps should be the same size.  If they are not
    // then the number of active elements is not the same as the sum over all
    // processors of the number of active elements per processor, which means
    // there must be some unpartitioned objects out there.
    libmesh_error_msg_if(global_index_map.size() != _global_index_by_pid_map.size(),
                         "ERROR:  ParmetisPartitioner cannot handle unpartitioned objects!");
  }
 
  // Finally, we need to initialize the vertex (partition) weights and the initial subdomain
  // mapping.  The subdomain mapping will be independent of the processor mapping, and is
  // defined by a simple mapping of the global indices we just found.
  {
    std::vector<dof_id_type> subdomain_bounds(mesh.n_processors());
 
    const dof_id_type first_local_elem = _pmetis->vtxdist[mesh.processor_id()];
 
    for (auto pid : make_range(mesh.n_processors()))
      {
        dof_id_type tgt_subdomain_size = 0;
 
        // watch out for the case that n_subdomains < n_processors
        if (pid < static_cast<unsigned int>(_pmetis->nparts))
          {
            tgt_subdomain_size = n_active_elem/std::min
              (cast_int<Parmetis::idx_t>(mesh.n_processors()), _pmetis->nparts);
 
            if (pid < n_active_elem%_pmetis->nparts)
              tgt_subdomain_size++;
          }
        if (pid == 0)
          subdomain_bounds[0] = tgt_subdomain_size;
        else
          subdomain_bounds[pid] = subdomain_bounds[pid-1] + tgt_subdomain_size;
      }
 
    libmesh_assert_equal_to (subdomain_bounds.back(), n_active_elem);
 
    Threads::parallel_for
      (mesh.active_local_element_stored_range(),
       [first_local_elem, n_active_elem, n_active_local_elem, this,
        &global_index_map, &subdomain_bounds](const ConstElemRange & range)
       {
         for (const Elem * elem : range)
           {
             const dof_id_type global_index_by_pid =
               libmesh_map_find(_global_index_by_pid_map, elem->id());
             libmesh_assert_less (global_index_by_pid, n_active_elem);
 
             const dof_id_type local_index =
               global_index_by_pid - first_local_elem;
 
             libmesh_assert_less (local_index, n_active_local_elem);
             libmesh_assert_less (local_index, _pmetis->vwgt.size());
 
             libmesh_ignore(n_active_elem); // unused outside dbg/devel
             libmesh_ignore(n_active_local_elem); // unused outside dbg/devel
 
             // Spline nodes are a special case (storing all the
             // unconstrained DoFs in an IGA simulation), but in general
             // we'll try to distribute work by expecting it to be roughly
             // proportional to DoFs, which are roughly proportional to
             // nodes.
             if (elem->type() == NODEELEM &&
                 elem->mapping_type() == RATIONAL_BERNSTEIN_MAP)
               _pmetis->vwgt[local_index] = 50;
             else
               _pmetis->vwgt[local_index] = elem->n_nodes();
 
             // find the subdomain this element belongs in
             const dof_id_type global_index =
               libmesh_map_find(global_index_map, elem->id());
 
             libmesh_assert_less (global_index, subdomain_bounds.back());
 
             const unsigned int subdomain_id =
               cast_int<unsigned int>
               (std::distance(subdomain_bounds.begin(),
                              std::lower_bound(subdomain_bounds.begin(),
                                               subdomain_bounds.end(),
                                               global_index)));
             libmesh_assert_less (subdomain_id, _pmetis->nparts);
             libmesh_assert_less (local_index, _pmetis->part.size());
 
             _pmetis->part[local_index] = subdomain_id;
           }
       });
  }
}

References libMesh::MeshCommunication::find_global_indices(), libMesh::DofObject::id(), libMesh::make_range(), and mesh.

operator=() [1/2]

ParmetisPartitioner & libMesh::ParmetisPartitioner::operator= ( const ParmetisPartitioner &  )

delete

This class contains a unique_ptr member, so it can't be default copy assigned.

operator=() [2/2]

ParmetisPartitioner & libMesh::ParmetisPartitioner::operator= ( ParmetisPartitioner &&  )

default

partition() [1/2]

void libMesh::Partitioner::partition ( MeshBase &  mesh )

virtualinherited

Partitions the MeshBase into mesh.n_processors() by setting processor_id() on Nodes and Elems.

Note

If you are implementing a new type of Partitioner, you most likely do not want to override the partition() function, see instead the protected virtual _do_partition() method below. The partition() function is responsible for doing a lot of libmesh-internals-specific setup and finalization before and after the _do_partition() function is called. The only responsibility of the _do_partition() function, on the other hand, is to set the processor IDs of the elements according to a specific partitioning algorithm. See, e.g. MetisPartitioner for an example.

Definition at line 189 of file partitioner.C.

{
  this->partition(mesh,mesh.n_processors());
}

References mesh, libMesh::ParallelObject::n_processors(), and libMesh::Partitioner::partition().

partition() [2/2]

void libMesh::Partitioner::partition ( MeshBase &  mesh, const unsigned int  n  )

virtualinherited

Partitions the MeshBase into n parts by setting processor_id() on Nodes and Elems.

Note

If you are implementing a new type of Partitioner, you most likely do not want to override the partition() function, see instead the protected virtual _do_partition() method below. The partition() function is responsible for doing a lot of libmesh-internals-specific setup and finalization before and after the _do_partition() function is called. The only responsibility of the _do_partition() function, on the other hand, is to set the processor IDs of the elements according to a specific partitioning algorithm. See, e.g. MetisPartitioner for an example.

Definition at line 196 of file partitioner.C.

{
  libmesh_parallel_only(mesh.comm());
 
  // BSK - temporary fix while redistribution is integrated 6/26/2008
  // Uncomment this to not repartition in parallel
  //   if (!mesh.is_serial())
  //     return;
 
  // we cannot partition into more pieces than we have
  // active elements!
  const unsigned int n_parts =
    static_cast<unsigned int>
    (std::min(mesh.n_active_elem(), static_cast<dof_id_type>(n)));
 
  // Set the number of partitions in the mesh
  mesh.set_n_partitions()=n_parts;
 
  if (n_parts == 1)
    {
      this->single_partition (mesh);
      return;
    }
 
  // First assign a temporary partitioning to any unpartitioned elements
  Partitioner::partition_unpartitioned_elements(mesh, n_parts);
 
  // Call the partitioning function
  this->_do_partition(mesh,n_parts);
 
  // Set the parent's processor ids
  Partitioner::set_parent_processor_ids(mesh);
 
  // Redistribute elements if necessary, before setting node processor
  // ids, to make sure those will be set consistently
  mesh.redistribute();
 
#ifdef DEBUG
  MeshTools::libmesh_assert_valid_remote_elems(mesh);
 
  // Messed up elem processor_id()s can leave us without the child
  // elements we need to restrict vectors on a distributed mesh
  MeshTools::libmesh_assert_valid_procids<Elem>(mesh);
#endif
 
  // Set the node's processor ids
  Partitioner::set_node_processor_ids(mesh);
 
#ifdef DEBUG
  MeshTools::libmesh_assert_valid_procids<Elem>(mesh);
#endif
 
  // Give derived Mesh classes a chance to update any cached data to
  // reflect the new partitioning
  mesh.update_post_partitioning();
}

References libMesh::Partitioner::_do_partition(), libMesh::ParallelObject::comm(), libMesh::MeshTools::libmesh_assert_valid_remote_elems(), mesh, libMesh::MeshBase::n_active_elem(), libMesh::Partitioner::partition_unpartitioned_elements(), libMesh::MeshBase::redistribute(), libMesh::MeshBase::set_n_partitions(), libMesh::Partitioner::set_node_processor_ids(), libMesh::Partitioner::set_parent_processor_ids(), libMesh::Partitioner::single_partition(), and libMesh::MeshBase::update_post_partitioning().

Referenced by _do_repartition(), and libMesh::Partitioner::partition().

partition_range()

virtual void libMesh::Partitioner::partition_range ( MeshBase &  , MeshBase::element_iterator  , MeshBase::element_iterator  , const unsigned int    )

inlinevirtualinherited

Partitions elements in the range (it, end) into n parts.

The mesh from which the iterators are created must also be passed in, since it is a parallel object and has other useful information in it.

Although partition_range() is part of the public Partitioner interface, it should not generally be called by applications. Its main purpose is to support the SubdomainPartitioner, which uses it internally to individually partition ranges of elements before combining them into the final partitioning. Most of the time, the protected _do_partition() function is implemented in terms of partition_range() by passing a range which includes all the elements of the Mesh.

Reimplemented in libMesh::CentroidPartitioner, libMesh::LinearPartitioner, libMesh::MappedSubdomainPartitioner, libMesh::MetisPartitioner, and libMesh::SFCPartitioner.

Definition at line 137 of file partitioner.h.

  { libmesh_not_implemented(); }

Referenced by libMesh::SubdomainPartitioner::_do_partition().

partition_unpartitioned_elements() [1/2]

void libMesh::Partitioner::partition_unpartitioned_elements ( MeshBase &  mesh )

staticinherited

These functions assign processor IDs to newly-created elements (in parallel) which are currently assigned to processor 0.

Definition at line 345 of file partitioner.C.

{
  Partitioner::partition_unpartitioned_elements(mesh, mesh.n_processors());
}

References mesh, libMesh::ParallelObject::n_processors(), and libMesh::Partitioner::partition_unpartitioned_elements().

Referenced by libMesh::Partitioner::partition(), libMesh::Partitioner::partition_unpartitioned_elements(), and libMesh::Partitioner::repartition().

partition_unpartitioned_elements() [2/2]

void libMesh::Partitioner::partition_unpartitioned_elements ( MeshBase &  mesh, const unsigned int  n  )

staticinherited

Definition at line 352 of file partitioner.C.

{
  MeshBase::element_iterator       it  = mesh.unpartitioned_elements_begin();
  const MeshBase::element_iterator end = mesh.unpartitioned_elements_end();
 
  const dof_id_type n_unpartitioned_elements = MeshTools::n_elem (it, end);
 
  // the unpartitioned elements must exist on all processors. If the range is empty on one
  // it is empty on all, and we can quit right here.
  if (!n_unpartitioned_elements)
    return;
 
  // find the target subdomain sizes
  std::vector<dof_id_type> subdomain_bounds(mesh.n_processors());
 
  for (auto pid : make_range(mesh.n_processors()))
    {
      dof_id_type tgt_subdomain_size = 0;
 
      // watch out for the case that n_subdomains < n_processors
      if (pid < n_subdomains)
        {
          tgt_subdomain_size = n_unpartitioned_elements/n_subdomains;
 
          if (pid < n_unpartitioned_elements%n_subdomains)
            tgt_subdomain_size++;
 
        }
 
      //libMesh::out << "pid, #= " << pid << ", " << tgt_subdomain_size << std::endl;
      if (pid == 0)
        subdomain_bounds[0] = tgt_subdomain_size;
      else
        subdomain_bounds[pid] = subdomain_bounds[pid-1] + tgt_subdomain_size;
    }
 
  libmesh_assert_equal_to (subdomain_bounds.back(), n_unpartitioned_elements);
 
  // create the unique mapping for all unpartitioned elements independent of partitioning
  // determine the global indexing for all the unpartitioned elements
  std::vector<dof_id_type> global_indices;
 
  // Calling this on all processors a unique range in [0,n_unpartitioned_elements) is constructed.
  // Only the indices for the elements we pass in are returned in the array.
  MeshCommunication().find_global_indices (mesh.comm(),
                                           MeshTools::create_bounding_box(mesh), it, end,
                                           global_indices);
 
  dof_id_type cnt=0;
  for (auto & elem : as_range(it, end))
    {
      libmesh_assert_less (cnt, global_indices.size());
      const dof_id_type global_index =
        global_indices[cnt++];
 
      libmesh_assert_less (global_index, subdomain_bounds.back());
      libmesh_assert_less (global_index, n_unpartitioned_elements);
 
      const processor_id_type subdomain_id =
        cast_int<processor_id_type>
        (std::distance(subdomain_bounds.begin(),
                       std::upper_bound(subdomain_bounds.begin(),
                                        subdomain_bounds.end(),
                                        global_index)));
      libmesh_assert_less (subdomain_id, n_subdomains);
 
      elem->processor_id() = subdomain_id;
      //libMesh::out << "assigning " << global_index << " to " << subdomain_id << std::endl;
    }
}

References libMesh::as_range(), libMesh::ParallelObject::comm(), libMesh::MeshTools::create_bounding_box(), libMesh::MeshCommunication::find_global_indices(), libMesh::make_range(), mesh, libMesh::MeshTools::n_elem(), and libMesh::ParallelObject::n_processors().

processor_pairs_to_interface_nodes()

void libMesh::Partitioner::processor_pairs_to_interface_nodes ( MeshBase &  mesh, std::map< std::pair< processor_id_type, processor_id_type >, std::set< dof_id_type > > &  processor_pair_to_nodes  )

staticinherited

On the partitioning interface, a surface is shared by two and only two processors.

Try to find which pair of processors corresponds to which surfaces, and store their nodes.

Definition at line 579 of file partitioner.C.

{
  // This function must be run on all processors at once
  libmesh_parallel_only(mesh.comm());
 
  processor_pair_to_nodes.clear();
 
  std::set<dof_id_type> mynodes;
  std::set<dof_id_type> neighbor_nodes;
  std::vector<dof_id_type> common_nodes;
 
  // Loop over all the active elements
  for (auto & elem : mesh.active_element_ptr_range())
    {
      libmesh_assert(elem);
 
      libmesh_assert_not_equal_to (elem->processor_id(), DofObject::invalid_processor_id);
 
      auto n_nodes = elem->n_nodes();
 
      // prepare data for this element
      mynodes.clear();
      neighbor_nodes.clear();
      common_nodes.clear();
 
      for (unsigned int inode = 0; inode < n_nodes; inode++)
        mynodes.insert(elem->node_id(inode));
 
      for (auto i : elem->side_index_range())
        {
          auto neigh = elem->neighbor_ptr(i);
          if (neigh && !neigh->is_remote() && neigh->processor_id() != elem->processor_id())
            {
              neighbor_nodes.clear();
              common_nodes.clear();
              auto neigh_n_nodes = neigh->n_nodes();
              for (unsigned int inode = 0; inode < neigh_n_nodes; inode++)
                neighbor_nodes.insert(neigh->node_id(inode));
 
              std::set_intersection(mynodes.begin(), mynodes.end(),
                                    neighbor_nodes.begin(), neighbor_nodes.end(),
                                    std::back_inserter(common_nodes));
 
              auto & map_set = processor_pair_to_nodes[std::make_pair(std::min(elem->processor_id(), neigh->processor_id()),
                                                                      std::max(elem->processor_id(), neigh->processor_id()))];
              for (auto global_node_id : common_nodes)
                map_set.insert(global_node_id);
            }
        }
    }
}

References libMesh::ParallelObject::comm(), libMesh::DofObject::invalid_processor_id, libMesh::libmesh_assert(), mesh, and n_nodes.

Referenced by libMesh::Partitioner::set_interface_node_processor_ids_BFS(), libMesh::Partitioner::set_interface_node_processor_ids_linear(), and libMesh::Partitioner::set_interface_node_processor_ids_petscpartitioner().

repartition() [1/2]

void libMesh::Partitioner::repartition ( MeshBase &  mesh )

inherited

Repartitions the MeshBase into mesh.n_processors() parts.

This is required since some partitioning algorithms can repartition more efficiently than computing a new partitioning from scratch.

Definition at line 256 of file partitioner.C.

{
  this->repartition(mesh,mesh.n_processors());
}

References mesh, libMesh::ParallelObject::n_processors(), and libMesh::Partitioner::repartition().

repartition() [2/2]

void libMesh::Partitioner::repartition ( MeshBase &  mesh, const unsigned int  n  )

inherited

Repartitions the MeshBase into n parts.

(Some partitioning algorithms can repartition more efficiently than computing a new partitioning from scratch.) The default behavior is to simply call this->partition(mesh,n).

Definition at line 263 of file partitioner.C.

{
  // we cannot partition into more pieces than we have
  // active elements!
  const unsigned int n_parts =
    static_cast<unsigned int>
    (std::min(mesh.n_active_elem(), static_cast<dof_id_type>(n)));
 
  // Set the number of partitions in the mesh
  mesh.set_n_partitions()=n_parts;
 
  if (n_parts == 1)
    {
      this->single_partition (mesh);
      return;
    }
 
  // First assign a temporary partitioning to any unpartitioned elements
  Partitioner::partition_unpartitioned_elements(mesh, n_parts);
 
  // Call the partitioning function
  this->_do_repartition(mesh,n_parts);
 
  // Set the parent's processor ids
  Partitioner::set_parent_processor_ids(mesh);
 
  // Set the node's processor ids
  Partitioner::set_node_processor_ids(mesh);
}

References libMesh::Partitioner::_do_repartition(), mesh, libMesh::MeshBase::n_active_elem(), libMesh::Partitioner::partition_unpartitioned_elements(), libMesh::MeshBase::set_n_partitions(), libMesh::Partitioner::set_node_processor_ids(), libMesh::Partitioner::set_parent_processor_ids(), and libMesh::Partitioner::single_partition().

Referenced by libMesh::Partitioner::repartition().

set_interface_node_processor_ids_BFS()

void libMesh::Partitioner::set_interface_node_processor_ids_BFS ( MeshBase &  mesh )

staticinherited

Nodes on the partitioning interface is clustered into two groups BFS (Breadth First Search)scheme for per pair of processors.

Definition at line 657 of file partitioner.C.

{
  // This function must be run on all processors at once
  libmesh_parallel_only(mesh.comm());
 
  // I see occasional consistency failures when using this on a
  // distributed mesh
  libmesh_experimental();
 
  std::map<std::pair<processor_id_type, processor_id_type>, std::set<dof_id_type>> processor_pair_to_nodes;
 
  processor_pairs_to_interface_nodes(mesh, processor_pair_to_nodes);
 
  std::unordered_map<dof_id_type, std::vector<const Elem *>> nodes_to_elem_map;
 
  MeshTools::build_nodes_to_elem_map(mesh, nodes_to_elem_map);
 
  std::vector<const Node *>  neighbors;
  std::set<dof_id_type> neighbors_order;
  std::vector<dof_id_type> common_nodes;
  std::queue<dof_id_type> nodes_queue;
  std::set<dof_id_type> visted_nodes;
 
  for (auto & pmap : processor_pair_to_nodes)
    {
      std::size_t n_own_nodes = pmap.second.size()/2;
 
      // Initialize node assignment
      for (dof_id_type id : pmap.second)
        mesh.node_ref(id).processor_id() = pmap.first.second;
 
      visted_nodes.clear();
      for (dof_id_type id : pmap.second)
        {
          mesh.node_ref(id).processor_id() = pmap.first.second;
 
          if (visted_nodes.count(id))
            continue;
          else
            {
              nodes_queue.push(id);
              visted_nodes.insert(id);
              if (visted_nodes.size() >= n_own_nodes)
                break;
            }
 
          while (!nodes_queue.empty())
            {
              auto & node = mesh.node_ref(nodes_queue.front());
              nodes_queue.pop();
 
              neighbors.clear();
              MeshTools::find_nodal_neighbors(mesh, node, nodes_to_elem_map, neighbors);
              neighbors_order.clear();
              for (auto & neighbor : neighbors)
                neighbors_order.insert(neighbor->id());
 
              common_nodes.clear();
              std::set_intersection(pmap.second.begin(), pmap.second.end(),
                                    neighbors_order.begin(), neighbors_order.end(),
                                    std::back_inserter(common_nodes));
 
              for (auto c_node : common_nodes)
                if (!visted_nodes.count(c_node))
                  {
                    nodes_queue.push(c_node);
                    visted_nodes.insert(c_node);
                    if (visted_nodes.size() >= n_own_nodes)
                      goto queue_done;
                  }
 
              if (visted_nodes.size() >= n_own_nodes)
                goto queue_done;
            }
        }
    queue_done:
      for (auto node : visted_nodes)
        mesh.node_ref(node).processor_id() = pmap.first.first;
    }
}

References libMesh::MeshTools::build_nodes_to_elem_map(), libMesh::ParallelObject::comm(), libMesh::MeshTools::find_nodal_neighbors(), mesh, libMesh::MeshBase::node_ref(), libMesh::DofObject::processor_id(), and libMesh::Partitioner::processor_pairs_to_interface_nodes().

Referenced by libMesh::Partitioner::set_node_processor_ids().

set_interface_node_processor_ids_linear()

void libMesh::Partitioner::set_interface_node_processor_ids_linear ( MeshBase &  mesh )

staticinherited

Nodes on the partitioning interface is linearly assigned to each pair of processors.

Definition at line 632 of file partitioner.C.

{
  // This function must be run on all processors at once
  libmesh_parallel_only(mesh.comm());
 
  std::map<std::pair<processor_id_type, processor_id_type>, std::set<dof_id_type>> processor_pair_to_nodes;
 
  processor_pairs_to_interface_nodes(mesh, processor_pair_to_nodes);
 
  for (auto & pmap : processor_pair_to_nodes)
    {
      std::size_t n_own_nodes = pmap.second.size()/2, i = 0;
 
      for (dof_id_type id : pmap.second)
        {
          auto & node = mesh.node_ref(id);
          if (i <= n_own_nodes)
            node.processor_id() = pmap.first.first;
          else
            node.processor_id() = pmap.first.second;
          i++;
        }
    }
}

References libMesh::ParallelObject::comm(), mesh, libMesh::MeshBase::node_ref(), libMesh::DofObject::processor_id(), and libMesh::Partitioner::processor_pairs_to_interface_nodes().

Referenced by libMesh::Partitioner::set_node_processor_ids().

set_interface_node_processor_ids_petscpartitioner()

void libMesh::Partitioner::set_interface_node_processor_ids_petscpartitioner ( MeshBase &  mesh )

staticinherited

Nodes on the partitioning interface is partitioned into two groups using a PETSc partitioner for each pair of processors.

Definition at line 738 of file partitioner.C.

{
  libmesh_ignore(mesh); // Only used if LIBMESH_HAVE_PETSC
 
  // This function must be run on all processors at once
  libmesh_parallel_only(mesh.comm());
 
#ifdef LIBMESH_HAVE_PETSC
  std::map<std::pair<processor_id_type, processor_id_type>, std::set<dof_id_type>> processor_pair_to_nodes;
 
  processor_pairs_to_interface_nodes(mesh, processor_pair_to_nodes);
 
  std::vector<std::vector<const Elem *>> nodes_to_elem_map;
 
  MeshTools::build_nodes_to_elem_map(mesh, nodes_to_elem_map);
 
  std::vector<const Node *>  neighbors;
  std::set<dof_id_type> neighbors_order;
  std::vector<dof_id_type> common_nodes;
 
  std::vector<dof_id_type> rows;
  std::vector<dof_id_type> cols;
 
  std::map<dof_id_type, dof_id_type> global_to_local;
 
  for (auto & pmap : processor_pair_to_nodes)
    {
      unsigned int i = 0;
 
      rows.clear();
      rows.resize(pmap.second.size()+1);
      cols.clear();
      for (dof_id_type id : pmap.second)
        global_to_local[id] = i++;
 
      i = 0;
      for (auto id : pmap.second)
        {
          auto & node = mesh.node_ref(id);
          neighbors.clear();
          MeshTools::find_nodal_neighbors(mesh, node, nodes_to_elem_map, neighbors);
          neighbors_order.clear();
          for (auto & neighbor : neighbors)
            neighbors_order.insert(neighbor->id());
 
          common_nodes.clear();
          std::set_intersection(pmap.second.begin(), pmap.second.end(),
                                neighbors_order.begin(), neighbors_order.end(),
                                std::back_inserter(common_nodes));
 
          rows[i+1] = rows[i] + cast_int<dof_id_type>(common_nodes.size());
 
          for (auto c_node : common_nodes)
            cols.push_back(global_to_local[c_node]);
 
          i++;
        }
 
      // Next we construct an IS from a MatPartitioning
      WrappedPetsc<IS> is;
      {
        PetscInt *adj_i, *adj_j;
        LibmeshPetscCall2(mesh.comm(), PetscCalloc1(rows.size(), &adj_i));
        LibmeshPetscCall2(mesh.comm(), PetscCalloc1(cols.size(), &adj_j));
        PetscInt rows_size = cast_int<PetscInt>(rows.size());
        for (PetscInt ii=0; ii<rows_size; ii++)
          adj_i[ii] = rows[ii];
 
        PetscInt cols_size = cast_int<PetscInt>(cols.size());
        for (PetscInt ii=0; ii<cols_size; ii++)
          adj_j[ii] = cols[ii];
 
        const PetscInt sz = cast_int<PetscInt>(pmap.second.size());
 
        // Create sparse matrix representing an adjacency list
        WrappedPetsc<Mat> adj;
        LibmeshPetscCall2(mesh.comm(), MatCreateMPIAdj(PETSC_COMM_SELF, sz, sz, adj_i, adj_j, nullptr, adj.get()));
 
        // Create MatPartitioning object
        WrappedPetsc<MatPartitioning> part;
        LibmeshPetscCall2(mesh.comm(), MatPartitioningCreate(PETSC_COMM_SELF, part.get()));
 
        // Apply MatPartitioning, storing results in "is"
        LibmeshPetscCall2(mesh.comm(), MatPartitioningSetAdjacency(part, adj));
        LibmeshPetscCall2(mesh.comm(), MatPartitioningSetNParts(part, 2));
        LibmeshPetscCall2(mesh.comm(), PetscObjectSetOptionsPrefix((PetscObject)(*part), "balance_"));
        LibmeshPetscCall2(mesh.comm(), MatPartitioningSetFromOptions(part));
        LibmeshPetscCall2(mesh.comm(), MatPartitioningApply(part, is.get()));
      }
 
      PetscInt local_size;
      const PetscInt *indices;
      LibmeshPetscCall2(mesh.comm(), ISGetLocalSize(is, &local_size));
      LibmeshPetscCall2(mesh.comm(), ISGetIndices(is, &indices));
 
      i = 0;
      for (auto id : pmap.second)
        {
          auto & node = mesh.node_ref(id);
          if (indices[i])
            node.processor_id() = pmap.first.second;
          else
            node.processor_id() = pmap.first.first;
 
          i++;
        }
      LibmeshPetscCall2(mesh.comm(), ISRestoreIndices(is, &indices));
    }
#else
  libmesh_error_msg("PETSc is required");
#endif
}

References libMesh::MeshTools::build_nodes_to_elem_map(), libMesh::ParallelObject::comm(), libMesh::MeshTools::find_nodal_neighbors(), libMesh::WrappedPetsc< T >::get(), libMesh::is, libMesh::libmesh_ignore(), mesh, libMesh::MeshBase::node_ref(), libMesh::DofObject::processor_id(), and libMesh::Partitioner::processor_pairs_to_interface_nodes().

Referenced by libMesh::Partitioner::set_node_processor_ids().

set_node_processor_ids()

void libMesh::Partitioner::set_node_processor_ids ( MeshBase &  mesh )

staticinherited

This function is called after partitioning to set the processor IDs for the nodes.

By definition, a Node's processor ID is the minimum processor ID for all of the elements which share the node.

Definition at line 852 of file partitioner.C.

{
  LOG_SCOPE("set_node_processor_ids()","Partitioner");
 
  // This function must be run on all processors at once
  libmesh_parallel_only(mesh.comm());
 
  // If we have any unpartitioned elements at this
  // stage there is a problem
  libmesh_assert (MeshTools::n_elem(mesh.unpartitioned_elements_begin(),
                                    mesh.unpartitioned_elements_end()) == 0);
 
  // Start from scratch here: nodes we used to own may not be
  // eligible for us to own any more.
  for (auto & node : mesh.node_ptr_range())
    {
      node->processor_id() = DofObject::invalid_processor_id;
    }
 
  // Loop over all the active elements
  for (auto & elem : mesh.active_element_ptr_range())
    {
      libmesh_assert(elem);
 
      libmesh_assert_not_equal_to (elem->processor_id(), DofObject::invalid_processor_id);
 
      // Consider updating the processor id on this element's nodes
      for (Node & node : elem->node_ref_range())
        {
          processor_id_type & pid = node.processor_id();
          pid = node.choose_processor_id(pid, elem->processor_id());
        }
    }
 
  // How we finish off the node partitioning depends on our command
  // line options.
 
  const bool load_balanced_nodes_linear =
      libMesh::on_command_line ("--load-balanced-nodes-linear");
 
  const bool load_balanced_nodes_bfs =
       libMesh::on_command_line ("--load-balanced-nodes-bfs");
 
  const bool load_balanced_nodes_petscpartition =
      libMesh::on_command_line ("--load-balanced-nodes-petscpartitioner");
 
  unsigned int n_load_balance_options = load_balanced_nodes_linear;
  n_load_balance_options += load_balanced_nodes_bfs;
  n_load_balance_options += load_balanced_nodes_petscpartition;
  libmesh_error_msg_if(n_load_balance_options > 1,
                       "Cannot perform more than one load balancing type at a time");
 
  if (load_balanced_nodes_linear)
    set_interface_node_processor_ids_linear(mesh);
  else if (load_balanced_nodes_bfs)
    set_interface_node_processor_ids_BFS(mesh);
  else if (load_balanced_nodes_petscpartition)
    set_interface_node_processor_ids_petscpartitioner(mesh);
 
   // Node balancing algorithm will response to assign owned nodes.
   // We still need to sync PIDs
  {
    // For inactive elements, we will have already gotten most of
    // these nodes, *except* for the case of a parent with a subset
    // of active descendants which are remote elements.  In that
    // case some of the parent nodes will not have been properly
    // handled yet on our processor.
    //
    // We don't want to inadvertently give one of them an incorrect
    // processor id, but if we're not in serial then we have to
    // assign them temporary pids to make querying work, so we'll
    // save our *valid* pids before assigning temporaries.
    //
    // Even in serial we'll want to check and make sure we're not
    // overwriting valid active node pids with pids from subactive
    // elements.
    std::unordered_set<dof_id_type> bad_pids;
 
    for (auto & node : mesh.node_ptr_range())
      if (node->processor_id() == DofObject::invalid_processor_id)
        bad_pids.insert(node->id());
 
    // If we assign our temporary ids by looping from finer elements
    // to coarser elements, we'll always get an id from the finest
    // ghost element we can see, which will usually be "closer" to
    // the true processor we want to query and so will reduce query
    // cycles that don't reach that processor.
 
    // But we can still end up with a query cycle that dead-ends, so
    // we need to prepare a "push" communication step here.
 
    const bool is_serial = mesh.is_serial();
    std::unordered_map
      <processor_id_type,
       std::unordered_map<dof_id_type, processor_id_type>>
      potential_pids;
 
    const unsigned int n_levels = MeshTools::n_levels(mesh);
    for (unsigned int level = n_levels; level > 0; --level)
      {
        for (auto & elem : as_range(mesh.level_elements_begin(level-1),
                                    mesh.level_elements_end(level-1)))
          {
            libmesh_assert_not_equal_to (elem->processor_id(),
                                         DofObject::invalid_processor_id);
 
            const processor_id_type elem_pid = elem->processor_id();
 
            // Consider updating the processor id on this element's nodes
            for (Node & node : elem->node_ref_range())
              {
                processor_id_type & pid = node.processor_id();
                if (bad_pids.count(node.id()))
                  pid = node.choose_processor_id(pid, elem_pid);
                else if (!is_serial)
                  potential_pids[elem_pid][node.id()] = pid;
              }
          }
      }
 
    if (!is_serial)
      {
        std::unordered_map
          <processor_id_type,
           std::vector<std::pair<dof_id_type, processor_id_type>>>
          potential_pids_vecs;
 
        for (auto & pair : potential_pids)
          potential_pids_vecs[pair.first].assign(pair.second.begin(), pair.second.end());
 
        auto pids_action_functor =
          [& mesh, & bad_pids]
          (processor_id_type /* src_pid */,
           const std::vector<std::pair<dof_id_type, processor_id_type>> & data)
          {
            for (auto pair : data)
              {
                Node & node = mesh.node_ref(pair.first);
                processor_id_type & pid = node.processor_id();
                if (const auto it = bad_pids.find(pair.first);
                    it != bad_pids.end())
                  {
                    pid = pair.second;
                    bad_pids.erase(it);
                  }
                else
                  pid = node.choose_processor_id(pid, pair.second);
              }
          };
 
        Parallel::push_parallel_vector_data
          (mesh.comm(), potential_pids_vecs, pids_action_functor);
 
        // Using default libMesh options, we'll just need to sync
        // between processors now.  The catch here is that we can't
        // initially trust Node::choose_processor_id() because some
        // of those node processor ids are the temporary ones.
        CorrectProcIds correct_pids(mesh, bad_pids);
        Parallel::sync_node_data_by_element_id
          (mesh, mesh.elements_begin(), mesh.elements_end(),
           Parallel::SyncEverything(), Parallel::SyncEverything(),
           correct_pids);
 
        // But once we've got all the non-temporary pids synced, we
        // may need to sync again to get any pids on nodes only
        // connected to subactive elements, for which *only*
        // "temporary" pids are possible.
        bad_pids.clear();
        Parallel::sync_node_data_by_element_id
          (mesh,
           mesh.elements_begin(), mesh.elements_end(),
           Parallel::SyncEverything(), Parallel::SyncEverything(),
           correct_pids);
      }
  }
 
  // We can't assert that all nodes are connected to elements, because
  // a DistributedMesh with NodeConstraints might have pulled in some
  // remote nodes solely for evaluating those constraints.
  // MeshTools::libmesh_assert_connected_nodes(mesh);
 
#ifdef DEBUG
  MeshTools::libmesh_assert_valid_procids<Node>(mesh);
  //MeshTools::libmesh_assert_canonical_node_procids(mesh);
#endif
}

References libMesh::as_range(), libMesh::Node::choose_processor_id(), libMesh::ParallelObject::comm(), libMesh::DofObject::id(), libMesh::DofObject::invalid_processor_id, libMesh::MeshBase::is_serial(), libMesh::libmesh_assert(), mesh, libMesh::MeshTools::n_elem(), libMesh::MeshTools::n_levels(), libMesh::MeshBase::node_ref(), libMesh::on_command_line(), libMesh::DofObject::processor_id(), TIMPI::push_parallel_vector_data(), libMesh::Partitioner::set_interface_node_processor_ids_BFS(), libMesh::Partitioner::set_interface_node_processor_ids_linear(), libMesh::Partitioner::set_interface_node_processor_ids_petscpartitioner(), and libMesh::Parallel::sync_node_data_by_element_id().

Referenced by libMesh::UnstructuredMesh::all_first_order(), libMesh::Partitioner::partition(), libMesh::XdrIO::read(), libMesh::Partitioner::repartition(), and libMesh::BoundaryInfo::sync().

set_parent_processor_ids()

void libMesh::Partitioner::set_parent_processor_ids ( MeshBase &  mesh )

staticinherited

This function is called after partitioning to set the processor IDs for the inactive parent elements.

A parent's processor ID is the same as its first child.

Definition at line 426 of file partitioner.C.

{
  // Ignore the parameter when !LIBMESH_ENABLE_AMR
  libmesh_ignore(mesh);
 
  LOG_SCOPE("set_parent_processor_ids()", "Partitioner");
 
#ifdef LIBMESH_ENABLE_AMR
 
  // If the mesh is serial we have access to all the elements,
  // in particular all the active ones.  We can therefore set
  // the parent processor ids indirectly through their children, and
  // set the subactive processor ids while examining their active
  // ancestors.
  // By convention a parent is assigned to the minimum processor
  // of all its children, and a subactive is assigned to the processor
  // of its active ancestor.
  if (mesh.is_serial())
    {
      for (auto & elem : mesh.active_element_ptr_range())
        {
          // First set descendents
          std::vector<Elem *> subactive_family;
          elem->total_family_tree(subactive_family);
          for (const auto & f : subactive_family)
            f->processor_id() = elem->processor_id();
 
          // Then set ancestors
          Elem * parent = elem->parent();
 
          while (parent)
            {
              // invalidate the parent id, otherwise the min below
              // will not work if the current parent id is less
              // than all the children!
              parent->invalidate_processor_id();
 
              for (auto & child : parent->child_ref_range())
                {
                  libmesh_assert(!child.is_remote());
                  libmesh_assert_not_equal_to (child.processor_id(), DofObject::invalid_processor_id);
                  parent->processor_id() = std::min(parent->processor_id(),
                                                    child.processor_id());
                }
              parent = parent->parent();
            }
        }
    }
 
  // When the mesh is parallel we cannot guarantee that parents have access to
  // all their children.
  else
    {
      // Setting subactive processor ids is easy: we can guarantee
      // that children have access to all their parents.
 
      // Loop over all the active elements in the mesh
      for (auto & child : mesh.active_element_ptr_range())
        {
          std::vector<Elem *> subactive_family;
          child->total_family_tree(subactive_family);
          for (const auto & f : subactive_family)
            f->processor_id() = child->processor_id();
        }
 
      // When the mesh is parallel we cannot guarantee that parents have access to
      // all their children.
 
      // We will use a brute-force approach here.  Each processor finds its parent
      // elements and sets the parent pid to the minimum of its
      // semilocal descendants.
      // A global reduction is then performed to make sure the true minimum is found.
      // As noted, this is required because we cannot guarantee that a parent has
      // access to all its children on any single processor.
      libmesh_parallel_only(mesh.comm());
      libmesh_assert(MeshTools::n_elem(mesh.unpartitioned_elements_begin(),
                                       mesh.unpartitioned_elements_end()) == 0);
 
      const dof_id_type max_elem_id = mesh.max_elem_id();
 
      std::vector<processor_id_type>
        parent_processor_ids (std::min(communication_blocksize,
                                       max_elem_id));
 
      for (dof_id_type blk=0, last_elem_id=0; last_elem_id<max_elem_id; blk++)
        {
          last_elem_id =
            std::min(static_cast<dof_id_type>((blk+1)*communication_blocksize),
                     max_elem_id);
          const dof_id_type first_elem_id = blk*communication_blocksize;
 
          std::fill (parent_processor_ids.begin(),
                     parent_processor_ids.end(),
                     DofObject::invalid_processor_id);
 
          // first build up local contributions to parent_processor_ids
          bool have_parent_in_block = false;
 
          for (auto & parent : as_range(mesh.ancestor_elements_begin(),
                                        mesh.ancestor_elements_end()))
            {
              const dof_id_type parent_idx = parent->id();
              libmesh_assert_less (parent_idx, max_elem_id);
 
              if ((parent_idx >= first_elem_id) &&
                  (parent_idx <  last_elem_id))
                {
                  have_parent_in_block = true;
                  processor_id_type parent_pid = DofObject::invalid_processor_id;
 
                  std::vector<const Elem *> active_family;
                  parent->active_family_tree(active_family);
                  for (const auto & f : active_family)
                    parent_pid = std::min (parent_pid, f->processor_id());
 
                  const dof_id_type packed_idx = parent_idx - first_elem_id;
                  libmesh_assert_less (packed_idx, parent_processor_ids.size());
 
                  parent_processor_ids[packed_idx] = parent_pid;
                }
            }
 
          // then find the global minimum
          mesh.comm().min (parent_processor_ids);
 
          // and assign the ids, if we have a parent in this block.
          if (have_parent_in_block)
            for (auto & parent : as_range(mesh.ancestor_elements_begin(),
                                          mesh.ancestor_elements_end()))
              {
                const dof_id_type parent_idx = parent->id();
 
                if ((parent_idx >= first_elem_id) &&
                    (parent_idx <  last_elem_id))
                  {
                    const dof_id_type packed_idx = parent_idx - first_elem_id;
                    libmesh_assert_less (packed_idx, parent_processor_ids.size());
 
                    const processor_id_type parent_pid =
                      parent_processor_ids[packed_idx];
 
                    libmesh_assert_not_equal_to (parent_pid, DofObject::invalid_processor_id);
 
                    parent->processor_id() = parent_pid;
                  }
              }
        }
    }
 
#endif // LIBMESH_ENABLE_AMR
}

References libMesh::as_range(), libMesh::Elem::child_ref_range(), libMesh::ParallelObject::comm(), libMesh::Partitioner::communication_blocksize, libMesh::DofObject::invalid_processor_id, libMesh::DofObject::invalidate_processor_id(), libMesh::MeshBase::is_serial(), libMesh::libmesh_assert(), libMesh::libmesh_ignore(), libMesh::MeshBase::max_elem_id(), mesh, libMesh::Parallel::Communicator::min(), libMesh::MeshTools::n_elem(), libMesh::Elem::parent(), libMesh::DofObject::processor_id(), and libMesh::Elem::total_family_tree().

Referenced by libMesh::Partitioner::partition(), and libMesh::Partitioner::repartition().

single_partition()

bool libMesh::Partitioner::single_partition ( MeshBase &  mesh )

protectedinherited

Trivially "partitions" the mesh for one processor.

Simply loops through the elements and assigns all of them to processor 0. Is is provided as a separate function so that derived classes may use it without reimplementing it.

Returns true iff any processor id was changed.

Definition at line 298 of file partitioner.C.

{
  bool changed_pid =
    this->single_partition_range(mesh.elements_begin(),
                                 mesh.elements_end());
 
  // If we have a distributed mesh with an empty rank (or where rank
  // 0 has only its own component of a disconnected mesh, I guess),
  // that rank might need to be informed of a change.
  mesh.comm().max(changed_pid);
 
  // We may need to redistribute, in case someone (like our unit
  // tests) is doing something silly (like moving a whole
  // already-distributed mesh back onto rank 0).
  if (changed_pid)
    mesh.redistribute();
 
  return changed_pid;
}

References libMesh::ParallelObject::comm(), libMesh::Parallel::Communicator::max(), mesh, libMesh::MeshBase::redistribute(), and libMesh::Partitioner::single_partition_range().

Referenced by libMesh::SubdomainPartitioner::_do_partition(), libMesh::Partitioner::partition(), and libMesh::Partitioner::repartition().

single_partition_range()

bool libMesh::Partitioner::single_partition_range ( MeshBase::element_iterator  it, MeshBase::element_iterator  end  )

protectedinherited

Slightly generalized version of single_partition which acts on a range of elements defined by the pair of iterators (it, end).

Returns true iff any processor id was changed.

Definition at line 320 of file partitioner.C.

{
  LOG_SCOPE("single_partition_range()", "Partitioner");
 
  bool changed_pid = false;
 
  for (auto & elem : as_range(it, end))
    {
      if (elem->processor_id())
        changed_pid = true;
      elem->processor_id() = 0;
 
      // Assign all this element's nodes to processor 0 as well.
      for (Node & node : elem->node_ref_range())
        {
          if (node.processor_id())
            changed_pid = true;
          node.processor_id() = 0;
        }
    }
 
  return changed_pid;
}

References libMesh::as_range(), and libMesh::DofObject::processor_id().

Referenced by NonManifoldTestPartitioner::_do_partition(), OverlappingTestPartitioner::_do_partition(), libMesh::CentroidPartitioner::partition_range(), libMesh::LinearPartitioner::partition_range(), libMesh::MappedSubdomainPartitioner::partition_range(), libMesh::MetisPartitioner::partition_range(), libMesh::SFCPartitioner::partition_range(), and libMesh::Partitioner::single_partition().

type()

virtual PartitionerType libMesh::ParmetisPartitioner::type ( ) const

overridevirtual

Reimplemented from libMesh::Partitioner.

Member Data Documentation

_dual_graph

std::vector<std::vector<dof_id_type> > libMesh::Partitioner::_dual_graph

protectedinherited

A dual graph corresponds to the mesh, and it is typically used in paritioner.

A vertex represents an element, and its neighbors are the element neighbors.

Definition at line 302 of file partitioner.h.

Referenced by libMesh::Partitioner::build_graph().

_global_index_by_pid_map

std::unordered_map<dof_id_type, dof_id_type> libMesh::Partitioner::_global_index_by_pid_map

protectedinherited

Maps active element ids into a contiguous range, as needed by parallel partitioner.

Definition at line 286 of file partitioner.h.

Referenced by libMesh::Partitioner::_find_global_index_by_pid_map(), libMesh::Partitioner::assign_partitioning(), and libMesh::Partitioner::build_graph().

_local_id_to_elem

std::vector<Elem *> libMesh::Partitioner::_local_id_to_elem

protectedinherited

Definition at line 305 of file partitioner.h.

Referenced by libMesh::Partitioner::build_graph().

_n_active_elem_on_proc

std::vector<dof_id_type> libMesh::Partitioner::_n_active_elem_on_proc

protectedinherited

The number of active elements on each processor.

Note

ParMETIS requires that each processor have some active elements; it will abort if any processor passes a nullptr _part array.

Definition at line 295 of file partitioner.h.

Referenced by libMesh::Partitioner::_find_global_index_by_pid_map(), libMesh::Partitioner::assign_partitioning(), and libMesh::Partitioner::build_graph().

_pmetis

std::unique_ptr<ParmetisHelper> libMesh::ParmetisPartitioner::_pmetis

private

Pointer to the Parmetis-specific data structures.

Lets us avoid including parmetis.h here.

Definition at line 124 of file parmetis_partitioner.h.

_weights

ErrorVector* libMesh::Partitioner::_weights

protectedinherited

The weights that might be used for partitioning.

Definition at line 281 of file partitioner.h.

Referenced by libMesh::MetisPartitioner::attach_weights(), and libMesh::MetisPartitioner::partition_range().

communication_blocksize

const dof_id_type libMesh::Partitioner::communication_blocksize

staticprotectedinherited

Initial value:

=
  dof_id_type(1000000)

The blocksize to use when doing blocked parallel communication.

This limits the maximum vector size which can be used in a single communication step.

Definition at line 258 of file partitioner.h.

Referenced by libMesh::Partitioner::set_parent_processor_ids().

---

The documentation for this class was generated from the following files:

• include/partitioning/parmetis_partitioner.h
• src/partitioning/parmetis_partitioner.C