Charm++: Charm Source Code Documentation

00001 /*
00002  * Copyright 1997, Regents of the University of Minnesota
00003  *
00004  * kwayvolrefine.c
00005  *
00006  * This file contains the driving routines for multilevel k-way refinement
00007  *
00008  * Started 7/28/97
00009  * George
00010  *
00011  * $Id$
00012  */
00013 
00014 #include <metis.h>
00015 
00016 
00017 /*************************************************************************
00018 * This function is the entry point of refinement
00019 **************************************************************************/
00020 void RefineVolKWay(CtrlType *ctrl, GraphType *orggraph, GraphType *graph, int nparts, 
00021                    floattype *tpwgts, floattype ubfactor)
00022 {
00023   int i, nlevels;
00024   GraphType *ptr;
00025 
00026   IFSET(ctrl->dbglvl, DBG_TIME, starttimer(ctrl->UncoarsenTmr));
00027 
00028   /* Take care any non-contiguity */
00029   IFSET(ctrl->dbglvl, DBG_TIME, starttimer(ctrl->AuxTmr1));
00030   if (ctrl->RType == RTYPE_KWAYRANDOM_MCONN) {
00031     ComputeVolKWayPartitionParams(ctrl, graph, nparts);
00032     EliminateVolComponents(ctrl, graph, nparts, tpwgts, 1.25);
00033     EliminateVolSubDomainEdges(ctrl, graph, nparts, tpwgts);
00034     EliminateVolComponents(ctrl, graph, nparts, tpwgts, 1.25);
00035   }
00036   IFSET(ctrl->dbglvl, DBG_TIME, stoptimer(ctrl->AuxTmr1));
00037 
00038 
00039   /* Determine how many levels are there */
00040   for (ptr=graph, nlevels=0; ptr!=orggraph; ptr=ptr->finer, nlevels++); 
00041 
00042   /* Compute the parameters of the coarsest graph */
00043   ComputeVolKWayPartitionParams(ctrl, graph, nparts);
00044 
00045   for (i=0; ;i++) {
00046     /*PrintSubDomainGraph(graph, nparts, graph->where);*/
00047     MALLOC_CHECK(NULL);
00048     IFSET(ctrl->dbglvl, DBG_TIME, starttimer(ctrl->RefTmr));
00049 
00050     if (2*i >= nlevels && !IsBalanced(graph->pwgts, nparts, tpwgts, 1.04*ubfactor)) {
00051       ComputeVolKWayBalanceBoundary(ctrl, graph, nparts);
00052       switch (ctrl->RType) {
00053         case RTYPE_KWAYRANDOM:
00054           Greedy_KWayVolBalance(ctrl, graph, nparts, tpwgts, ubfactor, 1); 
00055           break;
00056         case RTYPE_KWAYRANDOM_MCONN:
00057           Greedy_KWayVolBalanceMConn(ctrl, graph, nparts, tpwgts, ubfactor, 1); 
00058           break;
00059       }
00060       ComputeVolKWayBoundary(ctrl, graph, nparts);
00061     }
00062 
00063     switch (ctrl->RType) {
00064       case RTYPE_KWAYRANDOM:
00065         Random_KWayVolRefine(ctrl, graph, nparts, tpwgts, ubfactor, 10, 1); 
00066         break;
00067       case RTYPE_KWAYRANDOM_MCONN:
00068         Random_KWayVolRefineMConn(ctrl, graph, nparts, tpwgts, ubfactor, 10, 1); 
00069         break;
00070     }
00071     IFSET(ctrl->dbglvl, DBG_TIME, stoptimer(ctrl->RefTmr));
00072 
00073     if (graph == orggraph)
00074       break;
00075 
00076     GKfree(&graph->gdata, LTERM);  /* Deallocate the graph related arrays */
00077 
00078     graph = graph->finer;
00079 
00080     IFSET(ctrl->dbglvl, DBG_TIME, starttimer(ctrl->ProjectTmr));
00081     ProjectVolKWayPartition(ctrl, graph, nparts);
00082     IFSET(ctrl->dbglvl, DBG_TIME, stoptimer(ctrl->ProjectTmr));
00083   }
00084 
00085   if (!IsBalanced(graph->pwgts, nparts, tpwgts, ubfactor)) {
00086     ComputeVolKWayBalanceBoundary(ctrl, graph, nparts);
00087     switch (ctrl->RType) {
00088       case RTYPE_KWAYRANDOM:
00089         Greedy_KWayVolBalance(ctrl, graph, nparts, tpwgts, ubfactor, 8); 
00090         Random_KWayVolRefine(ctrl, graph, nparts, tpwgts, ubfactor, 10, 0); 
00091         break;
00092       case RTYPE_KWAYRANDOM_MCONN:
00093         Greedy_KWayVolBalanceMConn(ctrl, graph, nparts, tpwgts, ubfactor, 8); 
00094         Random_KWayVolRefineMConn(ctrl, graph, nparts, tpwgts, ubfactor, 10, 0); 
00095         break;
00096     }
00097   }
00098 
00099   EliminateVolComponents(ctrl, graph, nparts, tpwgts, ubfactor); 
00100 
00101   IFSET(ctrl->dbglvl, DBG_TIME, stoptimer(ctrl->UncoarsenTmr));
00102 }
00103 
00104 
00105 
00106 /*************************************************************************
00107 * This function allocates memory for k-way edge refinement
00108 **************************************************************************/
00109 void AllocateVolKWayPartitionMemory(CtrlType *ctrl, GraphType *graph, int nparts)
00110 {
00111   int nvtxs, pad64;
00112 
00113   nvtxs = graph->nvtxs;
00114 
00115   pad64 = (3*nvtxs+nparts)%2;
00116 
00117   graph->rdata = idxmalloc(3*nvtxs+nparts+(sizeof(VRInfoType)/sizeof(idxtype))*nvtxs+pad64, "AllocateVolKWayPartitionMemory: rdata");
00118   graph->pwgts          = graph->rdata;
00119   graph->where          = graph->rdata + nparts;
00120   graph->bndptr         = graph->rdata + nvtxs + nparts;
00121   graph->bndind         = graph->rdata + 2*nvtxs + nparts;
00122   graph->vrinfo          = (VRInfoType *)(graph->rdata + 3*nvtxs+nparts + pad64);
00123 
00124 }
00125 
00126 
00127 
00128 /*************************************************************************
00129 * This function computes the initial id/ed 
00130 **************************************************************************/
00131 void ComputeVolKWayPartitionParams(CtrlType *ctrl, GraphType *graph, int nparts)
00132 {
00133   int i, ii, j, k, kk, l, nvtxs, nbnd, mincut, minvol, me, other, pid; 
00134   idxtype *xadj, *vwgt, *adjncy, *adjwgt, *pwgts, *where;
00135   VRInfoType *rinfo, *myrinfo, *orinfo;
00136   VEDegreeType *myedegrees, *oedegrees;
00137 
00138   nvtxs = graph->nvtxs;
00139   xadj = graph->xadj;
00140   vwgt = graph->vwgt;
00141   adjncy = graph->adjncy;
00142   adjwgt = graph->adjwgt;
00143 
00144   where = graph->where;
00145   pwgts = idxset(nparts, 0, graph->pwgts);
00146   rinfo = graph->vrinfo;
00147 
00148 starttimer(ctrl->AuxTmr1);
00149 
00150   /*------------------------------------------------------------
00151   / Compute now the id/ed degrees
00152   /------------------------------------------------------------*/
00153   ctrl->wspace.cdegree = 0;
00154   mincut = 0;
00155   for (i=0; i<nvtxs; i++) {
00156     me = where[i];
00157     pwgts[me] += vwgt[i];
00158 
00159     myrinfo = rinfo+i;
00160     myrinfo->id = myrinfo->ed = myrinfo->nid = myrinfo->ndegrees = 0;
00161     myrinfo->edegrees = NULL;
00162 
00163     for (j=xadj[i]; j<xadj[i+1]; j++) {
00164       if (me == where[adjncy[j]]) {
00165         myrinfo->id += adjwgt[j];
00166         myrinfo->nid++;
00167       }
00168     }
00169     myrinfo->ed = graph->adjwgtsum[i] - myrinfo->id;
00170 
00171     mincut += myrinfo->ed;
00172 
00173     /* Time to compute the particular external degrees */
00174     if (myrinfo->ed > 0) { 
00175       myedegrees = myrinfo->edegrees = ctrl->wspace.vedegrees+ctrl->wspace.cdegree;
00176       ctrl->wspace.cdegree += xadj[i+1]-xadj[i];
00177 
00178       for (j=xadj[i]; j<xadj[i+1]; j++) {
00179         other = where[adjncy[j]];
00180         if (me != other) {
00181           for (k=0; k<myrinfo->ndegrees; k++) {
00182             if (myedegrees[k].pid == other) {
00183               myedegrees[k].ed += adjwgt[j];
00184               myedegrees[k].ned++;
00185               break;
00186             }
00187           }
00188           if (k == myrinfo->ndegrees) {
00189             myedegrees[myrinfo->ndegrees].gv = 0;
00190             myedegrees[myrinfo->ndegrees].pid = other;
00191             myedegrees[myrinfo->ndegrees].ed = adjwgt[j];
00192             myedegrees[myrinfo->ndegrees++].ned = 1;
00193           }
00194         }
00195       }
00196 
00197       ASSERT(myrinfo->ndegrees <= xadj[i+1]-xadj[i]);
00198     }
00199   }
00200   graph->mincut = mincut/2;
00201 
00202 stoptimer(ctrl->AuxTmr1);
00203 
00204   ComputeKWayVolGains(ctrl, graph, nparts);
00205 
00206 }
00207 
00208 
00209 
00210 /*************************************************************************
00211 * This function computes the initial id/ed 
00212 **************************************************************************/
00213 void ComputeKWayVolGains(CtrlType *ctrl, GraphType *graph, int nparts)
00214 {
00215   int i, ii, j, k, kk, l, nvtxs, me, other, pid, myndegrees; 
00216   idxtype *xadj, *vsize, *adjncy, *adjwgt, *where, *bndind, *bndptr, *ophtable;
00217   VRInfoType *rinfo, *myrinfo, *orinfo;
00218   VEDegreeType *myedegrees, *oedegrees;
00219 
00220   nvtxs = graph->nvtxs;
00221   xadj = graph->xadj;
00222   vsize = graph->vsize;
00223   adjncy = graph->adjncy;
00224   adjwgt = graph->adjwgt;
00225 
00226   where = graph->where;
00227   bndind = graph->bndind;
00228   bndptr = idxset(nvtxs, -1, graph->bndptr);
00229   rinfo = graph->vrinfo;
00230 
00231 starttimer(ctrl->AuxTmr2);
00232 
00233   ophtable = idxset(nparts, -1, idxwspacemalloc(ctrl, nparts));
00234 
00235   /*------------------------------------------------------------
00236   / Compute now the iv/ev degrees
00237   /------------------------------------------------------------*/
00238   graph->minvol = graph->nbnd = 0;
00239   for (i=0; i<nvtxs; i++) {
00240     myrinfo = rinfo+i;
00241     myrinfo->gv = -MAXIDX;
00242 
00243     if (myrinfo->ndegrees > 0) {
00244       me = where[i];
00245       myedegrees = myrinfo->edegrees;
00246       myndegrees = myrinfo->ndegrees;
00247 
00248       graph->minvol += myndegrees*vsize[i];
00249 
00250       for (j=xadj[i]; j<xadj[i+1]; j++) {
00251         ii = adjncy[j];
00252         other = where[ii];
00253         orinfo = rinfo+ii;
00254         oedegrees = orinfo->edegrees;
00255 
00256         for (k=0; k<orinfo->ndegrees; k++) 
00257           ophtable[oedegrees[k].pid] = k;
00258         ophtable[other] = 1;  /* this is to simplify coding */
00259 
00260         if (me == other) {
00261           /* Find which domains 'i' is connected and 'ii' is not and update their gain */
00262           for (k=0; k<myndegrees; k++) {
00263             if (ophtable[myedegrees[k].pid] == -1)
00264               myedegrees[k].gv -= vsize[ii];
00265           }
00266         }
00267         else {
00268           ASSERT(ophtable[me] != -1);
00269 
00270           if (oedegrees[ophtable[me]].ned == 1) { /* I'm the only connection of 'ii' in 'me' */
00271             /* Increase the gains for all the common domains between 'i' and 'ii' */
00272             for (k=0; k<myndegrees; k++) {
00273               if (ophtable[myedegrees[k].pid] != -1) 
00274                 myedegrees[k].gv += vsize[ii];
00275             }
00276           }
00277           else {
00278             /* Find which domains 'i' is connected and 'ii' is not and update their gain */
00279             for (k=0; k<myndegrees; k++) {
00280               if (ophtable[myedegrees[k].pid] == -1) 
00281                 myedegrees[k].gv -= vsize[ii];
00282             }
00283           }
00284         }
00285 
00286         for (kk=0; kk<orinfo->ndegrees; kk++) 
00287           ophtable[oedegrees[kk].pid] = -1;
00288         ophtable[other] = -1;
00289       }
00290 
00291       /* Compute the max vgain */
00292       for (k=0; k<myndegrees; k++) {
00293         if (myedegrees[k].gv > myrinfo->gv)
00294           myrinfo->gv = myedegrees[k].gv;
00295       }
00296     }
00297 
00298     if (myrinfo->ed > 0 && myrinfo->id == 0) 
00299       myrinfo->gv += vsize[i];
00300 
00301     if (myrinfo->gv >= 0 || myrinfo->ed-myrinfo->id >= 0)
00302       BNDInsert(graph->nbnd, bndind, bndptr, i);
00303   }
00304 
00305 stoptimer(ctrl->AuxTmr2);
00306 
00307   idxwspacefree(ctrl, nparts);
00308 
00309 }
00310 
00311 
00312 
00313 /*************************************************************************
00314 * This function projects a partition, and at the same time computes the
00315 * parameters for refinement.
00316 **************************************************************************/
00317 void ProjectVolKWayPartition(CtrlType *ctrl, GraphType *graph, int nparts)
00318 {
00319   int i, j, k, nvtxs, me, other, istart, iend, ndegrees;
00320   idxtype *xadj, *adjncy, *adjwgt, *adjwgtsum;
00321   idxtype *cmap, *where;
00322   idxtype *cwhere;
00323   GraphType *cgraph;
00324   VRInfoType *crinfo, *rinfo, *myrinfo;
00325   VEDegreeType *myedegrees;
00326   idxtype *htable;
00327 
00328   cgraph = graph->coarser;
00329   cwhere = cgraph->where;
00330   crinfo = cgraph->vrinfo;
00331 
00332   nvtxs = graph->nvtxs;
00333   cmap = graph->cmap;
00334   xadj = graph->xadj;
00335   adjncy = graph->adjncy;
00336   adjwgt = graph->adjwgt;
00337   adjwgtsum = graph->adjwgtsum;
00338 
00339   AllocateVolKWayPartitionMemory(ctrl, graph, nparts);
00340   where = graph->where;
00341   rinfo = graph->vrinfo;
00342 
00343   /* Go through and project partition and compute id/ed for the nodes */
00344   for (i=0; i<nvtxs; i++) {
00345     k = cmap[i];
00346     where[i] = cwhere[k];
00347     cmap[i] = crinfo[k].ed;  /* For optimization */
00348   }
00349 
00350   htable = idxset(nparts, -1, idxwspacemalloc(ctrl, nparts));
00351 
00352   ctrl->wspace.cdegree = 0;
00353   for (i=0; i<nvtxs; i++) {
00354     me = where[i];
00355 
00356     myrinfo = rinfo+i;
00357     myrinfo->id = myrinfo->ed = myrinfo->nid = myrinfo->ndegrees = 0;
00358     myrinfo->edegrees = NULL;
00359 
00360     myrinfo->id = adjwgtsum[i];
00361     myrinfo->nid = xadj[i+1]-xadj[i];
00362 
00363     if (cmap[i] > 0) { /* If it is an interface node. Note cmap[i] = crinfo[cmap[i]].ed */
00364       istart = xadj[i];
00365       iend = xadj[i+1];
00366 
00367       myedegrees = myrinfo->edegrees = ctrl->wspace.vedegrees+ctrl->wspace.cdegree;
00368       ctrl->wspace.cdegree += iend-istart;
00369 
00370       ndegrees = 0;
00371       for (j=istart; j<iend; j++) {
00372         other = where[adjncy[j]];
00373         if (me != other) {
00374           myrinfo->ed += adjwgt[j];
00375           myrinfo->nid--;
00376           if ((k = htable[other]) == -1) {
00377             htable[other] = ndegrees;
00378             myedegrees[ndegrees].gv = 0;
00379             myedegrees[ndegrees].pid = other;
00380             myedegrees[ndegrees].ed = adjwgt[j];
00381             myedegrees[ndegrees++].ned = 1;
00382           }
00383           else {
00384             myedegrees[k].ed += adjwgt[j];
00385             myedegrees[k].ned++;
00386           }
00387         }
00388       }
00389       myrinfo->id -= myrinfo->ed;
00390 
00391       /* Remove space for edegrees if it was interior */
00392       if (myrinfo->ed == 0) { 
00393         myrinfo->edegrees = NULL;
00394         ctrl->wspace.cdegree -= iend-istart;
00395       }
00396       else {
00397         myrinfo->ndegrees = ndegrees;
00398 
00399         for (j=0; j<ndegrees; j++)
00400           htable[myedegrees[j].pid] = -1;
00401       }
00402     }
00403   }
00404 
00405   ComputeKWayVolGains(ctrl, graph, nparts);
00406 
00407   idxcopy(nparts, cgraph->pwgts, graph->pwgts);
00408   graph->mincut = cgraph->mincut;
00409 
00410   FreeGraph(graph->coarser);
00411   graph->coarser = NULL;
00412 
00413   idxwspacefree(ctrl, nparts);
00414 
00415 }
00416 
00417 
00418 
00419 /*************************************************************************
00420 * This function computes the boundary definition for balancing
00421 **************************************************************************/
00422 void ComputeVolKWayBoundary(CtrlType *ctrl, GraphType *graph, int nparts)
00423 {
00424   int i, nvtxs, nbnd;
00425   idxtype *bndind, *bndptr;
00426 
00427   nvtxs = graph->nvtxs;
00428   bndind = graph->bndind;
00429   bndptr = idxset(nvtxs, -1, graph->bndptr);
00430 
00431 
00432   /*------------------------------------------------------------
00433   / Compute the new boundary
00434   /------------------------------------------------------------*/
00435   nbnd = 0;
00436   for (i=0; i<nvtxs; i++) {
00437     if (graph->vrinfo[i].gv >=0 || graph->vrinfo[i].ed-graph->vrinfo[i].id >= 0) 
00438       BNDInsert(nbnd, bndind, bndptr, i);
00439   }
00440 
00441   graph->nbnd = nbnd;
00442 }
00443 
00444 /*************************************************************************
00445 * This function computes the boundary definition for balancing
00446 **************************************************************************/
00447 void ComputeVolKWayBalanceBoundary(CtrlType *ctrl, GraphType *graph, int nparts)
00448 {
00449   int i, nvtxs, nbnd;
00450   idxtype *bndind, *bndptr;
00451 
00452   nvtxs = graph->nvtxs;
00453   bndind = graph->bndind;
00454   bndptr = idxset(nvtxs, -1, graph->bndptr);
00455 
00456 
00457   /*------------------------------------------------------------
00458   / Compute the new boundary
00459   /------------------------------------------------------------*/
00460   nbnd = 0;
00461   for (i=0; i<nvtxs; i++) {
00462     if (graph->vrinfo[i].ed > 0) 
00463       BNDInsert(nbnd, bndind, bndptr, i);
00464   }
00465 
00466   graph->nbnd = nbnd;
00467 }
00468
libs/ck-libs/parmetis/METISLib/kwayvolrefine.c
