LifeV
MeshPartitionTool.hpp
Go to the documentation of this file.
1 //@HEADER
2 /*
3 *******************************************************************************
4 
5 Copyright (C) 2004, 2005, 2007 EPFL, Politecnico di Milano, INRIA
6 Copyright (C) 2010, 2011, 2012 EPFL, Politecnico di Milano, Emory University
7 
8 This file is part of LifeV.
9 
10 LifeV is free software; you can redistribute it and/or modify
11 it under the terms of the GNU Lesser General Public License as published by
12 the Free Software Foundation, either version 3 of the License, or
13 (at your option) any later version.
14 
15 LifeV is distributed in the hope that it will be useful,
16 but WITHOUT ANY WARRANTY; without even the implied warranty of
17 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
18 Lesser General Public License for more details.
19 
20 You should have received a copy of the GNU Lesser General Public License
21 along with LifeV. If not, see <http://www.gnu.org/licenses/>.
22 
23 *******************************************************************************
24 */
25 //@HEADER
26 
27 /*!
28  @file
29  @brief Class that does flexible mesh partitioning
30 
31  @date 16-11-2011
32  @author Radu Popescu <radu.popescu@epfl.ch>
33 
34  @maintainer Radu Popescu <radu.popescu@epfl.ch>
35 */
36 
37 #ifndef MESH_PARTITION_TOOL_H
38 #define MESH_PARTITION_TOOL_H 1
39 
40 #include <fstream>
41 #include <iostream>
42 #include <set>
43 #include <sstream>
44 #include <string>
45 #include <vector>
46 
47 #include <boost/shared_ptr.hpp>
48 #include <Epetra_MpiComm.h>
49 #include <Teuchos_ParameterList.hpp>
50 
51 #include <lifev/core/LifeV.hpp>
52 #include <lifev/core/fem/DOF.hpp>
53 #include <lifev/core/mesh/RegionMesh.hpp>
54 #include <lifev/core/mesh/GraphCutterParMETIS.hpp>
55 #include <lifev/core/mesh/GraphCutterZoltan.hpp>
56 #include <lifev/core/mesh/GraphUtil.hpp>
57 #include <lifev/core/mesh/MeshPartBuilder.hpp>
58 
59 namespace LifeV
60 {
61 
62 using namespace GraphUtil;
63 
64 /*!
65  @brief Class that does flexible mesh partitioning
66  @author Radu Popescu radu.popescu@epfl.ch
67 
68  This class implements the partitioning of a global mesh and allows choosing
69  the graph partitioning tool and the method to build the mesh parts.
70 
71  The class is configured through the Teuchos::Parameter list passed to the
72  constructor. The following parameters are used:
73 
74  graph-lib - std::string - "parmetis" or "zoltan" selects the graph partition
75  library to be used (default "parmetis")
76  overlap - UInt - level of overlap for the mesh partition process (default 0)
77  offline-mode - bool - mode of operation; offline mode can
78  only be used in serial (default false == online)
79  num-parts - Int - (for offline-mode only) sets the number of parts for the
80  mesh partition process (no default value)
81  hierarchical - bool - enable hierarchical partitioning mode (default false)
82  topology - std::string - value which represents the number of mesh parts per
83  compute node
84  (N == num-parts; topology="m"; N % m == 0)
85  (default "1")
86 
87  Notes:
88 
89  * The value of the "topology" parameter is given as a string due to a
90  requirement of the Zoltan interface
91  * When using Zoltan as a graph partition library, additional advanced
92  parameters are available. See GraphCutterZoltan.hpp for more information.
93  * Hierarchical partitioning is available in online mode ONLY when using
94  Zoltan and in offline mode ONLY when using ParMETIS.
95 
96 
97 */
98 template < typename MeshType>
100 {
101 public:
102  //! @name Public Types
103  //@{
104  typedef MeshType mesh_Type;
113  //@}
114 
115  //! \name Constructors & Destructors
116  //@{
117  //! Constructor
118  /*!
119  * The constructor takes as parameters the global uncut mesh, the Epetra
120  * comm of the group or processes involved in the mesh partition process
121  * and a Teuchos parameter list.
122  *
123  * After initializing the object, the constructor will call the private
124  * run() method and perform the mesh partition
125  *
126  * \param mesh - shared pointer to the global uncut mesh
127  * \param comm - shared pointer to the Epetra comm object containing the
128  * processes involved in the mesh partition process
129  * \param parameters - Teuchos parameter list
130  */
131  MeshPartitionTool (const meshPtr_Type& mesh,
132  const std::shared_ptr<Epetra_Comm>& comm,
133  const Teuchos::ParameterList parameters
134  = Teuchos::ParameterList() );
135 
136  //! Empty destructor
138  //@}
139 
140  //! \name Public Methods
141  //! Prints information about the state (data) of the object
142  void showMe (std::ostream& output = std::cout) const;
143  //@}
144 
145  //! \name Get Methods
146  //@{
147  //! Return the succeess state of the partitioning (true || false)
148  bool success() const
149  {
150  return M_success;
151  }
152  //! Return a shared pointer to the mesh part (online mode, const ver.)
153  const meshPtr_Type& meshPart() const
154  {
155  return M_meshPart;
156  }
157  //! Return a shared pointer to the mesh parts
158  /*!
159  * Return a shared pointer to the mesh parts on offline partition (const)
160  */
162  {
163  return M_allMeshParts;
164  }
165 
166  //! Return a shared pointer to the second stage graph parts (for ShyLU-MT)
167  /*!
168  * Return a shared pointer to the second stage graph parts (for ShyLU-MT)
169  * Offline mode
170  */
172  {
173  return M_secondStageParts;
174  }
175 
176  //! Return a shared pointer to the second stage graph parts (for ShyLU-MT)
177  /*!
178  * Return a shared pointer to the second stage graph parts (for ShyLU-MT)
179  * Online mode
180  */
182  {
183  return M_secondStageParts->at (0);
184  }
185  //@}
186 
187 private:
188  //! \name Private methods
189  //@{
190  //! This method performs all the steps for the mesh and graph partitioning
191  void run();
192 
193  //! Initialize M_entityPID
194  void fillEntityPID (idTablePtr_Type graph);
195 
196  //! Global to local element ID conversion for second stage
197  void globalToLocal (const Int curPart);
198  //@}
199 
200  // Private copy constructor and assignment operator are disabled
203 
204  //! Private Data Members
205  //@{
212  std::string M_graphLib;
215  bool M_success;
219 
220  //! Store ownership for each entity, subdivided by entity type
222 
223  //@}
224 }; // class MeshPartitionToolOnline
225 
226 //
227 // IMPLEMENTATION
228 //
229 
230 // =================================
231 // Constructors and destructor
232 // =================================
233 
234 template < typename MeshType>
236  const meshPtr_Type& mesh,
237  const std::shared_ptr<Epetra_Comm>& comm,
238  const Teuchos::ParameterList parameters) :
239  M_comm (comm),
240  M_myPID (M_comm->MyPID() ),
242  M_originalMesh (mesh),
243  M_meshPart(),
244  M_allMeshParts(),
245  M_graphLib (M_parameters.get<std::string> ("graph-lib", "parmetis") ),
247  M_parameters.get<UInt> ("overlap", 0), M_comm) ),
248  M_success (false),
249  M_secondStage (M_parameters.get<bool> ("second-stage", false) ),
250  M_secondStageNumParts (M_parameters.get<Int> ("second-stage-num-parts", 1) ),
252 {
253  if (! M_graphLib.compare ("parmetis") )
254  {
255  M_graphCutter.reset (new GraphCutterParMETIS<mesh_Type> (M_originalMesh, M_comm, M_parameters) );
256  }
257  else if (! M_graphLib.compare ("zoltan") )
258  {
259  M_graphCutter.reset (new GraphCutterZoltan<mesh_Type> (M_originalMesh, M_comm, M_parameters) );
260  }
261  else
262  {
263  std::cout << "Graph partitioner type not defined.\n";
264  }
265 
266  run();
267 }
268 
269 // =================================
270 // Public methods
271 // =================================
272 
273 template < typename MeshType>
274 void MeshPartitionTool < MeshType >::run()
275 {
276  if (!M_myPID)
277  {
278  std::cout << "Partitioning mesh graph ..." << std::endl;
279  }
280  // If the graph partitioning failed, just abort the mesh partitioning.
281  // MeshPartitionTool::success() will return false.
282  if (M_graphCutter->run() )
283  {
284  return;
285  }
286 
287  // Extract the graph from the graphCutter
288  idTablePtr_Type graph = M_graphCutter->getGraph();
289 
290  // Dispose of the graph partitioner object
291  M_graphCutter.reset();
292 
293  // Get the current operation mode and number of parts
294  bool offlineMode = M_parameters.get<bool> ("offline-mode", false);
295 
296  // Do a second stage graph partitioning for ShyLU-MT
297  if (M_secondStage)
298  {
299  if (!M_myPID)
300  {
301  std::cout << "Performing second stage partitioning ..."
302  << std::endl;
303  }
304  // MPI comm object for second stage is always MPI_COMM_SELF
305 #ifdef EPETRA_MPI
306  std::shared_ptr<Epetra_Comm>
307  secondStageComm (new Epetra_MpiComm (MPI_COMM_SELF) );
308 #else
309  std::shared_ptr<Epetra_Comm>
310  secondStageComm (new Epetra_SerialComm);
311 #endif
312 
313  Teuchos::ParameterList secondStageParams;
314  secondStageParams.set<Int> ("num-parts", M_secondStageNumParts);
315  secondStageParams.set<Int> ("my-pid", M_myPID);
316  secondStageParams.set<bool> ("verbose", false);
317  if (! offlineMode)
318  {
319  M_secondStageParts->resize (1);
320  // For each set of elements in graph perform a second stage partitioning
321  const idListPtr_Type currentIds = graph->at (M_myPID);
322  partitionGraphParMETIS (currentIds, *M_originalMesh,
323  secondStageParams,
324  M_secondStageParts->at (0),
325  secondStageComm);
326  }
327  else
328  {
329  M_secondStageParts->resize (graph->size() );
330  // For each set of elements in graph perform a second stage partitioning
331  for (size_t i = 0; i < graph->size(); ++i)
332  {
333  const idListPtr_Type& currentIds = graph->at (i);
334  partitionGraphParMETIS (currentIds, *M_originalMesh,
335  secondStageParams,
336  M_secondStageParts->at (i),
337  secondStageComm);
338  }
339  }
340  }
341 
342  // Fill entity PID
343  if (!M_myPID)
344  {
345  std::cout << "Filling entity PID lists ..." << std::endl;
346  }
347  fillEntityPID (graph);
348 
349  if (!M_myPID)
350  {
351  std::cout << "Building mesh parts ..." << std::endl;
352  }
353 
354  if (! offlineMode)
355  {
356  // Online partitioning
357  M_meshPart.reset (new mesh_Type (M_comm) );
358  M_meshPart->setIsPartitioned (true);
359  M_meshPartBuilder->run (M_meshPart, graph, M_entityPID, M_myPID);
360 
361  // Make the global to local element ID conversion for the second stage
362  if (M_secondStage)
363  {
364  globalToLocal (0);
365  }
366 
367  // Reset the mesh part builder
368  M_meshPartBuilder->reset();
369 
370  // Mark the partition as successful
371  M_success = true;
372  }
373  else
374  {
375  // Offline partitioning
376  if (M_comm->NumProc() != 1)
377  {
378  if (!M_myPID)
379  {
380  std::cout << "Offline partition must be done in serial."
381  << std::endl;
382  }
383  }
384  else
385  {
386  /*
387  * In offline partitioning mode, with overlap, we must make sure
388  * that each time the M_meshPartBuilder is run, which modifies the
389  * partition graph, it modifies the original graph, not the
390  * augmented graph from the previous part.
391  */
392 
393  Int numParts = M_parameters.get<Int> ("num-parts");
394  M_allMeshParts.reset (new partMesh_Type (numParts) );
395  for (Int curPart = 0; curPart < numParts; ++curPart)
396  {
397  // Backup the elements of the current graph part
398  idList_Type backup ( * (graph->at (curPart) ) );
399  M_allMeshParts->at (curPart).reset (new mesh_Type);
400  M_allMeshParts->at (curPart)->setIsPartitioned (true);
401  M_meshPartBuilder->run (M_allMeshParts->at (curPart),
402  graph, M_entityPID,
403  curPart);
404 
405  // At this point (*graph)[curPart] has been modified. Restore
406  // to the original state
407  * (graph->at (curPart) ) = backup;
408 
409  // Make the global to local element ID conversion for the second stage
410  if (M_secondStage)
411  {
412  globalToLocal (curPart);
413  }
414 
415  // Reset the mesh part builder
416  M_meshPartBuilder->reset();
417 
418  // Mark the partition as successful
419  M_success = true;
420  }
421  }
422  }
423 
424  if (!M_myPID)
425  {
426  std::cout << "Mesh partition complete." << std::endl;
427  }
428  // Destroy the mesh part builder to clear memory
429  M_meshPartBuilder.reset();
430  // Release the pointer to the original uncut mesh
431  M_originalMesh.reset();
432 }
433 
434 template<typename MeshType>
435 void
436 MeshPartitionTool<MeshType>::fillEntityPID (idTablePtr_Type graph)
437 {
438  Int numParts = graph->size();
439 
440  // initialize entity PIDs to 0
441  M_entityPID.points.resize ( M_originalMesh->numPoints(), 0 );
442  M_entityPID.elements.resize ( M_originalMesh->numElements(), 0 );
443  M_entityPID.facets.resize ( M_originalMesh->numFacets(), 0 );
444  M_entityPID.ridges.resize ( M_originalMesh->numRidges(), 0 );
445 
446  // check: parallel algorithm seems to be slower for this
447  // p = 0 can be skipped since M_entityPID is already initialized at that value
448  for ( Int p = 1; p < numParts; p++ )
449  {
450  for ( UInt e = 0; e < graph->at (p)->size(); e++ )
451  {
452  // point block
453  for ( UInt k = 0; k < mesh_Type::element_Type::S_numPoints; k++ )
454  {
455  const ID& pointID = M_originalMesh->element ( graph->at (p)->at (e) ).point ( k ).id();
456  // pointPID should be the maximum between the procs that own it
457  M_entityPID.points[ pointID ] = std::max ( M_entityPID.points[ pointID ], p );
458  }
459 
460  // elem block
461  const ID& elemID = M_originalMesh->element ( graph->at (p)->at (e) ).id();
462  // at his stage each element belongs to a single partition, overlap is not yet done.
463  M_entityPID.elements[ elemID ] = p;
464 
465  // facet block
466  for ( UInt k = 0; k < mesh_Type::element_Type::S_numFacets; k++ )
467  {
468  const ID& facetID = M_originalMesh->facet ( M_originalMesh->localFacetId ( elemID, k ) ).id();
469  // facetPID should be the maximum between the proc that own it
470  M_entityPID.facets[ facetID ] = std::max ( M_entityPID.facets[ facetID ], p );
471  }
472 
473  // ridge block
474  for ( UInt k = 0; k < mesh_Type::element_Type::S_numRidges; k++ )
475  {
476  const ID& ridgeID = M_originalMesh->ridge ( M_originalMesh->localRidgeId ( elemID, k ) ).id();
477  // ridgePID should be the maximum between the proc that own it
478  M_entityPID.ridges[ ridgeID ] = std::max ( M_entityPID.ridges[ ridgeID ], p );
479  }
480  }
481  }
482 }
483 
484 template < typename MeshType>
485 void
486 MeshPartitionTool < MeshType >::globalToLocal (const Int curPart)
487 {
488  const std::map<Int, Int>& globalToLocalMap =
489  M_meshPartBuilder->globalToLocalElement();
490  idTable_Type& currentGraph = * (M_secondStageParts->at (curPart) );
491 
492  for (size_t i = 0; i < currentGraph.size(); ++i)
493  {
494  int currentSize = currentGraph[i]->size();
495  idList_Type& currentElements = * (currentGraph[i]);
496  for (Int j = 0; j < currentSize; ++j)
497  {
498  currentElements[j] = globalToLocalMap.find (currentElements[j])->second;
499  }
500  }
501 }
502 
503 template < typename MeshType>
504 void
505 MeshPartitionTool < MeshType >::showMe (std::ostream& output) const
506 {
507  output << "Sorry, this method is not implemented, yet." << std::endl
508  << "We appreciate your interest." << std::endl
509  << "Check back in a bit!" << std::endl;
510 }
511 
512 } // namespace LifeV
513 
514 #endif // MESH_PARTITION_TOOL_H
std::shared_ptr< vertexPartitionTable_Type > vertexPartitionTablePtr_Type
MeshPartBuilder< mesh_Type > meshPartBuilder_Type
GraphCutterBase< mesh_Type > graphCutter_Type
Class that does flexible mesh partitioning.
std::shared_ptr< partMesh_Type > partMeshPtr_Type
Graph cutter base class (abstract)
int32_type Int
Generic integer data.
Definition: LifeV.hpp:188
MeshPartitionTool(const MeshPartitionTool &)
MeshPartitionTool(const meshPtr_Type &mesh, const std::shared_ptr< Epetra_Comm > &comm, const Teuchos::ParameterList parameters=Teuchos::ParameterList())
Constructor.
const idTablePtr_Type & mySecondStageParts() const
Return a shared pointer to the second stage graph parts (for ShyLU-MT)
std::vector< LifeV::Int > idList_Type
Definition: GraphUtil.hpp:60
MeshPartitionTool & operator=(const MeshPartitionTool &)
Teuchos::ParameterList M_parameters
bool success() const
Return the succeess state of the partitioning (true || false)
std::shared_ptr< Epetra_Comm > M_comm
Private Data Members.
void run()
This method performs all the steps for the mesh and graph partitioning.
void fillEntityPID(idTablePtr_Type graph)
Initialize M_entityPID.
void showMe(std::ostream &output=std::cout) const
std::shared_ptr< graphCutter_Type > M_graphCutter
std::vector< idTablePtr_Type > vertexPartitionTable_Type
const partMeshPtr_Type & allMeshParts() const
Return a shared pointer to the mesh parts.
void globalToLocal(const Int curPart)
Global to local element ID conversion for second stage.
const meshPtr_Type & meshPart() const
Return a shared pointer to the mesh part (online mode, const ver.)
vertexPartitionTablePtr_Type M_secondStageParts
const vertexPartitionTablePtr_Type & secondStageParts() const
Return a shared pointer to the second stage graph parts (for ShyLU-MT)
std::shared_ptr< meshPartBuilder_Type > M_meshPartBuilder
Class that builds a mesh part, after the graph has been partitioned.
std::vector< meshPtr_Type > partMesh_Type
~MeshPartitionTool()
Empty destructor.
std::shared_ptr< idTable_Type > idTablePtr_Type
Definition: GraphUtil.hpp:63
meshPartBuilder_Type::entityPID_Type M_entityPID
Store ownership for each entity, subdivided by entity type.
std::shared_ptr< mesh_Type > meshPtr_Type