45 #ifndef _ZOLTAN2_ALGPULP_HPP_
46 #define _ZOLTAN2_ALGPULP_HPP_
59 #ifndef HAVE_ZOLTAN2_PULP
65 template <
typename Adapter>
71 const RCP<
const Comm<int> > &,
72 const RCP<const base_adapter_t> &
75 throw std::runtime_error(
76 "BUILD ERROR: PuLP requested but not compiled into Zoltan2.\n"
77 "Please set CMake flag TPL_ENABLE_PuLP:BOOL=ON.");
94 #ifdef HAVE_ZOLTAN2_PULP
100 #ifndef HAVE_ZOLTAN2_MPI
103 #include "xtrapulp.h"
108 template <
typename Adapter>
109 class AlgPuLP :
public Algorithm<Adapter>
115 typedef typename Adapter::offset_t offset_t;
116 typedef typename Adapter::scalar_t
scalar_t;
119 typedef typename Adapter::userCoord_t userCoord_t;
131 AlgPuLP(
const RCP<const Environment> &env__,
132 const RCP<
const Comm<int> > &problemComm__,
133 const RCP<
const IdentifierAdapter<user_t> > &adapter__) :
134 env(env__), problemComm(problemComm__), adapter(adapter__)
136 std::string errStr =
"cannot build GraphModel from IdentifierAdapter, ";
137 errStr +=
"PuLP requires Graph, Matrix, or Mesh Adapter";
138 throw std::runtime_error(errStr);
141 AlgPuLP(
const RCP<const Environment> &env__,
142 const RCP<
const Comm<int> > &problemComm__,
143 const RCP<
const VectorAdapter<user_t> > &adapter__) :
144 env(env__), problemComm(problemComm__), adapter(adapter__)
146 std::string errStr =
"cannot build GraphModel from VectorAdapter, ";
147 errStr +=
"PuLP requires Graph, Matrix, or Mesh Adapter";
148 throw std::runtime_error(errStr);
151 AlgPuLP(
const RCP<const Environment> &env__,
152 const RCP<
const Comm<int> > &problemComm__,
153 const RCP<
const GraphAdapter<user_t,userCoord_t> > &adapter__) :
154 env(env__), problemComm(problemComm__), adapter(adapter__)
162 AlgPuLP(
const RCP<const Environment> &env__,
163 const RCP<
const Comm<int> > &problemComm__,
164 const RCP<
const MatrixAdapter<user_t,userCoord_t> > &adapter__) :
165 env(env__), problemComm(problemComm__), adapter(adapter__)
170 const ParameterList &pl = env->getParameters();
171 const Teuchos::ParameterEntry *pe;
173 std::string defString(
"default");
174 std::string objectOfInterest(defString);
175 pe = pl.getEntryPtr(
"objects_to_partition");
177 objectOfInterest = pe->getValue<std::string>(&objectOfInterest);
179 if (objectOfInterest == defString ||
180 objectOfInterest == std::string(
"matrix_rows") )
182 else if (objectOfInterest == std::string(
"matrix_columns"))
184 else if (objectOfInterest == std::string(
"matrix_nonzeros"))
190 AlgPuLP(
const RCP<const Environment> &env__,
191 const RCP<
const Comm<int> > &problemComm__,
192 const RCP<
const MeshAdapter<user_t> > &adapter__) :
193 env(env__), problemComm(problemComm__), adapter(adapter__)
198 const ParameterList &pl = env->getParameters();
199 const Teuchos::ParameterEntry *pe;
201 std::string defString(
"default");
202 std::string objectOfInterest(defString);
203 pe = pl.getEntryPtr(
"objects_to_partition");
205 objectOfInterest = pe->getValue<std::string>(&objectOfInterest);
207 if (objectOfInterest == defString ||
208 objectOfInterest == std::string(
"mesh_nodes") )
210 else if (objectOfInterest == std::string(
"mesh_elements"))
220 pl.set(
"pulp_vert_imbalance", 1.1,
"vertex imbalance tolerance, ratio of "
221 "maximum load over average load",
224 pl.set(
"pulp_edge_imbalance", 1.1,
"edge imbalance tolerance, ratio of "
225 "maximum load over average load",
228 pl.set(
"pulp_imbalance", 1.1,
"multiweight imbalance tolerance, ratio of "
229 "maximum load over average load",
233 pl.set(
"pulp_lp_init",
false,
"perform label propagation-based "
237 pl.set(
"pulp_minimize_maxcut",
false,
"perform per-part max cut "
241 pl.set(
"pulp_verbose",
false,
"verbose output",
245 pl.set(
"pulp_do_repart",
false,
"perform repartitioning",
251 void partition(
const RCP<PartitioningSolution<Adapter> > &solution);
257 int* scale_weights(
size_t n,
int nWgt,
258 ArrayView<StridedData<lno_t, scalar_t> > fwgts);
260 const RCP<const Environment> env;
261 const RCP<const Comm<int> > problemComm;
262 const RCP<const base_adapter_t> adapter;
263 RCP<const GraphModel<base_adapter_t> > model;
268 template <
typename Adapter>
269 void AlgPuLP<Adapter>::buildModel(
modelFlag_t &flags)
271 const ParameterList &pl = env->getParameters();
272 const Teuchos::ParameterEntry *pe;
274 std::string defString(
"default");
275 std::string symParameter(defString);
276 pe = pl.getEntryPtr(
"symmetrize_graph");
278 symParameter = pe->getValue<std::string>(&symParameter);
279 if (symParameter == std::string(
"transpose"))
281 else if (symParameter == std::string(
"bipartite"))
284 bool sgParameter =
false;
285 pe = pl.getEntryPtr(
"subset_graph");
287 sgParameter = pe->getValue(&sgParameter);
293 #ifndef HAVE_ZOLTAN2_MPI
297 this->model = rcp(
new GraphModel<base_adapter_t>(this->adapter, this->env,
298 this->problemComm, flags));
307 template <
typename Adapter>
309 const RCP<PartitioningSolution<Adapter> > &solution
314 size_t numGlobalParts = solution->getTargetGlobalNumberOfParts();
316 int num_parts = (int)numGlobalParts;
323 int np = problemComm->getSize();
326 const size_t modelVerts = model->getLocalNumVertices();
327 const size_t modelEdges = model->getLocalNumEdges();
328 int num_verts = (int)modelVerts;
329 long num_edges = (long)modelEdges;
334 ArrayView<const gno_t> vtxIDs;
335 ArrayView<StridedData<lno_t, scalar_t> > vwgts;
336 size_t nVtx = model->getVertexList(vtxIDs, vwgts);
337 int nVwgts = model->getNumWeightsPerVertex();
340 #ifndef HAVE_ZOLTAN2_MPI
343 std::cerr <<
"Warning: NumWeightsPerVertex is " << nVwgts
344 <<
" but PuLP allows only one weight. "
345 <<
" Zoltan2 will use only the first weight per vertex."
349 std::unique_ptr<int[]> vertex_weights;
350 long vertex_weights_sum = 0;
353 vertex_weights = std::unique_ptr<int[]>(scale_weights(nVtx, nVwgts, vwgts));
355 for (
int i = 0; i < num_verts; ++i)
356 vertex_weights_sum += (
long)vertex_weights[i];
358 vertex_weights = std::unique_ptr<int[]>(
nullptr);
362 std::unique_ptr<int[]> vertex_weights;
364 vertex_weights = std::unique_ptr<int[]>(scale_weights(nVtx, nVwgts, vwgts));
366 vertex_weights = std::unique_ptr<int[]>(
nullptr);
371 ArrayView<const gno_t> adjs;
372 ArrayView<const offset_t> offsets;
373 ArrayView<StridedData<lno_t, scalar_t> > ewgts;
374 size_t nEdge = model->getEdgeList(adjs, offsets, ewgts);
375 int nEwgts = model->getNumWeightsPerEdge();
377 std::cerr <<
"Warning: NumWeightsPerEdge is " << nEwgts
378 <<
" but PuLP/XtraPuLP allows only one weight. "
379 <<
" Zoltan2 will use only the first weight per edge."
383 std::unique_ptr<int[]> edge_weights;
386 edge_weights = std::unique_ptr<int[]>(scale_weights(nEdge, nEwgts, ewgts));
390 vertex_weights = std::unique_ptr<int[]>(
new int[nVtx]);
392 for (
size_t i = 0; i < nVtx; ++i) {
393 vertex_weights[i] = 1;
399 edge_weights = std::unique_ptr<int[]>(
new int[nEdge]);
400 for (
size_t i = 0; i < nEdge; ++i) {
404 edge_weights = std::unique_ptr<int[]>(
nullptr);
407 #ifndef HAVE_ZOLTAN2_MPI
409 int* out_edges =
nullptr;
410 long* out_offsets =
nullptr;
414 pulp_graph_t g = {num_verts, num_edges,
415 out_edges, out_offsets,
416 vertex_weights.get(), edge_weights.get(),
421 unsigned long* out_edges =
nullptr;
422 unsigned long* out_offsets =
nullptr;
426 const size_t modelVertsGlobal = model->getGlobalNumVertices();
427 const size_t modelEdgesGlobal = model->getGlobalNumEdges();
428 unsigned long num_verts_global = (
unsigned long)modelVertsGlobal;
429 unsigned long num_edges_global = (
unsigned long)modelEdgesGlobal;
431 unsigned long* global_ids =
nullptr;
434 ArrayView<size_t> vtxDist;
435 model->getVertexDist(vtxDist);
436 unsigned long* verts_per_rank =
new unsigned long[np+1];
437 for (
int i = 0; i < np+1; ++i)
438 verts_per_rank[i] = vtxDist[i];
441 create_xtrapulp_dist_graph(&g, num_verts_global, num_edges_global,
442 (
unsigned long)num_verts, (
unsigned long)num_edges,
443 out_edges, out_offsets, global_ids, verts_per_rank,
444 nVwgts, vertex_weights.get(), edge_weights.get());
450 ArrayRCP<part_t> partList(
new part_t[num_verts], 0, num_verts,
true);
451 int* parts =
nullptr;
452 if (num_verts && (
sizeof(
int) ==
sizeof(
part_t))) {
454 parts = (
int *)partList.getRawPtr();
458 parts =
new int[num_verts];
465 const Teuchos::ParameterList &pl = env->getParameters();
466 const Teuchos::ParameterEntry *pe;
474 bool do_lp_init =
false;
475 bool do_bfs_init =
true;
476 bool do_edge_bal =
false;
477 bool do_repart =
false;
478 bool do_maxcut_min =
false;
479 bool verbose_output =
false;
482 pe = pl.getEntryPtr(
"pulp_lp_init");
483 if (pe) do_lp_init = pe->getValue(&do_lp_init);
484 if (do_lp_init) do_bfs_init =
false;
487 pe = pl.getEntryPtr(
"pulp_minimize_maxcut");
489 do_maxcut_min = pe->getValue(&do_maxcut_min);
492 if (do_maxcut_min) do_edge_bal =
true;
495 pe = pl.getEntryPtr(
"pulp_do_repart");
497 do_repart = pe->getValue(&do_repart);
505 std::string errStr =
"repartitioning within (Xtra)PuLP is ";
506 errStr +=
"currently unsupported.";
507 throw std::runtime_error(errStr);
512 double vert_imbalance = 1.1;
513 double edge_imbalance = 1.1;
514 double imbalance = 1.1;
516 pe = pl.getEntryPtr(
"pulp_vert_imbalance");
517 if (pe) vert_imbalance = pe->getValue<
double>(&vert_imbalance);
518 pe = pl.getEntryPtr(
"pulp_edge_imbalance");
520 edge_imbalance = pe->getValue<
double>(&edge_imbalance);
524 pe = pl.getEntryPtr(
"pulp_imbalance");
525 if (pe) imbalance = pe->getValue<
double>(&imbalance);
527 if (vert_imbalance < 1.0)
528 throw std::runtime_error(
"pulp_vert_imbalance must be '1.0' or greater.");
529 if (edge_imbalance < 1.0)
530 throw std::runtime_error(
"pulp_edge_imbalance must be '1.0' or greater.");
532 throw std::runtime_error(
"pulp_imbalance must be '1.0' or greater.");
536 pe = pl.getEntryPtr(
"pulp_verbose");
537 if (pe) verbose_output = pe->getValue(&verbose_output);
540 int pulp_seed = rand();
541 pe = pl.getEntryPtr(
"pulp_seed");
542 if (pe) pulp_seed = pe->getValue(&pulp_seed);
545 if (verbose_output) {
546 printf(
"procid: %d, n: %i, m: %li, vb: %f, eb: %f, imb: %f, p: %i\n",
547 problemComm->getRank(),
548 num_verts, num_edges,
549 vert_imbalance, edge_imbalance, imbalance, num_parts);
553 #ifndef HAVE_ZOLTAN2_MPI
555 pulp_part_control_t ppc = {vert_imbalance, edge_imbalance,
556 do_lp_init, do_bfs_init, do_repart,
557 do_edge_bal, do_maxcut_min,
558 verbose_output, pulp_seed};
560 ierr = pulp_run(&g, &ppc, parts, num_parts);
562 env->globalInputAssertion(__FILE__, __LINE__,
"pulp_run",
566 std::unique_ptr<double[]> constraints;
568 constraints = std::unique_ptr<double[]>(
new double[nVwgts]);
569 for (
int i = 0; i < nVwgts; ++i) {
570 constraints[i] = imbalance;
573 constraints = std::unique_ptr<double[]>(
nullptr);
577 pulp_part_control_t ppc = {
578 vert_imbalance, edge_imbalance,
579 constraints.get(), nVwgts,
580 do_lp_init, do_bfs_init, do_repart,
581 do_edge_bal, do_maxcut_min,
582 verbose_output, pulp_seed};
584 ierr = xtrapulp_run(&g, &ppc, parts, num_parts);
586 env->globalInputAssertion(__FILE__, __LINE__,
"xtrapulp_run",
592 if ( (
sizeof(
int) !=
sizeof(
part_t)) || (num_verts == 0) ) {
593 for (
int i = 0; i < num_verts; i++)
594 partList[i] = parts[i];
598 solution->setParts(partList);
600 env->memory(
"Zoltan2-(Xtra)PuLP: After creating solution");
603 #ifndef HAVE_ZOLTAN2_MPI
627 template <
typename Adapter>
628 int* AlgPuLP<Adapter>::scale_weights(
629 size_t nVtx,
int nWgt,
631 typename Adapter::scalar_t> > fwgts
634 const double INT_EPSILON = 1e-5;
636 int *iwgts =
new int[nVtx*nWgt];
637 int *nonint_local =
new int[nWgt+nWgt];
638 int *nonint = nonint_local + nWgt;
640 double *sum_wgt_local =
new double[nWgt*4];
641 double *max_wgt_local = sum_wgt_local + nWgt;
642 double *sum_wgt = max_wgt_local + nWgt;
643 double *max_wgt = sum_wgt + nWgt;
645 for (
int i = 0; i < nWgt; i++) {
647 sum_wgt_local[i] = 0.0;
648 max_wgt_local[i] = 0.0;
653 for (
int j = 0; j < nWgt; j++) {
654 for (
size_t i = 0; i < nVtx; i++) {
655 double fw = double(fwgts[j][i]);
656 if (!nonint_local[j]) {
657 int tmp = (int) floor(fw + .5);
658 if (fabs((
double)tmp-fw) > INT_EPSILON) {
662 sum_wgt_local[j] += fw;
663 if (fw > max_wgt_local[j]) max_wgt_local[j] = fw;
667 Teuchos::reduceAll<int,int> (*problemComm, Teuchos::REDUCE_MAX, nWgt,
668 nonint_local, nonint);
669 Teuchos::reduceAll<int,double>(*problemComm, Teuchos::REDUCE_SUM, nWgt,
670 sum_wgt_local, sum_wgt);
671 Teuchos::reduceAll<int,double>(*problemComm, Teuchos::REDUCE_MAX, nWgt,
672 max_wgt_local, max_wgt);
674 const double max_wgt_sum = double(std::numeric_limits<int>::max()/8);
675 for (
int j = 0; j < nWgt; j++) {
680 if (nonint[j] || (max_wgt[j]<=INT_EPSILON) || (sum_wgt[j]>max_wgt_sum)) {
682 if (sum_wgt[j] != 0.) scale = max_wgt_sum/sum_wgt[j];
686 for (
size_t i = 0; i < nVtx; i++)
687 iwgts[i*nWgt+j] = (
int) ceil(
double(fwgts[j][i])*scale);
690 delete [] nonint_local;
691 delete [] sum_wgt_local;
699 #endif // HAVE_ZOLTAN2_PULP
use columns as graph vertices
Zoltan2::BaseAdapter< userTypes_t > base_adapter_t
use mesh nodes as vertices
virtual void partition(const RCP< PartitioningSolution< Adapter > > &)
Partitioning method.
fast typical checks for valid arguments
Adapter::base_adapter_t base_adapter_t
static RCP< Teuchos::BoolParameterEntryValidator > getBoolValidator()
Exists to make setting up validators less cluttered.
algorithm requires consecutive ids
std::bitset< NUM_MODEL_FLAGS > modelFlag_t
model must symmetrize input
map_t::global_ordinal_type gno_t
model must symmetrize input
Defines the PartitioningSolution class.
static RCP< Teuchos::AnyNumberParameterEntryValidator > getAnyDoubleValidator()
Exists to make setting up validators less cluttered.
sub-steps, each method's entry and exit
SparseMatrixAdapter_t::part_t part_t
use matrix rows as graph vertices
algorithm requires no self edges
Adapter::scalar_t scalar_t
use nonzeros as graph vertices
Algorithm defines the base class for all algorithms.
map_t::local_ordinal_type lno_t
static RCP< Teuchos::AnyNumberParameterEntryValidator > getAnyIntValidator()
Exists to make setting up validators less cluttered.
Traits class to handle conversions between gno_t/lno_t and TPL data types (e.g., ParMETIS's idx_t...
use mesh elements as vertices
static void ASSIGN_ARRAY(first_t **a, ArrayView< second_t > &b)
Defines the GraphModel interface.
A gathering of useful namespace methods.
static void DELETE_ARRAY(first_t **a)
model represents graph within only one rank
static void getValidParameters(ParameterList &)
Set up validators specific to this algorithm.
AlgPuLP(const RCP< const Environment > &, const RCP< const Comm< int > > &, const RCP< const base_adapter_t > &)
Zoltan2::BasicUserTypes< zscalar_t, zlno_t, zgno_t > user_t