Charm++: Charm Source Code Documentation

00001 /*
00002  * Copyright 1997, Regents of the University of Minnesota
00003  *
00004  * mbalance.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 /*************************************************************************
00020 * This function is the entry point of the bisection balancing algorithms.
00021 **************************************************************************/
00022 void MocBalance2Way(CtrlType *ctrl, GraphType *graph, floattype *tpwgts, floattype lbfactor)
00023 {
00024 
00025   if (Compute2WayHLoadImbalance(graph->ncon, graph->npwgts, tpwgts) < lbfactor)
00026     return;
00027 
00028   MocGeneral2WayBalance(ctrl, graph, tpwgts, lbfactor);
00029 
00030 }
00031 
00032 
00033 /*************************************************************************
00034 * This function performs an edge-based FM refinement
00035 **************************************************************************/
00036 void MocGeneral2WayBalance(CtrlType *ctrl, GraphType *graph, floattype *tpwgts, floattype lbfactor)
00037 {
00038   int i, ii, j, k, l, kwgt, nvtxs, ncon, nbnd, nswaps, from, to, pass, me, limit, tmp, cnum;
00039   idxtype *xadj, *adjncy, *adjwgt, *where, *id, *ed, *bndptr, *bndind;
00040   idxtype *moved, *swaps, *perm, *qnum;
00041   floattype *nvwgt, *npwgts, mindiff[MAXNCON], origbal, minbal, newbal;
00042   PQueueType parts[MAXNCON][2];
00043   int higain, oldgain, mincut, newcut, mincutorder;
00044   int qsizes[MAXNCON][2];
00045 
00046   nvtxs = graph->nvtxs;
00047   ncon = graph->ncon;
00048   xadj = graph->xadj;
00049   nvwgt = graph->nvwgt;
00050   adjncy = graph->adjncy;
00051   adjwgt = graph->adjwgt;
00052   where = graph->where;
00053   id = graph->id;
00054   ed = graph->ed;
00055   npwgts = graph->npwgts;
00056   bndptr = graph->bndptr;
00057   bndind = graph->bndind;
00058 
00059   moved = idxwspacemalloc(ctrl, nvtxs);
00060   swaps = idxwspacemalloc(ctrl, nvtxs);
00061   perm = idxwspacemalloc(ctrl, nvtxs);
00062   qnum = idxwspacemalloc(ctrl, nvtxs);
00063 
00064   limit = amin(amax(0.01*nvtxs, 15), 100);
00065 
00066   /* Initialize the queues */
00067   for (i=0; i<ncon; i++) {
00068     PQueueInit(ctrl, &parts[i][0], nvtxs, PLUS_GAINSPAN+1);
00069     PQueueInit(ctrl, &parts[i][1], nvtxs, PLUS_GAINSPAN+1);
00070     qsizes[i][0] = qsizes[i][1] = 0;
00071   }
00072 
00073   for (i=0; i<nvtxs; i++) {
00074     qnum[i] = samax(ncon, nvwgt+i*ncon);
00075     qsizes[qnum[i]][where[i]]++;
00076   }
00077 
00078 /*
00079   printf("Weight Distribution:    \t");
00080   for (i=0; i<ncon; i++) 
00081     printf(" [%d %d]", qsizes[i][0], qsizes[i][1]); 
00082   printf("\n");
00083 */
00084 
00085   for (from=0; from<2; from++) {
00086     for (j=0; j<ncon; j++) {
00087       if (qsizes[j][from] == 0) {
00088         for (i=0; i<nvtxs; i++) {
00089           if (where[i] != from)
00090             continue;
00091 
00092           k = samax2(ncon, nvwgt+i*ncon);
00093           if (k == j && qsizes[qnum[i]][from] > qsizes[j][from] && nvwgt[i*ncon+qnum[i]] < 1.3*nvwgt[i*ncon+j]) {
00094             qsizes[qnum[i]][from]--;
00095             qsizes[j][from]++;
00096             qnum[i] = j;
00097           }
00098         }
00099       }
00100     }
00101   }
00102 
00103 /*
00104   printf("Weight Distribution (after):\t ");
00105   for (i=0; i<ncon; i++) 
00106     printf(" [%d %d]", qsizes[i][0], qsizes[i][1]); 
00107   printf("\n");
00108 */
00109 
00110 
00111 
00112   for (i=0; i<ncon; i++) 
00113     mindiff[i] = fabs(tpwgts[0]-npwgts[i]);
00114   minbal = origbal = Compute2WayHLoadImbalance(ncon, npwgts, tpwgts);
00115   newcut = mincut = graph->mincut;
00116   mincutorder = -1;
00117 
00118   if (ctrl->dbglvl&DBG_REFINE) {
00119     printf("Parts: [");
00120     for (l=0; l<ncon; l++)
00121       printf("(%.3f, %.3f) ", npwgts[l], npwgts[ncon+l]);
00122     printf("] T[%.3f %.3f], Nv-Nb[%5d, %5d]. ICut: %6d, LB: %.3f [B]\n", tpwgts[0], tpwgts[1], graph->nvtxs, graph->nbnd, graph->mincut, origbal);
00123   }
00124 
00125   idxset(nvtxs, -1, moved);
00126 
00127   ASSERT(ComputeCut(graph, where) == graph->mincut);
00128   ASSERT(CheckBnd(graph));
00129 
00130   /* Insert all nodes in the priority queues */
00131   nbnd = graph->nbnd;
00132   RandomPermute(nvtxs, perm, 1);
00133   for (ii=0; ii<nvtxs; ii++) {
00134     i = perm[ii];
00135     PQueueInsert(&parts[qnum[i]][where[i]], i, ed[i]-id[i]);
00136   }
00137 
00138   for (nswaps=0; nswaps<nvtxs; nswaps++) {
00139     if (minbal < lbfactor)
00140       break;
00141 
00142     SelectQueue(ncon, npwgts, tpwgts, &from, &cnum, parts);
00143     to = (from+1)%2;
00144 
00145     if (from == -1 || (higain = PQueueGetMax(&parts[cnum][from])) == -1)
00146       break;
00147 
00148     saxpy(ncon, 1.0, nvwgt+higain*ncon, 1, npwgts+to*ncon, 1);
00149     saxpy(ncon, -1.0, nvwgt+higain*ncon, 1, npwgts+from*ncon, 1);
00150     newcut -= (ed[higain]-id[higain]);
00151     newbal = Compute2WayHLoadImbalance(ncon, npwgts, tpwgts);
00152 
00153     if (newbal < minbal || (newbal == minbal && 
00154         (newcut < mincut || (newcut == mincut && BetterBalance(ncon, npwgts, tpwgts, mindiff))))) {
00155       mincut = newcut;
00156       minbal = newbal;
00157       mincutorder = nswaps;
00158       for (i=0; i<ncon; i++)
00159         mindiff[i] = fabs(tpwgts[0]-npwgts[i]);
00160     }
00161     else if (nswaps-mincutorder > limit) { /* We hit the limit, undo last move */
00162       newcut += (ed[higain]-id[higain]);
00163       saxpy(ncon, 1.0, nvwgt+higain*ncon, 1, npwgts+from*ncon, 1);
00164       saxpy(ncon, -1.0, nvwgt+higain*ncon, 1, npwgts+to*ncon, 1);
00165       break;
00166     }
00167 
00168     where[higain] = to;
00169     moved[higain] = nswaps;
00170     swaps[nswaps] = higain;
00171 
00172     if (ctrl->dbglvl&DBG_MOVEINFO) {
00173       printf("Moved %6d from %d(%d). Gain: %5d, Cut: %5d, NPwgts: ", higain, from, cnum, ed[higain]-id[higain], newcut);
00174       for (l=0; l<ncon; l++) 
00175         printf("(%.3f, %.3f) ", npwgts[l], npwgts[ncon+l]);
00176       printf(", %.3f LB: %.3f\n", minbal, newbal);
00177     }
00178 
00179 
00180     /**************************************************************
00181     * Update the id[i]/ed[i] values of the affected nodes
00182     ***************************************************************/
00183     SWAP(id[higain], ed[higain], tmp);
00184     if (ed[higain] == 0 && bndptr[higain] != -1 && xadj[higain] < xadj[higain+1]) 
00185       BNDDelete(nbnd, bndind,  bndptr, higain);
00186     if (ed[higain] > 0 && bndptr[higain] == -1)
00187       BNDInsert(nbnd, bndind,  bndptr, higain);
00188 
00189     for (j=xadj[higain]; j<xadj[higain+1]; j++) {
00190       k = adjncy[j];
00191       oldgain = ed[k]-id[k];
00192 
00193       kwgt = (to == where[k] ? adjwgt[j] : -adjwgt[j]);
00194       INC_DEC(id[k], ed[k], kwgt);
00195 
00196       /* Update the queue position */
00197       if (moved[k] == -1)
00198         PQueueUpdate(&parts[qnum[k]][where[k]], k, oldgain, ed[k]-id[k]);
00199 
00200       /* Update its boundary information */
00201       if (ed[k] == 0 && bndptr[k] != -1) 
00202         BNDDelete(nbnd, bndind, bndptr, k);
00203       else if (ed[k] > 0 && bndptr[k] == -1)  
00204         BNDInsert(nbnd, bndind, bndptr, k);
00205     }
00206   }
00207 
00208 
00209 
00210   /****************************************************************
00211   * Roll back computations
00212   *****************************************************************/
00213   for (nswaps--; nswaps>mincutorder; nswaps--) {
00214     higain = swaps[nswaps];
00215 
00216     to = where[higain] = (where[higain]+1)%2;
00217     SWAP(id[higain], ed[higain], tmp);
00218     if (ed[higain] == 0 && bndptr[higain] != -1 && xadj[higain] < xadj[higain+1])
00219       BNDDelete(nbnd, bndind,  bndptr, higain);
00220     else if (ed[higain] > 0 && bndptr[higain] == -1)
00221       BNDInsert(nbnd, bndind,  bndptr, higain);
00222 
00223     saxpy(ncon, 1.0, nvwgt+higain*ncon, 1, npwgts+to*ncon, 1);
00224     saxpy(ncon, -1.0, nvwgt+higain*ncon, 1, npwgts+((to+1)%2)*ncon, 1);
00225     for (j=xadj[higain]; j<xadj[higain+1]; j++) {
00226       k = adjncy[j];
00227 
00228       kwgt = (to == where[k] ? adjwgt[j] : -adjwgt[j]);
00229       INC_DEC(id[k], ed[k], kwgt);
00230 
00231       if (bndptr[k] != -1 && ed[k] == 0)
00232         BNDDelete(nbnd, bndind, bndptr, k);
00233       if (bndptr[k] == -1 && ed[k] > 0)
00234         BNDInsert(nbnd, bndind, bndptr, k);
00235     }
00236   }
00237 
00238   if (ctrl->dbglvl&DBG_REFINE) {
00239     printf("\tMincut: %6d at %5d, NBND: %6d, NPwgts: [", mincut, mincutorder, nbnd);
00240     for (l=0; l<ncon; l++)
00241       printf("(%.3f, %.3f) ", npwgts[l], npwgts[ncon+l]);
00242     printf("], LB: %.3f\n", Compute2WayHLoadImbalance(ncon, npwgts, tpwgts));
00243   }
00244 
00245   graph->mincut = mincut;
00246   graph->nbnd = nbnd;
00247 
00248 
00249   for (i=0; i<ncon; i++) {
00250     PQueueFree(ctrl, &parts[i][0]);
00251     PQueueFree(ctrl, &parts[i][1]);
00252   }
00253 
00254   idxwspacefree(ctrl, nvtxs);
00255   idxwspacefree(ctrl, nvtxs);
00256   idxwspacefree(ctrl, nvtxs);
00257   idxwspacefree(ctrl, nvtxs);
00258 
00259 }
00260
libs/ck-libs/parmetis/METISLib/mbalance.c
