Charm++: Charm Source Code Documentation

00001 
00011 #include "metislib.h"
00012 
00013 /*************************************************************************
00014 * This function is the entry poidx_t of the bisection balancing algorithms.
00015 **************************************************************************/
00016 void Balance2Way(ctrl_t *ctrl, graph_t *graph, real_t *ntpwgts)
00017 {
00018   if (ComputeLoadImbalanceDiff(graph, 2, ctrl->pijbm, ctrl->ubfactors) <= 0) 
00019     return;
00020 
00021   if (graph->ncon == 1) {
00022     /* return right away if the balance is OK */
00023     if (iabs((int)(ntpwgts[0]*graph->tvwgt[0]-graph->pwgts[0])) < 3*graph->tvwgt[0]/graph->nvtxs)
00024       return;
00025 
00026     if (graph->nbnd > 0)
00027       Bnd2WayBalance(ctrl, graph, ntpwgts);
00028     else
00029       General2WayBalance(ctrl, graph, ntpwgts);
00030   }
00031   else {
00032     McGeneral2WayBalance(ctrl, graph, ntpwgts);
00033   }
00034 }
00035 
00036 
00037 /*************************************************************************
00038 * This function balances two partitions by moving boundary nodes
00039 * from the domain that is overweight to the one that is underweight.
00040 **************************************************************************/
00041 void Bnd2WayBalance(ctrl_t *ctrl, graph_t *graph, real_t *ntpwgts)
00042 {
00043   idx_t i, ii, j, k, kwgt, nvtxs, nbnd, nswaps, from, to, pass, me, tmp;
00044   idx_t *xadj, *vwgt, *adjncy, *adjwgt, *where, *id, *ed, *bndptr, *bndind, *pwgts;
00045   idx_t *moved, *perm;
00046   rpq_t *queue;
00047   idx_t higain, mincut, mindiff;
00048   idx_t tpwgts[2];
00049 
00050   WCOREPUSH;
00051 
00052   nvtxs  = graph->nvtxs;
00053   xadj   = graph->xadj;
00054   vwgt   = graph->vwgt;
00055   adjncy = graph->adjncy;
00056   adjwgt = graph->adjwgt;
00057   where  = graph->where;
00058   id     = graph->id;
00059   ed     = graph->ed;
00060   pwgts  = graph->pwgts;
00061   bndptr = graph->bndptr;
00062   bndind = graph->bndind;
00063 
00064   moved = iwspacemalloc(ctrl, nvtxs);
00065   perm  = iwspacemalloc(ctrl, nvtxs);
00066 
00067   /* Determine from which domain you will be moving data */
00068   tpwgts[0] = graph->tvwgt[0]*ntpwgts[0];
00069   tpwgts[1] = graph->tvwgt[0] - tpwgts[0];
00070   mindiff   = iabs(tpwgts[0]-pwgts[0]);
00071   from      = (pwgts[0] < tpwgts[0] ? 1 : 0);
00072   to        = (from+1)%2;
00073 
00074   IFSET(ctrl->dbglvl, METIS_DBG_REFINE, 
00075      printf("Partitions: [%6"PRIDX" %6"PRIDX"] T[%6"PRIDX" %6"PRIDX"], Nv-Nb[%6"PRIDX" %6"PRIDX"]. ICut: %6"PRIDX" [B]\n",
00076              pwgts[0], pwgts[1], tpwgts[0], tpwgts[1], graph->nvtxs, graph->nbnd, 
00077              graph->mincut));
00078 
00079   queue = rpqCreate(nvtxs);
00080 
00081   iset(nvtxs, -1, moved);
00082 
00083   ASSERT(ComputeCut(graph, where) == graph->mincut);
00084   ASSERT(CheckBnd(graph));
00085 
00086   /* Insert the boundary nodes of the proper partition whose size is OK in the priority queue */
00087   nbnd = graph->nbnd;
00088   irandArrayPermute(nbnd, perm, nbnd/5, 1);
00089   for (ii=0; ii<nbnd; ii++) {
00090     i = perm[ii];
00091     ASSERT(ed[bndind[i]] > 0 || id[bndind[i]] == 0);
00092     ASSERT(bndptr[bndind[i]] != -1);
00093     if (where[bndind[i]] == from && vwgt[bndind[i]] <= mindiff)
00094       rpqInsert(queue, bndind[i], ed[bndind[i]]-id[bndind[i]]);
00095   }
00096 
00097   mincut = graph->mincut;
00098   for (nswaps=0; nswaps<nvtxs; nswaps++) {
00099     if ((higain = rpqGetTop(queue)) == -1)
00100       break;
00101     ASSERT(bndptr[higain] != -1);
00102 
00103     if (pwgts[to]+vwgt[higain] > tpwgts[to])
00104       break;
00105 
00106     mincut -= (ed[higain]-id[higain]);
00107     INC_DEC(pwgts[to], pwgts[from], vwgt[higain]);
00108 
00109     where[higain] = to;
00110     moved[higain] = nswaps;
00111 
00112     IFSET(ctrl->dbglvl, METIS_DBG_MOVEINFO, 
00113       printf("Moved %6"PRIDX" from %"PRIDX". [%3"PRIDX" %3"PRIDX"] %5"PRIDX" [%4"PRIDX" %4"PRIDX"]\n", higain, from, ed[higain]-id[higain], vwgt[higain], mincut, pwgts[0], pwgts[1]));
00114 
00115     /**************************************************************
00116     * Update the id[i]/ed[i] values of the affected nodes
00117     ***************************************************************/
00118     SWAP(id[higain], ed[higain], tmp);
00119     if (ed[higain] == 0 && xadj[higain] < xadj[higain+1]) 
00120       BNDDelete(nbnd, bndind,  bndptr, higain);
00121 
00122     for (j=xadj[higain]; j<xadj[higain+1]; j++) {
00123       k = adjncy[j];
00124       kwgt = (to == where[k] ? adjwgt[j] : -adjwgt[j]);
00125       INC_DEC(id[k], ed[k], kwgt);
00126 
00127       /* Update its boundary information and queue position */
00128       if (bndptr[k] != -1) { /* If k was a boundary vertex */
00129         if (ed[k] == 0) { /* Not a boundary vertex any more */
00130           BNDDelete(nbnd, bndind, bndptr, k);
00131           if (moved[k] == -1 && where[k] == from && vwgt[k] <= mindiff)  /* Remove it if in the queues */
00132             rpqDelete(queue, k);
00133         }
00134         else { /* If it has not been moved, update its position in the queue */
00135           if (moved[k] == -1 && where[k] == from && vwgt[k] <= mindiff)
00136             rpqUpdate(queue, k, ed[k]-id[k]);
00137         }
00138       }
00139       else {
00140         if (ed[k] > 0) {  /* It will now become a boundary vertex */
00141           BNDInsert(nbnd, bndind, bndptr, k);
00142           if (moved[k] == -1 && where[k] == from && vwgt[k] <= mindiff) 
00143             rpqInsert(queue, k, ed[k]-id[k]);
00144         }
00145       }
00146     }
00147   }
00148 
00149   IFSET(ctrl->dbglvl, METIS_DBG_REFINE, 
00150     printf("\tMinimum cut: %6"PRIDX", PWGTS: [%6"PRIDX" %6"PRIDX"], NBND: %6"PRIDX"\n", mincut, pwgts[0], pwgts[1], nbnd));
00151 
00152   graph->mincut = mincut;
00153   graph->nbnd   = nbnd;
00154 
00155   rpqDestroy(queue);
00156 
00157   WCOREPOP;
00158 }
00159 
00160 
00161 /*************************************************************************
00162 * This function balances two partitions by moving the highest gain 
00163 * (including negative gain) vertices to the other domain.
00164 * It is used only when tha unbalance is due to non contigous
00165 * subdomains. That is, the are no boundary vertices.
00166 * It moves vertices from the domain that is overweight to the one that 
00167 * is underweight.
00168 **************************************************************************/
00169 void General2WayBalance(ctrl_t *ctrl, graph_t *graph, real_t *ntpwgts)
00170 {
00171   idx_t i, ii, j, k, kwgt, nvtxs, nbnd, nswaps, from, to, pass, me, tmp;
00172   idx_t *xadj, *vwgt, *adjncy, *adjwgt, *where, *id, *ed, *bndptr, *bndind, *pwgts;
00173   idx_t *moved, *perm;
00174   rpq_t *queue;
00175   idx_t higain, mincut, mindiff;
00176   idx_t tpwgts[2];
00177 
00178   WCOREPUSH;
00179 
00180   nvtxs  = graph->nvtxs;
00181   xadj   = graph->xadj;
00182   vwgt   = graph->vwgt;
00183   adjncy = graph->adjncy;
00184   adjwgt = graph->adjwgt;
00185   where  = graph->where;
00186   id     = graph->id;
00187   ed     = graph->ed;
00188   pwgts  = graph->pwgts;
00189   bndptr = graph->bndptr;
00190   bndind = graph->bndind;
00191 
00192   moved = iwspacemalloc(ctrl, nvtxs);
00193   perm  = iwspacemalloc(ctrl, nvtxs);
00194 
00195   /* Determine from which domain you will be moving data */
00196   tpwgts[0] = graph->tvwgt[0]*ntpwgts[0];
00197   tpwgts[1] = graph->tvwgt[0] - tpwgts[0];
00198   mindiff   = iabs(tpwgts[0]-pwgts[0]);
00199   from      = (pwgts[0] < tpwgts[0] ? 1 : 0);
00200   to        = (from+1)%2;
00201 
00202   IFSET(ctrl->dbglvl, METIS_DBG_REFINE, 
00203      printf("Partitions: [%6"PRIDX" %6"PRIDX"] T[%6"PRIDX" %6"PRIDX"], Nv-Nb[%6"PRIDX" %6"PRIDX"]. ICut: %6"PRIDX" [B]\n",
00204              pwgts[0], pwgts[1], tpwgts[0], tpwgts[1], graph->nvtxs, graph->nbnd, graph->mincut));
00205 
00206   queue = rpqCreate(nvtxs);
00207 
00208   iset(nvtxs, -1, moved);
00209 
00210   ASSERT(ComputeCut(graph, where) == graph->mincut);
00211   ASSERT(CheckBnd(graph));
00212 
00213   /* Insert the nodes of the proper partition whose size is OK in the priority queue */
00214   irandArrayPermute(nvtxs, perm, nvtxs/5, 1);
00215   for (ii=0; ii<nvtxs; ii++) {
00216     i = perm[ii];
00217     if (where[i] == from && vwgt[i] <= mindiff)
00218       rpqInsert(queue, i, ed[i]-id[i]);
00219   }
00220 
00221   mincut = graph->mincut;
00222   nbnd = graph->nbnd;
00223   for (nswaps=0; nswaps<nvtxs; nswaps++) {
00224     if ((higain = rpqGetTop(queue)) == -1)
00225       break;
00226 
00227     if (pwgts[to]+vwgt[higain] > tpwgts[to])
00228       break;
00229 
00230     mincut -= (ed[higain]-id[higain]);
00231     INC_DEC(pwgts[to], pwgts[from], vwgt[higain]);
00232 
00233     where[higain] = to;
00234     moved[higain] = nswaps;
00235 
00236     IFSET(ctrl->dbglvl, METIS_DBG_MOVEINFO, 
00237       printf("Moved %6"PRIDX" from %"PRIDX". [%3"PRIDX" %3"PRIDX"] %5"PRIDX" [%4"PRIDX" %4"PRIDX"]\n", higain, from, ed[higain]-id[higain], vwgt[higain], mincut, pwgts[0], pwgts[1]));
00238 
00239     /**************************************************************
00240     * Update the id[i]/ed[i] values of the affected nodes
00241     ***************************************************************/
00242     SWAP(id[higain], ed[higain], tmp);
00243     if (ed[higain] == 0 && bndptr[higain] != -1 && xadj[higain] < xadj[higain+1]) 
00244       BNDDelete(nbnd, bndind,  bndptr, higain);
00245     if (ed[higain] > 0 && bndptr[higain] == -1)
00246       BNDInsert(nbnd, bndind,  bndptr, higain);
00247 
00248     for (j=xadj[higain]; j<xadj[higain+1]; j++) {
00249       k = adjncy[j];
00250 
00251       kwgt = (to == where[k] ? adjwgt[j] : -adjwgt[j]);
00252       INC_DEC(id[k], ed[k], kwgt);
00253 
00254       /* Update the queue position */
00255       if (moved[k] == -1 && where[k] == from && vwgt[k] <= mindiff)
00256         rpqUpdate(queue, k, ed[k]-id[k]);
00257 
00258       /* Update its boundary information */
00259       if (ed[k] == 0 && bndptr[k] != -1) 
00260         BNDDelete(nbnd, bndind, bndptr, k);
00261       else if (ed[k] > 0 && bndptr[k] == -1)  
00262         BNDInsert(nbnd, bndind, bndptr, k);
00263     }
00264   }
00265 
00266   IFSET(ctrl->dbglvl, METIS_DBG_REFINE, 
00267     printf("\tMinimum cut: %6"PRIDX", PWGTS: [%6"PRIDX" %6"PRIDX"], NBND: %6"PRIDX"\n", mincut, pwgts[0], pwgts[1], nbnd));
00268 
00269   graph->mincut = mincut;
00270   graph->nbnd   = nbnd;
00271 
00272   rpqDestroy(queue);
00273 
00274   WCOREPOP;
00275 }
00276 
00277 
00278 /*************************************************************************
00279 * This function performs an edge-based FM refinement
00280 **************************************************************************/
00281 void McGeneral2WayBalance(ctrl_t *ctrl, graph_t *graph, real_t *ntpwgts)
00282 {
00283   idx_t i, ii, j, k, l, kwgt, nvtxs, ncon, nbnd, nswaps, from, to, pass, 
00284         me, limit, tmp, cnum;
00285   idx_t *xadj, *adjncy, *vwgt, *adjwgt, *where, *pwgts, *id, *ed, *bndptr, *bndind;
00286   idx_t *moved, *swaps, *perm, *qnum, *qsizes;
00287   idx_t higain, mincut, newcut, mincutorder;
00288   real_t *invtvwgt, *minbalv, *newbalv, minbal, newbal;
00289   rpq_t **queues;
00290 
00291   WCOREPUSH;
00292 
00293   nvtxs    = graph->nvtxs;
00294   ncon     = graph->ncon;
00295   xadj     = graph->xadj;
00296   vwgt     = graph->vwgt;
00297   adjncy   = graph->adjncy;
00298   adjwgt   = graph->adjwgt;
00299   invtvwgt = graph->invtvwgt;
00300   where    = graph->where;
00301   id       = graph->id;
00302   ed       = graph->ed;
00303   pwgts    = graph->pwgts;
00304   bndptr   = graph->bndptr;
00305   bndind   = graph->bndind;
00306 
00307   moved   = iwspacemalloc(ctrl, nvtxs);
00308   swaps   = iwspacemalloc(ctrl, nvtxs);
00309   perm    = iwspacemalloc(ctrl, nvtxs);
00310   qnum    = iwspacemalloc(ctrl, nvtxs);
00311   newbalv = rwspacemalloc(ctrl, ncon);
00312   minbalv = rwspacemalloc(ctrl, ncon);
00313   qsizes  = iwspacemalloc(ctrl, 2*ncon);
00314 
00315   limit = gk_min(gk_max(0.01*nvtxs, 15), 100);
00316 
00317   /* Initialize the queues */
00318   queues = (rpq_t **)wspacemalloc(ctrl, 2*ncon*sizeof(rpq_t *));
00319   for (i=0; i<2*ncon; i++) {
00320     queues[i] = rpqCreate(nvtxs);
00321     qsizes[i] = 0;
00322   }
00323 
00324   for (i=0; i<nvtxs; i++) {
00325     qnum[i] = iargmax_nrm(ncon, vwgt+i*ncon, invtvwgt);
00326     qsizes[2*qnum[i]+where[i]]++;
00327   }
00328 
00329 
00330   /* for the empty queues, move into them vertices from other queues */
00331   for (from=0; from<2; from++) {
00332     for (j=0; j<ncon; j++) {
00333       if (qsizes[2*j+from] == 0) {
00334         for (i=0; i<nvtxs; i++) {
00335           if (where[i] != from)
00336             continue;
00337 
00338           k = iargmax2_nrm(ncon, vwgt+i*ncon, invtvwgt);
00339           if (k == j && 
00340               qsizes[2*qnum[i]+from] > qsizes[2*j+from] && 
00341               vwgt[i*ncon+qnum[i]]*invtvwgt[qnum[i]] < 1.3*vwgt[i*ncon+j]*invtvwgt[j]) {
00342             qsizes[2*qnum[i]+from]--;
00343             qsizes[2*j+from]++;
00344             qnum[i] = j;
00345           }
00346         }
00347       }
00348     }
00349   }
00350 
00351 
00352   minbal = ComputeLoadImbalanceDiffVec(graph, 2, ctrl->pijbm, ctrl->ubfactors, minbalv);
00353   ASSERT(minbal > 0.0);
00354 
00355   newcut = mincut = graph->mincut;
00356   mincutorder = -1;
00357 
00358   if (ctrl->dbglvl&METIS_DBG_REFINE) {
00359     printf("Parts: [");
00360     for (l=0; l<ncon; l++)
00361       printf("(%6"PRIDX" %6"PRIDX" %.3"PRREAL" %.3"PRREAL") ", 
00362           pwgts[l], pwgts[ncon+l], ntpwgts[l], ntpwgts[ncon+l]);
00363     printf("] Nv-Nb[%5"PRIDX", %5"PRIDX"]. ICut: %6"PRIDX", LB: %+.3"PRREAL" [B]\n", 
00364            graph->nvtxs, graph->nbnd, graph->mincut, minbal);
00365   }
00366 
00367   iset(nvtxs, -1, moved);
00368 
00369   ASSERT(ComputeCut(graph, where) == graph->mincut);
00370   ASSERT(CheckBnd(graph));
00371 
00372   /* Insert all nodes in the priority queues */
00373   nbnd = graph->nbnd;
00374   irandArrayPermute(nvtxs, perm, nvtxs/10, 1);
00375   for (ii=0; ii<nvtxs; ii++) {
00376     i = perm[ii];
00377     rpqInsert(queues[2*qnum[i]+where[i]], i, ed[i]-id[i]);
00378   }
00379 
00380   for (nswaps=0; nswaps<nvtxs; nswaps++) {
00381     if (minbal <= 0.0)
00382       break;
00383 
00384     SelectQueue(graph, ctrl->pijbm, ctrl->ubfactors, queues, &from, &cnum);
00385     to = (from+1)%2;
00386 
00387     if (from == -1 || (higain = rpqGetTop(queues[2*cnum+from])) == -1)
00388       break;
00389 
00390     newcut -= (ed[higain]-id[higain]);
00391 
00392     iaxpy(ncon,  1, vwgt+higain*ncon, 1, pwgts+to*ncon,   1);
00393     iaxpy(ncon, -1, vwgt+higain*ncon, 1, pwgts+from*ncon, 1);
00394     newbal = ComputeLoadImbalanceDiffVec(graph, 2, ctrl->pijbm, ctrl->ubfactors, newbalv);
00395 
00396     if (newbal < minbal || (newbal == minbal && 
00397         (newcut < mincut || 
00398          (newcut == mincut && BetterBalance2Way(ncon, minbalv, newbalv))))) {
00399       mincut      = newcut;
00400       minbal      = newbal;
00401       mincutorder = nswaps;
00402       rcopy(ncon, newbalv, minbalv);
00403     }
00404     else if (nswaps-mincutorder > limit) { /* We hit the limit, undo last move */
00405       newcut += (ed[higain]-id[higain]);
00406       iaxpy(ncon,  1, vwgt+higain*ncon, 1, pwgts+from*ncon, 1);
00407       iaxpy(ncon, -1, vwgt+higain*ncon, 1, pwgts+to*ncon,   1);
00408       break;
00409     }
00410 
00411     where[higain] = to;
00412     moved[higain] = nswaps;
00413     swaps[nswaps] = higain;
00414 
00415     if (ctrl->dbglvl&METIS_DBG_MOVEINFO) {
00416       printf("Moved %6"PRIDX" from %"PRIDX"(%"PRIDX"). Gain: %5"PRIDX", "
00417              "Cut: %5"PRIDX", NPwgts: ", higain, from, cnum, ed[higain]-id[higain], newcut);
00418       for (l=0; l<ncon; l++) 
00419         printf("(%6"PRIDX", %6"PRIDX") ", pwgts[l], pwgts[ncon+l]);
00420       printf(", %+.3"PRREAL" LB: %+.3"PRREAL"\n", minbal, newbal);
00421     }
00422 
00423 
00424     /**************************************************************
00425     * Update the id[i]/ed[i] values of the affected nodes
00426     ***************************************************************/
00427     SWAP(id[higain], ed[higain], tmp);
00428     if (ed[higain] == 0 && bndptr[higain] != -1 && xadj[higain] < xadj[higain+1]) 
00429       BNDDelete(nbnd, bndind,  bndptr, higain);
00430     if (ed[higain] > 0 && bndptr[higain] == -1)
00431       BNDInsert(nbnd, bndind,  bndptr, higain);
00432 
00433     for (j=xadj[higain]; j<xadj[higain+1]; j++) {
00434       k = adjncy[j];
00435 
00436       kwgt = (to == where[k] ? adjwgt[j] : -adjwgt[j]);
00437       INC_DEC(id[k], ed[k], kwgt);
00438 
00439       /* Update the queue position */
00440       if (moved[k] == -1)
00441         rpqUpdate(queues[2*qnum[k]+where[k]], k, ed[k]-id[k]);
00442 
00443       /* Update its boundary information */
00444       if (ed[k] == 0 && bndptr[k] != -1) 
00445         BNDDelete(nbnd, bndind, bndptr, k);
00446       else if (ed[k] > 0 && bndptr[k] == -1)  
00447         BNDInsert(nbnd, bndind, bndptr, k);
00448     }
00449   }
00450 
00451 
00452 
00453   /****************************************************************
00454   * Roll back computations
00455   *****************************************************************/
00456   for (nswaps--; nswaps>mincutorder; nswaps--) {
00457     higain = swaps[nswaps];
00458 
00459     to = where[higain] = (where[higain]+1)%2;
00460     SWAP(id[higain], ed[higain], tmp);
00461     if (ed[higain] == 0 && bndptr[higain] != -1 && xadj[higain] < xadj[higain+1])
00462       BNDDelete(nbnd, bndind,  bndptr, higain);
00463     else if (ed[higain] > 0 && bndptr[higain] == -1)
00464       BNDInsert(nbnd, bndind,  bndptr, higain);
00465 
00466     iaxpy(ncon,  1, vwgt+higain*ncon, 1, pwgts+to*ncon,         1);
00467     iaxpy(ncon, -1, vwgt+higain*ncon, 1, pwgts+((to+1)%2)*ncon, 1);
00468     for (j=xadj[higain]; j<xadj[higain+1]; j++) {
00469       k = adjncy[j];
00470 
00471       kwgt = (to == where[k] ? adjwgt[j] : -adjwgt[j]);
00472       INC_DEC(id[k], ed[k], kwgt);
00473 
00474       if (bndptr[k] != -1 && ed[k] == 0)
00475         BNDDelete(nbnd, bndind, bndptr, k);
00476       if (bndptr[k] == -1 && ed[k] > 0)
00477         BNDInsert(nbnd, bndind, bndptr, k);
00478     }
00479   }
00480 
00481   if (ctrl->dbglvl&METIS_DBG_REFINE) {
00482     printf("\tMincut: %6"PRIDX" at %5"PRIDX", NBND: %6"PRIDX", NPwgts: [", 
00483         mincut, mincutorder, nbnd);
00484     for (l=0; l<ncon; l++)
00485       printf("(%6"PRIDX", %6"PRIDX") ", pwgts[l], pwgts[ncon+l]);
00486     printf("], LB: %.3"PRREAL"\n", ComputeLoadImbalance(graph, 2, ctrl->pijbm));
00487   }
00488 
00489   graph->mincut = mincut;
00490   graph->nbnd   = nbnd;
00491 
00492 
00493   for (i=0; i<2*ncon; i++) 
00494     rpqDestroy(queues[i]);
00495 
00496   WCOREPOP;
00497 }
00498
libs/ck-libs/metis/libmetis/balance.c
