Charm++: Charm Source Code Documentation

00001 /*
00002  * Copyright 1997, Regents of the University of Minnesota
00003  *
00004  * kwayrefine.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 RefineKWay(CtrlType *ctrl, GraphType *orggraph, GraphType *graph, int nparts, floattype *tpwgts, floattype ubfactor)
00021 {
00022   int i, nlevels, mustfree=0;
00023   GraphType *ptr;
00024 
00025   IFSET(ctrl->dbglvl, DBG_TIME, starttimer(ctrl->UncoarsenTmr));
00026 
00027   /* Compute the parameters of the coarsest graph */
00028   ComputeKWayPartitionParams(ctrl, graph, nparts);
00029 
00030   /* Take care any non-contiguity */
00031   IFSET(ctrl->dbglvl, DBG_TIME, starttimer(ctrl->AuxTmr1));
00032   if (ctrl->RType == RTYPE_KWAYRANDOM_MCONN) {
00033     EliminateComponents(ctrl, graph, nparts, tpwgts, 1.25);
00034     EliminateSubDomainEdges(ctrl, graph, nparts, tpwgts);
00035     EliminateComponents(ctrl, graph, nparts, tpwgts, 1.25);
00036   }
00037   IFSET(ctrl->dbglvl, DBG_TIME, stoptimer(ctrl->AuxTmr1));
00038 
00039   /* Determine how many levels are there */
00040   for (ptr=graph, nlevels=0; ptr!=orggraph; ptr=ptr->finer, nlevels++); 
00041 
00042   for (i=0; ;i++) {
00043     /* PrintSubDomainGraph(graph, nparts, graph->where); */
00044     if (ctrl->RType == RTYPE_KWAYRANDOM_MCONN && (i == nlevels/2 || i == nlevels/2+1))
00045       EliminateSubDomainEdges(ctrl, graph, nparts, tpwgts);
00046 
00047     IFSET(ctrl->dbglvl, DBG_TIME, starttimer(ctrl->RefTmr));
00048 
00049     if (2*i >= nlevels && !IsBalanced(graph->pwgts, nparts, tpwgts, 1.04*ubfactor)) {
00050       ComputeKWayBalanceBoundary(ctrl, graph, nparts);
00051       if (ctrl->RType == RTYPE_KWAYRANDOM_MCONN)
00052         Greedy_KWayEdgeBalanceMConn(ctrl, graph, nparts, tpwgts, ubfactor, 1); 
00053       else
00054         Greedy_KWayEdgeBalance(ctrl, graph, nparts, tpwgts, ubfactor, 1); 
00055       ComputeKWayBoundary(ctrl, graph, nparts);
00056     }
00057 
00058     switch (ctrl->RType) {
00059       case RTYPE_KWAYRANDOM:
00060         Random_KWayEdgeRefine(ctrl, graph, nparts, tpwgts, ubfactor, 10, 1); 
00061         break;
00062       case RTYPE_KWAYGREEDY:
00063         Greedy_KWayEdgeRefine(ctrl, graph, nparts, tpwgts, ubfactor, 10); 
00064         break;
00065       case RTYPE_KWAYRANDOM_MCONN:
00066         Random_KWayEdgeRefineMConn(ctrl, graph, nparts, tpwgts, ubfactor, 10, 1); 
00067         break;
00068     }
00069     IFSET(ctrl->dbglvl, DBG_TIME, stoptimer(ctrl->RefTmr));
00070 
00071     if (graph == orggraph)
00072       break;
00073 
00074     GKfree(&graph->gdata, LTERM);  /* Deallocate the graph related arrays */
00075 
00076     graph = graph->finer;
00077 
00078     IFSET(ctrl->dbglvl, DBG_TIME, starttimer(ctrl->ProjectTmr));
00079     if (graph->vwgt == NULL) {
00080       graph->vwgt = idxsmalloc(graph->nvtxs, 1, "RefineKWay: graph->vwgt");
00081       graph->adjwgt = idxsmalloc(graph->nedges, 1, "RefineKWay: graph->adjwgt");
00082       mustfree = 1;
00083     }
00084     ProjectKWayPartition(ctrl, graph, nparts);
00085     IFSET(ctrl->dbglvl, DBG_TIME, stoptimer(ctrl->ProjectTmr));
00086   }
00087 
00088   if (!IsBalanced(graph->pwgts, nparts, tpwgts, ubfactor)) {
00089     ComputeKWayBalanceBoundary(ctrl, graph, nparts);
00090     if (ctrl->RType == RTYPE_KWAYRANDOM_MCONN) {
00091       Greedy_KWayEdgeBalanceMConn(ctrl, graph, nparts, tpwgts, ubfactor, 8); 
00092       Random_KWayEdgeRefineMConn(ctrl, graph, nparts, tpwgts, ubfactor, 10, 0); 
00093     }
00094     else {
00095       Greedy_KWayEdgeBalance(ctrl, graph, nparts, tpwgts, ubfactor, 8); 
00096       Random_KWayEdgeRefine(ctrl, graph, nparts, tpwgts, ubfactor, 10, 0); 
00097     }
00098   }
00099 
00100   /* Take care any trivial non-contiguity */
00101   IFSET(ctrl->dbglvl, DBG_TIME, starttimer(ctrl->AuxTmr2));
00102   EliminateComponents(ctrl, graph, nparts, tpwgts, ubfactor);
00103   IFSET(ctrl->dbglvl, DBG_TIME, stoptimer(ctrl->AuxTmr2));
00104 
00105   if (mustfree) 
00106     GKfree(&graph->vwgt, &graph->adjwgt, LTERM);
00107 
00108   IFSET(ctrl->dbglvl, DBG_TIME, stoptimer(ctrl->UncoarsenTmr));
00109 }
00110 
00111 
00112 /*************************************************************************
00113 * This function allocates memory for k-way edge refinement
00114 **************************************************************************/
00115 void AllocateKWayPartitionMemory(CtrlType *ctrl, GraphType *graph, int nparts)
00116 {
00117   int nvtxs, pad64;
00118 
00119   nvtxs = graph->nvtxs;
00120 
00121   pad64 = (3*nvtxs+nparts)%2;
00122 
00123   graph->rdata = idxmalloc(3*nvtxs+nparts+(sizeof(RInfoType)/sizeof(idxtype))*nvtxs+pad64, "AllocateKWayPartitionMemory: rdata");
00124   graph->pwgts          = graph->rdata;
00125   graph->where          = graph->rdata + nparts;
00126   graph->bndptr         = graph->rdata + nvtxs + nparts;
00127   graph->bndind         = graph->rdata + 2*nvtxs + nparts;
00128   graph->rinfo          = (RInfoType *)(graph->rdata + 3*nvtxs+nparts + pad64);
00129 
00130 /*
00131   if (ctrl->wspace.edegrees != NULL)
00132     free(ctrl->wspace.edegrees);
00133   ctrl->wspace.edegrees = (EDegreeType *)GKmalloc(graph->nedges*sizeof(EDegreeType), "AllocateKWayPartitionMemory: edegrees");
00134 */
00135 }
00136 
00137 
00138 /*************************************************************************
00139 * This function computes the initial id/ed 
00140 **************************************************************************/
00141 void ComputeKWayPartitionParams(CtrlType *ctrl, GraphType *graph, int nparts)
00142 {
00143   int i, j, k, l, nvtxs, nbnd, mincut, me, other;
00144   idxtype *xadj, *vwgt, *adjncy, *adjwgt, *pwgts, *where, *bndind, *bndptr;
00145   RInfoType *rinfo, *myrinfo;
00146   EDegreeType *myedegrees;
00147 
00148   nvtxs = graph->nvtxs;
00149   xadj = graph->xadj;
00150   vwgt = graph->vwgt;
00151   adjncy = graph->adjncy;
00152   adjwgt = graph->adjwgt;
00153 
00154   where = graph->where;
00155   pwgts = idxset(nparts, 0, graph->pwgts);
00156   bndind = graph->bndind;
00157   bndptr = idxset(nvtxs, -1, graph->bndptr);
00158   rinfo = graph->rinfo;
00159 
00160 
00161   /*------------------------------------------------------------
00162   / Compute now the id/ed degrees
00163   /------------------------------------------------------------*/
00164   ctrl->wspace.cdegree = 0;
00165   nbnd = mincut = 0;
00166   for (i=0; i<nvtxs; i++) {
00167     me = where[i];
00168     pwgts[me] += vwgt[i];
00169 
00170     myrinfo = rinfo+i;
00171     myrinfo->id = myrinfo->ed = myrinfo->ndegrees = 0;
00172     myrinfo->edegrees = NULL;
00173 
00174     for (j=xadj[i]; j<xadj[i+1]; j++) {
00175       if (me != where[adjncy[j]])
00176         myrinfo->ed += adjwgt[j];
00177     }
00178     myrinfo->id = graph->adjwgtsum[i] - myrinfo->ed;
00179 
00180     if (myrinfo->ed > 0) 
00181       mincut += myrinfo->ed;
00182 
00183     if (myrinfo->ed-myrinfo->id >= 0)
00184       BNDInsert(nbnd, bndind, bndptr, i);
00185 
00186     /* Time to compute the particular external degrees */
00187     if (myrinfo->ed > 0) { 
00188       myedegrees = myrinfo->edegrees = ctrl->wspace.edegrees+ctrl->wspace.cdegree;
00189       ctrl->wspace.cdegree += xadj[i+1]-xadj[i];
00190 
00191       for (j=xadj[i]; j<xadj[i+1]; j++) {
00192         other = where[adjncy[j]];
00193         if (me != other) {
00194           for (k=0; k<myrinfo->ndegrees; k++) {
00195             if (myedegrees[k].pid == other) {
00196               myedegrees[k].ed += adjwgt[j];
00197               break;
00198             }
00199           }
00200           if (k == myrinfo->ndegrees) {
00201             myedegrees[myrinfo->ndegrees].pid = other;
00202             myedegrees[myrinfo->ndegrees++].ed = adjwgt[j];
00203           }
00204         }
00205       }
00206 
00207       ASSERT(myrinfo->ndegrees <= xadj[i+1]-xadj[i]);
00208     }
00209   }
00210 
00211   graph->mincut = mincut/2;
00212   graph->nbnd = nbnd;
00213 
00214 }
00215 
00216 
00217 
00218 /*************************************************************************
00219 * This function projects a partition, and at the same time computes the
00220 * parameters for refinement.
00221 **************************************************************************/
00222 void ProjectKWayPartition(CtrlType *ctrl, GraphType *graph, int nparts)
00223 {
00224   int i, j, k, nvtxs, nbnd, me, other, istart, iend, ndegrees;
00225   idxtype *xadj, *adjncy, *adjwgt, *adjwgtsum;
00226   idxtype *cmap, *where, *bndptr, *bndind;
00227   idxtype *cwhere;
00228   GraphType *cgraph;
00229   RInfoType *crinfo, *rinfo, *myrinfo;
00230   EDegreeType *myedegrees;
00231   idxtype *htable;
00232 
00233   cgraph = graph->coarser;
00234   cwhere = cgraph->where;
00235   crinfo = cgraph->rinfo;
00236 
00237   nvtxs = graph->nvtxs;
00238   cmap = graph->cmap;
00239   xadj = graph->xadj;
00240   adjncy = graph->adjncy;
00241   adjwgt = graph->adjwgt;
00242   adjwgtsum = graph->adjwgtsum;
00243 
00244   AllocateKWayPartitionMemory(ctrl, graph, nparts);
00245   where = graph->where;
00246   rinfo = graph->rinfo;
00247   bndind = graph->bndind;
00248   bndptr = idxset(nvtxs, -1, graph->bndptr);
00249 
00250   /* Go through and project partition and compute id/ed for the nodes */
00251   for (i=0; i<nvtxs; i++) {
00252     k = cmap[i];
00253     where[i] = cwhere[k];
00254     cmap[i] = crinfo[k].ed;  /* For optimization */
00255   }
00256 
00257   htable = idxset(nparts, -1, idxwspacemalloc(ctrl, nparts));
00258 
00259   ctrl->wspace.cdegree = 0;
00260   for (nbnd=0, i=0; i<nvtxs; i++) {
00261     me = where[i];
00262 
00263     myrinfo = rinfo+i;
00264     myrinfo->id = myrinfo->ed = myrinfo->ndegrees = 0;
00265     myrinfo->edegrees = NULL;
00266 
00267     myrinfo->id = adjwgtsum[i];
00268 
00269     if (cmap[i] > 0) { /* If it is an interface node. Note cmap[i] = crinfo[cmap[i]].ed */
00270       istart = xadj[i];
00271       iend = xadj[i+1];
00272 
00273       myedegrees = myrinfo->edegrees = ctrl->wspace.edegrees+ctrl->wspace.cdegree;
00274       ctrl->wspace.cdegree += iend-istart;
00275 
00276       ndegrees = 0;
00277       for (j=istart; j<iend; j++) {
00278         other = where[adjncy[j]];
00279         if (me != other) {
00280           myrinfo->ed += adjwgt[j];
00281           if ((k = htable[other]) == -1) {
00282             htable[other] = ndegrees;
00283             myedegrees[ndegrees].pid = other;
00284             myedegrees[ndegrees++].ed = adjwgt[j];
00285           }
00286           else {
00287             myedegrees[k].ed += adjwgt[j];
00288           }
00289         }
00290       }
00291       myrinfo->id -= myrinfo->ed;
00292 
00293       /* Remove space for edegrees if it was interior */
00294       if (myrinfo->ed == 0) { 
00295         myrinfo->edegrees = NULL;
00296         ctrl->wspace.cdegree -= iend-istart;
00297       }
00298       else {
00299         if (myrinfo->ed-myrinfo->id >= 0) 
00300           BNDInsert(nbnd, bndind, bndptr, i); 
00301 
00302         myrinfo->ndegrees = ndegrees;
00303 
00304         for (j=0; j<ndegrees; j++)
00305           htable[myedegrees[j].pid] = -1;
00306       }
00307     }
00308   }
00309 
00310   idxcopy(nparts, cgraph->pwgts, graph->pwgts);
00311   graph->mincut = cgraph->mincut;
00312   graph->nbnd = nbnd;
00313 
00314   FreeGraph(graph->coarser);
00315   graph->coarser = NULL;
00316 
00317   idxwspacefree(ctrl, nparts);
00318 
00319   ASSERT(CheckBnd2(graph));
00320 
00321 }
00322 
00323 
00324 
00325 /*************************************************************************
00326 * This function checks if the partition weights are within the balance
00327 * contraints
00328 **************************************************************************/
00329 int IsBalanced(idxtype *pwgts, int nparts, floattype *tpwgts, floattype ubfactor)
00330 {
00331   int i, j, tvwgt;
00332 
00333   tvwgt = idxsum(nparts, pwgts);
00334   for (i=0; i<nparts; i++) {
00335     if (pwgts[i] > tpwgts[i]*tvwgt*(ubfactor+0.005))
00336       return 0;
00337   }
00338 
00339   return 1;
00340 }
00341 
00342 
00343 /*************************************************************************
00344 * This function computes the boundary definition for balancing
00345 **************************************************************************/
00346 void ComputeKWayBoundary(CtrlType *ctrl, GraphType *graph, int nparts)
00347 {
00348   int i, nvtxs, nbnd;
00349   idxtype *bndind, *bndptr;
00350 
00351   nvtxs = graph->nvtxs;
00352   bndind = graph->bndind;
00353   bndptr = idxset(nvtxs, -1, graph->bndptr);
00354 
00355 
00356   /*------------------------------------------------------------
00357   / Compute the new boundary
00358   /------------------------------------------------------------*/
00359   nbnd = 0;
00360   for (i=0; i<nvtxs; i++) {
00361     if (graph->rinfo[i].ed-graph->rinfo[i].id >= 0) 
00362       BNDInsert(nbnd, bndind, bndptr, i);
00363   }
00364 
00365   graph->nbnd = nbnd;
00366 }
00367 
00368 /*************************************************************************
00369 * This function computes the boundary definition for balancing
00370 **************************************************************************/
00371 void ComputeKWayBalanceBoundary(CtrlType *ctrl, GraphType *graph, int nparts)
00372 {
00373   int i, nvtxs, nbnd;
00374   idxtype *bndind, *bndptr;
00375 
00376   nvtxs = graph->nvtxs;
00377   bndind = graph->bndind;
00378   bndptr = idxset(nvtxs, -1, graph->bndptr);
00379 
00380 
00381   /*------------------------------------------------------------
00382   / Compute the new boundary
00383   /------------------------------------------------------------*/
00384   nbnd = 0;
00385   for (i=0; i<nvtxs; i++) {
00386     if (graph->rinfo[i].ed > 0) 
00387       BNDInsert(nbnd, bndind, bndptr, i);
00388   }
00389 
00390   graph->nbnd = nbnd;
00391 }
00392
libs/ck-libs/parmetis/METISLib/kwayrefine.c
