Zoltan2
Loading...
Searching...
No Matches
Zoltan2_ImbalanceMetricsUtility.hpp
Go to the documentation of this file.
1// @HEADER
2//
3// ***********************************************************************
4//
5// Zoltan2: A package of combinatorial algorithms for scientific computing
6// Copyright 2012 Sandia Corporation
7//
8// Under the terms of Contract DE-AC04-94AL85000 with Sandia Corporation,
9// the U.S. Government retains certain rights in this software.
10//
11// Redistribution and use in source and binary forms, with or without
12// modification, are permitted provided that the following conditions are
13// met:
14//
15// 1. Redistributions of source code must retain the above copyright
16// notice, this list of conditions and the following disclaimer.
17//
18// 2. Redistributions in binary form must reproduce the above copyright
19// notice, this list of conditions and the following disclaimer in the
20// documentation and/or other materials provided with the distribution.
21//
22// 3. Neither the name of the Corporation nor the names of the
23// contributors may be used to endorse or promote products derived from
24// this software without specific prior written permission.
25//
26// THIS SOFTWARE IS PROVIDED BY SANDIA CORPORATION "AS IS" AND ANY
27// EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
28// IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
29// PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL SANDIA CORPORATION OR THE
30// CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
31// EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
32// PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
33// PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
34// LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
35// NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
36// SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
37//
38// Questions? Contact Karen Devine (kddevin@sandia.gov)
39// Erik Boman (egboman@sandia.gov)
40// Siva Rajamanickam (srajama@sandia.gov)
41//
42// ***********************************************************************
43//
44// @HEADER
45
49#ifndef ZOLTAN2_IMBALANCEMETRICSUTILITY_HPP
50#define ZOLTAN2_IMBALANCEMETRICSUTILITY_HPP
51
54
55namespace Zoltan2{
56
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,
105 int vwgtDim,
106 const ArrayView<StridedData<lno_t, scalar_t> > &vwgts,
107 multiCriteriaNorm mcNorm,
108 part_t targetNumParts,
109 part_t &numExistingParts,
110 part_t &numNonemptyParts,
111 ArrayRCP<RCP<BaseClassMetrics<scalar_t> > > &metrics,
112 ArrayRCP<scalar_t> &globalSums)
113{
114 env->debug(DETAILED_STATUS, "Entering globalSumsByPart");
116 // Initialize return values
117
118 numExistingParts = numNonemptyParts = 0;
119
120 int numMetrics = 1; // "object count"
121 if (vwgtDim) numMetrics++; // "normed weight" or "weight 0"
122 if (vwgtDim > 1) numMetrics += vwgtDim; // "weight n"
123
124 auto next = metrics.size(); // where we will start filling
125 typedef ImbalanceMetrics<scalar_t> im_t;
126 for(int n = 0; n < numMetrics; ++n) {
127 RCP<im_t> newMetric = addNewMetric<im_t, scalar_t>(env, metrics);
128 if (vwgtDim > 1) {
129 newMetric->setNorm(multiCriteriaNorm(mcNorm));
130 }
131 }
132
134 // Figure out the global number of parts in use.
135 // Verify number of vertex weights is the same everywhere.
136
137 lno_t localNumObj = part.size();
138 part_t localNum[2], globalNum[2];
139 localNum[0] = static_cast<part_t>(vwgtDim);
140 localNum[1] = 0;
141
142 for (lno_t i=0; i < localNumObj; i++)
143 if (part[i] > localNum[1]) localNum[1] = part[i];
144
145 try{
146 reduceAll<int, part_t>(*comm, Teuchos::REDUCE_MAX, 2,
147 localNum, globalNum);
148 }
150
151 env->globalBugAssertion(__FILE__,__LINE__,
152 "inconsistent number of vertex weights",
153 globalNum[0] == localNum[0], DEBUG_MODE_ASSERTION, comm);
154
155 part_t maxPartPlusOne = globalNum[1] + 1; // Range of possible part IDs:
156 // [0,maxPartPlusOne)
157
158 part_t globalSumSize = maxPartPlusOne * numMetrics;
159
160 scalar_t * sumBuf = new scalar_t[globalSumSize];
161 env->localMemoryAssertion(__FILE__, __LINE__, globalSumSize, sumBuf);
162 globalSums = arcp(sumBuf, 0, globalSumSize);
163
165 // Calculate the local totals by part.
166
167 scalar_t *localBuf = new scalar_t[globalSumSize];
168 env->localMemoryAssertion(__FILE__, __LINE__, globalSumSize, localBuf);
169 memset(localBuf, 0, sizeof(scalar_t) * globalSumSize);
170
171 scalar_t *obj = localBuf; // # of objects
172
173 for (lno_t i=0; i < localNumObj; i++)
174 obj[part[i]]++;
175
176 if (numMetrics > 1){
177
178 scalar_t *wgt = localBuf+maxPartPlusOne; // single normed weight or weight 0
179 try{
180 normedPartWeights<scalar_t, lno_t, part_t>(env, maxPartPlusOne,
181 part, vwgts, mcNorm, wgt);
182 }
184
185 // This code assumes the solution has the part ordered the
186 // same way as the user input. (Bug 5891 is resolved.)
187 if (vwgtDim > 1){
188 wgt += maxPartPlusOne; // individual weights
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;
193 }
194 }
195 }
196
197 // Metric: local sums on process
198 metrics[next]->setName("object count");
199 metrics[next]->setMetricValue("local sum", localNumObj);
200
201 next++;
202
203 if (numMetrics > 1){
204 scalar_t *wgt = localBuf+maxPartPlusOne; // single normed weight or weight 0
205 scalar_t total = 0.0;
206
207 for (int p=0; p < maxPartPlusOne; p++){
208 total += wgt[p];
209 }
210
211 if (vwgtDim == 1)
212 metrics[next]->setName("weight 0");
213 else
214 metrics[next]->setName("normed weight");
215
216 metrics[next]->setMetricValue("local sum", total);
217
218 next++;
219
220 if (vwgtDim > 1){
221 for (int vdim = 0; vdim < vwgtDim; vdim++){
222 wgt += maxPartPlusOne;
223 total = 0.0;
224 for (int p=0; p < maxPartPlusOne; p++){
225 total += wgt[p];
226 }
227
228 std::ostringstream oss;
229 oss << "weight " << vdim;
230
231 metrics[next]->setName(oss.str());
232 metrics[next]->setMetricValue("local sum", total);
233
234 next++;
235 }
236 }
237 }
238
240 // Obtain global totals by part.
241
242 try{
243 reduceAll<int, scalar_t>(*comm, Teuchos::REDUCE_SUM, globalSumSize,
244 localBuf, sumBuf);
245 }
247
248 delete [] localBuf;
249
251 // Global sum, min, max, and average over all parts
252
253 obj = sumBuf; // # of objects
254 scalar_t min=0, max=0, sum=0;
255 next = metrics.size() - numMetrics; // MDM - this is most likely temporary
256 // to preserve the format here - we are
257 // now filling a larger array so we may
258 // not have started at 0
259
260
261 ArrayView<scalar_t> objVec(obj, maxPartPlusOne);
262 getStridedStats<scalar_t>(objVec, 1, 0, min, max, sum);
263 if (maxPartPlusOne < targetNumParts)
264 min = scalar_t(0); // Some of the target parts are empty
265
266 metrics[next]->setMetricValue("global minimum", min);
267 metrics[next]->setMetricValue("global maximum", max);
268 metrics[next]->setMetricValue("global sum", sum);
269 next++;
270
271 if (numMetrics > 1){
272 scalar_t *wgt = sumBuf + maxPartPlusOne; // single normed weight or weight 0
273
274 ArrayView<scalar_t> normedWVec(wgt, maxPartPlusOne);
275 getStridedStats<scalar_t>(normedWVec, 1, 0, min, max, sum);
276 if (maxPartPlusOne < targetNumParts)
277 min = scalar_t(0); // Some of the target parts are empty
278
279 metrics[next]->setMetricValue("global minimum", min);
280 metrics[next]->setMetricValue("global maximum", max);
281 metrics[next]->setMetricValue("global sum", sum);
282 next++;
283
284 if (vwgtDim > 1){
285 for (int vdim=0; vdim < vwgtDim; vdim++){
286 wgt += maxPartPlusOne; // individual weights
287 ArrayView<scalar_t> fromVec(wgt, maxPartPlusOne);
288 getStridedStats<scalar_t>(fromVec, 1, 0, min, max, sum);
289 if (maxPartPlusOne < targetNumParts)
290 min = scalar_t(0); // Some of the target parts are empty
291
292 metrics[next]->setMetricValue("global minimum", min);
293 metrics[next]->setMetricValue("global maximum", max);
294 metrics[next]->setMetricValue("global sum", sum);
295 next++;
296 }
297 }
298 }
299
301 // How many parts do we actually have.
302
303 numExistingParts = maxPartPlusOne;
304 obj = sumBuf; // # of objects
305
306 /*for (part_t p=nparts-1; p > 0; p--){
307 if (obj[p] > 0) break;
308 numExistingParts--;
309 }*/
310
311 numNonemptyParts = numExistingParts;
312
313 for (part_t p=0; p < numExistingParts; p++)
314 if (obj[p] == 0) numNonemptyParts--;
315
316 env->debug(DETAILED_STATUS, "Exiting globalSumsByPart");
317}
318
349template <typename Adapter>
351 const RCP<const Environment> &env,
352 const RCP<const Comm<int> > &comm,
353 multiCriteriaNorm mcNorm,
354 const Adapter *ia,
355 const PartitioningSolution<Adapter> *solution,
356 const ArrayView<const typename Adapter::part_t> &partArray,
357 const RCP<const GraphModel<typename Adapter::base_adapter_t> > &graphModel,
358 typename Adapter::part_t &numExistingParts,
359 typename Adapter::part_t &numNonemptyParts,
360 ArrayRCP<RCP<BaseClassMetrics<typename Adapter::scalar_t> > > &metrics)
361{
362 env->debug(DETAILED_STATUS, "Entering objectMetrics");
363
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;
369 typedef StridedData<lno_t, scalar_t> sdata_t;
370
371 // Local number of objects.
372
373 size_t numLocalObjects = ia->getLocalNumIDs();
374
375 // Weights, if any, for each object.
376
377 int nWeights = ia->getNumWeightsPerID();
378 int numCriteria = (nWeights > 0 ? nWeights : 1);
379 Array<sdata_t> weights(numCriteria);
380
381 if (nWeights == 0){
382 // One set of uniform weights is implied.
383 // StridedData default constructor creates length 0 strided array.
384 weights[0] = sdata_t();
385 }
386 else{
387 // whether vertex degree is ever used as vertex weight.
388 enum BaseAdapterType adapterType = ia->adapterType();
389 bool useDegreeAsWeight = false;
390 if (adapterType == GraphAdapterType) {
391 useDegreeAsWeight = reinterpret_cast<const GraphAdapter
392 <typename Adapter::user_t, typename Adapter::userCoord_t> *>(ia)->
393 useDegreeAsWeight(0);
394 } else if (adapterType == MatrixAdapterType) {
395 useDegreeAsWeight = reinterpret_cast<const MatrixAdapter
396 <typename Adapter::user_t, typename Adapter::userCoord_t> *>(ia)->
397 useDegreeAsWeight(0);
398 } else if (adapterType == MeshAdapterType) {
399 useDegreeAsWeight =
400 reinterpret_cast<const MeshAdapter<typename Adapter::user_t> *>(ia)->
401 useDegreeAsWeight(0);
402 }
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);
411 graph = rcp(new GraphModel<base_adapter_t>(bia,env,comm,modelFlags));
412 graph->getVertexList(Ids, vwgts);
413 } else {
414 graphModel->getVertexList(Ids, vwgts);
415 }
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];
420 }
421 ArrayRCP<const scalar_t> wgtArray(wgt,0,numLocalObjects,false);
422 weights[i] = sdata_t(wgtArray, 1);
423 }
424 } else {
425 for (int i=0; i < nWeights; i++){
426 const scalar_t *wgt;
427 int stride;
428 ia->getWeightsView(wgt, stride, i);
429 ArrayRCP<const scalar_t> wgtArray(wgt,0,stride*numLocalObjects,false);
430 weights[i] = sdata_t(wgtArray, stride);
431 }
432 }
433 }
434
435 // Relative part sizes, if any, assigned to the parts.
436
437 part_t targetNumParts = comm->getSize();
438 scalar_t *psizes = NULL;
439
440 ArrayRCP<ArrayRCP<scalar_t> > partSizes(numCriteria);
441 if (solution) {
442 targetNumParts = solution->getTargetGlobalNumberOfParts();
443 for (int dim=0; dim < numCriteria; dim++){
444 if (solution->criteriaHasUniformPartSizes(dim) != true){
445 psizes = new scalar_t [targetNumParts];
446 env->localMemoryAssertion(__FILE__, __LINE__, targetNumParts, psizes);
447 for (part_t i=0; i < targetNumParts; i++){
448 psizes[i] = solution->getCriteriaPartSize(dim, i);
449 }
450 partSizes[dim] = arcp(psizes, 0, targetNumParts, true);
451 }
452 }
453 }
454
456 // Get number of parts, and the number that are non-empty.
457 // Get sums per part of objects, individual weights, and normed weight sums.
458
459 ArrayRCP<scalar_t> globalSums;
460
461 int initialMetricCount = metrics.size();
462 try{
463 globalSumsByPart<scalar_t, lno_t, part_t>(env, comm,
464 partArray, nWeights, weights.view(0, numCriteria), mcNorm,
465 targetNumParts, numExistingParts, numNonemptyParts, metrics, globalSums);
466 }
468
469 int addedMetricsCount = metrics.size() - initialMetricCount;
470
472 // Compute imbalances for the object count.
473 // (Use first index of part sizes.)
474
475 int index = initialMetricCount;
476
477 scalar_t *objCount = globalSums.getRawPtr();
478 scalar_t min, max, avg;
479 psizes=NULL;
480
481 if (partSizes[0].size() > 0)
482 psizes = partSizes[0].getRawPtr();
483
484 scalar_t gsum = metrics[index]->getMetricValue("global sum");
485 computeImbalances<scalar_t, part_t>(numExistingParts, targetNumParts, psizes,
486 gsum, objCount, min, max, avg);
487
488 metrics[index]->setMetricValue("global average", gsum / targetNumParts);
489
490 metrics[index]->setMetricValue("maximum imbalance", 1.0 + max);
491 metrics[index]->setMetricValue("average imbalance", avg);
492
494 // Compute imbalances for the normed weight sum.
495
496 scalar_t *wgts = globalSums.getRawPtr() + numExistingParts;
497
498 if (addedMetricsCount > 1){
499 ++index;
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);
503
504 metrics[index]->setMetricValue("global average", gsum / targetNumParts);
505
506 metrics[index]->setMetricValue("maximum imbalance", 1.0 + max);
507 metrics[index]->setMetricValue("average imbalance", avg);
508
509 if (addedMetricsCount > 2){
510
512 // Compute imbalances for each individual weight.
513
514 ++index;
515
516 for (int vdim=0; vdim < numCriteria; vdim++){
517 wgts += numExistingParts;
518 psizes = NULL;
519
520 if (partSizes[vdim].size() > 0)
521 psizes = partSizes[vdim].getRawPtr();
522
523 gsum = metrics[index]->getMetricValue("global sum");
524 computeImbalances<scalar_t, part_t>(numExistingParts, targetNumParts,
525 psizes, gsum, wgts, min, max, avg);
526
527 metrics[index]->setMetricValue("global average", gsum / targetNumParts);
528
529 metrics[index]->setMetricValue("maximum imbalance", 1.0 + max);
530 metrics[index]->setMetricValue("average imbalance", avg);
531 index++;
532 }
533 }
534
535 }
536 env->debug(DETAILED_STATUS, "Exiting objectMetrics");
537}
538
541template <typename scalar_t, typename part_t>
543 std::ostream &os,
544 part_t targetNumParts,
545 part_t numExistingParts,
546 part_t numNonemptyParts)
547{
548 os << "Imbalance Metrics: (" << numExistingParts << " existing parts)";
549 if (numNonemptyParts < numExistingParts) {
550 os << " (" << numNonemptyParts << " of which are non-empty)";
551 }
552 os << std::endl;
553 if (targetNumParts != numExistingParts) {
554 os << "Target number of parts is " << targetNumParts << std::endl;
555 }
557}
558
561template <typename scalar_t, typename part_t>
563 std::ostream &os,
564 part_t targetNumParts,
565 part_t numExistingParts,
566 part_t numNonemptyParts,
567 const ArrayView<RCP<BaseClassMetrics<scalar_t> > > &infoList)
568{
569 printImbalanceMetricsHeader<scalar_t, part_t>(os, targetNumParts,
570 numExistingParts,
571 numNonemptyParts);
572 for (int i=0; i < infoList.size(); i++) {
573 if (infoList[i]->getName() != METRICS_UNSET_STRING) {
574 infoList[i]->printLine(os);
575 }
576 }
577 os << std::endl;
578}
579
582template <typename scalar_t, typename part_t>
584 std::ostream &os,
585 part_t targetNumParts,
586 part_t numExistingParts,
587 part_t numNonemptyParts,
588 RCP<BaseClassMetrics<scalar_t>> metricValue)
589{
590 printImbalanceMetricsHeader<scalar_t, part_t>(os, targetNumParts,
591 numExistingParts,
592 numNonemptyParts);
593 metricValue->printLine(os);
594}
595
596} //namespace Zoltan2
597
598
599#endif
#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.
static void printHeader(std::ostream &os)
Print a standard header.
MatrixAdapter defines the adapter interface for matrices.
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.
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.
static ArrayRCP< ArrayRCP< zscalar_t > > weights
SparseMatrixAdapter_t::part_t part_t