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
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");
640
641 try{
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.
part_t getAssignedProcForTask(part_t taskId)
getAssignedProcForTask function, returns the assigned processor id for the given task
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.
GraphModel defines the interface required for graph models.
MachineRepresentation Class Base class for representing machine coordinates, networks,...
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.
A PartitioningSolution is a solution to a partitioning problem.
Problem base class from which other classes (PartitioningProblem, ColoringProblem,...
Multi Jagged coordinate partitioning algorithm.
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
@ MACRO_TIMERS
Time an algorithm (or other entity) as a whole.
@ DETAILED_STATUS
sub-steps, each method's entry and exit
@ 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