49 #ifndef ZOLTAN2_IMBALANCEMETRICSUTILITY_HPP
50 #define ZOLTAN2_IMBALANCEMETRICSUTILITY_HPP
100 template <
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--;
349 template <
typename Adapter>
351 const RCP<const Environment> &env,
352 const RCP<
const Comm<int> > &comm,
356 const ArrayView<const typename Adapter::part_t> &partArray,
364 typedef typename Adapter::scalar_t scalar_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);
384 weights[0] = sdata_t();
389 bool useDegreeAsWeight =
false;
393 useDegreeAsWeight(0);
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);
541 template <
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;
561 template <
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);
582 template <
typename scalar_t,
typename part_t>
590 printImbalanceMetricsHeader<scalar_t, part_t>(os, targetNumParts,
593 metricValue->printLine(os);
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.
Zoltan2::BaseAdapter< userTypes_t > base_adapter_t
scalar_t getCriteriaPartSize(int idx, part_t part) const
Get the size for a given weight index and a given part.
#define Z2_FORWARD_EXCEPTIONS
Forward an exception back through call stack.
MatrixAdapter defines the adapter interface for matrices.
GraphAdapter defines the interface for graph-based user data.
MeshAdapter defines the interface for mesh input.
map_t::global_ordinal_type gno_t
sub-steps, each method's entry and exit
SparseMatrixAdapter_t::part_t part_t
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.
A PartitioningSolution is a solution to a partitioning problem.
static void printHeader(std::ostream &os)
Print a standard header.
BaseAdapterType
An enum to identify general types of adapters.
The StridedData class manages lists of weights or coordinates.
map_t::local_ordinal_type lno_t
void setNorm(multiCriteriaNorm normVal)
Set or reset the norm.
GraphModel defines the interface required for graph models.
multiCriteriaNorm
Enumerator used in code for multicriteria norm choice.
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.
void printImbalanceMetricsHeader(std::ostream &os, part_t targetNumParts, part_t numExistingParts, part_t numNonemptyParts)
Print out header info for imbalance metrics.
#define Z2_THROW_OUTSIDE_ERROR(env)
Throw an error returned from outside the Zoltan2 library.
bool criteriaHasUniformPartSizes(int idx) const
Determine if balancing criteria has uniform part sizes. (User can specify differing part sizes...
size_t getTargetGlobalNumberOfParts() const
Returns the global number of parts desired in the solution.
#define METRICS_UNSET_STRING
Zoltan2::BasicUserTypes< zscalar_t, zlno_t, zgno_t > user_t