Zoltan2
Zoltan2_AlgZoltan.hpp
Go to the documentation of this file.
1 // @HEADER
2 //
3 // ***********************************************************************
4 //
5 // Zoltan2: A package of combinatorial algorithms for scientific computing
6 // Copyright 2012 Sandia Corporation
7 //
8 // Under the terms of Contract DE-AC04-94AL85000 with Sandia Corporation,
9 // the U.S. Government retains certain rights in this software.
10 //
11 // Redistribution and use in source and binary forms, with or without
12 // modification, are permitted provided that the following conditions are
13 // met:
14 //
15 // 1. Redistributions of source code must retain the above copyright
16 // notice, this list of conditions and the following disclaimer.
17 //
18 // 2. Redistributions in binary form must reproduce the above copyright
19 // notice, this list of conditions and the following disclaimer in the
20 // documentation and/or other materials provided with the distribution.
21 //
22 // 3. Neither the name of the Corporation nor the names of the
23 // contributors may be used to endorse or promote products derived from
24 // this software without specific prior written permission.
25 //
26 // THIS SOFTWARE IS PROVIDED BY SANDIA CORPORATION "AS IS" AND ANY
27 // EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
28 // IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
29 // PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL SANDIA CORPORATION OR THE
30 // CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
31 // EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
32 // PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
33 // PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
34 // LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
35 // NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
36 // SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
37 //
38 // Questions? Contact Karen Devine (kddevin@sandia.gov)
39 // Erik Boman (egboman@sandia.gov)
40 // Siva Rajamanickam (srajama@sandia.gov)
41 //
42 // ***********************************************************************
43 //
44 // @HEADER
45 #ifndef _ZOLTAN2_ALGZOLTAN_HPP_
46 #define _ZOLTAN2_ALGZOLTAN_HPP_
47 
48 #include <Zoltan2_Standards.hpp>
49 #include <Zoltan2_Algorithm.hpp>
51 #include <Zoltan2_Util.hpp>
52 #include <Zoltan2_TPLTraits.hpp>
53 
54 #include <Zoltan2_Model.hpp>
55 
57 #include <zoltan_cpp.h>
58 
62 //
63 // This first design templates Zoltan's callback functions on the
64 // input adapter. This approach has the advantage of simplicity and
65 // is most similar to current usage of Zoltan (where the callbacks define
66 // the model).
67 // A better approach might template them on a model,
68 // allowing Zoltan2 greater flexibility in creating models from the input.
69 // Alternatively, different callback implementations could be provided to
70 // represent different models to Zoltan.
72 
73 namespace Zoltan2 {
74 
75 template <typename Adapter>
76 class AlgZoltan : public Algorithm<Adapter>
77 {
78 
79 private:
80 
81  typedef typename Adapter::lno_t lno_t;
82  typedef typename Adapter::gno_t gno_t;
83  typedef typename Adapter::scalar_t scalar_t;
84  typedef typename Adapter::part_t part_t;
85  typedef typename Adapter::user_t user_t;
86  typedef typename Adapter::userCoord_t userCoord_t;
87 
88  const RCP<const Environment> env;
89  const RCP<const Comm<int> > problemComm;
90  const RCP<const typename Adapter::base_adapter_t> adapter;
91  RCP<const Model<Adapter> > model;
92  RCP<Zoltan> zz;
93 
94  MPI_Comm mpicomm;
95 
96  void setMPIComm(const RCP<const Comm<int> > &problemComm__) {
97 # ifdef HAVE_ZOLTAN2_MPI
98  mpicomm = Teuchos::getRawMpiComm(*problemComm__);
99 # else
100  mpicomm = MPI_COMM_WORLD; // taken from siMPI
101 # endif
102  }
103 
104  void zoltanInit() {
105  // call Zoltan_Initialize to make sure MPI_Init is called (in MPI or siMPI).
106  int argc = 0;
107  char **argv = NULL;
108  float ver;
109  Zoltan_Initialize(argc, argv, &ver);
110  }
111 
112  void setCallbacksIDs()
113  {
114  zz->Set_Num_Obj_Fn(zoltanNumObj<Adapter>, (void *) &(*adapter));
115  zz->Set_Obj_List_Fn(zoltanObjList<Adapter>, (void *) &(*adapter));
116 
117  const part_t *myparts;
118  adapter->getPartsView(myparts);
119  if (myparts != NULL)
120  zz->Set_Part_Multi_Fn(zoltanParts<Adapter>, (void *) &(*adapter));
121 
122  char tmp[4];
123  sprintf(tmp, "%d", TPL_Traits<ZOLTAN_ID_PTR, gno_t>::NUM_ID);
124  zz->Set_Param("NUM_GID_ENTRIES", tmp);
125  sprintf(tmp, "%d", TPL_Traits<ZOLTAN_ID_PTR, lno_t>::NUM_ID);
126  zz->Set_Param("NUM_LID_ENTRIES", tmp);
127  }
128 
129  template <typename AdapterWithCoords>
130  void setCallbacksGeom(const AdapterWithCoords *ia)
131  {
132  // Coordinates may be provided by the MeshAdapter or VectorAdapter.
133  // VectorAdapter may be provided directly by user or indirectly through
134  // GraphAdapter or MatrixAdapter. So separate template type is needed.
135  zz->Set_Num_Geom_Fn(zoltanNumGeom<AdapterWithCoords>, (void *) ia);
136  zz->Set_Geom_Multi_Fn(zoltanGeom<AdapterWithCoords>, (void *) ia);
137  }
138 
139  void setCallbacksGraph(
140  const RCP<const GraphAdapter<user_t,userCoord_t> > &adp)
141  {
142  // std::cout << "NotReadyForGraphYet" << std::endl;
143  // TODO
144  }
145 
146  void setCallbacksGraph(
147  const RCP<const MatrixAdapter<user_t,userCoord_t> > &adp)
148  {
149  // std::cout << "NotReadyForGraphYet" << std::endl;
150  // TODO
151  }
152 
153  void setCallbacksGraph(
154  const RCP<const MeshAdapter<user_t> > &adp)
155  {
156  // std::cout << "NotReadyForGraphYet" << std::endl;
157  // TODO
158  }
159 
160  void setCallbacksHypergraph(
161  const RCP<const MatrixAdapter<user_t,userCoord_t> > &adp)
162  {
163  // TODO: If add parameter list to this function, can register
164  // TODO: different callbacks depending on the hypergraph model to use
165 
166  zz->Set_HG_Size_CS_Fn(zoltanHGSizeCS_withMatrixAdapter<Adapter>,
167  (void *) &(*adp));
168  zz->Set_HG_CS_Fn(zoltanHGCS_withMatrixAdapter<Adapter>,
169  (void *) &(*adp));
170 
171  // zz->Set_HG_Size_Edge_Wts_Fn(zoltanHGSizeEdgeWts_withMatrixAdapter<Adapter>,
172  // (void *) &(*adapter));
173  // zz->Set_HG_Edge_Wts_Fn(zoltanHGSizeEdgeWts_withMatrixAdapter<Adapter>,
174  // (void *) &(*adapter));
175  }
176 
177  void setCallbacksHypergraph(const RCP<const MeshAdapter<user_t> > &adp)
178  {
179 
180  const Teuchos::ParameterList &pl = env->getParameters();
181 
182  const Teuchos::ParameterEntry *pe = pl.getEntryPtr("hypergraph_model_type");
183  std::string model_type("traditional");
184  if (pe){
185  model_type = pe->getValue<std::string>(&model_type);
186  }
187 
188  if (model_type=="ghosting" ||
189  !adp->areEntityIDsUnique(adp->getPrimaryEntityType())) {
190  Zoltan2::modelFlag_t flags;
192  problemComm, flags,
194  model = rcp(static_cast<const Model<Adapter>* >(mdl),true);
195 
196  zz->Set_Num_Obj_Fn(zoltanHGNumObj_withModel<Adapter>, (void *) &(*mdl));
197  zz->Set_Obj_List_Fn(zoltanHGObjList_withModel<Adapter>, (void *) &(*mdl));
198 
199  zz->Set_HG_Size_CS_Fn(zoltanHGSizeCS_withModel<Adapter>, (void *) &(*mdl));
200  zz->Set_HG_CS_Fn(zoltanHGCS_withModel<Adapter>, (void *) &(*mdl));
201  }
202  else {
203  //If entities are unique we dont need the extra cost of the model
204  zz->Set_HG_Size_CS_Fn(zoltanHGSizeCS_withMeshAdapter<Adapter>,
205  (void *) &(*adp));
206  zz->Set_HG_CS_Fn(zoltanHGCS_withMeshAdapter<Adapter>,
207  (void *) &(*adp));
208  }
209  // zz->Set_HG_Size_Edge_Wts_Fn(zoltanHGSizeEdgeWts_withMeshAdapter<Adapter>,
210  // (void *) &(*adp));
211  // zz->Set_HG_Edge_Wts_Fn(zoltanHGSizeEdgeWts_withMeshAdapter<Adapter>,
212  // (void *) &(*adp));
213  }
214 
215 public:
216 
222  AlgZoltan(const RCP<const Environment> &env__,
223  const RCP<const Comm<int> > &problemComm__,
224  const RCP<const IdentifierAdapter<user_t> > &adapter__):
225  env(env__), problemComm(problemComm__), adapter(adapter__)
226  {
227  setMPIComm(problemComm__);
228  zoltanInit();
229  zz = rcp(new Zoltan(mpicomm));
230  setCallbacksIDs();
231  }
232 
233  AlgZoltan(const RCP<const Environment> &env__,
234  const RCP<const Comm<int> > &problemComm__,
235  const RCP<const VectorAdapter<user_t> > &adapter__) :
236  env(env__), problemComm(problemComm__), adapter(adapter__)
237  {
238  setMPIComm(problemComm__);
239  zoltanInit();
240  zz = rcp(new Zoltan(mpicomm));
241  setCallbacksIDs();
242  setCallbacksGeom(&(*adapter));
243  }
244 
245  AlgZoltan(const RCP<const Environment> &env__,
246  const RCP<const Comm<int> > &problemComm__,
247  const RCP<const GraphAdapter<user_t,userCoord_t> > &adapter__) :
248  env(env__), problemComm(problemComm__), adapter(adapter__)
249  {
250  setMPIComm(problemComm__);
251  zoltanInit();
252  zz = rcp(new Zoltan(mpicomm));
253  setCallbacksIDs();
254  setCallbacksGraph(adapter);
255  if (adapter->coordinatesAvailable()) {
256  setCallbacksGeom(adapter->getCoordinateInput());
257  }
258  }
259 
260  AlgZoltan(const RCP<const Environment> &env__,
261  const RCP<const Comm<int> > &problemComm__,
262  const RCP<const MatrixAdapter<user_t,userCoord_t> > &adapter__) :
263  env(env__), problemComm(problemComm__), adapter(adapter__)
264  {
265  setMPIComm(problemComm__);
266  zoltanInit();
267  zz = rcp(new Zoltan(mpicomm));
268  setCallbacksIDs();
269  setCallbacksGraph(adapter);
270  setCallbacksHypergraph(adapter);
271  if (adapter->coordinatesAvailable()) {
272  setCallbacksGeom(adapter->getCoordinateInput());
273  }
274  }
275 
276  AlgZoltan(const RCP<const Environment> &env__,
277  const RCP<const Comm<int> > &problemComm__,
278  const RCP<const MeshAdapter<user_t> > &adapter__) :
279  env(env__), problemComm(problemComm__), adapter(adapter__)
280  {
281  setMPIComm(problemComm__);
282  zoltanInit();
283  zz = rcp(new Zoltan(mpicomm));
284  setCallbacksIDs();
285  setCallbacksGraph(adapter);
286  //TODO:: check parameter list to see if hypergraph is needed. We dont want to build the model
287  // if we don't have to and we shouldn't as it can take a decent amount of time if the
288  // primary entity is copied
289  setCallbacksHypergraph(adapter);
290  setCallbacksGeom(&(*adapter));
291  }
292 
293  void partition(const RCP<PartitioningSolution<Adapter> > &solution);
294  // void color(const RCP<ColoringSolution<Adapter> > &solution);
295 
296 };
297 
299 template <typename Adapter>
301  const RCP<PartitioningSolution<Adapter> > &solution
302 )
303 {
304  HELLO;
305  char paramstr[128];
306 
307  size_t numGlobalParts = solution->getTargetGlobalNumberOfParts();
308 
309  sprintf(paramstr, "%lu", numGlobalParts);
310  zz->Set_Param("NUM_GLOBAL_PARTS", paramstr);
311 
312  int wdim = adapter->getNumWeightsPerID();
313  sprintf(paramstr, "%d", wdim);
314  zz->Set_Param("OBJ_WEIGHT_DIM", paramstr);
315 
316  const Teuchos::ParameterList &pl = env->getParameters();
317 
318  double tolerance;
319  const Teuchos::ParameterEntry *pe = pl.getEntryPtr("imbalance_tolerance");
320  if (pe){
321  char str[30];
322  tolerance = pe->getValue<double>(&tolerance);
323  sprintf(str, "%f", tolerance);
324  zz->Set_Param("IMBALANCE_TOL", str);
325  }
326 
327  pe = pl.getEntryPtr("partitioning_approach");
328  if (pe){
329  std::string approach;
330  approach = pe->getValue<std::string>(&approach);
331  if (approach == "partition")
332  zz->Set_Param("LB_APPROACH", "PARTITION");
333  else
334  zz->Set_Param("LB_APPROACH", "REPARTITION");
335  }
336 
337  pe = pl.getEntryPtr("partitioning_objective");
338  if (pe){
339  std::string strChoice = pe->getValue<std::string>(&strChoice);
340  if (strChoice == std::string("multicriteria_minimize_total_weight"))
341  zz->Set_Param("RCB_MULTICRITERIA_NORM", "1");
342  else if (strChoice == std::string("multicriteria_balance_total_maximum"))
343  zz->Set_Param("RCB_MULTICRITERIA_NORM", "2");
344  else if (strChoice == std::string("multicriteria_minimize_maximum_weight"))
345  zz->Set_Param("RCB_MULTICRITERIA_NORM", "3");
346  }
347 
348  pe = pl.getEntryPtr("rectilinear");
349  if (pe) {
350  bool val = pe->getValue(&val);
351  if (val)
352  zz->Set_Param("RCB_RECTILINEAR_BLOCKS", "1");
353  }
354 
355  // Look for zoltan_parameters sublist; pass all zoltan parameters to Zoltan
356  try {
357  const Teuchos::ParameterList &zpl = pl.sublist("zoltan_parameters");
358  for (ParameterList::ConstIterator iter = zpl.begin();
359  iter != zpl.end(); iter++) {
360  const std::string &zname = pl.name(iter);
361  // Convert the value to a string to pass to Zoltan
362  std::string zval = pl.entry(iter).getValue(&zval);
363  zz->Set_Param(zname.c_str(), zval.c_str());
364  }
365  }
366  catch (std::exception &e) {
367  // No zoltan_parameters sublist found; no Zoltan parameters to register
368  }
369 
370  // Get target part sizes
371  int pdim = (wdim > 1 ? wdim : 1);
372  for (int d = 0; d < pdim; d++) {
373  if (!solution->criteriaHasUniformPartSizes(d)) {
374  float *partsizes = new float[numGlobalParts];
375  int *partidx = new int[numGlobalParts];
376  int *wgtidx = new int[numGlobalParts];
377  for (size_t i=0; i<numGlobalParts; i++) partidx[i] = i;
378  for (size_t i=0; i<numGlobalParts; i++) wgtidx[i] = d;
379  for (size_t i=0; i<numGlobalParts; i++)
380  partsizes[i] = solution->getCriteriaPartSize(0, i);
381  zz->LB_Set_Part_Sizes(1, numGlobalParts, partidx, wgtidx, partsizes);
382  delete [] partsizes;
383  delete [] partidx;
384  delete [] wgtidx;
385  }
386  }
387 
388  // Make the call to LB_Partition
389  int changed = 0;
392 
393  int nDummy = -1; // Dummy vars to satisfy arglist
394  ZOLTAN_ID_PTR dGids = NULL, dLids = NULL;
395  int *dProcs = NULL, *dParts = NULL;
396  int nObj = -1; // Output vars with new part info
397  ZOLTAN_ID_PTR oGids = NULL, oLids = NULL;
398  int *oProcs = NULL, *oParts = NULL;
399 
400  zz->Set_Param("RETURN_LISTS", "PARTS"); // required format for Zoltan2;
401  // results in last five arguments
402 
403  int ierr = zz->LB_Partition(changed, nGidEnt, nLidEnt,
404  nDummy, dGids, dLids, dProcs, dParts,
405  nObj, oGids, oLids, oProcs, oParts);
406 
407  env->globalInputAssertion(__FILE__, __LINE__, "Zoltan LB_Partition",
408  (ierr==ZOLTAN_OK || ierr==ZOLTAN_WARN), BASIC_ASSERTION, problemComm);
409 
410  int numObjects=nObj;
411  // The number of objects may be larger than zoltan knows due to copies that
412  // were removed by the hypergraph model
413  if (model!=RCP<const Model<Adapter> >() &&
414  dynamic_cast<const HyperGraphModel<Adapter>* >(&(*model)) &&
415  !(dynamic_cast<const HyperGraphModel<Adapter>* >(&(*model))->areVertexIDsUnique())) {
416  numObjects=model->getLocalNumObjects();
417  }
418 
419  // Load answer into the solution.
420  ArrayRCP<part_t> partList(new part_t[numObjects], 0, numObjects, true);
421  for (int i = 0; i < nObj; i++) {
422  lno_t tmp;
423  TPL_Traits<lno_t, ZOLTAN_ID_PTR>::ASSIGN(tmp, &(oLids[i*nLidEnt]));
424  partList[tmp] = oParts[i];
425  }
426 
427  if (model!=RCP<const Model<Adapter> >() &&
428  dynamic_cast<const HyperGraphModel<Adapter>* >(&(*model)) &&
429  !(dynamic_cast<const HyperGraphModel<Adapter>* >(&(*model))->areVertexIDsUnique())) {
430  // Setup the part ids for copied entities removed by ownership in
431  // hypergraph model.
432  const HyperGraphModel<Adapter>* mdl =
433  static_cast<const HyperGraphModel<Adapter>* >(&(*model));
434 
435  typedef typename HyperGraphModel<Adapter>::map_t map_t;
436  Teuchos::RCP<const map_t> mapWithCopies;
437  Teuchos::RCP<const map_t> oneToOneMap;
438  mdl->getVertexMaps(mapWithCopies,oneToOneMap);
439 
440  typedef Tpetra::Vector<scalar_t, lno_t, gno_t> vector_t;
441  vector_t vecWithCopies(mapWithCopies);
442  vector_t oneToOneVec(oneToOneMap);
443 
444  // Set values in oneToOneVec: each entry == rank
445  assert(nObj == lno_t(oneToOneMap->getNodeNumElements()));
446  for (lno_t i = 0; i < nObj; i++)
447  oneToOneVec.replaceLocalValue(i, oParts[i]);
448 
449  // Now import oneToOneVec's values back to vecWithCopies
450  Teuchos::RCP<const Tpetra::Import<lno_t, gno_t> > importer =
451  Tpetra::createImport<lno_t, gno_t>(oneToOneMap, mapWithCopies);
452  vecWithCopies.doImport(oneToOneVec, *importer, Tpetra::REPLACE);
453 
454  // Should see copied vector values when print VEC WITH COPIES
455  lno_t nlocal = lno_t(mapWithCopies->getNodeNumElements());
456  for (lno_t i = 0; i < nlocal; i++)
457  partList[i] = vecWithCopies.getData()[i];
458  }
459 
460  solution->setParts(partList);
461 
462  // Clean up
463  zz->LB_Free_Part(&oGids, &oLids, &oProcs, &oParts);
464 }
465 
466 } // namespace Zoltan2
467 
468 #endif
AlgZoltan(const RCP< const Environment > &env__, const RCP< const Comm< int > > &problemComm__, const RCP< const VectorAdapter< user_t > > &adapter__)
#define HELLO
IdentifierAdapter defines the interface for identifiers.
fast typical checks for valid arguments
MatrixAdapter defines the adapter interface for matrices.
Defines the Model interface.
AlgZoltan(const RCP< const Environment > &env__, const RCP< const Comm< int > > &problemComm__, const RCP< const MatrixAdapter< user_t, userCoord_t > > &adapter__)
GraphAdapter defines the interface for graph-based user data.
MeshAdapter defines the interface for mesh input.
std::bitset< NUM_MODEL_FLAGS > modelFlag_t
Defines the PartitioningSolution class.
void partition(const RCP< PartitioningSolution< Adapter > > &solution)
Partitioning method.
callback functions for the Zoltan package (templated on Adapter)
A PartitioningSolution is a solution to a partitioning problem.
VectorAdapter defines the interface for vector input.
AlgZoltan(const RCP< const Environment > &env__, const RCP< const Comm< int > > &problemComm__, const RCP< const MeshAdapter< user_t > > &adapter__)
Algorithm defines the base class for all algorithms.
static void ASSIGN(first_t &a, second_t b)
Traits class to handle conversions between gno_t/lno_t and TPL data types (e.g., ParMETIS&#39;s idx_t...
Gathering definitions used in software development.
void getVertexMaps(Teuchos::RCP< const map_t > &copiesMap, Teuchos::RCP< const map_t > &onetooneMap) const
Sets pointers to the vertex map with copies and the vertex map without copies Note: the pointers will...
The base class for all model classes.
AlgZoltan(const RCP< const Environment > &env__, const RCP< const Comm< int > > &problemComm__, const RCP< const GraphAdapter< user_t, userCoord_t > > &adapter__)
A gathering of useful namespace methods.
HyperGraphModel defines the interface required for hyper graph models.
AlgZoltan(const RCP< const Environment > &env__, const RCP< const Comm< int > > &problemComm__, const RCP< const IdentifierAdapter< user_t > > &adapter__)