Zoltan2
Zoltan2_PartitioningProblem.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 
50 #ifndef _ZOLTAN2_PARTITIONINGPROBLEM_HPP_
51 #define _ZOLTAN2_PARTITIONINGPROBLEM_HPP_
52 
53 #include <Zoltan2_Problem.hpp>
57 #include <Zoltan2_GraphModel.hpp>
62 #ifdef ZOLTAN2_TASKMAPPING_MOVE
63 #include <Zoltan2_TaskMapping.hpp>
64 #endif
65 
66 #ifndef _WIN32
67 #include <unistd.h>
68 #else
69 #include <process.h>
70 #define NOMINMAX
71 #include <windows.h>
72 #endif
73 
74 #ifdef HAVE_ZOLTAN2_OVIS
75 #include <ovis.h>
76 #endif
77 
78 namespace Zoltan2{
79 
103 template<typename Adapter>
104 class PartitioningProblem : public Problem<Adapter>
105 {
106 public:
107 
108  typedef typename Adapter::scalar_t scalar_t;
109  typedef typename Adapter::gno_t gno_t;
110  typedef typename Adapter::lno_t lno_t;
111  typedef typename Adapter::part_t part_t;
112  typedef typename Adapter::user_t user_t;
114 
115 #ifdef HAVE_ZOLTAN2_MPI
116  typedef Teuchos::OpaqueWrapper<MPI_Comm> mpiWrapper_t;
119  PartitioningProblem(Adapter *A, ParameterList *p, MPI_Comm comm):
120  Problem<Adapter>(A,p,comm), solution_(),
121  inputType_(InvalidAdapterType),
122  graphFlags_(), idFlags_(), coordFlags_(), algName_(),
123  numberOfWeights_(), partIds_(), partSizes_(),
124  numberOfCriteria_(), levelNumberParts_(), hierarchical_(false)
125  {
126  for(int i=0;i<MAX_NUM_MODEL_TYPES;i++) modelAvail_[i]=false;
127  initializeProblem();
128  }
129 #endif
130 
132  PartitioningProblem(Adapter *A, ParameterList *p):
133  Problem<Adapter>(A,p), solution_(),
134  inputType_(InvalidAdapterType),
135  graphFlags_(), idFlags_(), coordFlags_(), algName_(),
136  numberOfWeights_(),
137  partIds_(), partSizes_(), numberOfCriteria_(),
138  levelNumberParts_(), hierarchical_(false)
139  {
140  for(int i=0;i<MAX_NUM_MODEL_TYPES;i++) modelAvail_[i]=false;
141  initializeProblem();
142  }
143 
145  PartitioningProblem(Adapter *A, ParameterList *p,
146  const RCP<const Teuchos::Comm<int> > &comm):
147  Problem<Adapter>(A,p,comm), solution_(),
148  inputType_(InvalidAdapterType),
149  graphFlags_(), idFlags_(), coordFlags_(), algName_(),
150  numberOfWeights_(),
151  partIds_(), partSizes_(), numberOfCriteria_(),
152  levelNumberParts_(), hierarchical_(false)
153  {
154  for(int i=0;i<MAX_NUM_MODEL_TYPES;i++) modelAvail_[i]=false;
155  initializeProblem();
156  }
157 
161 
163  //
164  // \param updateInputData If true this indicates that either
165  // this is the first attempt at solution, or that we
166  // are computing a new solution and the input data has
167  // changed since the previous solution was computed.
168  // By input data we mean coordinates, topology, or weights.
169  // If false, this indicates that we are computing a
170  // new solution using the same input data was used for
171  // the previous solution, even though the parameters
172  // may have been changed.
173  //
174  // For the sake of performance, we ask the caller to set \c updateInputData
175  // to false if he/she is computing a new solution using the same input data,
176  // but different problem parameters, than that which was used to compute
177  // the most recent solution.
178 
179  void solve(bool updateInputData=true );
180 
182  //
183  // \return a reference to the solution to the most recent solve().
184 
186  return *(solution_.getRawPtr());
187  };
188 
227  void setPartSizes(int len, part_t *partIds, scalar_t *partSizes,
228  bool makeCopy=true)
229  {
230  setPartSizesForCriteria(0, len, partIds, partSizes, makeCopy);
231  }
232 
267  void setPartSizesForCriteria(int criteria, int len, part_t *partIds,
268  scalar_t *partSizes, bool makeCopy=true) ;
269 /*
270  void setMachine(MachineRepresentation<typename Adapter::base_adapter_t::scalar_t> *machine);
271 */
272 
275  static void getValidParameters(ParameterList & pl)
276  {
282 
283  // This set up does not use tuple because we didn't have constructors
284  // that took that many elements - Tuple will need to be modified and I
285  // didn't want to have low level changes with this particular refactor
286  // TO DO: Add more Tuple constructors and then redo this code to be
287  // Teuchos::tuple<std::string> algorithm_names( "rcb", "multijagged" ... );
288  Array<std::string> algorithm_names(17);
289  algorithm_names[0] = "rcb";
290  algorithm_names[1] = "multijagged";
291  algorithm_names[2] = "rib";
292  algorithm_names[3] = "hsfc";
293  algorithm_names[4] = "patoh";
294  algorithm_names[5] = "phg";
295  algorithm_names[6] = "metis";
296  algorithm_names[7] = "parmetis";
297  algorithm_names[8] = "pulp";
298  algorithm_names[9] = "parma";
299  algorithm_names[10] = "scotch";
300  algorithm_names[11] = "ptscotch";
301  algorithm_names[12] = "block";
302  algorithm_names[13] = "cyclic";
303  algorithm_names[14] = "random";
304  algorithm_names[15] = "zoltan";
305  algorithm_names[16] = "forTestingOnly";
306  RCP<Teuchos::StringValidator> algorithm_Validator = Teuchos::rcp(
307  new Teuchos::StringValidator( algorithm_names ));
308  pl.set("algorithm", "random", "partitioning algorithm",
309  algorithm_Validator);
310 
311  // bool parameter
312  pl.set("rectilinear", false, "If true, then when a cut is made, all of the "
313  "dots located on the cut are moved to the same side of the cut. The "
314  "resulting regions are then rectilinear. The resulting load balance may "
315  "not be as good as when the group of dots is split by the cut. ",
317 
318  RCP<Teuchos::StringValidator> partitioning_objective_Validator =
319  Teuchos::rcp( new Teuchos::StringValidator(
320  Teuchos::tuple<std::string>( "balance_object_count",
321  "balance_object_weight", "multicriteria_minimize_total_weight",
322  "multicriteria_minimize_maximum_weight",
323  "multicriteria_balance_total_maximum", "minimize_cut_edge_count",
324  "minimize_cut_edge_weight", "minimize_neighboring_parts",
325  "minimize_boundary_vertices" )));
326  pl.set("partitioning_objective", "balance_object_weight",
327  "objective of partitioning", partitioning_objective_Validator);
328 
329  pl.set("imbalance_tolerance", 1.1, "imbalance tolerance, ratio of "
330  "maximum load over average load", Environment::getAnyDoubleValidator());
331 
332  // num_global_parts >= 1
333  RCP<Teuchos::EnhancedNumberValidator<int>> num_global_parts_Validator =
334  Teuchos::rcp( new Teuchos::EnhancedNumberValidator<int>(
335  1, Teuchos::EnhancedNumberTraits<int>::max()) ); // no maximum
336  pl.set("num_global_parts", 1, "global number of parts to compute "
337  "(0 means use the number of processes)", num_global_parts_Validator);
338 
339  // num_local_parts >= 0
340  RCP<Teuchos::EnhancedNumberValidator<int>> num_local_parts_Validator =
341  Teuchos::rcp( new Teuchos::EnhancedNumberValidator<int>(
342  0, Teuchos::EnhancedNumberTraits<int>::max()) ); // no maximum
343  pl.set("num_local_parts", 0, "number of parts to compute for this "
344  "process (0 means one)", num_local_parts_Validator);
345 
346  RCP<Teuchos::StringValidator> partitioning_approach_Validator =
347  Teuchos::rcp( new Teuchos::StringValidator(
348  Teuchos::tuple<std::string>( "partition", "repartition",
349  "maximize_overlap" )));
350  pl.set("partitioning_approach", "partition", "Partition from scratch, "
351  "partition incrementally from current partition, of partition from "
352  "scratch but maximize overlap with the current partition",
353  partitioning_approach_Validator);
354 
355  RCP<Teuchos::StringValidator> objects_to_partition_Validator =
356  Teuchos::rcp( new Teuchos::StringValidator(
357  Teuchos::tuple<std::string>( "matrix_rows", "matrix_columns",
358  "matrix_nonzeros", "mesh_elements", "mesh_nodes", "graph_edges",
359  "graph_vertices", "coordinates", "identifiers" )));
360  pl.set("objects_to_partition", "graph_vertices", "Objects to be partitioned",
361  objects_to_partition_Validator);
362 
363  RCP<Teuchos::StringValidator> model_Validator = Teuchos::rcp(
364  new Teuchos::StringValidator(
365  Teuchos::tuple<std::string>( "hypergraph", "graph",
366  "geometry", "ids" )));
367  pl.set("model", "graph", "This is a low level parameter. Normally the "
368  "library will choose a computational model based on the algorithm or "
369  "objective specified by the user.", model_Validator);
370 
371  // bool parameter
372  pl.set("remap_parts", false, "remap part numbers to minimize migration "
373  "between old and new partitions", Environment::getBoolValidator() );
374 
375  pl.set("mapping_type", -1, "Mapping of solution to the processors. -1 No"
376  " Mapping, 0 coordinate mapping.", Environment::getAnyIntValidator());
377 
378  RCP<Teuchos::EnhancedNumberValidator<int>> ghost_layers_Validator =
379  Teuchos::rcp( new Teuchos::EnhancedNumberValidator<int>(1, 10, 1, 0) );
380  pl.set("ghost_layers", 2, "number of layers for ghosting used in "
381  "hypergraph ghost method", ghost_layers_Validator);
382  }
383 
384 private:
385  void initializeProblem();
386 
387  void createPartitioningProblem(bool newData);
388 
389  RCP<PartitioningSolution<Adapter> > solution_;
390 #ifdef ZOLTAN2_TASKMAPPING_MOVE
391  RCP<MachineRepresentation<scalar_t,part_t> > machine_;
392 #endif
393 
394  BaseAdapterType inputType_;
395 
396  //ModelType modelType_;
397  bool modelAvail_[MAX_NUM_MODEL_TYPES];
398 
399  modelFlag_t graphFlags_;
400  modelFlag_t idFlags_;
401  modelFlag_t coordFlags_;
402  std::string algName_;
403 
404  int numberOfWeights_;
405 
406  // Suppose Array<part_t> partIds = partIds_[w]. If partIds.size() > 0
407  // then the user supplied part sizes for weight index "w", and the sizes
408  // corresponding to the Ids in partIds are partSizes[w].
409  //
410  // If numberOfWeights_ >= 0, then there is an Id and Sizes array for
411  // for each weight. Otherwise the user did not supply object weights,
412  // but they can still specify part sizes.
413  // So numberOfCriteria_ is numberOfWeights_ or one, whichever is greater.
414 
415  ArrayRCP<ArrayRCP<part_t> > partIds_;
416  ArrayRCP<ArrayRCP<scalar_t> > partSizes_;
417  int numberOfCriteria_;
418 
419  // Number of parts to be computed at each level in hierarchical partitioning.
420 
421  ArrayRCP<int> levelNumberParts_;
422  bool hierarchical_;
423 };
425 
426 /*
427 template <typename Adapter>
428 void PartitioningProblem<Adapter>::setMachine(MachineRepresentation<typename Adapter::base_adapter_t::scalar_t> *machine){
429  this->machine_ = RCP<MachineRepresentation<typename Adapter::base_adapter_t::scalar_t> > (machine, false);
430 }
431 */
432 
433 
434 template <typename Adapter>
435  void PartitioningProblem<Adapter>::initializeProblem()
436 {
437  HELLO;
438 
439  this->env_->debug(DETAILED_STATUS, "PartitioningProblem::initializeProblem");
440 
441  if (getenv("DEBUGME")){
442 #ifndef _WIN32
443  std::cout << getpid() << std::endl;
444  sleep(15);
445 #else
446  std::cout << _getpid() << std::endl;
447  Sleep(15000);
448 #endif
449  }
450 
451 #ifdef HAVE_ZOLTAN2_OVIS
452  ovis_enabled(this->comm_->getRank());
453 #endif
454 
455  // Create a copy of the user's communicator.
456 
457 #ifdef ZOLTAN2_TASKMAPPING_MOVE
458  machine_ = RCP<MachineRepresentation<scalar_t,part_t> >(
459  new MachineRepresentation<scalar_t,part_t>(*(this->comm_)));
460 #endif
461 
462  // Number of criteria is number of user supplied weights if non-zero.
463  // Otherwise it is 1 and uniform weight is implied.
464 
465  numberOfWeights_ = this->inputAdapter_->getNumWeightsPerID();
466 
467  numberOfCriteria_ = (numberOfWeights_ > 1) ? numberOfWeights_ : 1;
468 
469  inputType_ = this->inputAdapter_->adapterType();
470 
471  // The Caller can specify part sizes in setPartSizes(). If he/she
472  // does not, the part size arrays are empty.
473 
474  ArrayRCP<part_t> *noIds = new ArrayRCP<part_t> [numberOfCriteria_];
475  ArrayRCP<scalar_t> *noSizes = new ArrayRCP<scalar_t> [numberOfCriteria_];
476 
477  partIds_ = arcp(noIds, 0, numberOfCriteria_, true);
478  partSizes_ = arcp(noSizes, 0, numberOfCriteria_, true);
479 
480  if (this->env_->getDebugLevel() >= DETAILED_STATUS){
481  std::ostringstream msg;
482  msg << this->comm_->getSize() << " procs,"
483  << numberOfWeights_ << " user-defined weights\n";
484  this->env_->debug(DETAILED_STATUS, msg.str());
485  }
486 
487  this->env_->memory("After initializeProblem");
488 }
489 
490 template <typename Adapter>
492  int criteria, int len, part_t *partIds, scalar_t *partSizes, bool makeCopy)
493 {
494  this->env_->localInputAssertion(__FILE__, __LINE__, "invalid length",
495  len>= 0, BASIC_ASSERTION);
496 
497  this->env_->localInputAssertion(__FILE__, __LINE__, "invalid criteria",
498  criteria >= 0 && criteria < numberOfCriteria_, BASIC_ASSERTION);
499 
500  if (len == 0){
501  partIds_[criteria] = ArrayRCP<part_t>();
502  partSizes_[criteria] = ArrayRCP<scalar_t>();
503  return;
504  }
505 
506  this->env_->localInputAssertion(__FILE__, __LINE__, "invalid arrays",
507  partIds && partSizes, BASIC_ASSERTION);
508 
509  // The global validity of the partIds and partSizes arrays is performed
510  // by the PartitioningSolution, which computes global part distribution and
511  // part sizes.
512 
513  part_t *z2_partIds = NULL;
514  scalar_t *z2_partSizes = NULL;
515  bool own_memory = false;
516 
517  if (makeCopy){
518  z2_partIds = new part_t [len];
519  z2_partSizes = new scalar_t [len];
520  this->env_->localMemoryAssertion(__FILE__, __LINE__, len, z2_partSizes);
521  memcpy(z2_partIds, partIds, len * sizeof(part_t));
522  memcpy(z2_partSizes, partSizes, len * sizeof(scalar_t));
523  own_memory=true;
524  }
525  else{
526  z2_partIds = partIds;
527  z2_partSizes = partSizes;
528  }
529 
530  partIds_[criteria] = arcp(z2_partIds, 0, len, own_memory);
531  partSizes_[criteria] = arcp(z2_partSizes, 0, len, own_memory);
532 }
533 
534 template <typename Adapter>
535 void PartitioningProblem<Adapter>::solve(bool updateInputData)
536 {
537  this->env_->debug(DETAILED_STATUS, "Entering solve");
538 
539  // Create the computational model.
540 
541  this->env_->timerStart(MACRO_TIMERS, "create problem");
542 
543  createPartitioningProblem(updateInputData);
544 
545  this->env_->timerStop(MACRO_TIMERS, "create problem");
546 
547  // TODO: If hierarchical_
548 
549  // Create the solution. The algorithm will query the Solution
550  // for part and weight information. The algorithm will
551  // update the solution with part assignments and quality metrics.
552 
553  // Create the algorithm
554  try {
555  if (algName_ == std::string("multijagged")) {
556  this->algorithm_ = rcp(new Zoltan2_AlgMJ<Adapter>(this->envConst_,
557  this->comm_,
558  this->coordinateModel_));
559  }
560  else if (algName_ == std::string("zoltan")) {
561  this->algorithm_ = rcp(new AlgZoltan<Adapter>(this->envConst_,
562  this->comm_,
563  this->baseInputAdapter_));
564  }
565  else if (algName_ == std::string("parma")) {
566  this->algorithm_ = rcp(new AlgParMA<Adapter>(this->envConst_,
567  this->comm_,
568  this->baseInputAdapter_));
569  }
570  else if (algName_ == std::string("scotch")) {
571  this->algorithm_ = rcp(new AlgPTScotch<Adapter>(this->envConst_,
572  this->comm_,
573  this->baseInputAdapter_));
574  }
575  else if (algName_ == std::string("parmetis")) {
576  this->algorithm_ = rcp(new AlgParMETIS<Adapter>(this->envConst_,
577  this->comm_,
578  this->graphModel_));
579  }
580  else if (algName_ == std::string("pulp")) {
581  this->algorithm_ = rcp(new AlgPuLP<Adapter>(this->envConst_,
582  this->comm_,
583  this->baseInputAdapter_));
584  }
585  else if (algName_ == std::string("block")) {
586  this->algorithm_ = rcp(new AlgBlock<Adapter>(this->envConst_,
587  this->comm_, this->identifierModel_));
588  }
589  else if (algName_ == std::string("phg") ||
590  algName_ == std::string("patoh")) {
591  // phg and patoh provided through Zoltan
592  Teuchos::ParameterList &pl = this->env_->getParametersNonConst();
593  Teuchos::ParameterList &zparams = pl.sublist("zoltan_parameters",false);
594  if (numberOfWeights_ > 0) {
595  char strval[10];
596  sprintf(strval, "%d", numberOfWeights_);
597  zparams.set("OBJ_WEIGHT_DIM", strval);
598  }
599  zparams.set("LB_METHOD", algName_.c_str());
600  zparams.set("LB_APPROACH", "PARTITION");
601  algName_ = std::string("zoltan");
602 
603  this->algorithm_ = rcp(new AlgZoltan<Adapter>(this->envConst_,
604  this->comm_,
605  this->baseInputAdapter_));
606  }
607  else if (algName_ == std::string("forTestingOnly")) {
608  this->algorithm_ = rcp(new AlgForTestingOnly<Adapter>(this->envConst_,
609  this->comm_,
610  this->baseInputAdapter_));
611  }
612  // else if (algName_ == std::string("rcb")) {
613  // this->algorithm_ = rcp(new AlgRCB<Adapter>(this->envConst_,this->comm_,
614  // this->coordinateModel_));
615  // }
616  else {
617  throw std::logic_error("partitioning algorithm not supported");
618  }
619  }
621 
622  // Create the solution
623  this->env_->timerStart(MACRO_TIMERS, "create solution");
624  PartitioningSolution<Adapter> *soln = NULL;
625 
626  try{
628  this->envConst_, this->comm_, numberOfWeights_,
629  partIds_.view(0, numberOfCriteria_),
630  partSizes_.view(0, numberOfCriteria_), this->algorithm_);
631  }
633 
634  solution_ = rcp(soln);
635 
636  this->env_->timerStop(MACRO_TIMERS, "create solution");
637  this->env_->memory("After creating Solution");
638 
639  // Call the algorithm
640 
641  try {
642  this->algorithm_->partition(solution_);
643  }
645 
646  //if mapping is requested
647  const Teuchos::ParameterEntry *pe = this->envConst_->getParameters().getEntryPtr("mapping_type");
648  int mapping_type = -1;
649  if (pe){
650  mapping_type = pe->getValue(&mapping_type);
651  }
652  //if mapping is 0 -- coordinate mapping
653 
654 #if ZOLTAN2_TASKMAPPING_MOVE
655  if (mapping_type == 0){
656 
657  //part_t *task_communication_xadj = NULL, *task_communication_adj = NULL;
658 
661  this->comm_.getRawPtr(),
662  machine_.getRawPtr(),
663  this->coordinateModel_.getRawPtr(),
664  solution_.getRawPtr(),
665  this->envConst_.getRawPtr()
666  //,task_communication_xadj,
667  //task_communication_adj
668  );
669 
670  // KDD For now, we would need to re-map the part numbers in the solution.
671  // KDD I suspect we'll later need to distinguish between part numbers and
672  // KDD process numbers to provide separation between partitioning and
673  // KDD mapping. For example, does this approach here assume #parts == #procs?
674  // KDD If we map k tasks to p processes with k > p, do we effectively reduce
675  // KDD the number of tasks (parts) in the solution?
676 
677 #ifdef KDD_READY
678  const part_t *oldParts = solution_->getPartListView();
679  size_t nLocal = ia->getNumLocalIds();
680  for (size_t i = 0; i < nLocal; i++) {
681  // kind of cheating since oldParts is a view; probably want an interface in solution
682  // for resetting the PartList rather than hacking in like this.
683  oldParts[i] = ctm->getAssignedProcForTask(oldParts[i]);
684  }
685 #endif
686 
687  //for now just delete the object.
688  delete ctm;
689  }
690 #endif
691 
692  else if (mapping_type == 1){
693  //if mapping is 1 -- graph mapping
694  }
695 
696  this->env_->debug(DETAILED_STATUS, "Exiting solve");
697 }
698 
699 template <typename Adapter>
701 {
702  this->env_->debug(DETAILED_STATUS,
703  "PartitioningProblem::createPartitioningProblem");
704 
705  using Teuchos::ParameterList;
706 
707  // A Problem object may be reused. The input data may have changed and
708  // new parameters or part sizes may have been set.
709  //
710  // Save these values in order to determine if we need to create a new model.
711 
712  //ModelType previousModel = modelType_;
713  bool prevModelAvail[MAX_NUM_MODEL_TYPES];
714  for(int i=0;i<MAX_NUM_MODEL_TYPES;i++)
715  {
716  prevModelAvail[i] = modelAvail_[i];
717  }
718 
719 
720  modelFlag_t previousGraphModelFlags = graphFlags_;
721  modelFlag_t previousIdentifierModelFlags = idFlags_;
722  modelFlag_t previousCoordinateModelFlags = coordFlags_;
723 
724  //modelType_ = InvalidModel;
725  for(int i=0;i<MAX_NUM_MODEL_TYPES;i++)
726  {
727  modelAvail_[i] = false;
728  }
729 
730  graphFlags_.reset();
731  idFlags_.reset();
732  coordFlags_.reset();
733 
735  // It's possible at this point that the Problem may want to
736  // add problem parameters to the parameter list in the Environment.
737  //
738  // Since the parameters in the Environment have already been
739  // validated in its constructor, a new Environment must be created:
741  // Teuchos::RCP<const Teuchos::Comm<int> > oldComm = this->env_->comm_;
742  // const ParameterList &oldParams = this->env_->getUnvalidatedParameters();
743  //
744  // ParameterList newParams = oldParams;
745  // newParams.set("new_parameter", "new_value");
746  //
747  // ParameterList &newPartParams = newParams.sublist("partitioning");
748  // newPartParams.set("new_partitioning_parameter", "its_value");
749  //
750  // this->env_ = rcp(new Environment(newParams, oldComm));
752 
753  this->env_->debug(DETAILED_STATUS, " parameters");
754  Environment &env = *(this->env_);
755  ParameterList &pl = env.getParametersNonConst();
756 
757  std::string defString("default");
758 
759  // Did the user specify a computational model?
760 
761  std::string model(defString);
762  const Teuchos::ParameterEntry *pe = pl.getEntryPtr("model");
763  if (pe)
764  model = pe->getValue<std::string>(&model);
765 
766  // Did the user specify an algorithm?
767 
768  std::string algorithm(defString);
769  pe = pl.getEntryPtr("algorithm");
770  if (pe)
771  algorithm = pe->getValue<std::string>(&algorithm);
772 
773  // Possible algorithm requirements that must be conveyed to the model:
774 
775  bool needConsecutiveGlobalIds = false;
776  bool removeSelfEdges= false;
777 
779  // Determine algorithm, model, and algorithm requirements. This
780  // is a first pass. Feel free to change this and add to it.
781 
782  if (algorithm != defString)
783  {
784 
785  // Figure out the model required by the algorithm
786  if (algorithm == std::string("block") ||
787  algorithm == std::string("random") ||
788  algorithm == std::string("cyclic") ){
789 
790  //modelType_ = IdentifierModelType;
791  modelAvail_[IdentifierModelType] = true;
792 
793  algName_ = algorithm;
794  }
795  else if (algorithm == std::string("zoltan") ||
796  algorithm == std::string("parma") ||
797  algorithm == std::string("forTestingOnly"))
798  {
799  algName_ = algorithm;
800  }
801  else if (algorithm == std::string("rcb") ||
802  algorithm == std::string("rib") ||
803  algorithm == std::string("hsfc"))
804  {
805  // rcb, rib, hsfc provided through Zoltan
806  Teuchos::ParameterList &zparams = pl.sublist("zoltan_parameters",false);
807  zparams.set("LB_METHOD", algorithm);
808  if (numberOfWeights_ > 0) {
809  char strval[10];
810  sprintf(strval, "%d", numberOfWeights_);
811  zparams.set("OBJ_WEIGHT_DIM", strval);
812  }
813  algName_ = std::string("zoltan");
814  }
815  else if (algorithm == std::string("multijagged"))
816  {
817  //modelType_ = CoordinateModelType;
818  modelAvail_[CoordinateModelType]=true;
819 
820  algName_ = algorithm;
821  }
822  else if (algorithm == std::string("metis") ||
823  algorithm == std::string("parmetis"))
824  {
825 
826  //modelType_ = GraphModelType;
827  modelAvail_[GraphModelType]=true;
828  algName_ = algorithm;
829  removeSelfEdges = true;
830  needConsecutiveGlobalIds = true;
831  }
832  else if (algorithm == std::string("scotch") ||
833  algorithm == std::string("ptscotch")) // BDD: Don't construct graph for scotch here
834  {
835  algName_ = algorithm;
836  }
837  else if (algorithm == std::string("pulp"))
838  {
839  algName_ = algorithm;
840  }
841  else if (algorithm == std::string("patoh") ||
842  algorithm == std::string("phg"))
843  {
844  // if ((modelType_ != GraphModelType) &&
845  // (modelType_ != HypergraphModelType) )
846  if ((modelAvail_[GraphModelType]==false) &&
847  (modelAvail_[HypergraphModelType]==false) )
848  {
849  //modelType_ = HypergraphModelType;
850  modelAvail_[HypergraphModelType]=true;
851  }
852  algName_ = algorithm;
853  }
854 #ifdef INCLUDE_ZOLTAN2_EXPERIMENTAL_WOLF
855  else if (algorithm == std::string("nd"))
856  {
857  modelAvail_[GraphModelType]=true;
858  modelAvail_[CoordinateModelType]=true;
859  algName_ = algorithm;
860  }
861 #endif
862  else
863  {
864  // Parameter list should ensure this does not happen.
865  throw std::logic_error("parameter list algorithm is invalid");
866  }
867  }
868  else if (model != defString)
869  {
870  // Figure out the algorithm suggested by the model.
871  if (model == std::string("hypergraph"))
872  {
873  //modelType_ = HypergraphModelType;
874  modelAvail_[HypergraphModelType]=true;
875 
876  if (this->comm_->getSize() > 1)
877  algName_ = std::string("phg");
878  else
879  algName_ = std::string("patoh");
880  }
881  else if (model == std::string("graph"))
882  {
883  //modelType_ = GraphModelType;
884  modelAvail_[GraphModelType]=true;
885 
886 #ifdef HAVE_ZOLTAN2_SCOTCH
887  modelAvail_[GraphModelType]=false; // graph constructed by AlgPTScotch
888  if (this->comm_->getSize() > 1)
889  algName_ = std::string("ptscotch");
890  else
891  algName_ = std::string("scotch");
892 #else
893 #ifdef HAVE_ZOLTAN2_PARMETIS
894  if (this->comm_->getSize() > 1)
895  algName_ = std::string("parmetis");
896  else
897  algName_ = std::string("metis");
898  removeSelfEdges = true;
899  needConsecutiveGlobalIds = true;
900 #else
901 #ifdef HAVE_ZOLTAN2_PULP
902  // TODO: XtraPuLP
903  //if (this->comm_->getSize() > 1)
904  // algName_ = std::string("xtrapulp");
905  //else
906  algName_ = std::string("pulp");
907 #else
908  if (this->comm_->getSize() > 1)
909  algName_ = std::string("phg");
910  else
911  algName_ = std::string("patoh");
912 #endif
913 #endif
914 #endif
915  }
916  else if (model == std::string("geometry"))
917  {
918  //modelType_ = CoordinateModelType;
919  modelAvail_[CoordinateModelType]=true;
920 
921  algName_ = std::string("multijagged");
922  }
923  else if (model == std::string("ids"))
924  {
925  //modelType_ = IdentifierModelType;
926  modelAvail_[IdentifierModelType]=true;
927 
928  algName_ = std::string("block");
929  }
930  else
931  {
932  // Parameter list should ensure this does not happen.
933  env.localBugAssertion(__FILE__, __LINE__,
934  "parameter list model type is invalid", 1, BASIC_ASSERTION);
935  }
936  }
937  else
938  {
939  // Determine an algorithm and model suggested by the input type.
940  // TODO: this is a good time to use the time vs. quality parameter
941  // in choosing an algorithm, and setting some parameters
942 
943  if (inputType_ == MatrixAdapterType)
944  {
945  //modelType_ = HypergraphModelType;
946  modelAvail_[HypergraphModelType]=true;
947 
948  if (this->comm_->getSize() > 1)
949  algName_ = std::string("phg");
950  else
951  algName_ = std::string("patoh");
952  }
953  else if (inputType_ == GraphAdapterType ||
954  inputType_ == MeshAdapterType)
955  {
956  //modelType_ = GraphModelType;
957  modelAvail_[GraphModelType]=true;
958 
959  if (this->comm_->getSize() > 1)
960  algName_ = std::string("phg");
961  else
962  algName_ = std::string("patoh");
963  }
964  else if (inputType_ == VectorAdapterType)
965  {
966  //modelType_ = CoordinateModelType;
967  modelAvail_[CoordinateModelType]=true;
968 
969  algName_ = std::string("multijagged");
970  }
971  else if (inputType_ == IdentifierAdapterType)
972  {
973  //modelType_ = IdentifierModelType;
974  modelAvail_[IdentifierModelType]=true;
975 
976  algName_ = std::string("block");
977  }
978  else{
979  // This should never happen
980  throw std::logic_error("input type is invalid");
981  }
982  }
983 
984  // Hierarchical partitioning?
985 
986  Array<int> valueList;
987  pe = pl.getEntryPtr("topology");
988 
989  if (pe){
990  valueList = pe->getValue<Array<int> >(&valueList);
991 
992  if (!Zoltan2::noValuesAreInRangeList<int>(valueList)){
993  int *n = new int [valueList.size() + 1];
994  levelNumberParts_ = arcp(n, 0, valueList.size() + 1, true);
995  int procsPerNode = 1;
996  for (int i=0; i < valueList.size(); i++){
997  levelNumberParts_[i+1] = valueList[i];
998  procsPerNode *= valueList[i];
999  }
1000  // Number of parts in the first level
1001  levelNumberParts_[0] = env.numProcs_ / procsPerNode;
1002 
1003  if (env.numProcs_ % procsPerNode > 0)
1004  levelNumberParts_[0]++;
1005  }
1006  }
1007  else{
1008  levelNumberParts_.clear();
1009  }
1010 
1011  hierarchical_ = levelNumberParts_.size() > 0;
1012 
1013  // Object to be partitioned? (rows, columns, etc)
1014 
1015  std::string objectOfInterest(defString);
1016  pe = pl.getEntryPtr("objects_to_partition");
1017  if (pe)
1018  objectOfInterest = pe->getValue<std::string>(&objectOfInterest);
1019 
1021  // Set model creation flags, if any.
1022 
1023  this->env_->debug(DETAILED_STATUS, " models");
1024  // if (modelType_ == GraphModelType)
1025  if (modelAvail_[GraphModelType]==true)
1026  {
1027 
1028  // Any parameters in the graph sublist?
1029 
1030  std::string symParameter(defString);
1031  pe = pl.getEntryPtr("symmetrize_graph");
1032  if (pe){
1033  symParameter = pe->getValue<std::string>(&symParameter);
1034  if (symParameter == std::string("transpose"))
1035  graphFlags_.set(SYMMETRIZE_INPUT_TRANSPOSE);
1036  else if (symParameter == std::string("bipartite"))
1037  graphFlags_.set(SYMMETRIZE_INPUT_BIPARTITE);
1038  }
1039 
1040  bool sgParameter = false;
1041  pe = pl.getEntryPtr("subset_graph");
1042  if (pe)
1043  sgParameter = pe->getValue(&sgParameter);
1044 
1045  if (sgParameter == 1)
1046  graphFlags_.set(BUILD_SUBSET_GRAPH);
1047 
1048  // Any special behaviors required by the algorithm?
1049 
1050  if (removeSelfEdges)
1051  graphFlags_.set(REMOVE_SELF_EDGES);
1052 
1053  if (needConsecutiveGlobalIds)
1054  graphFlags_.set(GENERATE_CONSECUTIVE_IDS);
1055 
1056  // How does user input map to vertices and edges?
1057 
1058  if (inputType_ == MatrixAdapterType){
1059  if (objectOfInterest == defString ||
1060  objectOfInterest == std::string("matrix_rows") )
1061  graphFlags_.set(VERTICES_ARE_MATRIX_ROWS);
1062  else if (objectOfInterest == std::string("matrix_columns"))
1063  graphFlags_.set(VERTICES_ARE_MATRIX_COLUMNS);
1064  else if (objectOfInterest == std::string("matrix_nonzeros"))
1065  graphFlags_.set(VERTICES_ARE_MATRIX_NONZEROS);
1066  }
1067 
1068  else if (inputType_ == MeshAdapterType){
1069  if (objectOfInterest == defString ||
1070  objectOfInterest == std::string("mesh_nodes") )
1071  graphFlags_.set(VERTICES_ARE_MESH_NODES);
1072  else if (objectOfInterest == std::string("mesh_elements"))
1073  graphFlags_.set(VERTICES_ARE_MESH_ELEMENTS);
1074  }
1075  }
1076  //MMW is it ok to remove else?
1077  // else if (modelType_ == IdentifierModelType)
1078  if (modelAvail_[IdentifierModelType]==true)
1079  {
1080 
1081  // Any special behaviors required by the algorithm?
1082 
1083  }
1084  // else if (modelType_ == CoordinateModelType)
1085  if (modelAvail_[CoordinateModelType]==true)
1086  {
1087 
1088  // Any special behaviors required by the algorithm?
1089 
1090  }
1091 
1092 
1093  if (newData ||
1094  (modelAvail_[GraphModelType]!=prevModelAvail[GraphModelType]) ||
1095  (modelAvail_[HypergraphModelType]!=prevModelAvail[HypergraphModelType])||
1096  (modelAvail_[CoordinateModelType]!=prevModelAvail[CoordinateModelType])||
1097  (modelAvail_[IdentifierModelType]!=prevModelAvail[IdentifierModelType])||
1098  // (modelType_ != previousModel) ||
1099  (graphFlags_ != previousGraphModelFlags) ||
1100  (coordFlags_ != previousCoordinateModelFlags) ||
1101  (idFlags_ != previousIdentifierModelFlags))
1102  {
1103  // Create the computational model.
1104  // Models are instantiated for base input adapter types (mesh,
1105  // matrix, graph, and so on). We pass a pointer to the input
1106  // adapter, cast as the base input type.
1107 
1108  //KDD Not sure why this shadow declaration is needed
1109  //KDD Comment out for now; revisit later if problems.
1110  //KDD const Teuchos::ParameterList pl = this->envConst_->getParameters();
1111  //bool exceptionThrow = true;
1112 
1113  if(modelAvail_[GraphModelType]==true)
1114  {
1115  this->env_->debug(DETAILED_STATUS, " building graph model");
1116  this->graphModel_ = rcp(new GraphModel<base_adapter_t>(
1117  this->baseInputAdapter_, this->envConst_, this->comm_,
1118  graphFlags_));
1119 
1120  this->baseModel_ = rcp_implicit_cast<const Model<base_adapter_t> >(
1121  this->graphModel_);
1122  }
1123  if(modelAvail_[HypergraphModelType]==true)
1124  {
1125  //KDD USING ZOLTAN FOR HYPERGRAPH FOR NOW
1126  //KDD std::cout << "Hypergraph model not implemented yet..." << std::endl;
1127  }
1128 
1129  if(modelAvail_[CoordinateModelType]==true)
1130  {
1131  this->env_->debug(DETAILED_STATUS, " building coordinate model");
1132  this->coordinateModel_ = rcp(new CoordinateModel<base_adapter_t>(
1133  this->baseInputAdapter_, this->envConst_, this->comm_,
1134  coordFlags_));
1135 
1136  this->baseModel_ = rcp_implicit_cast<const Model<base_adapter_t> >(
1137  this->coordinateModel_);
1138  }
1139 
1140  if(modelAvail_[IdentifierModelType]==true)
1141  {
1142  this->env_->debug(DETAILED_STATUS, " building identifier model");
1143  this->identifierModel_ = rcp(new IdentifierModel<base_adapter_t>(
1144  this->baseInputAdapter_, this->envConst_, this->comm_,
1145  idFlags_));
1146 
1147  this->baseModel_ = rcp_implicit_cast<const Model<base_adapter_t> >(
1148  this->identifierModel_);
1149  }
1150 
1151  this->env_->memory("After creating Model");
1152  this->env_->debug(DETAILED_STATUS, "createPartitioningProblem done");
1153  }
1154 }
1155 
1156 } // namespace Zoltan2
1157 #endif
use columns as graph vertices
Serial greedy first-fit graph coloring (local graph only)
#define HELLO
Zoltan2::BaseAdapter< userTypes_t > base_adapter_t
Time an algorithm (or other entity) as a whole.
ignore invalid neighbors
void setPartSizes(int len, part_t *partIds, scalar_t *partSizes, bool makeCopy=true)
Set or reset relative sizes for the parts that Zoltan2 will create.
use mesh nodes as vertices
fast typical checks for valid arguments
#define Z2_FORWARD_EXCEPTIONS
Forward an exception back through call stack.
static void getValidParameters(ParameterList &pl)
Set up validators specific to this algorithm.
static RCP< Teuchos::BoolParameterEntryValidator > getBoolValidator()
Exists to make setting up validators less cluttered.
algorithm requires consecutive ids
std::bitset< NUM_MODEL_FLAGS > modelFlag_t
PartitioningProblem(Adapter *A, ParameterList *p)
Constructor where communicator is the Teuchos default.
model must symmetrize input
model must symmetrize input
PartitioningProblem(Adapter *A, ParameterList *p, const RCP< const Teuchos::Comm< int > > &comm)
Constructor where Teuchos communicator is specified.
Defines the PartitioningSolution class.
static RCP< Teuchos::AnyNumberParameterEntryValidator > getAnyDoubleValidator()
Exists to make setting up validators less cluttered.
part_t getAssignedProcForTask(part_t taskId)
getAssignedProcForTask function, returns the assigned processor id for the given task ...
sub-steps, each method&#39;s entry and exit
static void getValidParameters(ParameterList &pl)
Set up validators specific to this Problem.
void setPartSizesForCriteria(int criteria, int len, part_t *partIds, scalar_t *partSizes, bool makeCopy=true)
Set or reset the relative sizes (per weight) for the parts that Zoltan2 will create.
use matrix rows as graph vertices
algorithm requires no self edges
Defines the IdentifierModel interface.
A PartitioningSolution is a solution to a partitioning problem.
use nonzeros as graph vertices
Defines the EvaluatePartition class.
BaseAdapterType
An enum to identify general types of adapters.
identifier data, just a list of IDs
Problem base class from which other classes (PartitioningProblem, ColoringProblem, OrderingProblem, MatchingProblem, etc.) derive.
Defines the Problem base class.
static RCP< Teuchos::AnyNumberParameterEntryValidator > getAnyIntValidator()
Exists to make setting up validators less cluttered.
static void getValidParameters(ParameterList &pl)
Set up validators specific to this algorithm.
Define IntegerRangeList validator.
const PartitioningSolution< Adapter > & getSolution()
Get the solution to the problem.
static void getValidParameters(ParameterList &pl)
Set up validators specific to this algorithm.
PartitioningProblem sets up partitioning problems for the user.
use mesh elements as vertices
Defines the GraphModel interface.
static void getValidParameters(ParameterList &pl)
Set up validators specific to this algorithm.
void solve(bool updateInputData=true)
Direct the problem to create a solution.
Multi Jagged coordinate partitioning algorithm.
static void getValidParameters(ParameterList &pl)
Set up validators specific to this algorithm.