45 #ifndef _ZOLTAN2_ALGPULP_HPP_ 46 #define _ZOLTAN2_ALGPULP_HPP_ 59 #ifndef HAVE_ZOLTAN2_PULP 65 template <
typename Adapter>
70 AlgPuLP(
const RCP<const Environment> &env,
71 const RCP<
const Comm<int> > &problemComm,
72 const RCP<const base_adapter_t> &adapter
75 throw std::runtime_error(
76 "BUILD ERROR: PuLP requested but not compiled into Zoltan2.\n" 77 "Please set CMake flag Zoltan2_ENABLE_PuLP:BOOL=ON.");
84 pl.set(
"pulp_vert_imbalance", 1.1,
"vertex imbalance tolerance, ratio of " 85 "maximum load over average load",
88 pl.set(
"pulp_edge_imbalance", 1.1,
"edge imbalance tolerance, ratio of " 89 "maximum load over average load",
93 pl.set(
"pulp_lp_init",
false,
"perform label propagation-based " 97 pl.set(
"pulp_minimize_maxcut",
false,
"perform per-part max cut " 101 pl.set(
"pulp_verbose",
false,
"verbose output",
105 pl.set(
"pulp_do_repart",
false,
"perform repartitioning",
118 #ifdef HAVE_ZOLTAN2_PULP 124 #ifndef HAVE_ZOLTAN2_MPI 127 #include "xtrapulp.h" 134 template <
typename Adapter>
135 class AlgPuLP :
public Algorithm<Adapter>
139 typedef typename Adapter::lno_t
lno_t;
140 typedef typename Adapter::gno_t
gno_t;
141 typedef typename Adapter::scalar_t
scalar_t;
142 typedef typename Adapter::part_t
part_t;
143 typedef typename Adapter::user_t user_t;
144 typedef typename Adapter::userCoord_t userCoord_t;
156 AlgPuLP(
const RCP<const Environment> &env__,
157 const RCP<
const Comm<int> > &problemComm__,
158 const RCP<
const IdentifierAdapter<user_t> > &adapter__) :
159 env(env__), problemComm(problemComm__), adapter(adapter__)
161 std::string errStr =
"cannot build GraphModel from IdentifierAdapter, ";
162 errStr +=
"PuLP requires Graph, Matrix, or Mesh Adapter";
163 throw std::runtime_error(errStr);
166 AlgPuLP(
const RCP<const Environment> &env__,
167 const RCP<
const Comm<int> > &problemComm__,
168 const RCP<
const VectorAdapter<user_t> > &adapter__) :
169 env(env__), problemComm(problemComm__), adapter(adapter__)
171 std::string errStr =
"cannot build GraphModel from VectorAdapter, ";
172 errStr +=
"PuLP requires Graph, Matrix, or Mesh Adapter";
173 throw std::runtime_error(errStr);
176 AlgPuLP(
const RCP<const Environment> &env__,
177 const RCP<
const Comm<int> > &problemComm__,
178 const RCP<
const GraphAdapter<user_t,userCoord_t> > &adapter__) :
179 env(env__), problemComm(problemComm__), adapter(adapter__)
187 AlgPuLP(
const RCP<const Environment> &env__,
188 const RCP<
const Comm<int> > &problemComm__,
189 const RCP<
const MatrixAdapter<user_t,userCoord_t> > &adapter__) :
190 env(env__), problemComm(problemComm__), adapter(adapter__)
195 const ParameterList &pl = env->getParameters();
196 const Teuchos::ParameterEntry *pe;
198 std::string defString(
"default");
199 std::string objectOfInterest(defString);
200 pe = pl.getEntryPtr(
"objects_to_partition");
202 objectOfInterest = pe->getValue<std::string>(&objectOfInterest);
204 if (objectOfInterest == defString ||
205 objectOfInterest == std::string(
"matrix_rows") )
207 else if (objectOfInterest == std::string(
"matrix_columns"))
209 else if (objectOfInterest == std::string(
"matrix_nonzeros"))
215 AlgPuLP(
const RCP<const Environment> &env__,
216 const RCP<
const Comm<int> > &problemComm__,
217 const RCP<
const MeshAdapter<user_t> > &adapter__) :
218 env(env__), problemComm(problemComm__), adapter(adapter__)
223 const ParameterList &pl = env->getParameters();
224 const Teuchos::ParameterEntry *pe;
226 std::string defString(
"default");
227 std::string objectOfInterest(defString);
228 pe = pl.getEntryPtr(
"objects_to_partition");
230 objectOfInterest = pe->getValue<std::string>(&objectOfInterest);
232 if (objectOfInterest == defString ||
233 objectOfInterest == std::string(
"mesh_nodes") )
235 else if (objectOfInterest == std::string(
"mesh_elements"))
241 void partition(
const RCP<PartitioningSolution<Adapter> > &solution);
247 void scale_weights(
size_t n, StridedData<lno_t, scalar_t> &fwgts,
250 const RCP<const Environment> env;
251 const RCP<const Comm<int> > problemComm;
252 const RCP<const base_adapter_t> adapter;
253 RCP<const GraphModel<base_adapter_t> > model;
258 template <
typename Adapter>
259 void AlgPuLP<Adapter>::buildModel(
modelFlag_t &flags)
261 const ParameterList &pl = env->getParameters();
262 const Teuchos::ParameterEntry *pe;
264 std::string defString(
"default");
265 std::string symParameter(defString);
266 pe = pl.getEntryPtr(
"symmetrize_graph");
268 symParameter = pe->getValue<std::string>(&symParameter);
269 if (symParameter == std::string(
"transpose"))
271 else if (symParameter == std::string(
"bipartite"))
274 bool sgParameter =
false;
275 pe = pl.getEntryPtr(
"subset_graph");
277 sgParameter = pe->getValue(&sgParameter);
283 #ifndef HAVE_ZOLTAN2_MPI 287 this->model = rcp(
new GraphModel<base_adapter_t>(this->adapter, this->env,
288 this->problemComm, flags));
296 template <
typename Adapter>
298 const RCP<PartitioningSolution<Adapter> > &solution
303 size_t numGlobalParts = solution->getTargetGlobalNumberOfParts();
305 int num_parts = (int)numGlobalParts;
312 int np = problemComm->getSize();
315 const size_t modelVerts = model->getLocalNumVertices();
316 const size_t modelEdges = model->getLocalNumEdges();
317 int num_verts = (int)modelVerts;
318 long num_edges = (long)modelEdges;
323 ArrayView<const gno_t> vtxIDs;
324 ArrayView<StridedData<lno_t, scalar_t> > vwgts;
325 size_t nVtx = model->getVertexList(vtxIDs, vwgts);
326 int nVwgts = model->getNumWeightsPerVertex();
328 std::cerr <<
"Warning: NumWeightsPerVertex is " << nVwgts
329 <<
" but PuLP allows only one weight. " 330 <<
" Zoltan2 will use only the first weight per vertex." 334 int* vertex_weights = NULL;
335 long vertex_weights_sum = 0;
337 vertex_weights =
new int[nVtx];
338 scale_weights(nVtx, vwgts[0], vertex_weights);
339 for (
int i = 0; i < num_verts; ++i)
340 vertex_weights_sum += vertex_weights[i];
344 ArrayView<const gno_t> adjs;
345 ArrayView<const lno_t> offsets;
346 ArrayView<StridedData<lno_t, scalar_t> > ewgts;
347 size_t nEdge = model->getEdgeList(adjs, offsets, ewgts);
348 int nEwgts = model->getNumWeightsPerEdge();
350 std::cerr <<
"Warning: NumWeightsPerEdge is " << nEwgts
351 <<
" but PuLP allows only one weight. " 352 <<
" Zoltan2 will use only the first weight per edge." 356 int* edge_weights = NULL;
358 edge_weights =
new int[nEdge];
359 scale_weights(nEdge, ewgts[0], edge_weights);
362 #ifndef HAVE_ZOLTAN2_MPI 364 int* out_edges = NULL;
365 long* out_offsets = NULL;
369 pulp_graph_t g = {num_verts, num_edges,
370 out_edges, out_offsets,
371 vertex_weights, edge_weights, vertex_weights_sum};
375 unsigned long* out_edges = NULL;
376 unsigned long* out_offsets = NULL;
380 const size_t modelVertsGlobal = model->getGlobalNumVertices();
381 const size_t modelEdgesGlobal = model->getGlobalNumEdges();
382 unsigned long num_verts_global = (
unsigned long)modelVertsGlobal;
383 unsigned long num_edges_global = (
unsigned long)modelEdgesGlobal;
385 unsigned long* global_ids = NULL;
388 ArrayView<size_t> vtxDist;
389 model->getVertexDist(vtxDist);
390 unsigned long* verts_per_rank =
new unsigned long[np+1];
391 for (
int i = 0; i < np+1; ++i)
392 verts_per_rank[i] = vtxDist[i];
395 create_xtrapulp_dist_graph(&g, num_verts_global, num_edges_global,
396 (
unsigned long)num_verts, (
unsigned long)num_edges,
397 out_edges, out_offsets, global_ids, verts_per_rank,
398 vertex_weights, edge_weights);
404 ArrayRCP<part_t> partList(
new part_t[num_verts], 0, num_verts,
true);
406 if (num_verts && (
sizeof(
int) ==
sizeof(part_t))) {
408 parts = (
int *) partList.getRawPtr();
412 parts =
new int[num_verts];
419 const Teuchos::ParameterList &pl = env->getParameters();
420 const Teuchos::ParameterEntry *pe;
427 bool do_lp_init =
false;
428 bool do_bfs_init =
true;
429 bool do_edge_bal =
false;
430 bool do_repart =
false;
431 bool do_maxcut_min =
false;
432 bool verbose_output =
false;
435 pe = pl.getEntryPtr(
"pulp_lp_init");
436 if (pe) do_lp_init = pe->getValue(&do_lp_init);
437 if (do_lp_init) do_bfs_init =
false;
440 pe = pl.getEntryPtr(
"pulp_minimize_maxcut");
442 do_maxcut_min = pe->getValue(&do_maxcut_min);
445 if (do_maxcut_min) do_edge_bal =
true;
448 pe = pl.getEntryPtr(
"pulp_do_repart");
450 do_repart = pe->getValue(&do_repart);
460 double vert_imbalance = 1.1;
461 double edge_imbalance = 1.1;
463 pe = pl.getEntryPtr(
"pulp_vert_imbalance");
464 if (pe) vert_imbalance = pe->getValue<
double>(&vert_imbalance);
465 pe = pl.getEntryPtr(
"pulp_edge_imbalance");
467 edge_imbalance = pe->getValue<
double>(&edge_imbalance);
472 if (vert_imbalance < 1.0)
473 throw std::runtime_error(
"pulp_vert_imbalance must be '1.0' or greater.");
474 if (edge_imbalance < 1.0)
475 throw std::runtime_error(
"pulp_edge_imbalance must be '1.0' or greater.");
479 pe = pl.getEntryPtr(
"pulp_verbose");
480 if (pe) verbose_output = pe->getValue(&verbose_output);
483 int pulp_seed = rand();
484 pe = pl.getEntryPtr(
"pulp_seed");
485 if (pe) pulp_seed = pe->getValue(&pulp_seed);
488 pulp_part_control_t ppc = {vert_imbalance, edge_imbalance,
489 do_lp_init, do_bfs_init, do_repart,
490 do_edge_bal, do_maxcut_min,
491 verbose_output, pulp_seed};
494 if (verbose_output) {
495 printf(
"procid: %d, n: %i, m: %li, vb: %lf, eb: %lf, p: %i\n",
496 problemComm->getRank(),
497 num_verts, num_edges, vert_imbalance, edge_imbalance, num_parts);
501 #ifndef HAVE_ZOLTAN2_MPI 502 ierr = pulp_run(&g, &ppc, parts, num_parts);
504 env->globalInputAssertion(__FILE__, __LINE__,
"pulp_run",
507 ierr = xtrapulp_run(&g, &ppc, parts, num_parts);
508 env->globalInputAssertion(__FILE__, __LINE__,
"xtrapulp_run",
515 if ((
sizeof(
int) !=
sizeof(part_t)) || (num_verts == 0)) {
516 for (
int i = 0; i < num_verts; i++) partList[i] = parts[i];
520 solution->setParts(partList);
522 env->memory(
"Zoltan2-(Xtra)PuLP: After creating solution");
525 #ifndef HAVE_ZOLTAN2_MPI 547 template <
typename Adapter>
548 void AlgPuLP<Adapter>::scale_weights(
550 StridedData<typename Adapter::lno_t, typename Adapter::scalar_t> &fwgts,
554 const double INT_EPSILON = 1e-5;
555 const double MAX_NUM = 1e9;
558 double sum_wgt = 0.0;
559 double max_wgt = 0.0;
563 for (
size_t i = 0; i < n; i++) {
564 double fw = double(fwgts[i]);
566 int tmp = (int) floor(fw + .5);
567 if (fabs((
double)tmp-fw) > INT_EPSILON) {
572 if (fw > max_wgt) max_wgt = fw;
578 if (nonint || (max_wgt <= INT_EPSILON) || (sum_wgt > MAX_NUM)) {
580 if (sum_wgt != 0.0) scale = MAX_NUM/sum_wgt;
584 for (
size_t i = 0; i < n; i++)
585 iwgts[i] = (
int) ceil(
double(fwgts[i])*scale);
592 #endif // HAVE_ZOLTAN2_PULP use columns as graph vertices
Zoltan2::BaseAdapter< userTypes_t > base_adapter_t
use mesh nodes as vertices
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
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
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.
static RCP< Teuchos::AnyNumberParameterEntryValidator > getAnyIntValidator()
Exists to make setting up validators less cluttered.
virtual void partition(const RCP< PartitioningSolution< Adapter > > &solution)
Partitioning method.
Traits class to handle conversions between gno_t/lno_t and TPL data types (e.g., ParMETIS's idx_t...
static void getValidParameters(ParameterList &pl)
Set up validators specific to this algorithm.
use mesh elements as vertices
static void ASSIGN_ARRAY(first_t **a, ArrayView< second_t > &b)
Defines the GraphModel interface.
AlgPuLP(const RCP< const Environment > &env, const RCP< const Comm< int > > &problemComm, const RCP< const base_adapter_t > &adapter)
A gathering of useful namespace methods.
static void DELETE_ARRAY(first_t **a)
model represents graph within only one rank