1 // The libMesh Finite Element Library. 2 // Copyright (C) 2002-2020 Benjamin S. Kirk, John W. Peterson, Roy H. Stogner 3 4 // This library is free software; you can redistribute it and/or 5 // modify it under the terms of the GNU Lesser General Public 6 // License as published by the Free Software Foundation; either 7 // version 2.1 of the License, or (at your option) any later version. 8 9 // This library is distributed in the hope that it will be useful, 10 // but WITHOUT ANY WARRANTY; without even the implied warranty of 11 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU 12 // Lesser General Public License for more details. 13 14 // You should have received a copy of the GNU Lesser General Public 15 // License along with this library; if not, write to the Free Software 16 // Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA 17 18 19 20 #ifndef LIBMESH_PARTITIONER_H 21 #define LIBMESH_PARTITIONER_H 22 23 // Local Includes 24 #include "libmesh/libmesh.h" 25 #include "libmesh/id_types.h" 26 #include "libmesh/mesh_base.h" // for MeshBase::element_iterator 27 28 // C++ Includes 29 #include <cstddef> 30 #include <memory> 31 #include <unordered_map> 32 #include <queue> 33 34 namespace libMesh 35 { 36 37 // Forward Declarations 38 class ErrorVector; 39 40 /** 41 * The \p Partitioner class provides a uniform interface for 42 * partitioning algorithms. It takes a reference to a \p MeshBase 43 * object as input, which it will partition into a number of 44 * subdomains. 45 * 46 * \author Benjamin S. Kirk 47 * \date 2003 48 * \brief Base class for all concrete Partitioner instantiations. 49 */ 50 class Partitioner 51 { 52 public: 53 54 /** 55 * Constructor. 56 */ Partitioner()57 Partitioner () : _weights(nullptr) {} 58 59 /** 60 * Copy/move ctor, copy/move assignment operator, and destructor are 61 * all explicitly defaulted for this class. 62 */ 63 Partitioner (const Partitioner &) = default; 64 Partitioner (Partitioner &&) = default; 65 Partitioner & operator= (const Partitioner &) = default; 66 Partitioner & operator= (Partitioner &&) = default; 67 virtual ~Partitioner() = default; 68 69 /** 70 * \returns A copy of this partitioner wrapped in a smart pointer. 71 * 72 * This is used when copying meshes, and must be overridden in the 73 * derived classes. 74 */ 75 virtual std::unique_ptr<Partitioner> clone () const = 0; 76 77 /** 78 * Partitions the \p MeshBase into \p n parts by setting 79 * processor_id() on Nodes and Elems. 80 * 81 * \note If you are implementing a new type of Partitioner, you most 82 * likely do \e not want to override the partition() function, see 83 * instead the protected virtual _do_partition() method below. The 84 * partition() function is responsible for doing a lot of 85 * libmesh-internals-specific setup and finalization before and 86 * after the _do_partition() function is called. The only 87 * responsibility of the _do_partition() function, on the other 88 * hand, is to set the processor IDs of the elements according to a 89 * specific partitioning algorithm. See, e.g. MetisPartitioner for 90 * an example. 91 */ 92 virtual void partition (MeshBase & mesh, 93 const unsigned int n); 94 95 /** 96 * Partitions the \p MeshBase into \p mesh.n_processors() by setting 97 * processor_id() on Nodes and Elems. 98 * 99 * \note If you are implementing a new type of Partitioner, you most 100 * likely do \e not want to override the partition() function, see 101 * instead the protected virtual _do_partition() method below. The 102 * partition() function is responsible for doing a lot of 103 * libmesh-internals-specific setup and finalization before and 104 * after the _do_partition() function is called. The only 105 * responsibility of the _do_partition() function, on the other 106 * hand, is to set the processor IDs of the elements according to a 107 * specific partitioning algorithm. See, e.g. MetisPartitioner for 108 * an example. 109 */ 110 virtual void partition (MeshBase & mesh); 111 112 /** 113 * Partitions elements in the range (it, end) into n parts. 114 * The mesh from which the iterators are created must also be passed 115 * in, since it is a parallel object and has other useful 116 * information in it. 117 * 118 * Although partition_range() is part of the public Partitioner 119 * interface, it should not generally be called by applications. 120 * Its main purpose is to support the SubdomainPartitioner, which 121 * uses it internally to individually partition ranges of elements 122 * before combining them into the final partitioning. Most of the 123 * time, the protected _do_partition() function is implemented in 124 * terms of partition_range() by passing a range which includes all 125 * the elements of the Mesh. 126 */ partition_range(MeshBase &,MeshBase::element_iterator,MeshBase::element_iterator,const unsigned int)127 virtual void partition_range (MeshBase & /*mesh*/, 128 MeshBase::element_iterator /*beg*/, 129 MeshBase::element_iterator /*end*/, 130 const unsigned int /*n_parts*/) 131 { libmesh_not_implemented(); } 132 133 /** 134 * Repartitions the \p MeshBase into \p n parts. (Some partitioning 135 * algorithms can repartition more efficiently than computing a new 136 * partitioning from scratch.) The default behavior is to simply 137 * call this->partition(mesh,n). 138 */ 139 void repartition (MeshBase & mesh, 140 const unsigned int n); 141 142 /** 143 * Repartitions the \p MeshBase into \p mesh.n_processors() parts. This 144 * is required since some partitioning algorithms can repartition 145 * more efficiently than computing a new partitioning from scratch. 146 */ 147 void repartition (MeshBase & mesh); 148 149 /** 150 * These functions assign processor IDs to newly-created elements 151 * (in parallel) which are currently assigned to processor 0. 152 */ 153 static void partition_unpartitioned_elements (MeshBase & mesh); 154 155 static void partition_unpartitioned_elements (MeshBase & mesh, 156 const unsigned int n); 157 158 /** 159 * This function is called after partitioning to set the processor IDs 160 * for the inactive parent elements. A parent's processor ID is the same 161 * as its first child. 162 */ 163 static void set_parent_processor_ids(MeshBase & mesh); 164 165 /** 166 * This function is called after partitioning to set the processor IDs 167 * for the nodes. By definition, a Node's processor ID is the minimum 168 * processor ID for all of the elements which share the node. 169 */ 170 static void set_node_processor_ids(MeshBase & mesh); 171 172 /** 173 * On the partitioning interface, a surface is shared by two and only two processors. 174 * Try to find which pair of processors corresponds to which surfaces, and store their 175 * nodes. 176 */ 177 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); 178 179 /** 180 * Nodes on the partitioning interface is linearly assigned to 181 * each pair of processors 182 */ 183 static void set_interface_node_processor_ids_linear(MeshBase & mesh); 184 185 /** 186 * Nodes on the partitioning interface is clustered into two groups BFS (Breadth First Search)scheme 187 * for per pair of processors 188 */ 189 static void set_interface_node_processor_ids_BFS(MeshBase & mesh); 190 191 192 /** 193 * Nodes on the partitioning interface is partitioned into two groups using a PETSc partitioner 194 * for each pair of processors 195 */ 196 static void set_interface_node_processor_ids_petscpartitioner(MeshBase & mesh); 197 198 /** 199 * Attach weights that can be used for partitioning. This ErrorVector should be 200 * _exactly_ the same on every processor and should have mesh->max_elem_id() 201 * entries. 202 */ attach_weights(ErrorVector *)203 virtual void attach_weights(ErrorVector * /*weights*/) { libmesh_not_implemented(); } 204 205 protected: 206 207 /** 208 * Trivially "partitions" the mesh for one processor. 209 * Simply loops through the elements and assigns all of them 210 * to processor 0. Is is provided as a separate function 211 * so that derived classes may use it without reimplementing it. 212 */ 213 void single_partition (MeshBase & mesh); 214 215 /** 216 * Slightly generalized version of single_partition which acts on a 217 * range of elements defined by the pair of iterators (it, end). 218 */ 219 void single_partition_range(MeshBase::element_iterator it, 220 MeshBase::element_iterator end); 221 222 /** 223 * This is the actual partitioning method which must be overridden 224 * in derived classes. It is called via the public partition() 225 * method above by the user. 226 */ 227 virtual void _do_partition(MeshBase & mesh, 228 const unsigned int n) = 0; 229 230 /** 231 * This is the actual re-partitioning method which can be overridden 232 * in derived classes. 233 * 234 * \note The default behavior is to simply call the partition 235 * function. 236 */ _do_repartition(MeshBase & mesh,const unsigned int n)237 virtual void _do_repartition (MeshBase & mesh, 238 const unsigned int n) { this->_do_partition (mesh, n); } 239 240 /** 241 * The blocksize to use when doing blocked parallel communication. This limits the 242 * maximum vector size which can be used in a single communication step. 243 */ 244 static const dof_id_type communication_blocksize; 245 246 /** 247 * Construct contiguous global indices for the current partitioning. The global indices 248 * are ordered part-by-part 249 */ 250 virtual void _find_global_index_by_pid_map(const MeshBase & mesh); 251 252 253 /** 254 * Build a dual graph for partitioner 255 * 256 */ 257 virtual void build_graph(const MeshBase & mesh); 258 259 /** 260 * Assign the computed partitioning to the mesh. 261 */ 262 void assign_partitioning (const MeshBase & mesh, const std::vector<dof_id_type> & parts); 263 264 /** 265 * The weights that might be used for partitioning. 266 */ 267 ErrorVector * _weights; 268 269 /** 270 * Maps active element ids into a contiguous range, as needed by parallel partitioner. 271 */ 272 std::unordered_map<dof_id_type, dof_id_type> _global_index_by_pid_map; 273 274 /** 275 * The number of active elements on each processor. 276 * 277 * \note ParMETIS requires that each processor have some active 278 * elements; it will abort if any processor passes a nullptr _part 279 * array. 280 */ 281 std::vector<dof_id_type> _n_active_elem_on_proc; 282 283 /** 284 * A dual graph corresponds to the mesh, and it is typically used 285 * in paritioner. A vertex represents an element, and its neighbors are the 286 * element neighbors. 287 */ 288 std::vector<std::vector<dof_id_type>> _dual_graph; 289 290 291 std::vector<Elem *> _local_id_to_elem; 292 }; 293 294 } // namespace libMesh 295 296 #endif // LIBMESH_PARTITIONER_H 297