Charm++: Charm Source Code Documentation

00001 /*
00002  * Copyright 1997, Regents of the University of Minnesota
00003  *
00004  * initpart.c
00005  *
00006  * This file contains code that performs the initial partition of the
00007  * coarsest graph
00008  *
00009  * Started 7/23/97
00010  * George
00011  *
00012  * $Id$
00013  *
00014  */
00015 
00016 #include <metis.h>
00017 
00018 /*************************************************************************
00019 * This function computes the initial bisection of the coarsest graph
00020 **************************************************************************/
00021 void Init2WayPartition(CtrlType *ctrl, GraphType *graph, int *tpwgts, floattype ubfactor) 
00022 {
00023   int dbglvl;
00024 
00025   dbglvl = ctrl->dbglvl;
00026   IFSET(ctrl->dbglvl, DBG_REFINE, ctrl->dbglvl -= DBG_REFINE);
00027   IFSET(ctrl->dbglvl, DBG_MOVEINFO, ctrl->dbglvl -= DBG_MOVEINFO);
00028 
00029   IFSET(ctrl->dbglvl, DBG_TIME, starttimer(ctrl->InitPartTmr));
00030 
00031   switch (ctrl->IType) {
00032     case IPART_GGPKL:
00033       if (graph->nedges == 0)
00034         RandomBisection(ctrl, graph, tpwgts, ubfactor);
00035       else
00036         GrowBisection(ctrl, graph, tpwgts, ubfactor);
00037       break;
00038     case 3:
00039       RandomBisection(ctrl, graph, tpwgts, ubfactor);
00040       break;
00041     default:
00042       errexit("Unknown initial partition type: %d\n", ctrl->IType);
00043   }
00044 
00045   IFSET(ctrl->dbglvl, DBG_IPART, printf("Initial Cut: %d\n", graph->mincut));
00046   IFSET(ctrl->dbglvl, DBG_TIME, stoptimer(ctrl->InitPartTmr));
00047   ctrl->dbglvl = dbglvl;
00048 
00049 /*
00050   IsConnectedSubdomain(ctrl, graph, 0);
00051   IsConnectedSubdomain(ctrl, graph, 1);
00052 */
00053 }
00054 
00055 /*************************************************************************
00056 * This function computes the initial bisection of the coarsest graph
00057 **************************************************************************/
00058 void InitSeparator(CtrlType *ctrl, GraphType *graph, floattype ubfactor) 
00059 {
00060   int dbglvl;
00061 
00062   dbglvl = ctrl->dbglvl;
00063   IFSET(ctrl->dbglvl, DBG_REFINE, ctrl->dbglvl -= DBG_REFINE);
00064   IFSET(ctrl->dbglvl, DBG_MOVEINFO, ctrl->dbglvl -= DBG_MOVEINFO);
00065 
00066   IFSET(ctrl->dbglvl, DBG_TIME, starttimer(ctrl->InitPartTmr));
00067 
00068   GrowBisectionNode(ctrl, graph, ubfactor);
00069   Compute2WayNodePartitionParams(ctrl, graph);
00070 
00071   IFSET(ctrl->dbglvl, DBG_IPART, printf("Initial Sep: %d\n", graph->mincut));
00072   IFSET(ctrl->dbglvl, DBG_TIME, stoptimer(ctrl->InitPartTmr));
00073 
00074   ctrl->dbglvl = dbglvl;
00075 
00076 }
00077 
00078 
00079 
00080 /*************************************************************************
00081 * This function takes a graph and produces a bisection by using a region
00082 * growing algorithm. The resulting partition is returned in
00083 * graph->where
00084 **************************************************************************/
00085 void GrowBisection(CtrlType *ctrl, GraphType *graph, int *tpwgts, floattype ubfactor)
00086 {
00087   int i, j, k, nvtxs, drain, nleft, first, last, pwgts[2], minpwgt[2], maxpwgt[2], from, bestcut, icut, mincut, me, pass, nbfs;
00088   idxtype *xadj, *vwgt, *adjncy, *adjwgt, *where;
00089   idxtype *queue, *touched, *gain, *bestwhere;
00090 
00091 
00092   nvtxs = graph->nvtxs;
00093   xadj = graph->xadj;
00094   vwgt = graph->vwgt;
00095   adjncy = graph->adjncy;
00096   adjwgt = graph->adjwgt;
00097 
00098   Allocate2WayPartitionMemory(ctrl, graph);
00099   where = graph->where;
00100 
00101   bestwhere = idxmalloc(nvtxs, "BisectGraph: bestwhere");
00102   queue = idxmalloc(nvtxs, "BisectGraph: queue");
00103   touched = idxmalloc(nvtxs, "BisectGraph: touched");
00104 
00105   ASSERTP(tpwgts[0]+tpwgts[1] == idxsum(nvtxs, vwgt), ("%d %d\n", tpwgts[0]+tpwgts[1], idxsum(nvtxs, vwgt)));
00106 
00107   maxpwgt[0] = ubfactor*tpwgts[0];
00108   maxpwgt[1] = ubfactor*tpwgts[1];
00109   minpwgt[0] = (1.0/ubfactor)*tpwgts[0];
00110   minpwgt[1] = (1.0/ubfactor)*tpwgts[1];
00111 
00112   nbfs = (nvtxs <= ctrl->CoarsenTo ? SMALLNIPARTS : LARGENIPARTS);
00113   bestcut = idxsum(nvtxs, graph->adjwgtsum)+1;  /* The +1 is for the 0 edges case */
00114   for (; nbfs>0; nbfs--) {
00115     idxset(nvtxs, 0, touched);
00116 
00117     pwgts[1] = tpwgts[0]+tpwgts[1];
00118     pwgts[0] = 0;
00119 
00120     idxset(nvtxs, 1, where);
00121 
00122     queue[0] = RandomInRange(nvtxs);
00123     touched[queue[0]] = 1;
00124     first = 0; last = 1;
00125     nleft = nvtxs-1;
00126     drain = 0;
00127 
00128     /* Start the BFS from queue to get a partition */
00129     for (;;) {
00130       if (first == last) { /* Empty. Disconnected graph! */
00131         if (nleft == 0 || drain)
00132           break;
00133 
00134         k = RandomInRange(nleft);
00135         for (i=0; i<nvtxs; i++) {
00136           if (touched[i] == 0) {
00137             if (k == 0)
00138               break;
00139             else
00140               k--;
00141           }
00142         }
00143 
00144         queue[0] = i;
00145         touched[i] = 1;
00146         first = 0; last = 1;;
00147         nleft--;
00148       }
00149 
00150       i = queue[first++];
00151       if (pwgts[0] > 0 && pwgts[1]-vwgt[i] < minpwgt[1]) {
00152         drain = 1;
00153         continue;
00154       }
00155 
00156       where[i] = 0;
00157       INC_DEC(pwgts[0], pwgts[1], vwgt[i]);
00158       if (pwgts[1] <= maxpwgt[1])
00159         break;
00160 
00161       drain = 0;
00162       for (j=xadj[i]; j<xadj[i+1]; j++) {
00163         k = adjncy[j];
00164         if (touched[k] == 0) {
00165           queue[last++] = k;
00166           touched[k] = 1;
00167           nleft--;
00168         }
00169       }
00170     }
00171 
00172     /* Check to see if we hit any bad limiting cases */
00173     if (pwgts[1] == 0) { 
00174       i = RandomInRange(nvtxs);
00175       where[i] = 1;
00176       INC_DEC(pwgts[1], pwgts[0], vwgt[i]);
00177     }
00178 
00179     /*************************************************************
00180     * Do some partition refinement 
00181     **************************************************************/
00182     Compute2WayPartitionParams(ctrl, graph);
00183     /*printf("IPART: %3d [%5d %5d] [%5d %5d] %5d\n", graph->nvtxs, pwgts[0], pwgts[1], graph->pwgts[0], graph->pwgts[1], graph->mincut); */
00184 
00185     Balance2Way(ctrl, graph, tpwgts, ubfactor);
00186     /*printf("BPART: [%5d %5d] %5d\n", graph->pwgts[0], graph->pwgts[1], graph->mincut);*/
00187 
00188     FM_2WayEdgeRefine(ctrl, graph, tpwgts, 4);
00189     /*printf("RPART: [%5d %5d] %5d\n", graph->pwgts[0], graph->pwgts[1], graph->mincut);*/
00190 
00191     if (bestcut > graph->mincut) {
00192       bestcut = graph->mincut;
00193       idxcopy(nvtxs, where, bestwhere);
00194       if (bestcut == 0)
00195         break;
00196     }
00197   }
00198 
00199   graph->mincut = bestcut;
00200   idxcopy(nvtxs, bestwhere, where);
00201 
00202   GKfree(&bestwhere, &queue, &touched, LTERM);
00203 }
00204 
00205 
00206 
00207 
00208 /*************************************************************************
00209 * This function takes a graph and produces a bisection by using a region
00210 * growing algorithm. The resulting partition is returned in
00211 * graph->where
00212 **************************************************************************/
00213 void GrowBisectionNode(CtrlType *ctrl, GraphType *graph, floattype ubfactor)
00214 {
00215   int i, j, k, nvtxs, drain, nleft, first, last, pwgts[2], tpwgts[2], minpwgt[2], maxpwgt[2], from, bestcut, icut, mincut, me, pass, nbfs;
00216   idxtype *xadj, *vwgt, *adjncy, *adjwgt, *where, *bndind;
00217   idxtype *queue, *touched, *gain, *bestwhere;
00218 
00219   nvtxs = graph->nvtxs;
00220   xadj = graph->xadj;
00221   vwgt = graph->vwgt;
00222   adjncy = graph->adjncy;
00223   adjwgt = graph->adjwgt;
00224 
00225   bestwhere = idxmalloc(nvtxs, "BisectGraph: bestwhere");
00226   queue = idxmalloc(nvtxs, "BisectGraph: queue");
00227   touched = idxmalloc(nvtxs, "BisectGraph: touched");
00228 
00229   tpwgts[0] = idxsum(nvtxs, vwgt);
00230   tpwgts[1] = tpwgts[0]/2;
00231   tpwgts[0] -= tpwgts[1];
00232 
00233   maxpwgt[0] = ubfactor*tpwgts[0];
00234   maxpwgt[1] = ubfactor*tpwgts[1];
00235   minpwgt[0] = (1.0/ubfactor)*tpwgts[0];
00236   minpwgt[1] = (1.0/ubfactor)*tpwgts[1];
00237 
00238   /* Allocate memory for graph->rdata. Allocate sufficient memory for both edge and node */
00239   graph->rdata = idxmalloc(5*nvtxs+3, "GrowBisectionNode: graph->rdata");
00240   graph->pwgts    = graph->rdata;
00241   graph->where    = graph->rdata + 3;
00242   graph->bndptr   = graph->rdata + nvtxs + 3;
00243   graph->bndind   = graph->rdata + 2*nvtxs + 3;
00244   graph->nrinfo   = (NRInfoType *)(graph->rdata + 3*nvtxs + 3);
00245   graph->id       = graph->rdata + 3*nvtxs + 3;
00246   graph->ed       = graph->rdata + 4*nvtxs + 3;
00247   
00248   where = graph->where;
00249   bndind = graph->bndind;
00250 
00251   nbfs = (nvtxs <= ctrl->CoarsenTo ? SMALLNIPARTS : LARGENIPARTS);
00252   bestcut = tpwgts[0]+tpwgts[1];
00253   for (nbfs++; nbfs>0; nbfs--) {
00254     idxset(nvtxs, 0, touched);
00255 
00256     pwgts[1] = tpwgts[0]+tpwgts[1];
00257     pwgts[0] = 0;
00258 
00259     idxset(nvtxs, 1, where);
00260 
00261     queue[0] = RandomInRange(nvtxs);
00262     touched[queue[0]] = 1;
00263     first = 0; last = 1;
00264     nleft = nvtxs-1;
00265     drain = 0;
00266 
00267     /* Start the BFS from queue to get a partition */
00268     if (nbfs >= 1) {
00269       for (;;) {
00270         if (first == last) { /* Empty. Disconnected graph! */
00271           if (nleft == 0 || drain)
00272             break;
00273   
00274           k = RandomInRange(nleft);
00275           for (i=0; i<nvtxs; i++) {
00276             if (touched[i] == 0) {
00277               if (k == 0)
00278                 break;
00279               else
00280                 k--;
00281             }
00282           }
00283 
00284           queue[0] = i;
00285           touched[i] = 1;
00286           first = 0; last = 1;;
00287           nleft--;
00288         }
00289 
00290         i = queue[first++];
00291         if (pwgts[1]-vwgt[i] < minpwgt[1]) {
00292           drain = 1;
00293           continue;
00294         }
00295 
00296         where[i] = 0;
00297         INC_DEC(pwgts[0], pwgts[1], vwgt[i]);
00298         if (pwgts[1] <= maxpwgt[1])
00299           break;
00300 
00301         drain = 0;
00302         for (j=xadj[i]; j<xadj[i+1]; j++) {
00303           k = adjncy[j];
00304           if (touched[k] == 0) {
00305             queue[last++] = k;
00306             touched[k] = 1;
00307             nleft--;
00308           }
00309         }
00310       }
00311     }
00312 
00313     /*************************************************************
00314     * Do some partition refinement 
00315     **************************************************************/
00316     Compute2WayPartitionParams(ctrl, graph);
00317     Balance2Way(ctrl, graph, tpwgts, ubfactor);
00318     FM_2WayEdgeRefine(ctrl, graph, tpwgts, 4);
00319 
00320     /* Construct and refine the vertex separator */
00321     for (i=0; i<graph->nbnd; i++) 
00322       where[bndind[i]] = 2;
00323 
00324     Compute2WayNodePartitionParams(ctrl, graph); 
00325     FM_2WayNodeRefine(ctrl, graph, ubfactor, 6);
00326 
00327     /* printf("ISep: [%d %d %d] %d\n", graph->pwgts[0], graph->pwgts[1], graph->pwgts[2], bestcut); */
00328 
00329     if (bestcut > graph->mincut) {
00330       bestcut = graph->mincut;
00331       idxcopy(nvtxs, where, bestwhere);
00332     }
00333   }
00334 
00335   graph->mincut = bestcut;
00336   idxcopy(nvtxs, bestwhere, where);
00337 
00338   Compute2WayNodePartitionParams(ctrl, graph); 
00339 
00340   GKfree(&bestwhere, &queue, &touched, LTERM);
00341 }
00342 
00343 
00344 /*************************************************************************
00345 * This function takes a graph and produces a bisection by using a region
00346 * growing algorithm. The resulting partition is returned in
00347 * graph->where
00348 **************************************************************************/
00349 void RandomBisection(CtrlType *ctrl, GraphType *graph, int *tpwgts, floattype ubfactor)
00350 {
00351   int i, ii, j, k, nvtxs, pwgts[2], minpwgt[2], maxpwgt[2], from, bestcut, icut, mincut, me, pass, nbfs;
00352   idxtype *xadj, *vwgt, *adjncy, *adjwgt, *where;
00353   idxtype *perm, *bestwhere;
00354 
00355   nvtxs = graph->nvtxs;
00356   xadj = graph->xadj;
00357   vwgt = graph->vwgt;
00358   adjncy = graph->adjncy;
00359   adjwgt = graph->adjwgt;
00360 
00361   Allocate2WayPartitionMemory(ctrl, graph);
00362   where = graph->where;
00363 
00364   bestwhere = idxmalloc(nvtxs, "BisectGraph: bestwhere");
00365   perm = idxmalloc(nvtxs, "BisectGraph: queue");
00366 
00367   ASSERTP(tpwgts[0]+tpwgts[1] == idxsum(nvtxs, vwgt), ("%d %d\n", tpwgts[0]+tpwgts[1], idxsum(nvtxs, vwgt)));
00368 
00369   maxpwgt[0] = ubfactor*tpwgts[0];
00370   maxpwgt[1] = ubfactor*tpwgts[1];
00371   minpwgt[0] = (1.0/ubfactor)*tpwgts[0];
00372   minpwgt[1] = (1.0/ubfactor)*tpwgts[1];
00373 
00374   nbfs = (nvtxs <= ctrl->CoarsenTo ? SMALLNIPARTS : LARGENIPARTS);
00375   bestcut = idxsum(nvtxs, graph->adjwgtsum)+1;  /* The +1 is for the 0 edges case */
00376   for (; nbfs>0; nbfs--) {
00377     RandomPermute(nvtxs, perm, 1);
00378 
00379     idxset(nvtxs, 1, where);
00380     pwgts[1] = tpwgts[0]+tpwgts[1];
00381     pwgts[0] = 0;
00382 
00383 
00384     if (nbfs != 1) {
00385       for (ii=0; ii<nvtxs; ii++) {
00386         i = perm[ii];
00387         if (pwgts[0]+vwgt[i] < maxpwgt[0]) {
00388           where[i] = 0;
00389           pwgts[0] += vwgt[i];
00390           pwgts[1] -= vwgt[i];
00391           if (pwgts[0] > minpwgt[0])
00392             break;
00393         }
00394       }
00395     }
00396 
00397     /*************************************************************
00398     * Do some partition refinement 
00399     **************************************************************/
00400     Compute2WayPartitionParams(ctrl, graph);
00401     /* printf("IPART: %3d [%5d %5d] [%5d %5d] %5d\n", graph->nvtxs, pwgts[0], pwgts[1], graph->pwgts[0], graph->pwgts[1], graph->mincut); */
00402 
00403     Balance2Way(ctrl, graph, tpwgts, ubfactor);
00404     /* printf("BPART: [%5d %5d] %5d\n", graph->pwgts[0], graph->pwgts[1], graph->mincut); */
00405 
00406     FM_2WayEdgeRefine(ctrl, graph, tpwgts, 4);
00407     /* printf("RPART: [%5d %5d] %5d\n", graph->pwgts[0], graph->pwgts[1], graph->mincut); */
00408 
00409     if (bestcut > graph->mincut) {
00410       bestcut = graph->mincut;
00411       idxcopy(nvtxs, where, bestwhere);
00412       if (bestcut == 0)
00413         break;
00414     }
00415   }
00416 
00417   graph->mincut = bestcut;
00418   idxcopy(nvtxs, bestwhere, where);
00419 
00420   GKfree(&bestwhere, &perm, LTERM);
00421 }
00422 
00423 
00424 
00425
libs/ck-libs/parmetis/METISLib/initpart.c
