Charm++: Charm Source Code Documentation

00001 /*
00002  * Copyright 1997, Regents of the University of Minnesota
00003  *
00004  * gkmetis.c
00005  *
00006  * This is the entry point of parallel geometry based partitioning
00007  * routines
00008  *
00009  * Started 10/19/96
00010  * George
00011  *
00012  * $Id$
00013  *
00014  */
00015 
00016 #include <parmetislib.h>
00017 
00018 
00019 
00020 
00021 /***********************************************************************************
00022 * This function is the entry point of the parallel kmetis algorithm that uses
00023 * coordinates to compute an initial graph distribution.
00024 ************************************************************************************/
00025 void ParMETIS_V3_PartGeomKway(idxtype *vtxdist, idxtype *xadj, idxtype *adjncy,
00026               idxtype *vwgt, idxtype *adjwgt, int *wgtflag, int *numflag, int *ndims, 
00027               floattype *xyz, int *ncon, int *nparts, floattype *tpwgts, floattype *ubvec, 
00028               int *options, int *edgecut, idxtype *part, MPI_Comm *comm)
00029 {
00030   int h, i, j;
00031   int nvtxs = -1, npes, mype;
00032   int uwgtflag, cut, gcut, maxnvtxs;
00033   int ltvwgts[MAXNCON];
00034   int moptions[10];
00035   CtrlType ctrl;
00036   idxtype *uvwgt;
00037   WorkSpaceType wspace;
00038   GraphType *graph, *mgraph;
00039   floattype avg, maximb, balance, *mytpwgts;
00040   int seed, dbglvl = 0;
00041   int iwgtflag, inumflag, incon, inparts, ioptions[10];
00042   floattype *itpwgts, iubvec[MAXNCON];
00043 
00044   MPI_Comm_size(*comm, &npes);
00045   MPI_Comm_rank(*comm, &mype);
00046 
00047   /********************************/
00048   /* Try and take care bad inputs */
00049   /********************************/
00050   if (options != NULL && options[0] == 1)
00051     dbglvl = options[PMV3_OPTION_DBGLVL];
00052 
00053   CheckInputs(STATIC_PARTITION, npes, dbglvl, wgtflag, &iwgtflag, numflag, &inumflag,
00054               ncon, &incon, nparts, &inparts, tpwgts, &itpwgts, ubvec, iubvec, 
00055               NULL, NULL, options, ioptions, part, comm);
00056 
00057 
00058   /*********************************/
00059   /* Take care the nparts = 1 case */
00060   /*********************************/
00061   if (inparts <= 1) {
00062     idxset(vtxdist[mype+1]-vtxdist[mype], 0, part);
00063     *edgecut = 0;
00064     return;
00065   }
00066 
00067   /******************************/
00068   /* Take care of npes = 1 case */
00069   /******************************/
00070   if (npes == 1 && inparts > 1) {
00071     moptions[0] = 0;
00072     nvtxs = vtxdist[1];
00073 
00074     if (incon == 1) {
00075       METIS_WPartGraphKway(&nvtxs, xadj, adjncy, vwgt, adjwgt, &iwgtflag, &inumflag, 
00076             &inparts, itpwgts, moptions, edgecut, part);
00077     }
00078     else {
00079       /* ADD: this is because METIS does not support tpwgts for all constraints */
00080       mytpwgts = fmalloc(inparts, "mytpwgts");
00081       for (i=0; i<inparts; i++)
00082         mytpwgts[i] = itpwgts[i*incon];
00083 
00084       moptions[7] = -1;
00085       METIS_mCPartGraphRecursive2(&nvtxs, &incon, xadj, adjncy, vwgt, adjwgt, &iwgtflag, 
00086             &inumflag, &inparts, mytpwgts, moptions, edgecut, part);
00087 
00088       free(mytpwgts);
00089     }
00090 
00091     return;
00092   }
00093 
00094 
00095   if (inumflag == 1)
00096     ChangeNumbering(vtxdist, xadj, adjncy, part, npes, mype, 1);
00097 
00098   /*****************************/
00099   /* Set up control structures */
00100   /*****************************/
00101   if (ioptions[0] == 1) {
00102     dbglvl = ioptions[PMV3_OPTION_DBGLVL];
00103     seed = ioptions[PMV3_OPTION_SEED];
00104   }
00105   else {
00106     dbglvl = GLOBAL_DBGLVL;
00107     seed = GLOBAL_SEED;
00108   }
00109   SetUpCtrl(&ctrl, npes, dbglvl, *comm);
00110   ctrl.CoarsenTo = amin(vtxdist[npes]+1, 25*incon*amax(npes, inparts));
00111   ctrl.seed = (seed == 0) ? mype : seed*mype;
00112   ctrl.sync = GlobalSEMax(&ctrl, seed);
00113   ctrl.partType = STATIC_PARTITION;
00114   ctrl.ps_relation = -1;
00115   ctrl.tpwgts = itpwgts;
00116   scopy(incon, iubvec, ctrl.ubvec);
00117 
00118   uwgtflag = iwgtflag|2;
00119   uvwgt = idxsmalloc(vtxdist[mype+1]-vtxdist[mype], 1, "uvwgt");
00120   graph = Moc_SetUpGraph(&ctrl, 1, vtxdist, xadj, uvwgt, adjncy, adjwgt, &uwgtflag);
00121   free(graph->nvwgt); graph->nvwgt = NULL;
00122 
00123   PreAllocateMemory(&ctrl, graph, &wspace);
00124 
00125   /*=================================================================
00126    * Compute the initial npes-way partitioning geometric partitioning
00127    =================================================================*/
00128   IFSET(ctrl.dbglvl, DBG_TIME, InitTimers(&ctrl));
00129   IFSET(ctrl.dbglvl, DBG_TIME, MPI_Barrier(ctrl.gcomm));
00130   IFSET(ctrl.dbglvl, DBG_TIME, starttimer(ctrl.TotalTmr));
00131 
00132   Coordinate_Partition(&ctrl, graph, *ndims, xyz, 1, &wspace);
00133 
00134   IFSET(ctrl.dbglvl, DBG_TIME, MPI_Barrier(ctrl.gcomm));
00135   IFSET(ctrl.dbglvl, DBG_TIME, stoptimer(ctrl.TotalTmr));
00136   IFSET(ctrl.dbglvl, DBG_TIME, PrintTimingInfo(&ctrl));
00137 
00138   /*=================================================================
00139    * Move the graph according to the partitioning
00140    =================================================================*/
00141   IFSET(ctrl.dbglvl, DBG_TIME, MPI_Barrier(ctrl.gcomm));
00142   IFSET(ctrl.dbglvl, DBG_TIME, starttimer(ctrl.MoveTmr));
00143 
00144   free(uvwgt);
00145   graph->vwgt = ((iwgtflag&2) != 0) ? vwgt : idxsmalloc(graph->nvtxs*incon, 1, "vwgt");
00146   graph->ncon = incon;
00147   j = ctrl.nparts;
00148   ctrl.nparts = ctrl.npes;
00149   mgraph = Moc_MoveGraph(&ctrl, graph, &wspace);
00150   ctrl.nparts = j;
00151 
00152   /**********************************************************/
00153   /* Do the same functionality as Moc_SetUpGraph for mgraph */
00154   /**********************************************************/
00155   /* compute tvwgts */
00156   for (j=0; j<incon; j++)
00157     ltvwgts[j] = 0;
00158 
00159   for (i=0; i<graph->nvtxs; i++)
00160     for (j=0; j<incon; j++)
00161       ltvwgts[j] += mgraph->vwgt[i*incon+j];
00162 
00163   for (j=0; j<incon; j++)
00164     ctrl.tvwgts[j] = GlobalSESum(&ctrl, ltvwgts[j]);
00165 
00166   /* check for zero wgt constraints */
00167   for (i=0; i<incon; i++) {
00168     /* ADD: take care of the case in which tvwgts is zero */
00169     if (ctrl.tvwgts[i] == 0) {
00170       if (ctrl.mype == 0) printf("ERROR: sum weight for constraint %d is zero\n", i);
00171       MPI_Finalize();
00172       exit(-1);
00173     }
00174   }
00175 
00176   /* compute nvwgt */
00177   mgraph->nvwgt = fmalloc(mgraph->nvtxs*incon, "mgraph->nvwgt");
00178   for (i=0; i<mgraph->nvtxs; i++)
00179     for (j=0; j<incon; j++)
00180       mgraph->nvwgt[i*incon+j] = (floattype)(mgraph->vwgt[i*incon+j]) / (floattype)(ctrl.tvwgts[j]);
00181 
00182 
00183   IFSET(ctrl.dbglvl, DBG_TIME, MPI_Barrier(ctrl.gcomm));
00184   IFSET(ctrl.dbglvl, DBG_TIME, stoptimer(ctrl.MoveTmr));
00185 
00186   if (ctrl.dbglvl&DBG_INFO) {
00187     cut = 0;
00188     for (i=0; i<graph->nvtxs; i++)
00189       for (j=graph->xadj[i]; j<graph->xadj[i+1]; j++)
00190         if (graph->where[i] != graph->where[graph->adjncy[j]])
00191           cut += graph->adjwgt[j];
00192     gcut = GlobalSESum(&ctrl, cut)/2;
00193     maxnvtxs = GlobalSEMax(&ctrl, mgraph->nvtxs);
00194     balance = (floattype)(maxnvtxs)/((floattype)(graph->gnvtxs)/(floattype)(npes));
00195     rprintf(&ctrl, "XYZ Cut: %6d \tBalance: %6.3f [%d %d %d]\n",
00196       gcut, balance, maxnvtxs, graph->gnvtxs, npes);
00197 
00198   }
00199 
00200   /*=================================================================
00201    * Set up the newly moved graph
00202    =================================================================*/
00203   IFSET(ctrl.dbglvl, DBG_TIME, MPI_Barrier(ctrl.gcomm));
00204   IFSET(ctrl.dbglvl, DBG_TIME, starttimer(ctrl.TotalTmr));
00205 
00206   ctrl.nparts = inparts;
00207   FreeWSpace(&wspace);
00208   PreAllocateMemory(&ctrl, mgraph, &wspace);
00209 
00210   /*=======================================================
00211    * Now compute the partition of the moved graph
00212    =======================================================*/
00213   if (vtxdist[npes] < SMALLGRAPH || vtxdist[npes] < npes*20 || GlobalSESum(&ctrl, mgraph->nedges) == 0) {
00214     IFSET(ctrl.dbglvl, DBG_INFO, rprintf(&ctrl, "Partitioning a graph of size %d serially\n", vtxdist[npes]));
00215     PartitionSmallGraph(&ctrl, mgraph, &wspace);
00216   }
00217   else {
00218     Moc_Global_Partition(&ctrl, mgraph, &wspace);
00219   }
00220   ParallelReMapGraph(&ctrl, mgraph, &wspace);
00221 
00222   /* Invert the ordering back to the original graph */
00223   ctrl.nparts = npes;
00224   ProjectInfoBack(&ctrl, graph, part, mgraph->where, &wspace);
00225 
00226   *edgecut = mgraph->mincut;
00227 
00228   IFSET(ctrl.dbglvl, DBG_TIME, MPI_Barrier(ctrl.gcomm));
00229   IFSET(ctrl.dbglvl, DBG_TIME, stoptimer(ctrl.TotalTmr));
00230 
00231   /*******************/
00232   /* Print out stats */
00233   /*******************/
00234   IFSET(ctrl.dbglvl, DBG_TIME, PrintTimingInfo(&ctrl));
00235   IFSET(ctrl.dbglvl, DBG_TIME, MPI_Barrier(ctrl.gcomm));
00236 
00237   if (ctrl.dbglvl&DBG_INFO) {
00238     rprintf(&ctrl, "Final %d-way CUT: %6d \tBalance: ", inparts, mgraph->mincut);
00239     avg = 0.0;
00240     for (h=0; h<incon; h++) {
00241       maximb = 0.0;
00242       for (i=0; i<inparts; i++)
00243         maximb = amax(maximb, mgraph->gnpwgts[i*incon+h]/itpwgts[i*incon+h]);
00244       avg += maximb;
00245       rprintf(&ctrl, "%.3f ", maximb);
00246     }
00247     rprintf(&ctrl, "  avg: %.3f\n", avg/(floattype)incon);
00248   }
00249 
00250   GKfree((void **)&itpwgts, LTERM);
00251   FreeGraph(mgraph);
00252   FreeInitialGraphAndRemap(graph, iwgtflag);
00253   FreeWSpace(&wspace);
00254   FreeCtrl(&ctrl);
00255 
00256   if (inumflag == 1)
00257     ChangeNumbering(vtxdist, xadj, adjncy, part, npes, mype, 0);
00258 
00259 }
00260 
00261 
00262 
00263 /***********************************************************************************
00264 * This function is the entry point of the parallel ordering algorithm.
00265 * This function assumes that the graph is already nice partitioned among the
00266 * processors and then proceeds to perform recursive bisection.
00267 ************************************************************************************/
00268 void ParMETIS_V3_PartGeom(idxtype *vtxdist, int *ndims, floattype *xyz, idxtype *part, MPI_Comm *comm)
00269 {
00270   int i, npes, mype, nvtxs, firstvtx, dbglvl;
00271   idxtype *xadj, *adjncy;
00272   CtrlType ctrl;
00273   WorkSpaceType wspace;
00274   GraphType *graph;
00275   int zeroflg = 0;
00276 
00277   MPI_Comm_size(*comm, &npes);
00278   MPI_Comm_rank(*comm, &mype);
00279 
00280   if (npes == 1) {
00281     idxset(vtxdist[mype+1]-vtxdist[mype], 0, part);
00282     return;
00283   }
00284 
00285   /* Setup a fake graph to allow the rest of the code to work unchanged */
00286   dbglvl = 0;
00287 
00288   nvtxs = vtxdist[mype+1]-vtxdist[mype];
00289   firstvtx = vtxdist[mype];
00290   xadj = idxmalloc(nvtxs+1, "ParMETIS_PartGeom: xadj");
00291   adjncy = idxmalloc(nvtxs, "ParMETIS_PartGeom: adjncy");
00292   for (i=0; i<nvtxs; i++) {
00293     xadj[i] = i;
00294     adjncy[i] = firstvtx + (i+1)%nvtxs;
00295   }
00296   xadj[nvtxs] = nvtxs;
00297 
00298   /* Proceed with the rest of the code */
00299   SetUpCtrl(&ctrl, npes, dbglvl, *comm);
00300   ctrl.seed      = mype;
00301   ctrl.CoarsenTo = amin(vtxdist[npes]+1, 25*npes);
00302 
00303   graph = Moc_SetUpGraph(&ctrl, 1, vtxdist, xadj, NULL, adjncy, NULL, &zeroflg);
00304 
00305   PreAllocateMemory(&ctrl, graph, &wspace);
00306 
00307   /*=======================================================
00308    * Compute the initial geometric partitioning
00309    =======================================================*/
00310   IFSET(ctrl.dbglvl, DBG_TIME, InitTimers(&ctrl));
00311   IFSET(ctrl.dbglvl, DBG_TIME, MPI_Barrier(ctrl.gcomm));
00312   IFSET(ctrl.dbglvl, DBG_TIME, starttimer(ctrl.TotalTmr));
00313 
00314   Coordinate_Partition(&ctrl, graph, *ndims, xyz, 0, &wspace);
00315 
00316   idxcopy(graph->nvtxs, graph->where, part);
00317 
00318   IFSET(ctrl.dbglvl, DBG_TIME, MPI_Barrier(ctrl.gcomm));
00319   IFSET(ctrl.dbglvl, DBG_TIME, stoptimer(ctrl.TotalTmr));
00320   IFSET(ctrl.dbglvl, DBG_TIME, PrintTimingInfo(&ctrl));
00321 
00322   FreeInitialGraphAndRemap(graph, 0);
00323   FreeWSpace(&wspace);
00324   FreeCtrl(&ctrl);
00325 
00326   GKfree((void **)&xadj, (void **)&adjncy, LTERM);
00327 }
00328 
00329 
00330 
00331
libs/ck-libs/parmetis/ParMETISLib/gkmetis.c
