Charm++: Charm Source Code Documentation

00001 /*
00002  * Copyright 1997, Regents of the University of Minnesota
00003  *
00004  * parmetis.c
00005  *
00006  * This file contains top level routines that are used by ParMETIS
00007  *
00008  * Started 10/14/97
00009  * George
00010  *
00011  * $Id$
00012  *
00013  */
00014 
00015 #include <metis.h>
00016 
00017 
00018 /*************************************************************************
00019 * This function is the entry point for KMETIS with seed specification
00020 * in options[7] 
00021 **************************************************************************/
00022 void METIS_PartGraphKway2(int *nvtxs, idxtype *xadj, idxtype *adjncy, idxtype *vwgt, 
00023                          idxtype *adjwgt, int *wgtflag, int *numflag, int *nparts, 
00024                          int *options, int *edgecut, idxtype *part)
00025 {
00026   int i;
00027   floattype *tpwgts;
00028 
00029   tpwgts = fmalloc(*nparts, "KMETIS: tpwgts");
00030   for (i=0; i<*nparts; i++) 
00031     tpwgts[i] = 1.0/(1.0*(*nparts));
00032 
00033   METIS_WPartGraphKway2(nvtxs, xadj, adjncy, vwgt, adjwgt, wgtflag, numflag, nparts, 
00034                        tpwgts, options, edgecut, part);
00035 
00036   free(tpwgts);
00037 }
00038 
00039 
00040 /*************************************************************************
00041 * This function is the entry point for KWMETIS with seed specification
00042 * in options[7] 
00043 **************************************************************************/
00044 void METIS_WPartGraphKway2(int *nvtxs, idxtype *xadj, idxtype *adjncy, idxtype *vwgt, 
00045                           idxtype *adjwgt, int *wgtflag, int *numflag, int *nparts, 
00046                           floattype *tpwgts, int *options, int *edgecut, idxtype *part)
00047 {
00048   int i, j;
00049   GraphType graph;
00050   CtrlType ctrl;
00051 
00052   if (*numflag == 1)
00053     Change2CNumbering(*nvtxs, xadj, adjncy);
00054 
00055   SetUpGraph(&graph, OP_KMETIS, *nvtxs, 1, xadj, adjncy, vwgt, adjwgt, *wgtflag);
00056 
00057   if (options[0] == 0) {  /* Use the default parameters */
00058     ctrl.CType = KMETIS_CTYPE;
00059     ctrl.IType = KMETIS_ITYPE;
00060     ctrl.RType = KMETIS_RTYPE;
00061     ctrl.dbglvl = KMETIS_DBGLVL;
00062   }
00063   else {
00064     ctrl.CType = options[OPTION_CTYPE];
00065     ctrl.IType = options[OPTION_ITYPE];
00066     ctrl.RType = options[OPTION_RTYPE];
00067     ctrl.dbglvl = options[OPTION_DBGLVL];
00068   }
00069   ctrl.optype = OP_KMETIS;
00070   ctrl.CoarsenTo = 20*(*nparts);
00071   ctrl.maxvwgt = 1.5*((graph.vwgt ? idxsum(*nvtxs, graph.vwgt) : (*nvtxs))/ctrl.CoarsenTo);
00072 
00073   InitRandom(options[7]);
00074 
00075   AllocateWorkSpace(&ctrl, &graph, *nparts);
00076 
00077   IFSET(ctrl.dbglvl, DBG_TIME, InitTimers(&ctrl));
00078   IFSET(ctrl.dbglvl, DBG_TIME, starttimer(ctrl.TotalTmr));
00079 
00080   *edgecut = MlevelKWayPartitioning(&ctrl, &graph, *nparts, part, tpwgts, 1.000);
00081 
00082   IFSET(ctrl.dbglvl, DBG_TIME, stoptimer(ctrl.TotalTmr));
00083   IFSET(ctrl.dbglvl, DBG_TIME, PrintTimers(&ctrl));
00084 
00085   FreeWorkSpace(&ctrl, &graph);
00086 
00087   if (*numflag == 1)
00088     Change2FNumbering(*nvtxs, xadj, adjncy, part);
00089 }
00090 
00091 
00092 /*************************************************************************
00093 * This function is the entry point for the node ND code for ParMETIS
00094 **************************************************************************/
00095 void METIS_NodeNDP(int nvtxs, idxtype *xadj, idxtype *adjncy, int npes, 
00096                    int *options, idxtype *perm, idxtype *iperm, idxtype *sizes) 
00097 {
00098   int i, ii, j, l, wflag, nflag;
00099   GraphType graph;
00100   CtrlType ctrl;
00101   idxtype *cptr, *cind;
00102 
00103   if (options[0] == 0) {  /* Use the default parameters */
00104     ctrl.CType   = ONMETIS_CTYPE;
00105     ctrl.IType   = ONMETIS_ITYPE;
00106     ctrl.RType   = ONMETIS_RTYPE;
00107     ctrl.dbglvl  = ONMETIS_DBGLVL;
00108     ctrl.oflags  = ONMETIS_OFLAGS;
00109     ctrl.pfactor = ONMETIS_PFACTOR;
00110     ctrl.nseps   = ONMETIS_NSEPS;
00111   }
00112   else {
00113     ctrl.CType   = options[OPTION_CTYPE];
00114     ctrl.IType   = options[OPTION_ITYPE];
00115     ctrl.RType   = options[OPTION_RTYPE];
00116     ctrl.dbglvl  = options[OPTION_DBGLVL];
00117     ctrl.oflags  = options[OPTION_OFLAGS];
00118     ctrl.pfactor = options[OPTION_PFACTOR];
00119     ctrl.nseps   = options[OPTION_NSEPS];
00120   }
00121   if (ctrl.nseps < 1)
00122     ctrl.nseps = 1;
00123 
00124   ctrl.optype = OP_ONMETIS;
00125   ctrl.CoarsenTo = 100;
00126 
00127   IFSET(ctrl.dbglvl, DBG_TIME, InitTimers(&ctrl));
00128   IFSET(ctrl.dbglvl, DBG_TIME, starttimer(ctrl.TotalTmr));
00129 
00130   InitRandom(-1);
00131 
00132   if (ctrl.oflags&OFLAG_COMPRESS) {
00133     /*============================================================
00134     * Compress the graph 
00135     ==============================================================*/
00136     cptr = idxmalloc(nvtxs+1, "ONMETIS: cptr");
00137     cind = idxmalloc(nvtxs, "ONMETIS: cind");
00138 
00139     CompressGraph(&ctrl, &graph, nvtxs, xadj, adjncy, cptr, cind);
00140 
00141     if (graph.nvtxs >= COMPRESSION_FRACTION*(nvtxs)) {
00142       ctrl.oflags--; /* We actually performed no compression */
00143       GKfree(&cptr, &cind, LTERM);
00144     }
00145     else if (2*graph.nvtxs < nvtxs && ctrl.nseps == 1)
00146       ctrl.nseps = 2;
00147   }
00148   else {
00149     SetUpGraph(&graph, OP_ONMETIS, nvtxs, 1, xadj, adjncy, NULL, NULL, 0);
00150   }
00151 
00152 
00153   /*=============================================================
00154   * Do the nested dissection ordering 
00155   --=============================================================*/
00156   ctrl.maxvwgt = 1.5*(idxsum(graph.nvtxs, graph.vwgt)/ctrl.CoarsenTo);
00157   AllocateWorkSpace(&ctrl, &graph, 2);
00158 
00159   idxset(2*npes-1, 0, sizes);
00160   MlevelNestedDissectionP(&ctrl, &graph, iperm, graph.nvtxs, npes, 0, sizes);
00161 
00162   FreeWorkSpace(&ctrl, &graph);
00163 
00164   if (ctrl.oflags&OFLAG_COMPRESS) { /* Uncompress the ordering */
00165     if (graph.nvtxs < COMPRESSION_FRACTION*(nvtxs)) { 
00166       /* construct perm from iperm */
00167       for (i=0; i<graph.nvtxs; i++)
00168         perm[iperm[i]] = i; 
00169       for (l=ii=0; ii<graph.nvtxs; ii++) {
00170         i = perm[ii];
00171         for (j=cptr[i]; j<cptr[i+1]; j++)
00172           iperm[cind[j]] = l++;
00173       }
00174     }
00175 
00176     GKfree(&cptr, &cind, LTERM);
00177   }
00178 
00179 
00180   for (i=0; i<nvtxs; i++)
00181     perm[iperm[i]] = i;
00182 
00183   IFSET(ctrl.dbglvl, DBG_TIME, stoptimer(ctrl.TotalTmr));
00184   IFSET(ctrl.dbglvl, DBG_TIME, PrintTimers(&ctrl));
00185 
00186 }
00187 
00188 
00189 
00190 /*************************************************************************
00191 * This function takes a graph and produces a bisection of it
00192 **************************************************************************/
00193 void MlevelNestedDissectionP(CtrlType *ctrl, GraphType *graph, idxtype *order, int lastvtx, 
00194                              int npes, int cpos, idxtype *sizes)
00195 {
00196   int i, j, nvtxs, nbnd, tvwgt, tpwgts2[2];
00197   idxtype *label, *bndind;
00198   GraphType lgraph, rgraph;
00199   floattype ubfactor;
00200 
00201   nvtxs = graph->nvtxs;
00202 
00203   if (nvtxs == 0) {
00204     GKfree(&graph->gdata, &graph->rdata, &graph->label, LTERM);
00205     return;
00206   }
00207 
00208   /* Determine the weights of the partitions */
00209   tvwgt = idxsum(nvtxs, graph->vwgt);
00210   tpwgts2[0] = tvwgt/2;
00211   tpwgts2[1] = tvwgt-tpwgts2[0];
00212 
00213   if (cpos >= npes-1) 
00214     ubfactor = ORDER_UNBALANCE_FRACTION;
00215   else 
00216     ubfactor = 1.05;
00217 
00218 
00219   MlevelNodeBisectionMultiple(ctrl, graph, tpwgts2, ubfactor);
00220 
00221   IFSET(ctrl->dbglvl, DBG_SEPINFO, printf("Nvtxs: %6d, [%6d %6d %6d]\n", graph->nvtxs, graph->pwgts[0], graph->pwgts[1], graph->pwgts[2]));
00222 
00223   if (cpos < npes-1) {
00224     sizes[2*npes-2-cpos] = graph->pwgts[2];
00225     sizes[2*npes-2-(2*cpos+1)] = graph->pwgts[1];
00226     sizes[2*npes-2-(2*cpos+2)] = graph->pwgts[0];
00227   }
00228 
00229   /* Order the nodes in the separator */
00230   nbnd = graph->nbnd;
00231   bndind = graph->bndind;
00232   label = graph->label;
00233   for (i=0; i<nbnd; i++) 
00234     order[label[bndind[i]]] = --lastvtx;
00235 
00236   SplitGraphOrder(ctrl, graph, &lgraph, &rgraph);
00237 
00238   /* Free the memory of the top level graph */
00239   GKfree(&graph->gdata, &graph->rdata, &graph->label, LTERM);
00240 
00241   if (rgraph.nvtxs > MMDSWITCH || 2*cpos+1 < npes-1) 
00242     MlevelNestedDissectionP(ctrl, &rgraph, order, lastvtx, npes, 2*cpos+1, sizes);
00243   else {
00244     MMDOrder(ctrl, &rgraph, order, lastvtx); 
00245     GKfree(&rgraph.gdata, &rgraph.rdata, &rgraph.label, LTERM);
00246   }
00247   if (lgraph.nvtxs > MMDSWITCH || 2*cpos+2 < npes-1) 
00248     MlevelNestedDissectionP(ctrl, &lgraph, order, lastvtx-rgraph.nvtxs, npes, 2*cpos+2, sizes);
00249   else {
00250     MMDOrder(ctrl, &lgraph, order, lastvtx-rgraph.nvtxs); 
00251     GKfree(&lgraph.gdata, &lgraph.rdata, &lgraph.label, LTERM);
00252   }
00253 }
00254 
00255 
00256 
00257 
00258 /*************************************************************************
00259 * This function is the entry point for ONWMETIS. It requires weights on the
00260 * vertices. It is for the case that the matrix has been pre-compressed.
00261 **************************************************************************/
00262 void METIS_NodeComputeSeparator(int *nvtxs, idxtype *xadj, idxtype *adjncy, idxtype *vwgt, 
00263            idxtype *adjwgt, int *options, int *sepsize, idxtype *part) 
00264 {
00265   int i, j, tvwgt, tpwgts[2];
00266   GraphType graph;
00267   CtrlType ctrl;
00268 
00269   SetUpGraph(&graph, OP_ONMETIS, *nvtxs, 1, xadj, adjncy, vwgt, adjwgt, 3);
00270   tvwgt = idxsum(*nvtxs, graph.vwgt);
00271 
00272   if (options[0] == 0) {  /* Use the default parameters */
00273     ctrl.CType = ONMETIS_CTYPE;
00274     ctrl.IType = ONMETIS_ITYPE;
00275     ctrl.RType = ONMETIS_RTYPE;
00276     ctrl.dbglvl = ONMETIS_DBGLVL;
00277   }
00278   else {
00279     ctrl.CType = options[OPTION_CTYPE];
00280     ctrl.IType = options[OPTION_ITYPE];
00281     ctrl.RType = options[OPTION_RTYPE];
00282     ctrl.dbglvl = options[OPTION_DBGLVL];
00283   }
00284 
00285   ctrl.oflags  = 0;
00286   ctrl.pfactor = 0;
00287   ctrl.nseps = 1;
00288   ctrl.optype = OP_ONMETIS;
00289   ctrl.CoarsenTo = amin(100, *nvtxs-1);
00290   ctrl.maxvwgt = 1.5*tvwgt/ctrl.CoarsenTo;
00291 
00292   InitRandom(options[7]);
00293 
00294   AllocateWorkSpace(&ctrl, &graph, 2);
00295 
00296   /*============================================================
00297    * Perform the bisection
00298    *============================================================*/ 
00299   tpwgts[0] = tvwgt/2;
00300   tpwgts[1] = tvwgt-tpwgts[0];
00301 
00302   MlevelNodeBisectionMultiple(&ctrl, &graph, tpwgts, 1.05);
00303 
00304   *sepsize = graph.pwgts[2];
00305   idxcopy(*nvtxs, graph.where, part);
00306 
00307   GKfree(&graph.gdata, &graph.rdata, &graph.label, LTERM);
00308 
00309 
00310   FreeWorkSpace(&ctrl, &graph);
00311 
00312 }
00313 
00314 
00315 
00316 /*************************************************************************
00317 * This function is the entry point for ONWMETIS. It requires weights on the
00318 * vertices. It is for the case that the matrix has been pre-compressed.
00319 **************************************************************************/
00320 void METIS_EdgeComputeSeparator(int *nvtxs, idxtype *xadj, idxtype *adjncy, idxtype *vwgt, 
00321            idxtype *adjwgt, int *options, int *sepsize, idxtype *part) 
00322 {
00323   int i, j, tvwgt, tpwgts[2];
00324   GraphType graph;
00325   CtrlType ctrl;
00326 
00327   SetUpGraph(&graph, OP_ONMETIS, *nvtxs, 1, xadj, adjncy, vwgt, adjwgt, 3);
00328   tvwgt = idxsum(*nvtxs, graph.vwgt);
00329 
00330   if (options[0] == 0) {  /* Use the default parameters */
00331     ctrl.CType = ONMETIS_CTYPE;
00332     ctrl.IType = ONMETIS_ITYPE;
00333     ctrl.RType = ONMETIS_RTYPE;
00334     ctrl.dbglvl = ONMETIS_DBGLVL;
00335   }
00336   else {
00337     ctrl.CType = options[OPTION_CTYPE];
00338     ctrl.IType = options[OPTION_ITYPE];
00339     ctrl.RType = options[OPTION_RTYPE];
00340     ctrl.dbglvl = options[OPTION_DBGLVL];
00341   }
00342 
00343   ctrl.oflags  = 0;
00344   ctrl.pfactor = 0;
00345   ctrl.nseps = 1;
00346   ctrl.optype = OP_OEMETIS;
00347   ctrl.CoarsenTo = amin(100, *nvtxs-1);
00348   ctrl.maxvwgt = 1.5*tvwgt/ctrl.CoarsenTo;
00349 
00350   InitRandom(options[7]);
00351 
00352   AllocateWorkSpace(&ctrl, &graph, 2);
00353 
00354   /*============================================================
00355    * Perform the bisection
00356    *============================================================*/ 
00357   tpwgts[0] = tvwgt/2;
00358   tpwgts[1] = tvwgt-tpwgts[0];
00359 
00360   MlevelEdgeBisection(&ctrl, &graph, tpwgts, 1.05);
00361   ConstructMinCoverSeparator(&ctrl, &graph, 1.05);
00362 
00363   *sepsize = graph.pwgts[2];
00364   idxcopy(*nvtxs, graph.where, part);
00365 
00366   GKfree(&graph.gdata, &graph.rdata, &graph.label, LTERM);
00367 
00368 
00369   FreeWorkSpace(&ctrl, &graph);
00370 
00371 }
00372 
00373 
00374 /*************************************************************************
00375 * This function is the entry point for PWMETIS that accepts exact weights
00376 * for the target partitions
00377 **************************************************************************/
00378 void METIS_mCPartGraphRecursive2(int *nvtxs, int *ncon, idxtype *xadj, idxtype *adjncy, 
00379        idxtype *vwgt, idxtype *adjwgt, int *wgtflag, int *numflag, int *nparts, 
00380        floattype *tpwgts, int *options, int *edgecut, idxtype *part)
00381 {
00382   int i, j;
00383   GraphType graph;
00384   CtrlType ctrl;
00385   floattype *mytpwgts;
00386   floattype avgwgt;
00387 
00388   if (*numflag == 1)
00389     Change2CNumbering(*nvtxs, xadj, adjncy);
00390 
00391   SetUpGraph(&graph, OP_PMETIS, *nvtxs, *ncon, xadj, adjncy, vwgt, adjwgt, *wgtflag);
00392   graph.npwgts = NULL;
00393   mytpwgts = fmalloc(*nparts, "mytpwgts");
00394   scopy(*nparts, tpwgts, mytpwgts);
00395 
00396   if (options[0] == 0) {  /* Use the default parameters */
00397     ctrl.CType  = McPMETIS_CTYPE;
00398     ctrl.IType  = McPMETIS_ITYPE;
00399     ctrl.RType  = McPMETIS_RTYPE;
00400     ctrl.dbglvl = McPMETIS_DBGLVL;
00401   }
00402   else {
00403     ctrl.CType  = options[OPTION_CTYPE];
00404     ctrl.IType  = options[OPTION_ITYPE];
00405     ctrl.RType  = options[OPTION_RTYPE];
00406     ctrl.dbglvl = options[OPTION_DBGLVL];
00407   }
00408   ctrl.optype = OP_PMETIS;
00409   ctrl.CoarsenTo = 100;
00410 
00411   ctrl.nmaxvwgt = 1.5/(1.0*ctrl.CoarsenTo);
00412 
00413   InitRandom(options[7]);
00414 
00415   AllocateWorkSpace(&ctrl, &graph, *nparts);
00416 
00417   IFSET(ctrl.dbglvl, DBG_TIME, InitTimers(&ctrl));
00418   IFSET(ctrl.dbglvl, DBG_TIME, starttimer(ctrl.TotalTmr));
00419 
00420   ASSERT(CheckGraph(&graph));
00421   *edgecut = MCMlevelRecursiveBisection2(&ctrl, &graph, *nparts, mytpwgts, part, 1.000, 0);
00422 
00423 /* 
00424 {
00425 idxtype wgt[2048], minwgt, maxwgt, sumwgt;
00426 
00427 printf("nvtxs: %d, nparts: %d, ncon: %d\n", graph.nvtxs, *nparts, *ncon);
00428 for (i=0; i<(*nparts)*(*ncon); i++)
00429   wgt[i] = 0;
00430 for (i=0; i<graph.nvtxs; i++)
00431   for (j=0; j<*ncon; j++)
00432     wgt[part[i]*(*ncon)+j] += vwgt[i*(*ncon)+j];
00433 
00434 for (j=0; j<*ncon; j++) {
00435  minwgt = maxwgt = sumwgt = 0;
00436  for (i=0; i<(*nparts); i++) {
00437    minwgt = (wgt[i*(*ncon)+j] < wgt[minwgt*(*ncon)+j]) ? i : minwgt;
00438    maxwgt = (wgt[i*(*ncon)+j] > wgt[maxwgt*(*ncon)+j]) ? i : maxwgt;
00439    sumwgt += wgt[i*(*ncon)+j];
00440  }
00441  avgwgt = (floattype)sumwgt / (floattype)*nparts;
00442  printf("min: %5d, max: %5d, avg: %5.2f, balance: %6.3f\n", wgt[minwgt*(*ncon)+j], wgt[maxwgt*(*ncon)+j], avgwgt, (floattype)wgt[maxwgt*(*ncon)+j] / avgwgt);
00443 }
00444 printf("\n");
00445 }
00446 */
00447 
00448   IFSET(ctrl.dbglvl, DBG_TIME, stoptimer(ctrl.TotalTmr));
00449   IFSET(ctrl.dbglvl, DBG_TIME, PrintTimers(&ctrl));
00450 
00451   FreeWorkSpace(&ctrl, &graph);
00452   GKfree((void *)&mytpwgts, LTERM);
00453 
00454   if (*numflag == 1)
00455     Change2FNumbering(*nvtxs, xadj, adjncy, part);
00456 }
00457 
00458 
00459 
00460 /*************************************************************************
00461 * This function takes a graph and produces a bisection of it
00462 **************************************************************************/
00463 int MCMlevelRecursiveBisection2(CtrlType *ctrl, GraphType *graph, int nparts,
00464     floattype *tpwgts, idxtype *part, floattype ubfactor, int fpart)
00465 {
00466   int i, nvtxs, cut;
00467   floattype wsum, tpwgts2[2];
00468   idxtype *label, *where;
00469   GraphType lgraph, rgraph;
00470 
00471   nvtxs = graph->nvtxs;
00472   if (nvtxs == 0) 
00473     return 0;
00474 
00475   /* Determine the weights of the partitions */
00476   tpwgts2[0] = ssum(nparts/2, tpwgts);
00477   tpwgts2[1] = 1.0-tpwgts2[0];
00478 
00479   MCMlevelEdgeBisection(ctrl, graph, tpwgts2, ubfactor);
00480   cut = graph->mincut;
00481 
00482   label = graph->label;
00483   where = graph->where;
00484   for (i=0; i<nvtxs; i++)
00485     part[label[i]] = where[i] + fpart;
00486 
00487   if (nparts > 2) 
00488     SplitGraphPart(ctrl, graph, &lgraph, &rgraph);
00489 
00490   /* Free the memory of the top level graph */
00491   GKfree(&graph->gdata, &graph->nvwgt, &graph->rdata, &graph->label, &graph->npwgts, LTERM);
00492 
00493   /* Scale the fractions in the tpwgts according to the true weight */
00494   wsum = ssum(nparts/2, tpwgts);
00495   sscale(nparts/2, 1.0/wsum, tpwgts);
00496   sscale(nparts-nparts/2, 1.0/(1.0-wsum), tpwgts+nparts/2);
00497 
00498   /* Do the recursive call */
00499   if (nparts > 3) {
00500     cut += MCMlevelRecursiveBisection2(ctrl, &lgraph, nparts/2, tpwgts, part, ubfactor, fpart);
00501     cut += MCMlevelRecursiveBisection2(ctrl, &rgraph, nparts-nparts/2, tpwgts+nparts/2, part, ubfactor, fpart+nparts/2);
00502   }
00503   else if (nparts == 3) {
00504     cut += MCMlevelRecursiveBisection2(ctrl, &rgraph, nparts-nparts/2, tpwgts+nparts/2, part, ubfactor, fpart+nparts/2);
00505     GKfree(&lgraph.gdata, &lgraph.nvwgt, &lgraph.label, LTERM);
00506   }
00507 
00508   return cut;
00509 
00510 }
00511 
00512
libs/ck-libs/parmetis/METISLib/parmetis.c
