src/libs/ck-libs/metis/libmetis/mcutil.c

   1 /*
   2  * mutil.c
   3  *
   4  * This file contains various utility functions for the MOC portion of the
   5  * code
   6  *
   7  * Started 2/15/98
   8  * George
   9  *
  10  * $Id: mcutil.c 13901 2013-03-24 16:17:03Z karypis $
  11  *
  12  */
  13
  14 #include "metislib.h"
  15
  16
  17 /*************************************************************************/
  18 /*! This function compares two vectors x & y and returns true
  19     if \forall i, x[i] <= y[i].
  20 */
  21 /**************************************************************************/
  22 int rvecle(idx_t n, real_t *x, real_t *y)
  23 {
  24   for (n--; n>=0; n--) {
  25     if (x[n] > y[n])
  26       return 0;
  27   }
  28
  29   return  1;
  30 }
  31
  32
  33 /*************************************************************************/
  34 /*! This function compares two vectors x & y and returns true
  35     if \forall i, x[i] >= y[i].
  36 */
  37 /**************************************************************************/
  38 int rvecge(idx_t n, real_t *x, real_t *y)
  39 {
  40   for (n--; n>=0; n--) {
  41     if (x[n] < y[n])
  42       return 0;
  43   }
  44
  45   return  1;
  46 }
  47
  48
  49 /*************************************************************************/
  50 /*! This function compares vectors x1+x2 against y and returns true
  51     if \forall i, x1[i]+x2[i] <= y[i].
  52 */
  53 /**************************************************************************/
  54 int rvecsumle(idx_t n, real_t *x1, real_t *x2, real_t *y)
  55 {
  56   for (n--; n>=0; n--) {
  57     if (x1[n]+x2[n] > y[n])
  58       return 0;
  59   }
  60
  61   return 1;
  62 }
  63
  64
  65 /*************************************************************************/
  66 /*! This function returns max_i(x[i]-y[i]) */
  67 /**************************************************************************/
  68 real_t rvecmaxdiff(idx_t n, real_t *x, real_t *y)
  69 {
  70   real_t max;
  71
  72   max = x[0]-y[0];
  73
  74   for (n--; n>0; n--) {
  75     if (max < x[n]-y[n])
  76       max = x[n]-y[n];
  77   }
  78
  79   return max;
  80 }
  81
  82
  83 /*************************************************************************/
  84 /*! This function returns true if \forall i, x[i] <= z[i]. */
  85 /**************************************************************************/
  86 int ivecle(idx_t n, idx_t *x, idx_t *z)
  87 {
  88   for (n--; n>=0; n--) {
  89     if (x[n] > z[n])
  90       return 0;
  91   }
  92
  93   return  1;
  94 }
  95
  96
  97 /*************************************************************************/
  98 /*! This function returns true if \forall i, x[i] >= z[i]. */
  99 /**************************************************************************/
 100 int ivecge(idx_t n, idx_t *x, idx_t *z)
 101 {
 102   for (n--; n>=0; n--) {
 103     if (x[n] < z[n])
 104       return 0;
 105   }
 106
 107   return  1;
 108 }
 109
 110
 111 /*************************************************************************/
 112 /*! This function returns true if \forall i, a*x[i]+y[i] <= z[i]. */
 113 /**************************************************************************/
 114 int ivecaxpylez(idx_t n, idx_t a, idx_t *x, idx_t *y, idx_t *z)
 115 {
 116   for (n--; n>=0; n--) {
 117     if (a*x[n]+y[n] > z[n])
 118       return 0;
 119   }
 120
 121   return  1;
 122 }
 123
 124
 125 /*************************************************************************/
 126 /*! This function returns true if \forall i, a*x[i]+y[i] >= z[i]. */
 127 /**************************************************************************/
 128 int ivecaxpygez(idx_t n, idx_t a, idx_t *x, idx_t *y, idx_t *z)
 129 {
 130   for (n--; n>=0; n--) {
 131     if (a*x[n]+y[n] < z[n])
 132       return 0;
 133   }
 134
 135   return  1;
 136 }
 137
 138
 139 /*************************************************************************/
 140 /*! This function checks if v+u2 provides a better balance in the weight
 141      vector that v+u1 */
 142 /*************************************************************************/
 143 int BetterVBalance(idx_t ncon, real_t *invtvwgt, idx_t *v_vwgt, idx_t *u1_vwgt,
 144         idx_t *u2_vwgt)
 145 {
 146   idx_t i;
 147   real_t sum1=0.0, sum2=0.0, diff1=0.0, diff2=0.0;
 148
 149   for (i=0; i<ncon; i++) {
 150     sum1 += (v_vwgt[i]+u1_vwgt[i])*invtvwgt[i];
 151     sum2 += (v_vwgt[i]+u2_vwgt[i])*invtvwgt[i];
 152   }
 153   sum1 = sum1/ncon;
 154   sum2 = sum2/ncon;
 155
 156   for (i=0; i<ncon; i++) {
 157     diff1 += rabs(sum1 - (v_vwgt[i]+u1_vwgt[i])*invtvwgt[i]);
 158     diff2 += rabs(sum2 - (v_vwgt[i]+u2_vwgt[i])*invtvwgt[i]);
 159   }
 160
 161   return (diff1 - diff2 >= 0);
 162 }
 163
 164
 165 /*************************************************************************/
 166 /*! This function takes two ubfactor-centered load imbalance vectors x & y,
 167     and returns true if y is better balanced than x. */
 168 /*************************************************************************/
 169 int BetterBalance2Way(idx_t n, real_t *x, real_t *y)
 170 {
 171   real_t nrm1=0.0, nrm2=0.0;
 172
 173   for (--n; n>=0; n--) {
 174     if (x[n] > 0) nrm1 += x[n]*x[n];
 175     if (y[n] > 0) nrm2 += y[n]*y[n];
 176   }
 177   return nrm2 < nrm1;
 178 }
 179
 180
 181 /*************************************************************************/
 182 /*! Given a vertex and two weights, this function returns 1, if the second
 183     partition will be more balanced than the first after the weighted
 184     additional of that vertex.
 185     The balance determination takes into account the ideal target weights
 186     of the two partitions.
 187 */
 188 /*************************************************************************/
 189 int BetterBalanceKWay(idx_t ncon, idx_t *vwgt, real_t *ubvec,
 190         idx_t a1, idx_t *pt1, real_t *bm1,
 191         idx_t a2, idx_t *pt2, real_t *bm2)
 192 {
 193   idx_t i;
 194   real_t tmp, nrm1=0.0, nrm2=0.0, max1=0.0, max2=0.0;
 195
 196   for (i=0; i<ncon; i++) {
 197     tmp = bm1[i]*(pt1[i]+a1*vwgt[i]) - ubvec[i];
 198     //printf("BB: %d %+.4f ", (int)i, (float)tmp);
 199     nrm1 += tmp*tmp;
 200     max1 = (tmp > max1 ? tmp : max1);
 201
 202     tmp = bm2[i]*(pt2[i]+a2*vwgt[i]) - ubvec[i];
 203     //printf("%+.4f ", (float)tmp);
 204     nrm2 += tmp*tmp;
 205     max2 = (tmp > max2 ? tmp : max2);
 206
 207     //printf("%4d %4d %4d %4d %4d %4d %4d %.2f\n",
 208     //    (int)vwgt[i],
 209     //    (int)a1, (int)pt1[i], (int)tpt1[i],
 210     //    (int)a2, (int)pt2[i], (int)tpt2[i], ubvec[i]);
 211   }
 212   //printf("   %.3f %.3f %.3f %.3f\n", (float)max1, (float)nrm1, (float)max2, (float)nrm2);
 213
 214   if (max2 < max1)
 215     return 1;
 216
 217   if (max2 == max1 && nrm2 < nrm1)
 218     return 1;
 219
 220   return 0;
 221 }
 222
 223
 224 /*************************************************************************/
 225 /*! Computes the maximum load imbalance of a partitioning solution over
 226     all the constraints. */
 227 /**************************************************************************/
 228 real_t ComputeLoadImbalance(graph_t *graph, idx_t nparts, real_t *pijbm)
 229 {
 230   idx_t i, j, ncon, *pwgts;
 231   real_t max, cur;
 232
 233   ncon  = graph->ncon;
 234   pwgts = graph->pwgts;
 235
 236   max = 1.0;
 237   for (i=0; i<ncon; i++) {
 238     for (j=0; j<nparts; j++) {
 239       cur = pwgts[j*ncon+i]*pijbm[j*ncon+i];
 240       if (cur > max)
 241         max = cur;
 242     }
 243   }
 244
 245   return max;
 246 }
 247
 248
 249 /*************************************************************************/
 250 /*! Computes the maximum load imbalance difference of a partitioning
 251     solution over all the constraints.
 252     The difference is defined with respect to the allowed maximum
 253     unbalance for the respective constraint.
 254  */
 255 /**************************************************************************/
 256 real_t ComputeLoadImbalanceDiff(graph_t *graph, idx_t nparts, real_t *pijbm,
 257            real_t *ubvec)
 258 {
 259   idx_t i, j, ncon, *pwgts;
 260   real_t max, cur;
 261
 262   ncon  = graph->ncon;
 263   pwgts = graph->pwgts;
 264
 265   max = -1.0;
 266   for (i=0; i<ncon; i++) {
 267     for (j=0; j<nparts; j++) {
 268       cur = pwgts[j*ncon+i]*pijbm[j*ncon+i] - ubvec[i];
 269       if (cur > max)
 270         max = cur;
 271     }
 272   }
 273
 274   return max;
 275 }
 276
 277
 278 /*************************************************************************/
 279 /*! Computes the difference between load imbalance of each constraint across
 280     the partitions minus the desired upper bound on the load imabalnce.
 281     It also returns the maximum load imbalance across the partitions &
 282     constraints. */
 283 /**************************************************************************/
 284 real_t ComputeLoadImbalanceDiffVec(graph_t *graph, idx_t nparts, real_t *pijbm,
 285          real_t *ubfactors, real_t *diffvec)
 286 {
 287   idx_t i, j, ncon, *pwgts;
 288   real_t cur, max;
 289
 290   ncon  = graph->ncon;
 291   pwgts = graph->pwgts;
 292
 293   for (max=-1.0, i=0; i<ncon; i++) {
 294     diffvec[i] = pwgts[i]*pijbm[i] - ubfactors[i];
 295     for (j=1; j<nparts; j++) {
 296       cur = pwgts[j*ncon+i]*pijbm[j*ncon+i] - ubfactors[i];
 297       if (cur > diffvec[i])
 298         diffvec[i] = cur;
 299     }
 300     if (max < diffvec[i])
 301       max = diffvec[i];
 302   }
 303
 304   return max;
 305 }
 306
 307
 308 /*************************************************************************/
 309 /*! Computes the load imbalance of each constraint across the partitions. */
 310 /**************************************************************************/
 311 void ComputeLoadImbalanceVec(graph_t *graph, idx_t nparts, real_t *pijbm,
 312          real_t *lbvec)
 313 {
 314   idx_t i, j, ncon, *pwgts;
 315   real_t cur;
 316
 317   ncon  = graph->ncon;
 318   pwgts = graph->pwgts;
 319
 320   for (i=0; i<ncon; i++) {
 321     lbvec[i] = pwgts[i]*pijbm[i];
 322     for (j=1; j<nparts; j++) {
 323       cur = pwgts[j*ncon+i]*pijbm[j*ncon+i];
 324       if (cur > lbvec[i])
 325         lbvec[i] = cur;
 326     }
 327   }
 328 }
 329
 330