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,
108 part_t targetNumParts,
109 part_t &numExistingParts,
110 part_t &numNonemptyParts,
112 ArrayRCP<scalar_t> &globalSums)
118 numExistingParts = numNonemptyParts = 0;
121 if (vwgtDim) numMetrics++;
122 if (vwgtDim > 1) numMetrics += vwgtDim;
126 typedef typename ArrayRCP<RCP<BaseClassMetrics<scalar_t> > >::size_type array_size_type;
127 metrics.resize( metrics.size() + numMetrics );
128 for(array_size_type n = metrics.size()-numMetrics; n < metrics.size(); ++n) {
129 mv_t * newMetric =
new mv_t;
140 env->localMemoryAssertion(__FILE__,__LINE__,1,newMetric);
141 metrics[n] = rcp( newMetric );
143 array_size_type next = metrics.size() - numMetrics;
155 lno_t localNumObj = part.size();
156 part_t localNum[2], globalNum[2];
157 localNum[0] =
static_cast<part_t
>(vwgtDim);
160 for (lno_t i=0; i < localNumObj; i++)
161 if (part[i] > localNum[1]) localNum[1] = part[i];
164 reduceAll<int, part_t>(*comm, Teuchos::REDUCE_MAX, 2,
165 localNum, globalNum);
169 env->globalBugAssertion(__FILE__,__LINE__,
170 "inconsistent number of vertex weights",
173 part_t maxPartPlusOne = globalNum[1] + 1;
176 part_t globalSumSize = maxPartPlusOne * numMetrics;
177 scalar_t * sumBuf =
new scalar_t [globalSumSize];
178 env->localMemoryAssertion(__FILE__, __LINE__, globalSumSize, sumBuf);
179 globalSums = arcp(sumBuf, 0, globalSumSize);
184 scalar_t *localBuf =
new scalar_t [globalSumSize];
185 env->localMemoryAssertion(__FILE__, __LINE__, globalSumSize, localBuf);
186 memset(localBuf, 0,
sizeof(scalar_t) * globalSumSize);
188 scalar_t *obj = localBuf;
190 for (lno_t i=0; i < localNumObj; i++)
195 scalar_t *wgt = localBuf+maxPartPlusOne;
197 normedPartWeights<scalar_t, lno_t, part_t>(env, maxPartPlusOne,
198 part, vwgts, mcNorm, wgt);
205 wgt += maxPartPlusOne;
206 for (
int vdim = 0; vdim < vwgtDim; vdim++){
207 for (lno_t i=0; i < localNumObj; i++)
208 wgt[part[i]] += vwgts[vdim][i];
209 wgt += maxPartPlusOne;
215 metrics[next]->setName(
"object count");
216 metrics[next]->setMetricValue(
"local sum", localNumObj);
221 scalar_t *wgt = localBuf+maxPartPlusOne;
222 scalar_t total = 0.0;
224 for (
int p=0; p < maxPartPlusOne; p++){
229 metrics[next]->setName(
"weight 0");
231 metrics[next]->setName(
"normed weight");
233 metrics[next]->setMetricValue(
"local sum", total);
238 for (
int vdim = 0; vdim < vwgtDim; vdim++){
239 wgt += maxPartPlusOne;
241 for (
int p=0; p < maxPartPlusOne; p++){
245 std::ostringstream oss;
246 oss <<
"weight " << vdim;
248 metrics[next]->setName(oss.str());
249 metrics[next]->setMetricValue(
"local sum", total);
260 reduceAll<int, scalar_t>(*comm, Teuchos::REDUCE_SUM, globalSumSize,
271 scalar_t min=0, max=0, sum=0;
272 next = metrics.size() - numMetrics;
278 ArrayView<scalar_t> objVec(obj, maxPartPlusOne);
279 getStridedStats<scalar_t>(objVec, 1, 0, min, max, sum);
280 if (maxPartPlusOne < targetNumParts)
283 metrics[next]->setMetricValue(
"global minimum", min);
284 metrics[next]->setMetricValue(
"global maximum", max);
285 metrics[next]->setMetricValue(
"global sum", sum);
289 scalar_t *wgt = sumBuf + maxPartPlusOne;
291 ArrayView<scalar_t> normedWVec(wgt, maxPartPlusOne);
292 getStridedStats<scalar_t>(normedWVec, 1, 0, min, max, sum);
293 if (maxPartPlusOne < targetNumParts)
296 metrics[next]->setMetricValue(
"global minimum", min);
297 metrics[next]->setMetricValue(
"global maximum", max);
298 metrics[next]->setMetricValue(
"global sum", sum);
302 for (
int vdim=0; vdim < vwgtDim; vdim++){
303 wgt += maxPartPlusOne;
304 ArrayView<scalar_t> fromVec(wgt, maxPartPlusOne);
305 getStridedStats<scalar_t>(fromVec, 1, 0, min, max, sum);
306 if (maxPartPlusOne < targetNumParts)
309 metrics[next]->setMetricValue(
"global minimum", min);
310 metrics[next]->setMetricValue(
"global maximum", max);
311 metrics[next]->setMetricValue(
"global sum", sum);
320 numExistingParts = maxPartPlusOne;
328 numNonemptyParts = numExistingParts;
330 for (part_t p=0; p < numExistingParts; p++)
331 if (obj[p] == 0) numNonemptyParts--;
366 template <
typename Adapter>
368 const RCP<const Environment> &env,
369 const RCP<
const Comm<int> > &comm,
373 const ArrayView<const typename Adapter::part_t> &partArray,
375 typename Adapter::part_t &numExistingParts,
376 typename Adapter::part_t &numNonemptyParts,
381 typedef typename Adapter::scalar_t scalar_t;
382 typedef typename Adapter::gno_t gno_t;
383 typedef typename Adapter::lno_t lno_t;
384 typedef typename Adapter::part_t part_t;
390 size_t numLocalObjects = ia->getLocalNumIDs();
394 int nWeights = ia->getNumWeightsPerID();
395 int numCriteria = (nWeights > 0 ? nWeights : 1);
396 Array<sdata_t>
weights(numCriteria);
406 bool useDegreeAsWeight =
false;
409 <typename Adapter::user_t, typename Adapter::userCoord_t
> *>(ia)->
410 useDegreeAsWeight(0);
413 <typename Adapter::user_t, typename Adapter::userCoord_t
> *>(ia)->
414 useDegreeAsWeight(0);
418 useDegreeAsWeight(0);
420 if (useDegreeAsWeight) {
421 ArrayView<const gno_t> Ids;
422 ArrayView<sdata_t> vwgts;
423 if (graphModel == Teuchos::null) {
424 std::bitset<NUM_MODEL_FLAGS> modelFlags;
425 RCP<GraphModel<base_adapter_t> > graph;
426 const RCP<const base_adapter_t> bia =
427 rcp(dynamic_cast<const base_adapter_t *>(ia),
false);
429 graph->getVertexList(Ids, vwgts);
431 graphModel->getVertexList(Ids, vwgts);
433 scalar_t *wgt =
new scalar_t[numLocalObjects];
434 for (
int i=0; i < nWeights; i++){
435 for (
size_t j=0; j < numLocalObjects; j++) {
436 wgt[j] = vwgts[i][j];
438 ArrayRCP<const scalar_t> wgtArray(wgt,0,numLocalObjects,
false);
439 weights[i] = sdata_t(wgtArray, 1);
442 for (
int i=0; i < nWeights; i++){
445 ia->getWeightsView(wgt, stride, i);
446 ArrayRCP<const scalar_t> wgtArray(wgt,0,stride*numLocalObjects,
false);
447 weights[i] = sdata_t(wgtArray, stride);
454 part_t targetNumParts = comm->getSize();
455 scalar_t *psizes = NULL;
457 ArrayRCP<ArrayRCP<scalar_t> > partSizes(numCriteria);
460 for (
int dim=0; dim < numCriteria; dim++){
462 psizes =
new scalar_t [targetNumParts];
463 env->localMemoryAssertion(__FILE__, __LINE__, targetNumParts, psizes);
464 for (part_t i=0; i < targetNumParts; i++){
467 partSizes[dim] = arcp(psizes, 0, targetNumParts,
true);
476 ArrayRCP<scalar_t> globalSums;
478 int initialMetricCount = metrics.size();
480 globalSumsByPart<scalar_t, lno_t, part_t>(env, comm,
481 partArray, nWeights,
weights.view(0, numCriteria), mcNorm,
482 targetNumParts, numExistingParts, numNonemptyParts, metrics, globalSums);
486 int addedMetricsCount = metrics.size() - initialMetricCount;
492 int index = initialMetricCount;
494 scalar_t *objCount = globalSums.getRawPtr();
495 scalar_t min, max, avg;
498 if (partSizes[0].size() > 0)
499 psizes = partSizes[0].getRawPtr();
501 scalar_t gsum = metrics[index]->getMetricValue(
"global sum");
502 computeImbalances<scalar_t, part_t>(numExistingParts, targetNumParts, psizes,
503 gsum, objCount, min, max, avg);
505 metrics[index]->setMetricValue(
"global average", gsum / targetNumParts);
507 metrics[index]->setMetricValue(
"maximum imbalance", 1.0 + max);
508 metrics[index]->setMetricValue(
"average imbalance", avg);
513 scalar_t *wgts = globalSums.getRawPtr() + numExistingParts;
515 if (addedMetricsCount > 1){
517 gsum = metrics[index]->getMetricValue(
"global sum");
518 computeImbalances<scalar_t, part_t>(numExistingParts, targetNumParts,
519 numCriteria, partSizes.view(0, numCriteria), gsum, wgts, min, max, avg);
521 metrics[index]->setMetricValue(
"global average", gsum / targetNumParts);
523 metrics[index]->setMetricValue(
"maximum imbalance", 1.0 + max);
524 metrics[index]->setMetricValue(
"average imbalance", avg);
526 if (addedMetricsCount > 2){
533 for (
int vdim=0; vdim < numCriteria; vdim++){
534 wgts += numExistingParts;
537 if (partSizes[vdim].size() > 0)
538 psizes = partSizes[vdim].getRawPtr();
540 gsum = metrics[index]->getMetricValue(
"global sum");
541 computeImbalances<scalar_t, part_t>(numExistingParts, targetNumParts,
542 psizes, gsum, wgts, min, max, avg);
544 metrics[index]->setMetricValue(
"global average", gsum / targetNumParts);
546 metrics[index]->setMetricValue(
"maximum imbalance", 1.0 + max);
547 metrics[index]->setMetricValue(
"average imbalance", avg);
558 template <
typename scalar_t,
typename part_t>
561 part_t targetNumParts,
562 part_t numExistingParts,
563 part_t numNonemptyParts)
565 os <<
"Imbalance Metrics: (" << numExistingParts <<
" existing parts)";
566 if (numNonemptyParts < numExistingParts) {
567 os <<
" (" << numNonemptyParts <<
" of which are non-empty)";
570 if (targetNumParts != numExistingParts) {
571 os <<
"Target number of parts is " << targetNumParts << std::endl;
578 template <
typename scalar_t,
typename part_t>
581 part_t targetNumParts,
582 part_t numExistingParts,
583 part_t numNonemptyParts,
586 printImbalanceMetricsHeader<scalar_t, part_t>(os, targetNumParts,
589 for (
int i=0; i < infoList.size(); i++) {
591 infoList[i]->printLine(os);
599 template <
typename scalar_t,
typename part_t>
602 part_t targetNumParts,
603 part_t numExistingParts,
604 part_t numNonemptyParts,
607 printImbalanceMetricsHeader<scalar_t, part_t>(os, targetNumParts,
610 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
#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.
sub-steps, each method's entry and exit
A PartitioningSolution is a solution to a partitioning problem.
static void printHeader(std::ostream &os)
Print a standard header.
scalar_t getCriteriaPartSize(int idx, part_t part) const
Get the size for a given weight index and a given part.
BaseAdapterType
An enum to identify general types of adapters.
The StridedData class manages lists of weights or coordinates.
void setNorm(multiCriteriaNorm normVal)
Set or reset the norm.
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.
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.
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.
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.
#define METRICS_UNSET_STRING