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 
328  // Look for zoltan_parameters sublist; pass all zoltan parameters to Zoltan
329  try {
330  const Teuchos::ParameterList &zpl = pl.sublist("zoltan_parameters");
331  for (ParameterList::ConstIterator iter = zpl.begin();
332  iter != zpl.end(); iter++) {
333  const std::string &zname = pl.name(iter);
334  // Convert the value to a string to pass to Zoltan
335  std::string zval = pl.entry(iter).getValue(&zval);
336  zz->Set_Param(zname.c_str(), zval.c_str());
337  }
338  }
339  catch (std::exception &e) {
340  // No zoltan_parameters sublist found; no Zoltan parameters to register
341  }
342 
343  // Get target part sizes
344  int pdim = (wdim > 1 ? wdim : 1);
345  for (int d = 0; d < pdim; d++) {
346  if (!solution->criteriaHasUniformPartSizes(d)) {
347  float *partsizes = new float[numGlobalParts];
348  int *partidx = new int[numGlobalParts];
349  int *wgtidx = new int[numGlobalParts];
350  for (size_t i=0; i<numGlobalParts; i++) partidx[i] = i;
351  for (size_t i=0; i<numGlobalParts; i++) wgtidx[i] = d;
352  for (size_t i=0; i<numGlobalParts; i++)
353  partsizes[i] = solution->getCriteriaPartSize(0, i);
354  zz->LB_Set_Part_Sizes(1, numGlobalParts, partidx, wgtidx, partsizes);
355  delete [] partsizes;
356  delete [] partidx;
357  delete [] wgtidx;
358  }
359  }
360 
361  // Make the call to LB_Partition
362  int changed = 0;
365 
366  int nDummy = -1; // Dummy vars to satisfy arglist
367  ZOLTAN_ID_PTR dGids = NULL, dLids = NULL;
368  int *dProcs = NULL, *dParts = NULL;
369  int nObj = -1; // Output vars with new part info
370  ZOLTAN_ID_PTR oGids = NULL, oLids = NULL;
371  int *oProcs = NULL, *oParts = NULL;
372 
373  zz->Set_Param("RETURN_LISTS", "PARTS"); // required format for Zoltan2;
374  // results in last five arguments
375 
376  int ierr = zz->LB_Partition(changed, nGidEnt, nLidEnt,
377  nDummy, dGids, dLids, dProcs, dParts,
378  nObj, oGids, oLids, oProcs, oParts);
379 
380  env->globalInputAssertion(__FILE__, __LINE__, "Zoltan LB_Partition",
381  (ierr==ZOLTAN_OK || ierr==ZOLTAN_WARN), BASIC_ASSERTION, problemComm);
382 
383  int numObjects=nObj;
384  // The number of objects may be larger than zoltan knows due to copies that
385  // were removed by the hypergraph model
386  if (model!=RCP<const Model<Adapter> >() &&
387  dynamic_cast<const HyperGraphModel<Adapter>* >(&(*model)) &&
388  !(dynamic_cast<const HyperGraphModel<Adapter>* >(&(*model))->areVertexIDsUnique())) {
389  numObjects=model->getLocalNumObjects();
390  }
391 
392  // Load answer into the solution.
393  ArrayRCP<part_t> partList(new part_t[numObjects], 0, numObjects, true);
394  for (int i = 0; i < nObj; i++) {
395  lno_t tmp;
396  TPL_Traits<lno_t, ZOLTAN_ID_PTR>::ASSIGN_TPL_T(tmp, &(oLids[i*nLidEnt]));
397  partList[tmp] = oParts[i];
398  }
399 
400  if (model!=RCP<const Model<Adapter> >() &&
401  dynamic_cast<const HyperGraphModel<Adapter>* >(&(*model)) &&
402  !(dynamic_cast<const HyperGraphModel<Adapter>* >(&(*model))->areVertexIDsUnique())) {
403  // Setup the part ids for copied entities removed by ownership in
404  // hypergraph model.
405  const HyperGraphModel<Adapter>* mdl =
406  static_cast<const HyperGraphModel<Adapter>* >(&(*model));
407 
408  typedef typename HyperGraphModel<Adapter>::map_t map_t;
409  Teuchos::RCP<const map_t> mapWithCopies;
410  Teuchos::RCP<const map_t> oneToOneMap;
411  mdl->getVertexMaps(mapWithCopies,oneToOneMap);
412 
413  typedef Tpetra::Vector<scalar_t, lno_t, gno_t> vector_t;
414  vector_t vecWithCopies(mapWithCopies);
415  vector_t oneToOneVec(oneToOneMap);
416 
417  // Set values in oneToOneVec: each entry == rank
418  assert(nObj == lno_t(oneToOneMap->getNodeNumElements()));
419  for (lno_t i = 0; i < nObj; i++)
420  oneToOneVec.replaceLocalValue(i, oParts[i]);
421 
422  // Now import oneToOneVec's values back to vecWithCopies
423  Teuchos::RCP<const Tpetra::Import<lno_t, gno_t> > importer =
424  Tpetra::createImport<lno_t, gno_t>(oneToOneMap, mapWithCopies);
425  vecWithCopies.doImport(oneToOneVec, *importer, Tpetra::REPLACE);
426 
427  // Should see copied vector values when print VEC WITH COPIES
428  lno_t nlocal = lno_t(mapWithCopies->getNodeNumElements());
429  for (lno_t i = 0; i < nlocal; i++)
430  partList[i] = vecWithCopies.getData()[i];
431  }
432 
433  solution->setParts(partList);
434 
435  // Clean up
436  zz->LB_Free_Part(&oGids, &oLids, &oProcs, &oParts);
437 }
438 
439 } // namespace Zoltan2
440 
441 #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.
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.
static void ASSIGN_TPL_T(tpl_t &a, zno_t b)
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.
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...
AlgZoltan(const RCP< const Environment > &env__, const RCP< const Comm< int > > &problemComm__, const RCP< const IdentifierAdapter< user_t > > &adapter__)