Charm++: Charm Source Code Documentation

00001 /*
00002  * Copyright 1997, Regents of the University of Minnesota
00003  *
00004  * kvmetis.c
00005  *
00006  * This file contains the top level routines for the multilevel k-way partitioning
00007  * algorithm KMETIS.
00008  *
00009  * Started 7/28/97
00010  * George
00011  *
00012  * $Id$
00013  *
00014  */
00015 
00016 #include <metis.h>
00017 
00018 
00019 /*************************************************************************
00020 * This function is the entry point for KMETIS
00021 **************************************************************************/
00022 void METIS_PartGraphVKway(int *nvtxs, idxtype *xadj, idxtype *adjncy, idxtype *vwgt, 
00023                          idxtype *vsize, int *wgtflag, int *numflag, int *nparts, 
00024                          int *options, int *volume, 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_WPartGraphVKway(nvtxs, xadj, adjncy, vwgt, vsize, wgtflag, numflag, nparts, 
00034                        tpwgts, options, volume, part);
00035 
00036   free(tpwgts);
00037 }
00038 
00039 
00040 /*************************************************************************
00041 * This function is the entry point for KWMETIS
00042 **************************************************************************/
00043 void METIS_WPartGraphVKway(int *nvtxs, idxtype *xadj, idxtype *adjncy, idxtype *vwgt, 
00044                           idxtype *vsize, int *wgtflag, int *numflag, int *nparts, 
00045                           floattype *tpwgts, int *options, int *volume, idxtype *part)
00046 {
00047   int i, j;
00048   GraphType graph;
00049   CtrlType ctrl;
00050 
00051   if (*numflag == 1)
00052     Change2CNumbering(*nvtxs, xadj, adjncy);
00053 
00054   VolSetUpGraph(&graph, OP_KVMETIS, *nvtxs, 1, xadj, adjncy, vwgt, vsize, *wgtflag);
00055 
00056   if (options[0] == 0) {  /* Use the default parameters */
00057     ctrl.CType = KVMETIS_CTYPE;
00058     ctrl.IType = KVMETIS_ITYPE;
00059     ctrl.RType = KVMETIS_RTYPE;
00060     ctrl.dbglvl = KVMETIS_DBGLVL;
00061   }
00062   else {
00063     ctrl.CType = options[OPTION_CTYPE];
00064     ctrl.IType = options[OPTION_ITYPE];
00065     ctrl.RType = options[OPTION_RTYPE];
00066     ctrl.dbglvl = options[OPTION_DBGLVL];
00067   }
00068   ctrl.optype = OP_KVMETIS;
00069   ctrl.CoarsenTo = amax((*nvtxs)/(40*log2Int(*nparts)), 20*(*nparts));
00070   ctrl.maxvwgt = 1.5*((graph.vwgt ? idxsum(*nvtxs, graph.vwgt) : (*nvtxs))/ctrl.CoarsenTo);
00071 
00072   InitRandom(-1);
00073 
00074   AllocateWorkSpace(&ctrl, &graph, *nparts);
00075 
00076   IFSET(ctrl.dbglvl, DBG_TIME, InitTimers(&ctrl));
00077   IFSET(ctrl.dbglvl, DBG_TIME, starttimer(ctrl.TotalTmr));
00078 
00079   *volume = MlevelVolKWayPartitioning(&ctrl, &graph, *nparts, part, tpwgts, 1.03);
00080 
00081   IFSET(ctrl.dbglvl, DBG_TIME, stoptimer(ctrl.TotalTmr));
00082   IFSET(ctrl.dbglvl, DBG_TIME, PrintTimers(&ctrl));
00083 
00084   FreeWorkSpace(&ctrl, &graph);
00085 
00086   if (*numflag == 1)
00087     Change2FNumbering(*nvtxs, xadj, adjncy, part);
00088 }
00089 
00090 
00091 /*************************************************************************
00092 * This function takes a graph and produces a bisection of it
00093 **************************************************************************/
00094 int MlevelVolKWayPartitioning(CtrlType *ctrl, GraphType *graph, int nparts, idxtype *part, 
00095                               floattype *tpwgts, floattype ubfactor)
00096 {
00097   int i, j, nvtxs, tvwgt, tpwgts2[2];
00098   GraphType *cgraph;
00099   int wgtflag=3, numflag=0, options[10], edgecut;
00100 
00101   cgraph = Coarsen2Way(ctrl, graph);
00102 
00103   IFSET(ctrl->dbglvl, DBG_TIME, starttimer(ctrl->InitPartTmr));
00104   AllocateVolKWayPartitionMemory(ctrl, cgraph, nparts);
00105 
00106   options[0] = 1; 
00107   options[OPTION_CTYPE] = MATCH_SHEMKWAY;
00108   options[OPTION_ITYPE] = IPART_GGPKL;
00109   options[OPTION_RTYPE] = RTYPE_FM;
00110   options[OPTION_DBGLVL] = 0;
00111 
00112   METIS_WPartGraphRecursive(&cgraph->nvtxs, cgraph->xadj, cgraph->adjncy, cgraph->vwgt, 
00113                             cgraph->adjwgt, &wgtflag, &numflag, &nparts, tpwgts, options, 
00114                             &edgecut, cgraph->where);
00115 
00116   IFSET(ctrl->dbglvl, DBG_TIME, stoptimer(ctrl->InitPartTmr));
00117   IFSET(ctrl->dbglvl, DBG_IPART, printf("Initial %d-way partitioning cut: %d\n", nparts, edgecut));
00118 
00119   IFSET(ctrl->dbglvl, DBG_KWAYPINFO, ComputePartitionInfo(cgraph, nparts, cgraph->where));
00120 
00121   RefineVolKWay(ctrl, graph, cgraph, nparts, tpwgts, ubfactor);
00122 
00123   idxcopy(graph->nvtxs, graph->where, part);
00124 
00125   GKfree(&graph->gdata, &graph->rdata, LTERM);
00126 
00127   return graph->minvol;
00128 
00129 }
00130
libs/ck-libs/parmetis/METISLib/kvmetis.c
