Charm++: Charm Source Code Documentation

00001 /*
00002  * Copyright 1997, Regents of the University of Minnesota
00003  *
00004  * balance.c
00005  *
00006  * This file contains code that is used to forcefully balance either
00007  * bisections or k-sections
00008  *
00009  * Started 7/29/97
00010  * George
00011  *
00012  * $Id$
00013  *
00014  */
00015 
00016 #include <metis.h>
00017 
00018 /*************************************************************************
00019 * This function is the entry point of the bisection balancing algorithms.
00020 **************************************************************************/
00021 void Balance2Way(CtrlType *ctrl, GraphType *graph, int *tpwgts, floattype ubfactor)
00022 {
00023   int i, j, nvtxs, from, imax, gain, mindiff;
00024   idxtype *id, *ed;
00025 
00026   /* Return right away if the balance is OK */
00027   mindiff = abs(tpwgts[0]-graph->pwgts[0]);
00028   if (mindiff < 3*(graph->pwgts[0]+graph->pwgts[1])/graph->nvtxs)
00029     return;
00030   if (graph->pwgts[0] > tpwgts[0] && graph->pwgts[0] < (int)(ubfactor*tpwgts[0]))
00031     return;
00032   if (graph->pwgts[1] > tpwgts[1] && graph->pwgts[1] < (int)(ubfactor*tpwgts[1]))
00033     return;
00034 
00035   if (graph->nbnd > 0)
00036     Bnd2WayBalance(ctrl, graph, tpwgts);
00037   else
00038     General2WayBalance(ctrl, graph, tpwgts);
00039 
00040 }
00041 
00042 
00043 
00044 /*************************************************************************
00045 * This function balances two partitions by moving boundary nodes
00046 * from the domain that is overweight to the one that is underweight.
00047 **************************************************************************/
00048 void Bnd2WayBalance(CtrlType *ctrl, GraphType *graph, int *tpwgts)
00049 {
00050   int i, ii, j, k, kwgt, nvtxs, nbnd, nswaps, from, to, pass, me, tmp;
00051   idxtype *xadj, *vwgt, *adjncy, *adjwgt, *where, *id, *ed, *bndptr, *bndind, *pwgts;
00052   idxtype *moved, *perm;
00053   PQueueType parts;
00054   int higain, oldgain, mincut, mindiff;
00055 
00056   nvtxs = graph->nvtxs;
00057   xadj = graph->xadj;
00058   vwgt = graph->vwgt;
00059   adjncy = graph->adjncy;
00060   adjwgt = graph->adjwgt;
00061   where = graph->where;
00062   id = graph->id;
00063   ed = graph->ed;
00064   pwgts = graph->pwgts;
00065   bndptr = graph->bndptr;
00066   bndind = graph->bndind;
00067 
00068   moved = idxwspacemalloc(ctrl, nvtxs);
00069   perm = idxwspacemalloc(ctrl, nvtxs);
00070 
00071   /* Determine from which domain you will be moving data */
00072   mindiff = abs(tpwgts[0]-pwgts[0]);
00073   from = (pwgts[0] < tpwgts[0] ? 1 : 0);
00074   to = (from+1)%2;
00075 
00076   IFSET(ctrl->dbglvl, DBG_REFINE, 
00077      printf("Partitions: [%6d %6d] T[%6d %6d], Nv-Nb[%6d %6d]. ICut: %6d [B]\n",
00078              pwgts[0], pwgts[1], tpwgts[0], tpwgts[1], graph->nvtxs, graph->nbnd, graph->mincut));
00079 
00080   tmp = graph->adjwgtsum[idxamax(nvtxs, graph->adjwgtsum)];
00081   PQueueInit(ctrl, &parts, nvtxs, tmp);
00082 
00083   idxset(nvtxs, -1, moved);
00084 
00085   ASSERT(ComputeCut(graph, where) == graph->mincut);
00086   ASSERT(CheckBnd(graph));
00087 
00088   /* Insert the boundary nodes of the proper partition whose size is OK in the priority queue */
00089   nbnd = graph->nbnd;
00090   RandomPermute(nbnd, perm, 1);
00091   for (ii=0; ii<nbnd; ii++) {
00092     i = perm[ii];
00093     ASSERT(ed[bndind[i]] > 0 || id[bndind[i]] == 0);
00094     ASSERT(bndptr[bndind[i]] != -1);
00095     if (where[bndind[i]] == from && vwgt[bndind[i]] <= mindiff)
00096       PQueueInsert(&parts, bndind[i], ed[bndind[i]]-id[bndind[i]]);
00097   }
00098 
00099   mincut = graph->mincut;
00100   for (nswaps=0; nswaps<nvtxs; nswaps++) {
00101     if ((higain = PQueueGetMax(&parts)) == -1)
00102       break;
00103     ASSERT(bndptr[higain] != -1);
00104 
00105     if (pwgts[to]+vwgt[higain] > tpwgts[to])
00106       break;
00107 
00108     mincut -= (ed[higain]-id[higain]);
00109     INC_DEC(pwgts[to], pwgts[from], vwgt[higain]);
00110 
00111     where[higain] = to;
00112     moved[higain] = nswaps;
00113 
00114     IFSET(ctrl->dbglvl, DBG_MOVEINFO, 
00115       printf("Moved %6d from %d. [%3d %3d] %5d [%4d %4d]\n", higain, from, ed[higain]-id[higain], vwgt[higain], mincut, pwgts[0], pwgts[1]));
00116 
00117     /**************************************************************
00118     * Update the id[i]/ed[i] values of the affected nodes
00119     ***************************************************************/
00120     SWAP(id[higain], ed[higain], tmp);
00121     if (ed[higain] == 0 && xadj[higain] < xadj[higain+1]) 
00122       BNDDelete(nbnd, bndind,  bndptr, higain);
00123 
00124     for (j=xadj[higain]; j<xadj[higain+1]; j++) {
00125       k = adjncy[j];
00126       oldgain = ed[k]-id[k];
00127 
00128       kwgt = (to == where[k] ? adjwgt[j] : -adjwgt[j]);
00129       INC_DEC(id[k], ed[k], kwgt);
00130 
00131       /* Update its boundary information and queue position */
00132       if (bndptr[k] != -1) { /* If k was a boundary vertex */
00133         if (ed[k] == 0) { /* Not a boundary vertex any more */
00134           BNDDelete(nbnd, bndind, bndptr, k);
00135           if (moved[k] == -1 && where[k] == from && vwgt[k] <= mindiff)  /* Remove it if in the queues */
00136             PQueueDelete(&parts, k, oldgain);
00137         }
00138         else { /* If it has not been moved, update its position in the queue */
00139           if (moved[k] == -1 && where[k] == from && vwgt[k] <= mindiff)
00140             PQueueUpdate(&parts, k, oldgain, ed[k]-id[k]);
00141         }
00142       }
00143       else {
00144         if (ed[k] > 0) {  /* It will now become a boundary vertex */
00145           BNDInsert(nbnd, bndind, bndptr, k);
00146           if (moved[k] == -1 && where[k] == from && vwgt[k] <= mindiff) 
00147             PQueueInsert(&parts, k, ed[k]-id[k]);
00148         }
00149       }
00150     }
00151   }
00152 
00153   IFSET(ctrl->dbglvl, DBG_REFINE, 
00154     printf("\tMinimum cut: %6d, PWGTS: [%6d %6d], NBND: %6d\n", mincut, pwgts[0], pwgts[1], nbnd));
00155 
00156   graph->mincut = mincut;
00157   graph->nbnd = nbnd;
00158 
00159   PQueueFree(ctrl, &parts);
00160 
00161   idxwspacefree(ctrl, nvtxs);
00162   idxwspacefree(ctrl, nvtxs);
00163 }
00164 
00165 
00166 /*************************************************************************
00167 * This function balances two partitions by moving the highest gain 
00168 * (including negative gain) vertices to the other domain.
00169 * It is used only when tha unbalance is due to non contigous
00170 * subdomains. That is, the are no boundary vertices.
00171 * It moves vertices from the domain that is overweight to the one that 
00172 * is underweight.
00173 **************************************************************************/
00174 void General2WayBalance(CtrlType *ctrl, GraphType *graph, int *tpwgts)
00175 {
00176   int i, ii, j, k, kwgt, nvtxs, nbnd, nswaps, from, to, pass, me, tmp;
00177   idxtype *xadj, *vwgt, *adjncy, *adjwgt, *where, *id, *ed, *bndptr, *bndind, *pwgts;
00178   idxtype *moved, *perm;
00179   PQueueType parts;
00180   int higain, oldgain, mincut, mindiff;
00181 
00182   nvtxs = graph->nvtxs;
00183   xadj = graph->xadj;
00184   vwgt = graph->vwgt;
00185   adjncy = graph->adjncy;
00186   adjwgt = graph->adjwgt;
00187   where = graph->where;
00188   id = graph->id;
00189   ed = graph->ed;
00190   pwgts = graph->pwgts;
00191   bndptr = graph->bndptr;
00192   bndind = graph->bndind;
00193 
00194   moved = idxwspacemalloc(ctrl, nvtxs);
00195   perm = idxwspacemalloc(ctrl, nvtxs);
00196 
00197   /* Determine from which domain you will be moving data */
00198   mindiff = abs(tpwgts[0]-pwgts[0]);
00199   from = (pwgts[0] < tpwgts[0] ? 1 : 0);
00200   to = (from+1)%2;
00201 
00202   IFSET(ctrl->dbglvl, DBG_REFINE, 
00203      printf("Partitions: [%6d %6d] T[%6d %6d], Nv-Nb[%6d %6d]. ICut: %6d [B]\n",
00204              pwgts[0], pwgts[1], tpwgts[0], tpwgts[1], graph->nvtxs, graph->nbnd, graph->mincut));
00205 
00206   tmp = graph->adjwgtsum[idxamax(nvtxs, graph->adjwgtsum)];
00207   PQueueInit(ctrl, &parts, nvtxs, tmp);
00208 
00209   idxset(nvtxs, -1, moved);
00210 
00211   ASSERT(ComputeCut(graph, where) == graph->mincut);
00212   ASSERT(CheckBnd(graph));
00213 
00214   /* Insert the nodes of the proper partition whose size is OK in the priority queue */
00215   RandomPermute(nvtxs, perm, 1);
00216   for (ii=0; ii<nvtxs; ii++) {
00217     i = perm[ii];
00218     if (where[i] == from && vwgt[i] <= mindiff)
00219       PQueueInsert(&parts, i, ed[i]-id[i]);
00220   }
00221 
00222   mincut = graph->mincut;
00223   nbnd = graph->nbnd;
00224   for (nswaps=0; nswaps<nvtxs; nswaps++) {
00225     if ((higain = PQueueGetMax(&parts)) == -1)
00226       break;
00227 
00228     if (pwgts[to]+vwgt[higain] > tpwgts[to])
00229       break;
00230 
00231     mincut -= (ed[higain]-id[higain]);
00232     INC_DEC(pwgts[to], pwgts[from], vwgt[higain]);
00233 
00234     where[higain] = to;
00235     moved[higain] = nswaps;
00236 
00237     IFSET(ctrl->dbglvl, DBG_MOVEINFO, 
00238       printf("Moved %6d from %d. [%3d %3d] %5d [%4d %4d]\n", higain, from, ed[higain]-id[higain], vwgt[higain], mincut, pwgts[0], pwgts[1]));
00239 
00240     /**************************************************************
00241     * Update the id[i]/ed[i] values of the affected nodes
00242     ***************************************************************/
00243     SWAP(id[higain], ed[higain], tmp);
00244     if (ed[higain] == 0 && bndptr[higain] != -1 && xadj[higain] < xadj[higain+1]) 
00245       BNDDelete(nbnd, bndind,  bndptr, higain);
00246     if (ed[higain] > 0 && bndptr[higain] == -1)
00247       BNDInsert(nbnd, bndind,  bndptr, higain);
00248 
00249     for (j=xadj[higain]; j<xadj[higain+1]; j++) {
00250       k = adjncy[j];
00251       oldgain = ed[k]-id[k];
00252 
00253       kwgt = (to == where[k] ? adjwgt[j] : -adjwgt[j]);
00254       INC_DEC(id[k], ed[k], kwgt);
00255 
00256       /* Update the queue position */
00257       if (moved[k] == -1 && where[k] == from && vwgt[k] <= mindiff)
00258         PQueueUpdate(&parts, k, oldgain, ed[k]-id[k]);
00259 
00260       /* Update its boundary information */
00261       if (ed[k] == 0 && bndptr[k] != -1) 
00262         BNDDelete(nbnd, bndind, bndptr, k);
00263       else if (ed[k] > 0 && bndptr[k] == -1)  
00264         BNDInsert(nbnd, bndind, bndptr, k);
00265     }
00266   }
00267 
00268   IFSET(ctrl->dbglvl, DBG_REFINE, 
00269     printf("\tMinimum cut: %6d, PWGTS: [%6d %6d], NBND: %6d\n", mincut, pwgts[0], pwgts[1], nbnd));
00270 
00271   graph->mincut = mincut;
00272   graph->nbnd = nbnd;
00273 
00274   PQueueFree(ctrl, &parts);
00275 
00276   idxwspacefree(ctrl, nvtxs);
00277   idxwspacefree(ctrl, nvtxs);
00278 }
libs/ck-libs/parmetis/METISLib/balance.c
