libMesh::Partitioner Class Reference

#include <partitioner.h>

Inheritance diagram for libMesh::Partitioner:

[legend]

List of all members.

Public Member Functions
	Partitioner ()
virtual	~Partitioner ()
virtual AutoPtr< Partitioner >	clone () const =0
void	partition (MeshBase &mesh, const unsigned int n=libMesh::n_processors())
void	repartition (MeshBase &mesh, const unsigned int n=libMesh::n_processors())
virtual void	attach_weights (ErrorVector *)
Static Public Member Functions
static void	partition_unpartitioned_elements (MeshBase &mesh, const unsigned int n=libMesh::n_processors())
static void	set_parent_processor_ids (MeshBase &mesh)
static void	set_node_processor_ids (MeshBase &mesh)
Protected Member Functions
void	single_partition (MeshBase &mesh)
virtual void	_do_partition (MeshBase &mesh, const unsigned int n)=0
virtual void	_do_repartition (MeshBase &mesh, const unsigned int n)
Protected Attributes
ErrorVector *	_weights
Static Protected Attributes
static const dof_id_type	communication_blocksize = 1000000

---

Detailed Description

The Partitioner class provides a uniform interface for partitioning algorithms. It takes a reference to a MeshBase object as input, which it will partition into a number of subdomains.

Definition at line 48 of file partitioner.h.

---

Constructor & Destructor Documentation

libMesh::Partitioner::Partitioner

(

)

[inline]

Constructor.

Definition at line 55 of file partitioner.h.

:_weights(NULL) {}

virtual libMesh::Partitioner::~Partitioner

(

)

[inline, virtual]

Destructor. Virtual so that we can derive from this class.

Definition at line 60 of file partitioner.h.

{}

---

Member Function Documentation

virtual void libMesh::Partitioner::_do_partition	(	MeshBase &	mesh,
		const unsigned int	n
	)			[protected, pure virtual]

This is the actual partitioning method which must be overloaded in derived classes. It is called via the public partition() method above by the user.

Implemented in libMesh::CentroidPartitioner, libMesh::HilbertSFCPartitioner, libMesh::LinearPartitioner, libMesh::MetisPartitioner, libMesh::MortonSFCPartitioner, libMesh::ParmetisPartitioner, and libMesh::SFCPartitioner.

Referenced by _do_repartition(), and partition().

virtual void libMesh::Partitioner::_do_repartition	(	MeshBase &	mesh,
		const unsigned int	n
	)			[inline, protected, virtual]

This is the actual re-partitioning method which can be overloaded in derived classes. Note that the default behavior is to simply call the partition function.

Reimplemented in libMesh::ParmetisPartitioner.

Definition at line 143 of file partitioner.h.

References _do_partition().

Referenced by repartition().

                                                      { this->_do_partition (mesh, n); }

virtual void libMesh::Partitioner::attach_weights

(

ErrorVector *

)

[inline, virtual]

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 118 of file partitioner.h.

{ libmesh_not_implemented(); }

virtual AutoPtr<Partitioner> libMesh::Partitioner::clone

(

)

const [pure virtual]

Creates a new partitioner of this type and returns it in an AutoPtr. This is used when copying meshes, and must be overloaded in the derived classes.

Implemented in libMesh::CentroidPartitioner, libMesh::HilbertSFCPartitioner, libMesh::LinearPartitioner, libMesh::MetisPartitioner, libMesh::MortonSFCPartitioner, libMesh::ParmetisPartitioner, and libMesh::SFCPartitioner.

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

Partition the MeshBase into n parts. If the user does not specify a number of pieces into which the mesh should be partitioned, then the default behavior of the partitioner is to partition according to the number of processors defined in libMesh::n_processors(). The partitioner currently does not modify the subdomain_id of each element. This number is reserved for things like material properties, etc.

Definition at line 48 of file partitioner.C.

References _do_partition(), libMesh::MeshTools::libmesh_assert_valid_procids< Elem >(), libMesh::MeshTools::libmesh_assert_valid_remote_elems(), std::min(), libMesh::MeshBase::n_active_elem(), partition_unpartitioned_elements(), libMesh::MeshBase::redistribute(), libMesh::MeshBase::set_n_partitions(), set_node_processor_ids(), set_parent_processor_ids(), single_partition(), and libMesh::MeshBase::update_post_partitioning().

Referenced by libMesh::SFCPartitioner::_do_partition(), libMesh::MetisPartitioner::_do_partition(), and libMesh::ParmetisPartitioner::_do_repartition().

{
  parallel_only();

  // 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();
}

void libMesh::Partitioner::partition_unpartitioned_elements	(	MeshBase &	mesh,
		const unsigned int	n = libMesh::n_processors()
	)			[static]

This function

Definition at line 168 of file partitioner.C.

References libMesh::MeshTools::bounding_box(), end, libMesh::MeshTools::n_elem(), libMesh::n_processors(), libMesh::DofObject::processor_id(), libMesh::MeshBase::unpartitioned_elements_begin(), and libMesh::MeshBase::unpartitioned_elements_end().

Referenced by partition(), and repartition().

{
  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(libMesh::n_processors());

  for (processor_id_type pid=0; pid<libMesh::n_processors(); pid++)
    {
      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 unpartitoned 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 (MeshTools::bounding_box(mesh), it, end,
                                           global_indices);

  for (dof_id_type cnt=0; it != end; ++it)
    {
      Elem *elem = *it;

      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 =
        libmesh_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;
    }
}

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

Repartitions the MeshBase into n parts. This is required since some partitoning algorithms can repartition more efficiently than computing a new partitioning from scratch. The default behavior is to simply call this->partition(n)

Definition at line 110 of file partitioner.C.

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

{
  // 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);
}

void libMesh::Partitioner::set_node_processor_ids

(

MeshBase &

mesh

)

[static]

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 419 of file partitioner.C.

References libMesh::MeshBase::active_elements_begin(), libMesh::MeshBase::active_elements_end(), libMesh::CommWorld, libMesh::Elem::get_node(), libMesh::DofObject::id(), libMesh::DofObject::invalid_processor_id, libMesh::DofObject::invalidate_processor_id(), libMesh::MeshTools::libmesh_assert_valid_procids< Node >(), std::min(), libMesh::MeshTools::n_elem(), libMesh::Elem::n_nodes(), libMesh::MeshBase::n_partitions(), libMesh::n_processors(), libMesh::MeshBase::node_ptr(), libMesh::MeshBase::nodes_begin(), libMesh::MeshBase::nodes_end(), libMesh::MeshBase::not_active_elements_begin(), libMesh::MeshBase::not_active_elements_end(), libMesh::processor_id(), libMesh::DofObject::processor_id(), libMesh::Parallel::Communicator::send_receive(), libMesh::MeshBase::subactive_elements_begin(), libMesh::MeshBase::subactive_elements_end(), libMesh::MeshBase::unpartitioned_elements_begin(), and libMesh::MeshBase::unpartitioned_elements_end().

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

{
  START_LOG("set_node_processor_ids()","Partitioner");

  // This function must be run on all processors at once
  parallel_only();

  // 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);


//   const dof_id_type orig_n_local_nodes = mesh.n_local_nodes();

//   libMesh::err << "[" << libMesh::processor_id() << "]: orig_n_local_nodes="
//          << orig_n_local_nodes << std::endl;

  // Build up request sets.  Each node is currently owned by a processor because
  // it is connected to an element owned by that processor.  However, during the
  // repartitioning phase that element may have been assigned a new processor id, but
  // it is still resident on the original processor.  We need to know where to look
  // for new ids before assigning new ids, otherwise we may be asking the wrong processors
  // for the wrong information.
  //
  // The only remaining issue is what to do with unpartitioned nodes.  Since they are required
  // to live on all processors we can simply rely on ourselves to number them properly.
  std::vector<std::vector<dof_id_type> >
    requested_node_ids(libMesh::n_processors());

  // Loop over all the nodes, count the ones on each processor.  We can skip ourself
  std::vector<dof_id_type> ghost_nodes_from_proc(libMesh::n_processors(), 0);

  MeshBase::node_iterator       node_it  = mesh.nodes_begin();
  const MeshBase::node_iterator node_end = mesh.nodes_end();

  for (; node_it != node_end; ++node_it)
    {
      Node *node = *node_it;
      libmesh_assert(node);
      const processor_id_type current_pid = node->processor_id();
      if (current_pid != libMesh::processor_id() &&
          current_pid != DofObject::invalid_processor_id)
        {
          libmesh_assert_less (current_pid, ghost_nodes_from_proc.size());
          ghost_nodes_from_proc[current_pid]++;
        }
    }

  // We know how many objects live on each processor, so reserve()
  // space for each.
  for (processor_id_type pid=0; pid != libMesh::n_processors(); ++pid)
    requested_node_ids[pid].reserve(ghost_nodes_from_proc[pid]);

  // We need to get the new pid for each node from the processor
  // which *currently* owns the node.  We can safely skip ourself
  for (node_it = mesh.nodes_begin(); node_it != node_end; ++node_it)
    {
      Node *node = *node_it;
      libmesh_assert(node);
      const processor_id_type current_pid = node->processor_id();
      if (current_pid != libMesh::processor_id() &&
          current_pid != DofObject::invalid_processor_id)
        {
          libmesh_assert_less (current_pid, requested_node_ids.size());
          libmesh_assert_less (requested_node_ids[current_pid].size(),
                              ghost_nodes_from_proc[current_pid]);
          requested_node_ids[current_pid].push_back(node->id());
        }

      // Unset any previously-set node processor ids
      node->invalidate_processor_id();
    }

  // Loop over all the active elements
  MeshBase::element_iterator       elem_it  = mesh.active_elements_begin();
  const MeshBase::element_iterator elem_end = mesh.active_elements_end();

  for ( ; elem_it != elem_end; ++elem_it)
    {
      Elem* elem = *elem_it;
      libmesh_assert(elem);

      libmesh_assert_not_equal_to (elem->processor_id(), DofObject::invalid_processor_id);

      // For each node, set the processor ID to the min of
      // its current value and this Element's processor id.
      //
      // TODO: we would probably get better parallel partitioning if
      // we did something like "min for even numbered nodes, max for
      // odd numbered".  We'd need to be careful about how that would
      // affect solution ordering for I/O, though.
      for (unsigned int n=0; n<elem->n_nodes(); ++n)
        elem->get_node(n)->processor_id() = std::min(elem->get_node(n)->processor_id(),
                                                     elem->processor_id());
    }

  // And loop over the subactive elements, but don't reassign
  // nodes that are already active on another processor.
  MeshBase::element_iterator       sub_it  = mesh.subactive_elements_begin();
  const MeshBase::element_iterator sub_end = mesh.subactive_elements_end();

  for ( ; sub_it != sub_end; ++sub_it)
    {
      Elem* elem = *sub_it;
      libmesh_assert(elem);

      libmesh_assert_not_equal_to (elem->processor_id(), DofObject::invalid_processor_id);

      for (unsigned int n=0; n<elem->n_nodes(); ++n)
        if (elem->get_node(n)->processor_id() == DofObject::invalid_processor_id)
          elem->get_node(n)->processor_id() = elem->processor_id();
    }

  // Same for the inactive elements -- we will have already gotten most of these
  // nodes, *except* for the case of a parent with a subset of children which are
  // ghost elements.  In that case some of the parent nodes will not have been
  // properly handled yet
  MeshBase::element_iterator       not_it  = mesh.not_active_elements_begin();
  const MeshBase::element_iterator not_end = mesh.not_active_elements_end();

  for ( ; not_it != not_end; ++not_it)
    {
      Elem* elem = *not_it;
      libmesh_assert(elem);

      libmesh_assert_not_equal_to (elem->processor_id(), DofObject::invalid_processor_id);

      for (unsigned int n=0; n<elem->n_nodes(); ++n)
        if (elem->get_node(n)->processor_id() == DofObject::invalid_processor_id)
          elem->get_node(n)->processor_id() = elem->processor_id();
    }

  // We can't assert that all nodes are connected to elements, because
  // a ParallelMesh with NodeConstraints might have pulled in some
  // remote nodes solely for evaluating those constraints.
  // MeshTools::libmesh_assert_connected_nodes(mesh);

  // For such nodes, we'll do a sanity check later when making sure
  // that we successfully reset their processor ids to something
  // valid.

  // Next set node ids from other processors, excluding self
  for (processor_id_type p=1; p != libMesh::n_processors(); ++p)
    {
      // Trade my requests with processor procup and procdown
      processor_id_type procup = (libMesh::processor_id() + p) %
                                  libMesh::n_processors();
      processor_id_type procdown = (libMesh::n_processors() +
                                    libMesh::processor_id() - p) %
                                    libMesh::n_processors();
      std::vector<dof_id_type> request_to_fill;
      CommWorld.send_receive(procup, requested_node_ids[procup],
                             procdown, request_to_fill);

      // Fill those requests in-place
      for (std::size_t i=0; i != request_to_fill.size(); ++i)
        {
          Node *node = mesh.node_ptr(request_to_fill[i]);
          libmesh_assert(node);
          const processor_id_type new_pid = node->processor_id();
          libmesh_assert_not_equal_to (new_pid, DofObject::invalid_processor_id);
          libmesh_assert_less (new_pid, mesh.n_partitions()); // this is the correct test --
          request_to_fill[i] = new_pid;           //  the number of partitions may
        }                                         //  not equal the number of processors

      // Trade back the results
      std::vector<dof_id_type> filled_request;
      CommWorld.send_receive(procdown, request_to_fill,
                             procup,   filled_request);
      libmesh_assert_equal_to (filled_request.size(), requested_node_ids[procup].size());

      // And copy the id changes we've now been informed of
      for (std::size_t i=0; i != filled_request.size(); ++i)
        {
          Node *node = mesh.node_ptr(requested_node_ids[procup][i]);
          libmesh_assert(node);
          libmesh_assert_less (filled_request[i], mesh.n_partitions()); // this is the correct test --
          node->processor_id(filled_request[i]);           //  the number of partitions may
        }                                                  //  not equal the number of processors
    }

#ifdef DEBUG
  MeshTools::libmesh_assert_valid_procids<Node>(mesh);
#endif

  STOP_LOG("set_node_processor_ids()","Partitioner");
}

static void libMesh::Partitioner::set_parent_processor_ids

(

MeshBase &

mesh

)

[static]

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.

Referenced by partition(), and repartition().

void libMesh::Partitioner::single_partition

(

MeshBase &

mesh

)

[protected]

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.

Definition at line 145 of file partitioner.C.

References libMesh::MeshBase::elements_begin(), libMesh::MeshBase::elements_end(), libMesh::MeshBase::nodes_begin(), and libMesh::MeshBase::nodes_end().

Referenced by libMesh::SFCPartitioner::_do_partition(), libMesh::MetisPartitioner::_do_partition(), libMesh::LinearPartitioner::_do_partition(), libMesh::CentroidPartitioner::_do_partition(), libMesh::ParmetisPartitioner::_do_repartition(), partition(), and repartition().

{
  START_LOG("single_partition()","Partitioner");

  // Loop over all the elements and assign them to processor 0.
  MeshBase::element_iterator       elem_it  = mesh.elements_begin();
  const MeshBase::element_iterator elem_end = mesh.elements_end();

  for ( ; elem_it != elem_end; ++elem_it)
    (*elem_it)->processor_id() = 0;

  // For a single partition, all the nodes are on processor 0
  MeshBase::node_iterator       node_it  = mesh.nodes_begin();
  const MeshBase::node_iterator node_end = mesh.nodes_end();

  for ( ; node_it != node_end; ++node_it)
    (*node_it)->processor_id() = 0;

  STOP_LOG("single_partition()","Partitioner");
}

---

Member Data Documentation

ErrorVector* libMesh::Partitioner::_weights [protected]

The weights that might be used for partitioning.

Definition at line 155 of file partitioner.h.

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

const dof_id_type libMesh::Partitioner::communication_blocksize = 1000000 [static, protected]

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 150 of file partitioner.h.

---

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

• partitioner.h
• partitioner.C