45 #ifndef _ZOLTAN2_ALGPARMETIS_HPP_
46 #define _ZOLTAN2_ALGPARMETIS_HPP_
59 #ifndef HAVE_ZOLTAN2_PARMETIS
65 template <
typename Adapter,
typename Model=GraphModel<
typename Adapter::base_adapter_t>>
70 const RCP<
const Comm<int> > &,
71 const RCP<const typename Adapter::base_adapter_t> &,
74 throw std::runtime_error(
75 "BUILD ERROR: ParMETIS requested but not compiled into Zoltan2.\n"
76 "Please set CMake flag Zoltan2_ENABLE_ParMETIS:BOOL=ON.");
86 #ifdef HAVE_ZOLTAN2_PARMETIS
88 #ifndef HAVE_ZOLTAN2_MPI
92 #error "TPL ParMETIS requires compilation with MPI. Configure with -DTPL_ENABLE_MPI:BOOL=ON or -DZoltan2_ENABLE_ParMETIS:BOOL=OFF"
100 #if (PARMETIS_MAJOR_VERSION < 4)
104 #error "Specified version of ParMETIS is not compatible with Zoltan2; upgrade to ParMETIS v4 or later, or build Zoltan2 without ParMETIS."
112 template <
typename Adapter,
typename Model=GraphModel<
typename Adapter::base_adapter_t>>
113 class AlgParMETIS :
public Algorithm<Adapter>
117 typedef GraphModel<typename Adapter::base_adapter_t> graphModel_t;
120 typedef typename Adapter::offset_t offset_t;
121 typedef typename Adapter::scalar_t
scalar_t;
124 typedef idx_t pm_idx_t;
125 typedef real_t pm_real_t;
138 const RCP<
const Comm<int> > &problemComm__,
139 const RCP<const typename Adapter::base_adapter_t> &adapter__,
141 env(env__), problemComm(problemComm__),
142 adapter(adapter__), graphFlags(graphFlags_)
145 void partition(
const RCP<PartitioningSolution<Adapter> > &solution);
149 const RCP<const Environment> env;
150 const RCP<const Comm<int> > problemComm;
151 const RCP<const typename Adapter::base_adapter_t> adapter;
154 void scale_weights(
size_t n, ArrayView<StridedData<lno_t, scalar_t> > &fwgts,
160 template <
typename Adapter,
typename Model>
162 const RCP<PartitioningSolution<Adapter> > &solution
167 size_t numGlobalParts = solution->getTargetGlobalNumberOfParts();
169 int me = problemComm->getRank();
170 int np = problemComm->getSize();
173 ArrayView<const gno_t> vtxgnos;
174 ArrayView<StridedData<lno_t, scalar_t> > vwgts;
176 const auto model = rcp(
new Model(adapter, env, problemComm, graphFlags));
178 int nVwgt = model->getNumWeightsPerVertex();
179 size_t nVtx = model->getVertexList(vtxgnos, vwgts);
183 pm_idx_t *pm_vwgts = NULL;
185 pm_vwgts =
new pm_idx_t[nVtx*nVwgt];
186 scale_weights(nVtx, vwgts, pm_vwgts);
190 ArrayView<const gno_t> adjgnos;
191 ArrayView<const offset_t> offsets;
192 ArrayView<StridedData<lno_t, scalar_t> > ewgts;
193 int nEwgt = model->getNumWeightsPerEdge();
194 size_t nEdge = model->getEdgeList(adjgnos, offsets, ewgts);
196 pm_idx_t *pm_ewgts = NULL;
198 pm_ewgts =
new pm_idx_t[nEdge*nEwgt];
199 scale_weights(nEdge, ewgts, pm_ewgts);
203 pm_idx_t *pm_offsets;
206 pm_idx_t pm_dummy_adj;
210 pm_adjs = &pm_dummy_adj;
214 pm_idx_t *pm_vtxdist;
215 ArrayView<size_t> vtxdist;
216 model->getVertexDist(vtxdist);
221 RCP<Comm<int> > subcomm;
226 Array<int> keepRanks(np);
227 for (
int i = 0; i < np; i++) {
228 if ((pm_vtxdist[i+1] - pm_vtxdist[i]) > 0) {
229 keepRanks[nKeep] = i;
230 pm_vtxdist[nKeep] = pm_vtxdist[i];
234 pm_vtxdist[nKeep] = pm_vtxdist[np];
236 subcomm = problemComm->createSubcommunicator(keepRanks.view(0,nKeep));
237 if (subcomm != Teuchos::null)
238 mpicomm = Teuchos::getRawMpiComm(*subcomm);
240 mpicomm = MPI_COMM_NULL;
243 mpicomm = Teuchos::getRawMpiComm(*problemComm);
247 mpicomm = Teuchos::getRawMpiComm(*problemComm);
251 pm_idx_t *pm_partList = NULL;
252 if (nVtx) pm_partList =
new pm_idx_t[nVtx];
253 for (
size_t i = 0; i < nVtx; i++) pm_partList[i] = 0;
254 int pm_return = METIS_OK;
256 if (mpicomm != MPI_COMM_NULL) {
260 pm_idx_t pm_nCon = (nVwgt == 0 ? 1 : pm_idx_t(nVwgt));
261 pm_real_t *pm_partsizes =
new pm_real_t[numGlobalParts*pm_nCon];
262 for (pm_idx_t dim = 0; dim < pm_nCon; dim++) {
263 if (!solution->criteriaHasUniformPartSizes(dim))
264 for (
size_t i=0; i<numGlobalParts; i++)
265 pm_partsizes[i*pm_nCon+dim] =
266 pm_real_t(solution->getCriteriaPartSize(dim,i));
268 for (
size_t i=0; i<numGlobalParts; i++)
269 pm_partsizes[i*pm_nCon+dim] = pm_real_t(1.)/pm_real_t(numGlobalParts);
273 double tolerance = 1.1;
274 const Teuchos::ParameterList &pl = env->getParameters();
275 const Teuchos::ParameterEntry *pe = pl.getEntryPtr(
"imbalance_tolerance");
276 if (pe) tolerance = pe->getValue<
double>(&tolerance);
280 if (tolerance <= 1.0) {
282 std::cerr <<
"Warning: ParMETIS requires imbalance_tolerance > 1.0; "
283 <<
"to comply, Zoltan2 reset imbalance_tolerance to 1.01."
288 pm_real_t *pm_imbTols =
new pm_real_t[pm_nCon];
289 for (pm_idx_t dim = 0; dim < pm_nCon; dim++)
290 pm_imbTols[dim] = pm_real_t(tolerance);
292 std::string parmetis_method(
"PARTKWAY");
293 pe = pl.getEntryPtr(
"partitioning_approach");
295 std::string approach;
296 approach = pe->getValue<std::string>(&approach);
297 if ((approach ==
"repartition") || (approach ==
"maximize_overlap")) {
300 parmetis_method =
"ADAPTIVE_REPART";
305 parmetis_method =
"PARTKWAY";
310 pm_idx_t pm_wgtflag = 2*(nVwgt > 0) + (nEwgt > 0);
311 pm_idx_t pm_numflag = 0;
312 pm_idx_t pm_edgecut = -1;
313 pm_idx_t pm_options[METIS_NOPTIONS];
315 for (
int i = 1; i < METIS_NOPTIONS; i++)
322 if (parmetis_method ==
"PARTKWAY") {
323 pm_return = ParMETIS_V3_PartKway(pm_vtxdist, pm_offsets, pm_adjs,
324 pm_vwgts, pm_ewgts, &pm_wgtflag,
325 &pm_numflag, &pm_nCon, &pm_nPart,
326 pm_partsizes, pm_imbTols, pm_options,
327 &pm_edgecut, pm_partList, &mpicomm);
329 else if (parmetis_method ==
"ADAPTIVE_REPART") {
333 pm_idx_t *pm_vsize =
new pm_idx_t[nVtx];
334 for (
size_t i = 0; i < nVtx; i++) pm_vsize[i] = 1;
336 pm_real_t itr = 100.;
337 pm_return = ParMETIS_V3_AdaptiveRepart(pm_vtxdist, pm_offsets, pm_adjs,
339 pm_vsize, pm_ewgts, &pm_wgtflag,
340 &pm_numflag, &pm_nCon, &pm_nPart,
341 pm_partsizes, pm_imbTols,
342 &itr, pm_options, &pm_edgecut,
343 pm_partList, &mpicomm);
356 throw std::logic_error(
"\nInvalid ParMETIS method requested.\n");
360 delete [] pm_partsizes;
361 delete [] pm_imbTols;
366 ArrayRCP<part_t> partList;
371 solution->setParts(partList);
373 env->memory(
"Zoltan2-ParMETIS: After creating solution");
381 if (nVwgt)
delete [] pm_vwgts;
382 if (nEwgt)
delete [] pm_ewgts;
384 if (pm_return != METIS_OK) {
385 throw std::runtime_error(
386 "\nParMETIS returned an error; no valid partition generated.\n"
387 "Look for 'PARMETIS ERROR' in your output for more details.\n");
401 template <
typename Adapter,
typename Model>
402 void AlgParMETIS<Adapter, Model>::scale_weights(
405 typename Adapter::scalar_t> > &fwgts,
409 const double INT_EPSILON = 1e-5;
410 const int nWgt = fwgts.size();
412 int *nonint_local =
new int[nWgt+nWgt];
413 int *nonint = nonint_local + nWgt;
415 double *sum_wgt_local =
new double[nWgt*4];
416 double *max_wgt_local = sum_wgt_local + nWgt;
417 double *sum_wgt = max_wgt_local + nWgt;
418 double *max_wgt = sum_wgt + nWgt;
420 for (
int i = 0; i < nWgt; i++) {
422 sum_wgt_local[i] = 0.;
423 max_wgt_local[i] = 0;
428 for (
int j = 0; j < nWgt; j++) {
429 for (
size_t i = 0; i < n; i++) {
430 double fw = double(fwgts[j][i]);
431 if (!nonint_local[j]) {
432 pm_idx_t tmp = (pm_idx_t) floor(fw + .5);
433 if (fabs((
double)tmp-fw) > INT_EPSILON) {
437 sum_wgt_local[j] += fw;
438 if (fw > max_wgt_local[j]) max_wgt_local[j] = fw;
442 Teuchos::reduceAll<int,int>(*problemComm, Teuchos::REDUCE_MAX, nWgt,
443 nonint_local, nonint);
444 Teuchos::reduceAll<int,double>(*problemComm, Teuchos::REDUCE_SUM, nWgt,
445 sum_wgt_local, sum_wgt);
446 Teuchos::reduceAll<int,double>(*problemComm, Teuchos::REDUCE_MAX, nWgt,
447 max_wgt_local, max_wgt);
449 const double max_wgt_sum = double(std::numeric_limits<pm_idx_t>::max()/8);
450 for (
int j = 0; j < nWgt; j++) {
455 if (nonint[j] || (max_wgt[j]<=INT_EPSILON) || (sum_wgt[j]>max_wgt_sum)) {
457 if (sum_wgt[j] != 0.) scale = max_wgt_sum/sum_wgt[j];
461 for (
size_t i = 0; i < n; i++)
462 iwgts[i*nWgt+j] = (pm_idx_t) ceil(
double(fwgts[j][i])*scale);
464 delete [] nonint_local;
465 delete [] sum_wgt_local;
470 #endif // PARMETIS VERSION 4 OR HIGHER CHECK
472 #endif // HAVE_ZOLTAN2_MPI
474 #endif // HAVE_ZOLTAN2_PARMETIS
virtual void partition(const RCP< PartitioningSolution< Adapter > > &)
Partitioning method.
std::bitset< NUM_MODEL_FLAGS > modelFlag_t
map_t::global_ordinal_type gno_t
Defines the PartitioningSolution class.
static void SAVE_ARRAYRCP(ArrayRCP< first_t > *a, second_t *b, size_t size)
SparseMatrixAdapter_t::part_t part_t
AlgParMETIS(const RCP< const Environment > &, const RCP< const Comm< int > > &, const RCP< const typename Adapter::base_adapter_t > &, const modelFlag_t &graphFlags_=modelFlag_t())
Adapter::scalar_t scalar_t
Algorithm defines the base class for all algorithms.
map_t::local_ordinal_type lno_t
static void ASSIGN(first_t &a, second_t b)
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)