45 #ifndef _ZOLTAN2_ALGPARMETIS_HPP_ 46 #define _ZOLTAN2_ALGPARMETIS_HPP_ 58 #ifndef HAVE_ZOLTAN2_PARMETIS 64 template <
typename Adapter>
69 const RCP<
const Comm<int> > &problemComm,
73 throw std::runtime_error(
74 "BUILD ERROR: ParMETIS requested but not compiled into Zoltan2.\n" 75 "Please set CMake flag Zoltan2_ENABLE_ParMETIS:BOOL=ON.");
85 #ifdef HAVE_ZOLTAN2_PARMETIS 87 #ifndef HAVE_ZOLTAN2_MPI 91 #error "TPL ParMETIS requires compilation with MPI. Configure with -DTPL_ENABLE_MPI:BOOL=ON or -DZoltan2_ENABLE_ParMETIS:BOOL=OFF" 99 #if (PARMETIS_MAJOR_VERSION < 4) 103 #error "Specified version of ParMETIS is not compatible with Zoltan2; upgrade to ParMETIS v4 or later, or build Zoltan2 without ParMETIS." 111 template <
typename Adapter>
117 typedef typename Adapter::lno_t
lno_t;
118 typedef typename Adapter::gno_t
gno_t;
119 typedef typename Adapter::scalar_t
scalar_t;
120 typedef typename Adapter::part_t
part_t;
122 typedef idx_t pm_idx_t;
123 typedef real_t pm_real_t;
136 const RCP<
const Comm<int> > &problemComm__,
137 const RCP<graphModel_t> &model__) :
138 env(env__), problemComm(problemComm__),
146 const RCP<const Environment> env;
147 const RCP<const Comm<int> > problemComm;
148 const RCP<GraphModel<typename Adapter::base_adapter_t> > model;
156 template <
typename Adapter>
163 size_t numGlobalParts = solution->getTargetGlobalNumberOfParts();
165 int me = problemComm->getRank();
166 int np = problemComm->getSize();
169 ArrayView<const gno_t> vtxgnos;
170 ArrayView<StridedData<lno_t, scalar_t> > vwgts;
171 int nVwgt = model->getNumWeightsPerVertex();
172 size_t nVtx = model->getVertexList(vtxgnos, vwgts);
176 pm_idx_t *pm_vwgts = NULL;
178 pm_vwgts =
new pm_idx_t[nVtx*nVwgt];
179 scale_weights(nVtx, vwgts, pm_vwgts);
183 ArrayView<const gno_t> adjgnos;
184 ArrayView<const lno_t> offsets;
185 ArrayView<StridedData<lno_t, scalar_t> > ewgts;
186 int nEwgt = model->getNumWeightsPerEdge();
187 size_t nEdge = model->getEdgeList(adjgnos, offsets, ewgts);
189 pm_idx_t *pm_ewgts = NULL;
191 pm_ewgts =
new pm_idx_t[nEdge*nEwgt];
192 scale_weights(nEdge, ewgts, pm_ewgts);
196 pm_idx_t *pm_offsets;
199 pm_idx_t pm_dummy_adj;
203 pm_adjs = &pm_dummy_adj;
207 pm_idx_t *pm_vtxdist;
208 ArrayView<size_t> vtxdist;
209 model->getVertexDist(vtxdist);
214 RCP<Comm<int> > subcomm;
219 Array<int> keepRanks(np);
220 for (
int i = 0; i < np; i++) {
221 if ((pm_vtxdist[i+1] - pm_vtxdist[i]) > 0) {
222 keepRanks[nKeep] = i;
223 pm_vtxdist[nKeep] = pm_vtxdist[i];
227 pm_vtxdist[nKeep] = pm_vtxdist[np];
229 subcomm = problemComm->createSubcommunicator(keepRanks.view(0,nKeep));
230 if (subcomm != Teuchos::null)
231 mpicomm = Teuchos::getRawMpiComm(*subcomm);
233 mpicomm = MPI_COMM_NULL;
236 mpicomm = Teuchos::getRawMpiComm(*problemComm);
240 mpicomm = Teuchos::getRawMpiComm(*problemComm);
244 pm_idx_t *pm_partList = NULL;
245 if (nVtx) pm_partList =
new pm_idx_t[nVtx];
247 if (mpicomm != MPI_COMM_NULL) {
251 pm_idx_t pm_nCon = (nVwgt == 0 ? 1 : pm_idx_t(nVwgt));
252 pm_real_t *pm_partsizes =
new pm_real_t[numGlobalParts*pm_nCon];
253 for (pm_idx_t dim = 0; dim < pm_nCon; dim++) {
254 if (!solution->criteriaHasUniformPartSizes(dim))
255 for (
size_t i=0; i<numGlobalParts; i++)
256 pm_partsizes[i*pm_nCon+dim] =
257 pm_real_t(solution->getCriteriaPartSize(dim,i));
259 for (
size_t i=0; i<numGlobalParts; i++)
260 pm_partsizes[i*pm_nCon+dim] = pm_real_t(1.)/pm_real_t(numGlobalParts);
264 double tolerance = 1.1;
265 const Teuchos::ParameterList &pl = env->getParameters();
266 const Teuchos::ParameterEntry *pe = pl.getEntryPtr(
"imbalance_tolerance");
267 if (pe) tolerance = pe->getValue<
double>(&tolerance);
271 if (tolerance <= 1.0) {
273 std::cerr <<
"Warning: ParMETIS requires imbalance_tolerance > 1.0; " 274 <<
"to comply, Zoltan2 reset imbalance_tolerance to 1.01." 279 pm_real_t *pm_imbTols =
new pm_real_t[pm_nCon];
280 for (pm_idx_t dim = 0; dim < pm_nCon; dim++)
281 pm_imbTols[dim] = pm_real_t(tolerance);
284 std::string parmetis_method(
"PARTKWAY");
285 pm_idx_t pm_wgtflag = 2*(nVwgt > 0) + (nEwgt > 0);
286 pm_idx_t pm_numflag = 0;
291 if (parmetis_method ==
"PARTKWAY") {
293 pm_idx_t pm_edgecut = -1;
294 pm_idx_t pm_options[METIS_NOPTIONS];
296 for (
int i = 0; i < METIS_NOPTIONS; i++)
300 ParMETIS_V3_PartKway(pm_vtxdist, pm_offsets, pm_adjs, pm_vwgts, pm_ewgts,
301 &pm_wgtflag, &pm_numflag, &pm_nCon, &pm_nPart,
302 pm_partsizes, pm_imbTols, pm_options,
303 &pm_edgecut, pm_partList, &mpicomm);
305 else if (parmetis_method ==
"ADAPTIVE_REPART") {
307 std::cout <<
"NOT READY FOR ADAPTIVE_REPART YET" << std::endl;
310 else if (parmetis_method ==
"PART_GEOM") {
312 std::cout <<
"NOT READY FOR PART_GEOM YET" << std::endl;
317 delete [] pm_partsizes;
318 delete [] pm_imbTols;
323 ArrayRCP<part_t> partList;
326 partList = ArrayRCP<part_t>((
part_t *)pm_partList, 0, nVtx,
true);
330 partList = ArrayRCP<part_t>(
new part_t[nVtx], 0, nVtx,
true);
331 for (
size_t i = 0; i < nVtx; i++) {
332 partList[i] =
part_t(pm_partList[i]);
334 delete [] pm_partList;
338 solution->setParts(partList);
340 env->memory(
"Zoltan2-ParMETIS: After creating solution");
348 if (nVwgt)
delete [] pm_vwgts;
349 if (nEwgt)
delete [] pm_ewgts;
362 template <
typename Adapter>
366 typename Adapter::scalar_t> > &fwgts,
370 const double INT_EPSILON = 1e-5;
371 const int nWgt = fwgts.size();
373 int *nonint_local =
new int[nWgt+nWgt];
374 int *nonint = nonint_local + nWgt;
376 double *sum_wgt_local =
new double[nWgt*4];
377 double *max_wgt_local = sum_wgt_local + nWgt;
378 double *sum_wgt = max_wgt_local + nWgt;
379 double *max_wgt = sum_wgt + nWgt;
381 for (
int i = 0; i < nWgt; i++) {
383 sum_wgt_local[i] = 0.;
384 max_wgt_local[i] = 0;
389 for (
int j = 0; j < nWgt; j++) {
390 for (
size_t i = 0; i < n; i++) {
391 double fw = double(fwgts[j][i]);
392 if (!nonint_local[j]) {
393 pm_idx_t tmp = (pm_idx_t) floor(fw + .5);
394 if (fabs((
double)tmp-fw) > INT_EPSILON) {
398 sum_wgt_local[j] += fw;
399 if (fw > max_wgt_local[j]) max_wgt_local[j] = fw;
403 Teuchos::reduceAll<int,int>(*problemComm, Teuchos::REDUCE_MAX, nWgt,
404 nonint_local, nonint);
405 Teuchos::reduceAll<int,double>(*problemComm, Teuchos::REDUCE_SUM, nWgt,
406 sum_wgt_local, sum_wgt);
407 Teuchos::reduceAll<int,double>(*problemComm, Teuchos::REDUCE_MAX, nWgt,
408 max_wgt_local, max_wgt);
410 const double max_wgt_sum = double(std::numeric_limits<pm_idx_t>::max()/8);
411 for (
int j = 0; j < nWgt; j++) {
416 if (nonint[j] || (max_wgt[j]<=INT_EPSILON) || (sum_wgt[j]>max_wgt_sum)) {
418 if (sum_wgt[j] != 0.) scale = max_wgt_sum/sum_wgt[j];
422 for (
size_t i = 0; i < n; i++)
423 iwgts[i*nWgt+j] = (pm_idx_t) ceil(
double(fwgts[j][i])*scale);
425 delete [] nonint_local;
426 delete [] sum_wgt_local;
431 #endif // PARMETIS VERSION 4 OR HIGHER CHECK 433 #endif // HAVE_ZOLTAN2_MPI 435 #endif // HAVE_ZOLTAN2_PARMETIS
static void DELETE_TPL_T_ARRAY(tpl_t **a)
Defines the PartitioningSolution class.
AlgParMETIS(const RCP< const Environment > &env, const RCP< const Comm< int > > &problemComm, const RCP< GraphModel< typename Adapter::base_adapter_t > > &model)
Adapter::scalar_t scalar_t
A PartitioningSolution is a solution to a partitioning problem.
The StridedData class manages lists of weights or coordinates.
Algorithm defines the base class for all algorithms.
static void ASSIGN_TPL_T_ARRAY(tpl_t **a, ArrayView< zno_t > &b)
virtual void partition(const RCP< PartitioningSolution< Adapter > > &solution)
Partitioning method.
GraphModel defines the interface required for graph models.
static void ASSIGN_TPL_T(tpl_t &a, zno_t b)
Defines the GraphModel interface.
A gathering of useful namespace methods.