Zoltan2
Loading...
Searching...
No Matches
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>
62#ifdef ZOLTAN2_TASKMAPPING_MOVE
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
78namespace Zoltan2{
79
103template<typename Adapter>
104class PartitioningProblem : public Problem<Adapter>
105{
106public:
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;
113 typedef typename Adapter::base_adapter_t base_adapter_t;
114
116 PartitioningProblem(Adapter *A, ParameterList *p,
117 const RCP<const Teuchos::Comm<int> > &comm):
118 Problem<Adapter>(A,p,comm),
119 solution_(),
124 {
126 }
127
128#ifdef HAVE_ZOLTAN2_MPI
131 PartitioningProblem(Adapter *A, ParameterList *p, MPI_Comm mpicomm):
133 rcp<const Comm<int> >(new Teuchos::MpiComm<int>(
134 Teuchos::opaqueWrapper(mpicomm))))
135 {}
136#endif
137
139 PartitioningProblem(Adapter *A, ParameterList *p):
140 PartitioningProblem(A, p, Tpetra::getDefaultComm())
141 {}
142
146
148 //
149 // \param updateInputData If true this indicates that either
150 // this is the first attempt at solution, or that we
151 // are computing a new solution and the input data has
152 // changed since the previous solution was computed.
153 // By input data we mean coordinates, topology, or weights.
154 // If false, this indicates that we are computing a
155 // new solution using the same input data was used for
156 // the previous solution, even though the parameters
157 // may have been changed.
158 //
159 // For the sake of performance, we ask the caller to set \c updateInputData
160 // to false if he/she is computing a new solution using the same input data,
161 // but different problem parameters, than that which was used to compute
162 // the most recent solution.
163
164 void solve(bool updateInputData=true);
165
167 //
168 // \return a reference to the solution to the most recent solve().
169
170 const PartitioningSolution<Adapter> &getSolution() {
171 return *(solution_.getRawPtr());
172 };
173
212 void setPartSizes(int len, part_t *partIds, scalar_t *partSizes,
213 bool makeCopy=true)
214 {
215 setPartSizesForCriteria(0, len, partIds, partSizes, makeCopy);
216 }
217
252 void setPartSizesForCriteria(int criteria, int len, part_t *partIds,
253 scalar_t *partSizes, bool makeCopy=true) ;
254/*
255 void setMachine(MachineRepresentation<typename Adapter::base_adapter_t::scalar_t> *machine);
256*/
257
260 static void getValidParameters(ParameterList & pl)
261 {
263
265
270
271 // This set up does not use tuple because we didn't have constructors
272 // that took that many elements - Tuple will need to be modified and I
273 // didn't want to have low level changes with this particular refactor
274 // TO DO: Add more Tuple constructors and then redo this code to be
275 // Teuchos::tuple<std::string> algorithm_names( "rcb", "multijagged" ... );
276 Array<std::string> algorithm_names(19);
277 algorithm_names[0] = "rcb";
278 algorithm_names[1] = "multijagged";
279 algorithm_names[2] = "rib";
280 algorithm_names[3] = "hsfc";
281 algorithm_names[4] = "patoh";
282 algorithm_names[5] = "phg";
283 algorithm_names[6] = "metis";
284 algorithm_names[7] = "parmetis";
285 algorithm_names[8] = "quotient";
286 algorithm_names[9] = "pulp";
287 algorithm_names[10] = "parma";
288 algorithm_names[11] = "scotch";
289 algorithm_names[12] = "ptscotch";
290 algorithm_names[13] = "block";
291 algorithm_names[14] = "cyclic";
292 algorithm_names[15] = "sarma";
293 algorithm_names[16] = "random";
294 algorithm_names[17] = "zoltan";
295 algorithm_names[18] = "forTestingOnly";
296 RCP<Teuchos::StringValidator> algorithm_Validator = Teuchos::rcp(
297 new Teuchos::StringValidator( algorithm_names ));
298 pl.set("algorithm", "random", "partitioning algorithm",
299 algorithm_Validator);
300
301 // bool parameter
302 pl.set("keep_partition_tree", false, "If true, will keep partition tree",
304
305 // bool parameter
306 pl.set("rectilinear", false, "If true, then when a cut is made, all of the "
307 "dots located on the cut are moved to the same side of the cut. The "
308 "resulting regions are then rectilinear. The resulting load balance may "
309 "not be as good as when the group of dots is split by the cut. ",
311
312 RCP<Teuchos::StringValidator> partitioning_objective_Validator =
313 Teuchos::rcp( new Teuchos::StringValidator(
314 Teuchos::tuple<std::string>( "balance_object_count",
315 "balance_object_weight", "multicriteria_minimize_total_weight",
316 "multicriteria_minimize_maximum_weight",
317 "multicriteria_balance_total_maximum", "minimize_cut_edge_count",
318 "minimize_cut_edge_weight", "minimize_neighboring_parts",
319 "minimize_boundary_vertices" )));
320 pl.set("partitioning_objective", "balance_object_weight",
321 "objective of partitioning", partitioning_objective_Validator);
322
323 pl.set("imbalance_tolerance", 1.1, "imbalance tolerance, ratio of "
324 "maximum load over average load", Environment::getAnyDoubleValidator());
325
326 // num_global_parts >= 1
327 RCP<Teuchos::EnhancedNumberValidator<int>> num_global_parts_Validator =
328 Teuchos::rcp( new Teuchos::EnhancedNumberValidator<int>(
329 1, Teuchos::EnhancedNumberTraits<int>::max()) ); // no maximum
330 pl.set("num_global_parts", 1, "global number of parts to compute "
331 "(0 means use the number of processes)", num_global_parts_Validator);
332
333 // num_local_parts >= 0
334 RCP<Teuchos::EnhancedNumberValidator<int>> num_local_parts_Validator =
335 Teuchos::rcp( new Teuchos::EnhancedNumberValidator<int>(
336 0, Teuchos::EnhancedNumberTraits<int>::max()) ); // no maximum
337 pl.set("num_local_parts", 0, "number of parts to compute for this "
338 "process (num_global_parts == sum of all num_local_parts)",
339 num_local_parts_Validator);
340
341 RCP<Teuchos::StringValidator> partitioning_approach_Validator =
342 Teuchos::rcp( new Teuchos::StringValidator(
343 Teuchos::tuple<std::string>( "partition", "repartition",
344 "maximize_overlap" )));
345 pl.set("partitioning_approach", "partition", "Partition from scratch, "
346 "partition incrementally from current partition, of partition from "
347 "scratch but maximize overlap with the current partition",
348 partitioning_approach_Validator);
349
350 RCP<Teuchos::StringValidator> objects_to_partition_Validator =
351 Teuchos::rcp( new Teuchos::StringValidator(
352 Teuchos::tuple<std::string>( "matrix_rows", "matrix_columns",
353 "matrix_nonzeros", "mesh_elements", "mesh_nodes", "graph_edges",
354 "graph_vertices", "coordinates", "identifiers" )));
355 pl.set("objects_to_partition", "graph_vertices", "Objects to be partitioned",
356 objects_to_partition_Validator);
357
358 RCP<Teuchos::StringValidator> model_Validator = Teuchos::rcp(
359 new Teuchos::StringValidator(
360 Teuchos::tuple<std::string>( "hypergraph", "graph",
361 "geometry", "ids" )));
362 pl.set("model", "graph", "This is a low level parameter. Normally the "
363 "library will choose a computational model based on the algorithm or "
364 "objective specified by the user.", model_Validator);
365
366 // bool parameter
367 pl.set("remap_parts", false, "remap part numbers to minimize migration "
368 "between old and new partitions", Environment::getBoolValidator() );
369
370 pl.set("mapping_type", -1, "Mapping of solution to the processors. -1 No"
371 " Mapping, 0 coordinate mapping.", Environment::getAnyIntValidator());
372
373 RCP<Teuchos::EnhancedNumberValidator<int>> ghost_layers_Validator =
374 Teuchos::rcp( new Teuchos::EnhancedNumberValidator<int>(1, 10, 1, 0) );
375 pl.set("ghost_layers", 2, "number of layers for ghosting used in "
376 "hypergraph ghost method", ghost_layers_Validator);
377 }
378
379protected:
380 void initializeProblem();
381 virtual void processAlgorithmName(const std::string& algorithm, const std::string& defString, const std::string& model,
382 Environment &env, bool& removeSelfEdges, bool &isGraphType, bool& needConsecutiveGlobalIds);
383
384 void createPartitioningProblem(bool newData);
385 virtual void createAlgorithm();
386
387 RCP<PartitioningSolution<Adapter> > solution_;
388#ifdef ZOLTAN2_TASKMAPPING_MOVE
389 RCP<MachineRepresentation<scalar_t,part_t> > machine_;
390#endif
391
393
397 std::string algName_;
398
400
401 // Suppose Array<part_t> partIds = partIds_[w]. If partIds.size() > 0
402 // then the user supplied part sizes for weight index "w", and the sizes
403 // corresponding to the Ids in partIds are partSizes[w].
404 //
405 // If numberOfWeights_ >= 0, then there is an Id and Sizes array for
406 // for each weight. Otherwise the user did not supply object weights,
407 // but they can still specify part sizes.
408 // So numberOfCriteria_ is numberOfWeights_ or one, whichever is greater.
409
410 ArrayRCP<ArrayRCP<part_t> > partIds_;
411 ArrayRCP<ArrayRCP<scalar_t> > partSizes_;
413
414 // Number of parts to be computed at each level in hierarchical partitioning.
415
416 ArrayRCP<int> levelNumberParts_;
418};
420
421/*
422template <typename Adapter>
423void PartitioningProblem<Adapter>::setMachine(MachineRepresentation<typename Adapter::base_adapter_t::scalar_t> *machine){
424 this->machine_ = RCP<MachineRepresentation<typename Adapter::base_adapter_t::scalar_t> > (machine, false);
425}
426*/
427
428
429template <typename Adapter>
431{
432 HELLO;
433
434 this->env_->debug(DETAILED_STATUS, "PartitioningProblem::initializeProblem");
435
436 if (getenv("DEBUGME")){
437#ifndef _WIN32
438 std::cout << getpid() << std::endl;
439 sleep(15);
440#else
441 std::cout << _getpid() << std::endl;
442 Sleep(15000);
443#endif
444 }
445
446#ifdef HAVE_ZOLTAN2_OVIS
447 ovis_enabled(this->comm_->getRank());
448#endif
449
450 // Create a copy of the user's communicator.
451
452#ifdef ZOLTAN2_TASKMAPPING_MOVE
453 machine_ = RCP<MachineRepresentation<scalar_t,part_t> >(
454 new MachineRepresentation<scalar_t,part_t>(*(this->comm_)));
455#endif
456
457 // Number of criteria is number of user supplied weights if non-zero.
458 // Otherwise it is 1 and uniform weight is implied.
459
460 numberOfWeights_ = this->inputAdapter_->getNumWeightsPerID();
461
462 numberOfCriteria_ = (numberOfWeights_ > 1) ? numberOfWeights_ : 1;
463
464 inputType_ = this->inputAdapter_->adapterType();
465
466 // The Caller can specify part sizes in setPartSizes(). If he/she
467 // does not, the part size arrays are empty.
468
469 ArrayRCP<part_t> *noIds = new ArrayRCP<part_t> [numberOfCriteria_];
470 ArrayRCP<scalar_t> *noSizes = new ArrayRCP<scalar_t> [numberOfCriteria_];
471
472 partIds_ = arcp(noIds, 0, numberOfCriteria_, true);
473 partSizes_ = arcp(noSizes, 0, numberOfCriteria_, true);
474
475 if (this->env_->getDebugLevel() >= DETAILED_STATUS){
476 std::ostringstream msg;
477 msg << this->comm_->getSize() << " procs,"
478 << numberOfWeights_ << " user-defined weights\n";
479 this->env_->debug(DETAILED_STATUS, msg.str());
480 }
481
482 this->env_->memory("After initializeProblem");
483}
484
485template <typename Adapter>
487 int criteria, int len, part_t *partIds, scalar_t *partSizes, bool makeCopy)
488{
489 this->env_->localInputAssertion(__FILE__, __LINE__, "invalid length",
490 len>= 0, BASIC_ASSERTION);
491
492 this->env_->localInputAssertion(__FILE__, __LINE__, "invalid criteria",
493 criteria >= 0 && criteria < numberOfCriteria_, BASIC_ASSERTION);
494
495 if (len == 0){
496 partIds_[criteria] = ArrayRCP<part_t>();
497 partSizes_[criteria] = ArrayRCP<scalar_t>();
498 return;
499 }
500
501 this->env_->localInputAssertion(__FILE__, __LINE__, "invalid arrays",
502 partIds && partSizes, BASIC_ASSERTION);
503
504 // The global validity of the partIds and partSizes arrays is performed
505 // by the PartitioningSolution, which computes global part distribution and
506 // part sizes.
507
508 part_t *z2_partIds = NULL;
509 scalar_t *z2_partSizes = NULL;
510 bool own_memory = false;
511
512 if (makeCopy){
513 z2_partIds = new part_t [len];
514 z2_partSizes = new scalar_t [len];
515 this->env_->localMemoryAssertion(__FILE__, __LINE__, len, z2_partSizes);
516 memcpy(z2_partIds, partIds, len * sizeof(part_t));
517 memcpy(z2_partSizes, partSizes, len * sizeof(scalar_t));
518 own_memory=true;
519 }
520 else{
521 z2_partIds = partIds;
522 z2_partSizes = partSizes;
523 }
524
525 partIds_[criteria] = arcp(z2_partIds, 0, len, own_memory);
526 partSizes_[criteria] = arcp(z2_partSizes, 0, len, own_memory);
527}
528
529 template <typename Adapter>
531 {
532 // Create the algorithm
533 if (algName_ == std::string("multijagged")) {
534 this->algorithm_ = rcp(new Zoltan2_AlgMJ<Adapter>(this->envConst_,
535 this->comm_,
536 this->baseInputAdapter_));
537 }
538 else if (algName_ == std::string("zoltan")) {
539 this->algorithm_ = rcp(new AlgZoltan<Adapter>(this->envConst_,
540 this->comm_,
541 this->baseInputAdapter_));
542 }
543 else if (algName_ == std::string("parma")) {
544 this->algorithm_ = rcp(new AlgParMA<Adapter>(this->envConst_,
545 this->comm_,
546 this->baseInputAdapter_));
547 }
548 else if (algName_ == std::string("scotch")) {
549 this->algorithm_ = rcp(new AlgPTScotch<Adapter>(this->envConst_,
550 this->comm_,
551 this->baseInputAdapter_));
552 }
553 else if (algName_ == std::string("parmetis")) {
554 using model_t = GraphModel<base_adapter_t>;
555 this->algorithm_ = rcp(new AlgParMETIS<Adapter, model_t>(this->envConst_,
556 this->comm_,
557 this->baseInputAdapter_,
558 this->graphFlags_));
559 }
560 else if (algName_ == std::string("quotient")) {
561 this->algorithm_ = rcp(new AlgQuotient<Adapter>(this->envConst_,
562 this->comm_,
563 this->baseInputAdapter_,
564 this->graphFlags_));
565 //"parmetis")); // The default alg. to use inside Quotient
566 } // is ParMETIS for now.
567 else if (algName_ == std::string("pulp")) {
568 this->algorithm_ = rcp(new AlgPuLP<Adapter>(this->envConst_,
569 this->comm_,
570 this->baseInputAdapter_));
571 }
572 else if (algName_ == std::string("block")) {
573 this->algorithm_ = rcp(new AlgBlock<Adapter>(this->envConst_,
574 this->comm_, this->baseInputAdapter_));
575 }
576 else if (algName_ == std::string("phg") ||
577 algName_ == std::string("patoh")) {
578 // phg and patoh provided through Zoltan
579 Teuchos::ParameterList &pl = this->env_->getParametersNonConst();
580 Teuchos::ParameterList &zparams = pl.sublist("zoltan_parameters",false);
581 if (numberOfWeights_ > 0) {
582 char strval[20];
583 sprintf(strval, "%d", numberOfWeights_);
584 zparams.set("OBJ_WEIGHT_DIM", strval);
585 }
586 zparams.set("LB_METHOD", algName_.c_str());
587 zparams.set("LB_APPROACH", "PARTITION");
588 algName_ = std::string("zoltan");
589
590 this->algorithm_ = rcp(new AlgZoltan<Adapter>(this->envConst_,
591 this->comm_,
592 this->baseInputAdapter_));
593 }
594 else if (algName_ == std::string("sarma")) {
595 this->algorithm_ = rcp(new AlgSarma<Adapter>(this->envConst_,
596 this->comm_,
597 this->baseInputAdapter_));
598 }
599 else if (algName_ == std::string("forTestingOnly")) {
600 this->algorithm_ = rcp(new AlgForTestingOnly<Adapter>(this->envConst_,
601 this->comm_,
602 this->baseInputAdapter_));
603 }
604 // else if (algName_ == std::string("rcb")) {
605 // this->algorithm_ = rcp(new AlgRCB<Adapter>(this->envConst_,this->comm_,
606 // this->coordinateModel_));
607 // }
608 else {
609 throw std::logic_error("partitioning algorithm not supported");
610 }
611 }
612
613template <typename Adapter>
614void PartitioningProblem<Adapter>::solve(bool updateInputData)
615{
616 this->env_->debug(DETAILED_STATUS, "Entering solve");
617
618 // Create the computational model.
619
620 this->env_->timerStart(MACRO_TIMERS, "create problem");
621
622 createPartitioningProblem(updateInputData);
623
624 this->env_->timerStop(MACRO_TIMERS, "create problem");
625
626 // TODO: If hierarchical_
627
628 // Create the solution. The algorithm will query the Solution
629 // for part and weight information. The algorithm will
630 // update the solution with part assignments and quality metrics.
631
632 // Create the algorithm
633 try {
634 this->createAlgorithm();
635 }
637 // Create the solution
638 this->env_->timerStart(MACRO_TIMERS, "create solution");
639 PartitioningSolution<Adapter> *soln = NULL;
640
641 try{
642 soln = new PartitioningSolution<Adapter>(
643 this->envConst_, this->comm_, numberOfWeights_,
644 partIds_.view(0, numberOfCriteria_),
645 partSizes_.view(0, numberOfCriteria_), this->algorithm_);
646 }
648
649 solution_ = rcp(soln);
650
651 this->env_->timerStop(MACRO_TIMERS, "create solution");
652 this->env_->memory("After creating Solution");
653
654 // Call the algorithm
655
656 try {
657 this->algorithm_->partition(solution_);
658 }
660
661 //if mapping is requested
662 const Teuchos::ParameterEntry *pe = this->envConst_->getParameters().getEntryPtr("mapping_type");
663 int mapping_type = -1;
664 if (pe){
665 mapping_type = pe->getValue(&mapping_type);
666 }
667 //if mapping is 0 -- coordinate mapping
668
669#if ZOLTAN2_TASKMAPPING_MOVE
670 if (mapping_type == 0){
671
672 //part_t *task_communication_xadj = NULL, *task_communication_adj = NULL;
673
674 Zoltan2::CoordinateTaskMapper <Adapter, part_t> *ctm=
676 this->comm_.getRawPtr(),
677 machine_.getRawPtr(),
678 this->baseInputAdapter_.getRawPtr(),
679 solution_.getRawPtr(),
680 this->envConst_.getRawPtr()
681 //,task_communication_xadj,
682 //task_communication_adj
683 );
684
685 // KDD For now, we would need to re-map the part numbers in the solution.
686 // KDD I suspect we'll later need to distinguish between part numbers and
687 // KDD process numbers to provide separation between partitioning and
688 // KDD mapping. For example, does this approach here assume #parts == #procs?
689 // KDD If we map k tasks to p processes with k > p, do we effectively reduce
690 // KDD the number of tasks (parts) in the solution?
691
692#ifdef KDD_READY
693 const part_t *oldParts = solution_->getPartListView();
694 size_t nLocal = ia->getNumLocalIds();
695 for (size_t i = 0; i < nLocal; i++) {
696 // kind of cheating since oldParts is a view; probably want an interface in solution
697 // for resetting the PartList rather than hacking in like this.
698 oldParts[i] = ctm->getAssignedProcForTask(oldParts[i]);
699 }
700#endif
701
702 //for now just delete the object.
703 delete ctm;
704 }
705#endif
706
707 else if (mapping_type == 1){
708 //if mapping is 1 -- graph mapping
709 }
710
711 this->env_->debug(DETAILED_STATUS, "Exiting solve");
712}
713
714template <typename Adapter>
716 const std::string &algorithm, const std::string &defString,
717 const std::string &model, Environment &env, bool &removeSelfEdges,
718 bool &isGraphType, bool &needConsecutiveGlobalIds) {
719 ParameterList &pl = env.getParametersNonConst();
720
721 if (algorithm != defString) {
722 if (algorithm == std::string("block") ||
723 algorithm == std::string("random") ||
724 algorithm == std::string("cyclic") ||
725 algorithm == std::string("zoltan") ||
726 algorithm == std::string("parma") ||
727 algorithm == std::string("forTestingOnly") ||
728 algorithm == std::string("quotient") ||
729 algorithm == std::string("scotch") ||
730 algorithm == std::string("ptscotch") ||
731 algorithm == std::string("pulp") || algorithm == std::string("sarma") ||
732 algorithm == std::string("patoh") || algorithm == std::string("phg") ||
733 algorithm == std::string("multijagged")) {
734 algName_ = algorithm;
735 } else if (algorithm == std::string("rcb") ||
736 algorithm == std::string("rib") ||
737 algorithm == std::string("hsfc")) {
738 // rcb, rib, hsfc provided through Zoltan
739 Teuchos::ParameterList &zparams = pl.sublist("zoltan_parameters", false);
740 zparams.set("LB_METHOD", algorithm);
741 if (numberOfWeights_ > 0) {
742 char strval[20];
743 sprintf(strval, "%d", numberOfWeights_);
744 zparams.set("OBJ_WEIGHT_DIM", strval);
745 }
746 algName_ = std::string("zoltan");
747 } else if (algorithm == std::string("metis") ||
748 algorithm == std::string("parmetis")) {
749 algName_ = algorithm;
750 removeSelfEdges = true;
751 needConsecutiveGlobalIds = true;
752 isGraphType = true;
753 } else {
754 // Parameter list should ensure this does not happen.
755 throw std::logic_error("parameter list algorithm is invalid");
756 }
757 } else if (model != defString) {
758 // Figure out the algorithm suggested by the model.
759 if (model == std::string("hypergraph")) {
760 algName_ = std::string("phg");
761 } else if (model == std::string("graph")) {
762#ifdef HAVE_ZOLTAN2_SCOTCH
763 if (this->comm_->getSize() > 1)
764 algName_ = std::string("ptscotch");
765 else
766 algName_ = std::string("scotch");
767#else
768#ifdef HAVE_ZOLTAN2_PARMETIS
769 if (this->comm_->getSize() > 1)
770 algName_ = std::string("parmetis");
771 else
772 algName_ = std::string("metis");
773 removeSelfEdges = true;
774 needConsecutiveGlobalIds = true;
775 isGraphType = true;
776#else
777#ifdef HAVE_ZOLTAN2_PULP
778 // TODO: XtraPuLP
779 // if (this->comm_->getSize() > 1)
780 // algName_ = std::string("xtrapulp");
781 // else
782 algName_ = std::string("pulp");
783#else
784 algName_ = std::string("phg");
785#endif
786#endif
787#endif
788 } else if (model == std::string("geometry")) {
789 algName_ = std::string("multijagged");
790 } else if (model == std::string("ids")) {
791 algName_ = std::string("block");
792 } else {
793 // Parameter list should ensure this does not happen.
794 env.localBugAssertion(__FILE__, __LINE__,
795 "parameter list model type is invalid", 1,
797 }
798 } else {
799 // Determine an algorithm and model suggested by the input type.
800 // TODO: this is a good time to use the time vs. quality parameter
801 // in choosing an algorithm, and setting some parameters
802
803 if (inputType_ == MatrixAdapterType) {
804 algName_ = std::string("phg");
805 } else if (inputType_ == GraphAdapterType ||
806 inputType_ == MeshAdapterType) {
807 algName_ = std::string("phg");
808 } else if (inputType_ == VectorAdapterType) {
809 algName_ = std::string("multijagged");
810 } else if (inputType_ == IdentifierAdapterType) {
811 algName_ = std::string("block");
812 } else {
813 // This should never happen
814 throw std::logic_error("input type is invalid");
815 }
816 }
817}
818
819template <typename Adapter>
821{
822 this->env_->debug(DETAILED_STATUS,
823 "PartitioningProblem::createPartitioningProblem");
824
825 using Teuchos::ParameterList;
826
827 graphFlags_.reset();
828 idFlags_.reset();
829 coordFlags_.reset();
830
832 // It's possible at this point that the Problem may want to
833 // add problem parameters to the parameter list in the Environment.
834 //
835 // Since the parameters in the Environment have already been
836 // validated in its constructor, a new Environment must be created:
838 // Teuchos::RCP<const Teuchos::Comm<int> > oldComm = this->env_->comm_;
839 // const ParameterList &oldParams = this->env_->getUnvalidatedParameters();
840 //
841 // ParameterList newParams = oldParams;
842 // newParams.set("new_parameter", "new_value");
843 //
844 // ParameterList &newPartParams = newParams.sublist("partitioning");
845 // newPartParams.set("new_partitioning_parameter", "its_value");
846 //
847 // this->env_ = rcp(new Environment(newParams, oldComm));
849
850 this->env_->debug(DETAILED_STATUS, " parameters");
851 Environment &env = *(this->env_);
852 ParameterList &pl = env.getParametersNonConst();
853
854 std::string defString("default");
855
856 // Did the user specify a computational model?
857
858 std::string model(defString);
859 const Teuchos::ParameterEntry *pe = pl.getEntryPtr("model");
860 if (pe)
861 model = pe->getValue<std::string>(&model);
862
863 // Did the user specify an algorithm?
864
865 std::string algorithm(defString);
866 pe = pl.getEntryPtr("algorithm");
867 if (pe)
868 algorithm = pe->getValue<std::string>(&algorithm);
869
870 // Possible algorithm requirements that must be conveyed to the model:
871
872 bool needConsecutiveGlobalIds = false;
873 bool removeSelfEdges= false;
874 bool isGraphModel = false;
875
877 // Determine algorithm, model, and algorithm requirements. This
878 // is a first pass. Feel free to change this and add to it.
879
880 this->processAlgorithmName(algorithm, defString, model, env, removeSelfEdges,
881 isGraphModel, needConsecutiveGlobalIds);
882
883 // Hierarchical partitioning?
884
885 Array<int> valueList;
886 pe = pl.getEntryPtr("topology");
887
888 if (pe){
889 valueList = pe->getValue<Array<int> >(&valueList);
890
891 if (!Zoltan2::noValuesAreInRangeList<int>(valueList)){
892 int *n = new int [valueList.size() + 1];
893 levelNumberParts_ = arcp(n, 0, valueList.size() + 1, true);
894 int procsPerNode = 1;
895 for (int i=0; i < valueList.size(); i++){
896 levelNumberParts_[i+1] = valueList[i];
897 procsPerNode *= valueList[i];
898 }
899 // Number of parts in the first level
900 levelNumberParts_[0] = env.numProcs_ / procsPerNode;
901
902 if (env.numProcs_ % procsPerNode > 0)
903 levelNumberParts_[0]++;
904 }
905 }
906 else{
907 levelNumberParts_.clear();
908 }
909
910 hierarchical_ = levelNumberParts_.size() > 0;
911
912 // Object to be partitioned? (rows, columns, etc)
913
914 std::string objectOfInterest(defString);
915 pe = pl.getEntryPtr("objects_to_partition");
916 if (pe)
917 objectOfInterest = pe->getValue<std::string>(&objectOfInterest);
918
920 // Set model creation flags, if any.
921
922 this->env_->debug(DETAILED_STATUS, " models");
923
924 if (isGraphModel == true)
925 {
926
927 // Any parameters in the graph sublist?
928
929 std::string symParameter(defString);
930 pe = pl.getEntryPtr("symmetrize_graph");
931 if (pe){
932 symParameter = pe->getValue<std::string>(&symParameter);
933 if (symParameter == std::string("transpose"))
934 graphFlags_.set(SYMMETRIZE_INPUT_TRANSPOSE);
935 else if (symParameter == std::string("bipartite"))
936 graphFlags_.set(SYMMETRIZE_INPUT_BIPARTITE);
937 }
938
939 bool sgParameter = false;
940 pe = pl.getEntryPtr("subset_graph");
941 if (pe)
942 sgParameter = pe->getValue(&sgParameter);
943
944 if (sgParameter == 1)
945 graphFlags_.set(BUILD_SUBSET_GRAPH);
946
947 // Any special behaviors required by the algorithm?
948
949 if (removeSelfEdges)
950 graphFlags_.set(REMOVE_SELF_EDGES);
951
952 if (needConsecutiveGlobalIds)
953 graphFlags_.set(GENERATE_CONSECUTIVE_IDS);
954
955 // How does user input map to vertices and edges?
956
957 if (inputType_ == MatrixAdapterType){
958 if (objectOfInterest == defString ||
959 objectOfInterest == std::string("matrix_rows") )
960 graphFlags_.set(VERTICES_ARE_MATRIX_ROWS);
961 else if (objectOfInterest == std::string("matrix_columns"))
962 graphFlags_.set(VERTICES_ARE_MATRIX_COLUMNS);
963 else if (objectOfInterest == std::string("matrix_nonzeros"))
964 graphFlags_.set(VERTICES_ARE_MATRIX_NONZEROS);
965 }
966
967 else if (inputType_ == MeshAdapterType){
968 if (objectOfInterest == defString ||
969 objectOfInterest == std::string("mesh_nodes") )
970 graphFlags_.set(VERTICES_ARE_MESH_NODES);
971 else if (objectOfInterest == std::string("mesh_elements"))
972 graphFlags_.set(VERTICES_ARE_MESH_ELEMENTS);
973 }
974 }
975}
976
977} // namespace Zoltan2
978#endif
Serial greedy first-fit graph coloring (local graph only)
Defines the EvaluatePartition class.
#define Z2_FORWARD_EXCEPTIONS
Forward an exception back through call stack.
Defines the GraphModel interface.
Defines the IdentifierModel interface.
Define IntegerRangeList validator.
Defines the PartitioningSolution class.
Defines the Problem base class.
#define HELLO
static void getValidParameters(ParameterList &pl)
Set up validators specific to this algorithm.
static void getValidParameters(ParameterList &pl)
Set up validators specific to this algorithm.
static void getValidParameters(ParameterList &)
Set up validators specific to this algorithm.
static void getValidParameters(ParameterList &pl)
Set up validators specific to this algorithm.
static void getValidParameters(ParameterList &pl)
Set up validators specific to this algorithm.
The user parameters, debug, timing and memory profiling output objects, and error checking methods.
static RCP< Teuchos::BoolParameterEntryValidator > getBoolValidator()
Exists to make setting up validators less cluttered.
static RCP< Teuchos::AnyNumberParameterEntryValidator > getAnyDoubleValidator()
Exists to make setting up validators less cluttered.
int numProcs_
number of processes (relative to comm_)
static RCP< Teuchos::AnyNumberParameterEntryValidator > getAnyIntValidator()
Exists to make setting up validators less cluttered.
void localBugAssertion(const char *file, int lineNum, const char *msg, bool ok, AssertionLevel level) const
Test for valid library behavior on local process only.
Teuchos::ParameterList & getParametersNonConst()
Returns a reference to a non-const copy of the parameters.
PartitioningProblem sets up partitioning problems for the user.
static void getValidParameters(ParameterList &pl)
Set up validators specific to this Problem.
ArrayRCP< ArrayRCP< part_t > > partIds_
virtual void processAlgorithmName(const std::string &algorithm, const std::string &defString, const std::string &model, Environment &env, bool &removeSelfEdges, bool &isGraphType, bool &needConsecutiveGlobalIds)
const PartitioningSolution< Adapter > & getSolution()
Get the solution to the 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.
ArrayRCP< ArrayRCP< scalar_t > > partSizes_
PartitioningProblem(Adapter *A, ParameterList *p, const RCP< const Teuchos::Comm< int > > &comm)
Constructor where Teuchos communicator is specified.
void solve(bool updateInputData=true)
Direct the problem to create a solution.
RCP< PartitioningSolution< Adapter > > solution_
PartitioningProblem(Adapter *A, ParameterList *p)
Constructor where communicator is the Teuchos default.
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.
Problem base class from which other classes (PartitioningProblem, ColoringProblem,...
static void getValidParameters(ParameterList &pl)
Set up validators specific to this algorithm.
Created by mbenlioglu on Aug 31, 2020.
std::bitset< NUM_MODEL_FLAGS > modelFlag_t
@ BASIC_ASSERTION
fast typical checks for valid arguments
BaseAdapterType
An enum to identify general types of adapters.
@ VectorAdapterType
vector data
@ InvalidAdapterType
unused value
@ GraphAdapterType
graph data
@ MatrixAdapterType
matrix data
@ MeshAdapterType
mesh data
@ IdentifierAdapterType
identifier data, just a list of IDs
@ VERTICES_ARE_MATRIX_ROWS
use matrix rows as graph vertices
@ VERTICES_ARE_MESH_ELEMENTS
use mesh elements as vertices
@ BUILD_SUBSET_GRAPH
ignore invalid neighbors
@ GENERATE_CONSECUTIVE_IDS
algorithm requires consecutive ids
@ SYMMETRIZE_INPUT_TRANSPOSE
model must symmetrize input
@ SYMMETRIZE_INPUT_BIPARTITE
model must symmetrize input
@ REMOVE_SELF_EDGES
algorithm requires no self edges
@ VERTICES_ARE_MESH_NODES
use mesh nodes as vertices
@ VERTICES_ARE_MATRIX_COLUMNS
use columns as graph vertices
@ VERTICES_ARE_MATRIX_NONZEROS
use nonzeros as graph vertices
SparseMatrixAdapter_t::part_t part_t