49#ifndef ZOLTAN2_IMBALANCEMETRICSUTILITY_HPP
50#define ZOLTAN2_IMBALANCEMETRICSUTILITY_HPP
100template <
typename scalar_t,
typename lno_t,
typename part_t>
102 const RCP<const Environment> &env,
103 const RCP<
const Comm<int> > &comm,
104 const ArrayView<const part_t> &part,
112 ArrayRCP<scalar_t> &globalSums)
118 numExistingParts = numNonemptyParts = 0;
121 if (vwgtDim) numMetrics++;
122 if (vwgtDim > 1) numMetrics += vwgtDim;
124 auto next = metrics.size();
126 for(
int n = 0; n < numMetrics; ++n) {
127 RCP<im_t> newMetric = addNewMetric<im_t, scalar_t>(env, metrics);
137 lno_t localNumObj = part.size();
138 part_t localNum[2], globalNum[2];
139 localNum[0] =
static_cast<part_t>(vwgtDim);
142 for (
lno_t i=0; i < localNumObj; i++)
143 if (part[i] > localNum[1]) localNum[1] = part[i];
146 reduceAll<int, part_t>(*comm, Teuchos::REDUCE_MAX, 2,
147 localNum, globalNum);
151 env->globalBugAssertion(__FILE__,__LINE__,
152 "inconsistent number of vertex weights",
155 part_t maxPartPlusOne = globalNum[1] + 1;
158 part_t globalSumSize = maxPartPlusOne * numMetrics;
160 scalar_t * sumBuf =
new scalar_t[globalSumSize];
161 env->localMemoryAssertion(__FILE__, __LINE__, globalSumSize, sumBuf);
162 globalSums = arcp(sumBuf, 0, globalSumSize);
167 scalar_t *localBuf =
new scalar_t[globalSumSize];
168 env->localMemoryAssertion(__FILE__, __LINE__, globalSumSize, localBuf);
169 memset(localBuf, 0,
sizeof(scalar_t) * globalSumSize);
171 scalar_t *obj = localBuf;
173 for (
lno_t i=0; i < localNumObj; i++)
178 scalar_t *wgt = localBuf+maxPartPlusOne;
180 normedPartWeights<scalar_t, lno_t, part_t>(env, maxPartPlusOne,
181 part, vwgts, mcNorm, wgt);
188 wgt += maxPartPlusOne;
189 for (
int vdim = 0; vdim < vwgtDim; vdim++){
190 for (
lno_t i=0; i < localNumObj; i++)
191 wgt[part[i]] += vwgts[vdim][i];
192 wgt += maxPartPlusOne;
198 metrics[next]->setName(
"object count");
199 metrics[next]->setMetricValue(
"local sum", localNumObj);
204 scalar_t *wgt = localBuf+maxPartPlusOne;
205 scalar_t total = 0.0;
207 for (
int p=0; p < maxPartPlusOne; p++){
212 metrics[next]->setName(
"weight 0");
214 metrics[next]->setName(
"normed weight");
216 metrics[next]->setMetricValue(
"local sum", total);
221 for (
int vdim = 0; vdim < vwgtDim; vdim++){
222 wgt += maxPartPlusOne;
224 for (
int p=0; p < maxPartPlusOne; p++){
228 std::ostringstream oss;
229 oss <<
"weight " << vdim;
231 metrics[next]->setName(oss.str());
232 metrics[next]->setMetricValue(
"local sum", total);
243 reduceAll<int, scalar_t>(*comm, Teuchos::REDUCE_SUM, globalSumSize,
254 scalar_t min=0, max=0, sum=0;
255 next = metrics.size() - numMetrics;
261 ArrayView<scalar_t> objVec(obj, maxPartPlusOne);
262 getStridedStats<scalar_t>(objVec, 1, 0, min, max, sum);
263 if (maxPartPlusOne < targetNumParts)
266 metrics[next]->setMetricValue(
"global minimum", min);
267 metrics[next]->setMetricValue(
"global maximum", max);
268 metrics[next]->setMetricValue(
"global sum", sum);
272 scalar_t *wgt = sumBuf + maxPartPlusOne;
274 ArrayView<scalar_t> normedWVec(wgt, maxPartPlusOne);
275 getStridedStats<scalar_t>(normedWVec, 1, 0, min, max, sum);
276 if (maxPartPlusOne < targetNumParts)
279 metrics[next]->setMetricValue(
"global minimum", min);
280 metrics[next]->setMetricValue(
"global maximum", max);
281 metrics[next]->setMetricValue(
"global sum", sum);
285 for (
int vdim=0; vdim < vwgtDim; vdim++){
286 wgt += maxPartPlusOne;
287 ArrayView<scalar_t> fromVec(wgt, maxPartPlusOne);
288 getStridedStats<scalar_t>(fromVec, 1, 0, min, max, sum);
289 if (maxPartPlusOne < targetNumParts)
292 metrics[next]->setMetricValue(
"global minimum", min);
293 metrics[next]->setMetricValue(
"global maximum", max);
294 metrics[next]->setMetricValue(
"global sum", sum);
303 numExistingParts = maxPartPlusOne;
311 numNonemptyParts = numExistingParts;
313 for (
part_t p=0; p < numExistingParts; p++)
314 if (obj[p] == 0) numNonemptyParts--;
349template <
typename Adapter>
351 const RCP<const Environment> &env,
352 const RCP<
const Comm<int> > &comm,
356 const ArrayView<const typename Adapter::part_t> &partArray,
358 typename Adapter::part_t &numExistingParts,
359 typename Adapter::part_t &numNonemptyParts,
364 typedef typename Adapter::scalar_t scalar_t;
365 typedef typename Adapter::gno_t
gno_t;
366 typedef typename Adapter::lno_t
lno_t;
367 typedef typename Adapter::part_t
part_t;
368 typedef typename Adapter::base_adapter_t base_adapter_t;
373 size_t numLocalObjects = ia->getLocalNumIDs();
377 int nWeights = ia->getNumWeightsPerID();
378 int numCriteria = (nWeights > 0 ? nWeights : 1);
379 Array<sdata_t>
weights(numCriteria);
389 bool useDegreeAsWeight =
false;
392 <typename Adapter::user_t, typename Adapter::userCoord_t
> *>(ia)->
393 useDegreeAsWeight(0);
396 <typename Adapter::user_t, typename Adapter::userCoord_t
> *>(ia)->
397 useDegreeAsWeight(0);
401 useDegreeAsWeight(0);
403 if (useDegreeAsWeight) {
404 ArrayView<const gno_t> Ids;
405 ArrayView<sdata_t> vwgts;
406 RCP<GraphModel<base_adapter_t> > graph;
407 if (graphModel == Teuchos::null) {
408 std::bitset<NUM_MODEL_FLAGS> modelFlags;
409 const RCP<const base_adapter_t> bia =
410 rcp(
dynamic_cast<const base_adapter_t *
>(ia),
false);
412 graph->getVertexList(Ids, vwgts);
414 graphModel->getVertexList(Ids, vwgts);
416 scalar_t *wgt =
new scalar_t[numLocalObjects];
417 for (
int i=0; i < nWeights; i++){
418 for (
size_t j=0; j < numLocalObjects; j++) {
419 wgt[j] = vwgts[i][j];
421 ArrayRCP<const scalar_t> wgtArray(wgt,0,numLocalObjects,
false);
422 weights[i] = sdata_t(wgtArray, 1);
425 for (
int i=0; i < nWeights; i++){
428 ia->getWeightsView(wgt, stride, i);
429 ArrayRCP<const scalar_t> wgtArray(wgt,0,stride*numLocalObjects,
false);
430 weights[i] = sdata_t(wgtArray, stride);
437 part_t targetNumParts = comm->getSize();
438 scalar_t *psizes = NULL;
440 ArrayRCP<ArrayRCP<scalar_t> > partSizes(numCriteria);
443 for (
int dim=0; dim < numCriteria; dim++){
445 psizes =
new scalar_t [targetNumParts];
446 env->localMemoryAssertion(__FILE__, __LINE__, targetNumParts, psizes);
447 for (
part_t i=0; i < targetNumParts; i++){
450 partSizes[dim] = arcp(psizes, 0, targetNumParts,
true);
459 ArrayRCP<scalar_t> globalSums;
461 int initialMetricCount = metrics.size();
463 globalSumsByPart<scalar_t, lno_t, part_t>(env, comm,
464 partArray, nWeights,
weights.view(0, numCriteria), mcNorm,
465 targetNumParts, numExistingParts, numNonemptyParts, metrics, globalSums);
469 int addedMetricsCount = metrics.size() - initialMetricCount;
475 int index = initialMetricCount;
477 scalar_t *objCount = globalSums.getRawPtr();
478 scalar_t min, max, avg;
481 if (partSizes[0].size() > 0)
482 psizes = partSizes[0].getRawPtr();
484 scalar_t gsum = metrics[index]->getMetricValue(
"global sum");
485 computeImbalances<scalar_t, part_t>(numExistingParts, targetNumParts, psizes,
486 gsum, objCount, min, max, avg);
488 metrics[index]->setMetricValue(
"global average", gsum / targetNumParts);
490 metrics[index]->setMetricValue(
"maximum imbalance", 1.0 + max);
491 metrics[index]->setMetricValue(
"average imbalance", avg);
496 scalar_t *wgts = globalSums.getRawPtr() + numExistingParts;
498 if (addedMetricsCount > 1){
500 gsum = metrics[index]->getMetricValue(
"global sum");
501 computeImbalances<scalar_t, part_t>(numExistingParts, targetNumParts,
502 numCriteria, partSizes.view(0, numCriteria), gsum, wgts, min, max, avg);
504 metrics[index]->setMetricValue(
"global average", gsum / targetNumParts);
506 metrics[index]->setMetricValue(
"maximum imbalance", 1.0 + max);
507 metrics[index]->setMetricValue(
"average imbalance", avg);
509 if (addedMetricsCount > 2){
516 for (
int vdim=0; vdim < numCriteria; vdim++){
517 wgts += numExistingParts;
520 if (partSizes[vdim].size() > 0)
521 psizes = partSizes[vdim].getRawPtr();
523 gsum = metrics[index]->getMetricValue(
"global sum");
524 computeImbalances<scalar_t, part_t>(numExistingParts, targetNumParts,
525 psizes, gsum, wgts, min, max, avg);
527 metrics[index]->setMetricValue(
"global average", gsum / targetNumParts);
529 metrics[index]->setMetricValue(
"maximum imbalance", 1.0 + max);
530 metrics[index]->setMetricValue(
"average imbalance", avg);
541template <
typename scalar_t,
typename part_t>
548 os <<
"Imbalance Metrics: (" << numExistingParts <<
" existing parts)";
549 if (numNonemptyParts < numExistingParts) {
550 os <<
" (" << numNonemptyParts <<
" of which are non-empty)";
553 if (targetNumParts != numExistingParts) {
554 os <<
"Target number of parts is " << targetNumParts << std::endl;
561template <
typename scalar_t,
typename part_t>
569 printImbalanceMetricsHeader<scalar_t, part_t>(os, targetNumParts,
572 for (
int i=0; i < infoList.size(); i++) {
574 infoList[i]->printLine(os);
582template <
typename scalar_t,
typename part_t>
590 printImbalanceMetricsHeader<scalar_t, part_t>(os, targetNumParts,
593 metricValue->printLine(os);
#define METRICS_UNSET_STRING
#define Z2_FORWARD_EXCEPTIONS
Forward an exception back through call stack.
#define Z2_THROW_OUTSIDE_ERROR(env)
Throw an error returned from outside the Zoltan2 library.
GraphAdapter defines the interface for graph-based user data.
GraphModel defines the interface required for graph models.
static void printHeader(std::ostream &os)
Print a standard header.
MatrixAdapter defines the adapter interface for matrices.
MeshAdapter defines the interface for mesh input.
A PartitioningSolution is a solution to a partitioning problem.
scalar_t getCriteriaPartSize(int idx, part_t part) const
Get the size for a given weight index and a given part.
size_t getTargetGlobalNumberOfParts() const
Returns the global number of parts desired in the solution.
bool criteriaHasUniformPartSizes(int idx) const
Determine if balancing criteria has uniform part sizes. (User can specify differing part sizes....
The StridedData class manages lists of weights or coordinates.
map_t::local_ordinal_type lno_t
map_t::global_ordinal_type gno_t
Created by mbenlioglu on Aug 31, 2020.
void imbalanceMetrics(const RCP< const Environment > &env, const RCP< const Comm< int > > &comm, multiCriteriaNorm mcNorm, const Adapter *ia, const PartitioningSolution< Adapter > *solution, const ArrayView< const typename Adapter::part_t > &partArray, const RCP< const GraphModel< typename Adapter::base_adapter_t > > &graphModel, typename Adapter::part_t &numExistingParts, typename Adapter::part_t &numNonemptyParts, ArrayRCP< RCP< BaseClassMetrics< typename Adapter::scalar_t > > > &metrics)
Compute imbalance metrics for a distribution.
void globalSumsByPart(const RCP< const Environment > &env, const RCP< const Comm< int > > &comm, const ArrayView< const part_t > &part, int vwgtDim, const ArrayView< StridedData< lno_t, scalar_t > > &vwgts, multiCriteriaNorm mcNorm, part_t targetNumParts, part_t &numExistingParts, part_t &numNonemptyParts, ArrayRCP< RCP< BaseClassMetrics< scalar_t > > > &metrics, ArrayRCP< scalar_t > &globalSums)
Given the local partitioning, compute the global sums in each part.
@ DETAILED_STATUS
sub-steps, each method's entry and exit
void printImbalanceMetrics(std::ostream &os, part_t targetNumParts, part_t numExistingParts, part_t numNonemptyParts, const ArrayView< RCP< BaseClassMetrics< scalar_t > > > &infoList)
Print out list of imbalance metrics.
@ DEBUG_MODE_ASSERTION
checks for logic errors
BaseAdapterType
An enum to identify general types of adapters.
@ GraphAdapterType
graph data
@ MatrixAdapterType
matrix data
@ MeshAdapterType
mesh data
void printImbalanceMetricsHeader(std::ostream &os, part_t targetNumParts, part_t numExistingParts, part_t numNonemptyParts)
Print out header info for imbalance metrics.
multiCriteriaNorm
Enumerator used in code for multicriteria norm choice.
SparseMatrixAdapter_t::part_t part_t