Zoltan2
Loading...
Searching...
No Matches
Zoltan2_MetricUtility.hpp
Go to the documentation of this file.
1// @HEADER
2// *****************************************************************************
3// Zoltan2: A package of combinatorial algorithms for scientific computing
4//
5// Copyright 2012 NTESS and the Zoltan2 contributors.
6// SPDX-License-Identifier: BSD-3-Clause
7// *****************************************************************************
8// @HEADER
9
14#ifndef ZOLTAN2_METRICFUNCTIONS_HPP
15#define ZOLTAN2_METRICFUNCTIONS_HPP
16
18
19namespace Zoltan2{
20
21// this utlity method is used to allocate more metrics in the metric array
22// the array is composed of an array of ptrs to BaseClassMetric
23// but each ptr is allocated to the specific derived metric type
24// So the array can access the polymorphic hierarchy
25//
26// Note this is currently only relevant to EvaluatePartition and the
27// GraphMetrics and ImbalanceMetrics calculations
28template <typename metric_t, typename scalar_t>
29RCP<metric_t> addNewMetric(const RCP<const Environment> &env,
30 ArrayRCP<RCP<BaseClassMetrics<scalar_t> > > &metrics)
31{
32 metrics.resize(metrics.size() + 1); // increase array size by 1
33 metric_t * newMetric = new metric_t; // allocate
34 env->localMemoryAssertion(__FILE__,__LINE__,1,newMetric); // check errors
35 RCP<metric_t> newRCP = rcp(newMetric); // rcp of derived class
36 metrics[metrics.size()-1] = newRCP; // create the new rcp
37 return newRCP;
38}
39
41// Namespace methods to compute metric values
43
53template <typename scalar_t>
54 void getStridedStats(const ArrayView<scalar_t> &v, int stride,
55 int offset, scalar_t &min, scalar_t &max, scalar_t &sum)
56{
57 if (v.size() < 1) return;
58 min = max = sum = v[offset];
59
60 for (int i=offset+stride; i < v.size(); i += stride){
61 if (v[i] < min) min = v[i];
62 else if (v[i] > max) max = v[i];
63 sum += v[i];
64 }
65}
66
75template <typename scalar_t>
76 void getStridedStats(const ArrayView<scalar_t> &v, int stride,
77 int offset, scalar_t &max, scalar_t &sum)
78{
79 if (v.size() < 1) return;
80 max = sum = v[offset];
81
82 for (int i=offset+stride; i < v.size(); i += stride){
83 if (v[i] > max) max = v[i];
84 sum += v[i];
85 }
86}
87
106template <typename scalar_t, typename lno_t, typename part_t>
108 const RCP<const Environment> &env,
109 part_t numberOfParts,
110 const ArrayView<const part_t> &parts,
111 const ArrayView<StridedData<lno_t, scalar_t> > &vwgts,
112 multiCriteriaNorm mcNorm,
113 scalar_t *weights)
114{
115 env->localInputAssertion(__FILE__, __LINE__, "parts or weights",
116 numberOfParts > 0 && vwgts.size() > 0, BASIC_ASSERTION);
117
118 int numObjects = parts.size();
119 int vwgtDim = vwgts.size();
120
121 memset(weights, 0, sizeof(scalar_t) * numberOfParts);
122
123 if (numObjects == 0)
124 return;
125
126 if (vwgtDim == 0) {
127 for (lno_t i=0; i < numObjects; i++){
128 weights[parts[i]]++;
129 }
130 }
131 else if (vwgtDim == 1){
132 for (lno_t i=0; i < numObjects; i++){
133 weights[parts[i]] += vwgts[0][i];
134 }
135 }
136 else{
137 switch (mcNorm){
139 for (int wdim=0; wdim < vwgtDim; wdim++){
140 for (lno_t i=0; i < numObjects; i++){
141 weights[parts[i]] += vwgts[wdim][i];
142 }
143 } // next weight index
144 break;
145
147 for (lno_t i=0; i < numObjects; i++){
148 scalar_t ssum = 0;
149 for (int wdim=0; wdim < vwgtDim; wdim++)
150 ssum += (vwgts[wdim][i] * vwgts[wdim][i]);
151 weights[parts[i]] += sqrt(ssum);
152 }
153 break;
154
156 for (lno_t i=0; i < numObjects; i++){
157 scalar_t max = 0;
158 for (int wdim=0; wdim < vwgtDim; wdim++)
159 if (vwgts[wdim][i] > max)
160 max = vwgts[wdim][i];
161 weights[parts[i]] += max;
162 }
163 break;
164
165 default:
166 env->localBugAssertion(__FILE__, __LINE__, "invalid norm", false,
168 break;
169 }
170 }
171}
172
203template <typename scalar_t, typename part_t>
205 part_t numExistingParts, // Max Part ID + 1
206 part_t targetNumParts, // comm.size() or requested global # parts from soln
207 const scalar_t *psizes,
208 scalar_t sumVals,
209 const scalar_t *vals,
210 scalar_t &min,
211 scalar_t &max,
212 scalar_t &avg)
213{
214 min = sumVals;
215 max = avg = 0;
216
217 if (sumVals <= 0 || targetNumParts < 1 || numExistingParts < 1)
218 return;
219
220 if (targetNumParts==1) {
221 min = max = avg = 0; // 0 imbalance
222 return;
223 }
224
225 if (!psizes){
226 scalar_t target = sumVals / targetNumParts;
227 for (part_t p=0; p < numExistingParts; p++){
228 scalar_t diff = vals[p] - target;
229 scalar_t adiff = (diff >= 0 ? diff : -diff);
230 scalar_t tmp = diff / target;
231 scalar_t atmp = adiff / target;
232 avg += atmp;
233 if (tmp > max) max = tmp;
234 if (tmp < min) min = tmp;
235 }
236 part_t emptyParts = targetNumParts - numExistingParts;
237 if (emptyParts > 0){
238 if (max < 1.0)
239 max = 1.0; // target divided by target
240 avg += emptyParts;
241 }
242 }
243 else{
244 for (part_t p=0; p < targetNumParts; p++){
245 if (psizes[p] > 0){
246 if (p < numExistingParts){
247 scalar_t target = sumVals * psizes[p];
248 scalar_t diff = vals[p] - target;
249 scalar_t adiff = (diff >= 0 ? diff : -diff);
250 scalar_t tmp = diff / target;
251 scalar_t atmp = adiff / target;
252 avg += atmp;
253 if (tmp > max) max = tmp;
254 if (tmp < min) min = tmp;
255 }
256 else{
257 if (max < 1.0)
258 max = 1.0; // target divided by target
259 avg += 1.0;
260 }
261 }
262 }
263 }
264
265 avg /= targetNumParts;
266}
267
301template <typename scalar_t, typename part_t>
303 part_t numExistingParts,
304 part_t targetNumParts,
305 int numSizes,
306 ArrayView<ArrayRCP<scalar_t> > psizes,
307 scalar_t sumVals,
308 const scalar_t *vals,
309 scalar_t &min,
310 scalar_t &max,
311 scalar_t &avg)
312{
313 min = sumVals;
314 max = avg = 0;
315
316 if (sumVals <= 0 || targetNumParts < 1 || numExistingParts < 1)
317 return;
318
319 if (targetNumParts==1) {
320 min = max = avg = 0; // 0 imbalance
321 return;
322 }
323
324 bool allUniformParts = true;
325 for (int i=0; i < numSizes; i++){
326 if (psizes[i].size() != 0){
327 allUniformParts = false;
328 break;
329 }
330 }
331
332 if (allUniformParts){
333 computeImbalances<scalar_t, part_t>(numExistingParts, targetNumParts, NULL,
334 sumVals, vals, min, max, avg);
335 return;
336 }
337
338 double uniformSize = 1.0 / targetNumParts;
339 std::vector<double> sizeVec(numSizes);
340 for (int i=0; i < numSizes; i++){
341 sizeVec[i] = uniformSize;
342 }
343
344 for (part_t p=0; p < numExistingParts; p++){
345
346 // If we have objects in parts that should have 0 objects,
347 // we don't compute an imbalance. It means that other
348 // parts have too few objects, and the imbalance will be
349 // picked up there.
350
351 if (p >= targetNumParts)
352 break;
353
354 // Vector of target amounts: T
355
356 double targetNorm = 0;
357 for (int i=0; i < numSizes; i++) {
358 if (psizes[i].size() > 0)
359 sizeVec[i] = psizes[i][p];
360 sizeVec[i] *= sumVals;
361 targetNorm += (sizeVec[i] * sizeVec[i]);
362 }
363 targetNorm = sqrt(targetNorm);
364
365 // If part is supposed to be empty, we don't compute an
366 // imbalance. Same argument as above.
367
368 if (targetNorm > 0){
369
370 // Vector of actual amounts: A
371
372 std::vector<double> actual(numSizes);
373 double actualNorm = 0.;
374 for (int i=0; i < numSizes; i++) {
375 actual[i] = vals[p] * -1.0;
376 actual[i] += sizeVec[i];
377 actualNorm += (actual[i] * actual[i]);
378 }
379 actualNorm = sqrt(actualNorm);
380
381 // |A - T| / |T|
382
383 scalar_t imbalance = actualNorm / targetNorm;
384
385 if (imbalance < min)
386 min = imbalance;
387 else if (imbalance > max)
388 max = imbalance;
389 avg += imbalance;
390 }
391 }
392
393 part_t numEmptyParts = 0;
394
395 for (part_t p=numExistingParts; p < targetNumParts; p++){
396 bool nonEmptyPart = false;
397 for (int i=0; !nonEmptyPart && i < numSizes; i++)
398 if (psizes[i].size() > 0 && psizes[i][p] > 0.0)
399 nonEmptyPart = true;
400
401 if (nonEmptyPart){
402 // The partition has no objects for this part, which
403 // is supposed to be non-empty.
404 numEmptyParts++;
405 }
406 }
407
408 if (numEmptyParts > 0){
409 avg += numEmptyParts;
410 if (max < 1.0)
411 max = 1.0; // target divided by target
412 }
413
414 avg /= targetNumParts;
415}
416
419template <typename scalar_t>
420 scalar_t normedWeight(ArrayView <scalar_t> weights,
422{
423 size_t dim = weights.size();
424 if (dim == 0)
425 return 0.0;
426 else if (dim == 1)
427 return weights[0];
428
429 scalar_t nweight = 0;
430
431 switch (norm){
434 for (size_t i=0; i <dim; i++)
435 nweight += weights[i];
436
437 break;
438
440 for (size_t i=0; i <dim; i++)
441 nweight += (weights[i] * weights[i]);
442
443 nweight = sqrt(nweight);
444
445 break;
446
449 nweight = weights[0];
450 for (size_t i=1; i <dim; i++)
451 if (weights[i] > nweight)
452 nweight = weights[i];
453
454 break;
455
456 default:
457 std::ostringstream emsg;
458 emsg << __FILE__ << ":" << __LINE__ << std::endl;
459 emsg << "bug: " << "invalid norm" << std::endl;
460 throw std::logic_error(emsg.str());
461 }
462
463 return nweight;
464}
465
468template<typename lno_t, typename scalar_t>
470 lno_t idx, multiCriteriaNorm norm)
471{
472 size_t dim = weights.size();
473 if (dim < 1)
474 return 0;
475
476 Array<scalar_t> vec(dim, 1.0);
477 for (size_t i=0; i < dim; i++)
478 if (weights[i].size() > 0)
479 vec[dim] = weights[i][idx];
480
481 return normedWeight(vec, norm);
482}
483
484} //namespace Zoltan2
485
486#endif
This file defines the StridedData class.
The StridedData class manages lists of weights or coordinates.
map_t::local_ordinal_type lno_t
Created by mbenlioglu on Aug 31, 2020.
void computeImbalances(part_t numExistingParts, part_t targetNumParts, const scalar_t *psizes, scalar_t sumVals, const scalar_t *vals, scalar_t &min, scalar_t &max, scalar_t &avg)
Compute the imbalance.
void normedPartWeights(const RCP< const Environment > &env, part_t numberOfParts, const ArrayView< const part_t > &parts, const ArrayView< StridedData< lno_t, scalar_t > > &vwgts, multiCriteriaNorm mcNorm, scalar_t *weights)
Compute the total weight in each part on this process.
void getStridedStats(const ArrayView< scalar_t > &v, int stride, int offset, scalar_t &min, scalar_t &max, scalar_t &sum)
Find min, max and sum of metric values.
RCP< metric_t > addNewMetric(const RCP< const Environment > &env, ArrayRCP< RCP< BaseClassMetrics< scalar_t > > > &metrics)
scalar_t normedWeight(ArrayView< scalar_t > weights, multiCriteriaNorm norm)
Compute the norm of the vector of weights.
@ BASIC_ASSERTION
fast typical checks for valid arguments
multiCriteriaNorm
Enumerator used in code for multicriteria norm choice.
static ArrayRCP< ArrayRCP< zscalar_t > > weights
SparseMatrixAdapter_t::part_t part_t