Charm++: Charm Source Code Documentation

00001 /*
00002  * Copyright 1997, Regents of the University of Minnesota
00003  *
00004  * mdrivers.c
00005  *
00006  * This file contains the driving routines for the various parallel
00007  * multilevel partitioning and repartitioning algorithms
00008  *
00009  * Started 11/19/96
00010  * George
00011  *
00012  * $Id$
00013  *
00014  */
00015 
00016 #include <parmetislib.h>
00017 
00018 
00019 
00020 /*************************************************************************
00021 * This function is the driver to the multi-constraint partitioning algorithm.
00022 **************************************************************************/
00023 void Moc_Global_Partition(CtrlType *ctrl, GraphType *graph, WorkSpaceType *wspace)
00024 {
00025   int i, ncon, nparts;
00026   floattype ftmp, ubavg, lbavg, lbvec[MAXNCON];
00027  
00028   ncon = graph->ncon;
00029   nparts = ctrl->nparts;
00030   ubavg = savg(graph->ncon, ctrl->ubvec);
00031 
00032   SetUp(ctrl, graph, wspace);
00033 
00034   if (ctrl->dbglvl&DBG_PROGRESS) {
00035     rprintf(ctrl, "[%6d %8d %5d %5d] [%d] [", graph->gnvtxs, GlobalSESum(ctrl, graph->nedges),
00036             GlobalSEMin(ctrl, graph->nvtxs), GlobalSEMax(ctrl, graph->nvtxs), ctrl->CoarsenTo);
00037     for (i=0; i<ncon; i++)
00038       rprintf(ctrl, " %.3f", GlobalSEMinFloat(ctrl,graph->nvwgt[samin_strd(graph->nvtxs, graph->nvwgt+i, ncon)*ncon+i]));  
00039     rprintf(ctrl, "] [");
00040     for (i=0; i<ncon; i++)
00041       rprintf(ctrl, " %.3f", GlobalSEMaxFloat(ctrl, graph->nvwgt[samax_strd(graph->nvtxs, graph->nvwgt+i, ncon)*ncon+i]));  
00042     rprintf(ctrl, "]\n");
00043   }
00044 
00045   if (graph->gnvtxs < 1.3*ctrl->CoarsenTo ||
00046         (graph->finer != NULL &&
00047         graph->gnvtxs > graph->finer->gnvtxs*COARSEN_FRACTION)) {
00048 
00049     /* Done with coarsening. Find a partition */
00050     graph->where = idxmalloc(graph->nvtxs+graph->nrecv, "graph->where");
00051     Moc_InitPartition_RB(ctrl, graph, wspace);
00052 
00053     if (ctrl->dbglvl&DBG_PROGRESS) {
00054       Moc_ComputeParallelBalance(ctrl, graph, graph->where, lbvec);
00055       rprintf(ctrl, "nvtxs: %10d, balance: ", graph->gnvtxs);
00056       for (i=0; i<graph->ncon; i++) 
00057         rprintf(ctrl, "%.3f ", lbvec[i]);
00058       rprintf(ctrl, "\n");
00059     }
00060 
00061     /* In case no coarsening took place */
00062     if (graph->finer == NULL) {
00063       Moc_ComputePartitionParams(ctrl, graph, wspace);
00064       Moc_KWayFM(ctrl, graph, wspace, NGR_PASSES);
00065     }
00066   }
00067   else {
00068     Moc_GlobalMatch_Balance(ctrl, graph, wspace);
00069 
00070     Moc_Global_Partition(ctrl, graph->coarser, wspace);
00071 
00072     Moc_ProjectPartition(ctrl, graph, wspace);
00073     Moc_ComputePartitionParams(ctrl, graph, wspace);
00074 
00075     if (graph->ncon > 1 && graph->level < 3) {
00076       for (i=0; i<ncon; i++) {
00077         ftmp = ssum_strd(nparts, graph->gnpwgts+i, ncon);
00078         if (ftmp != 0.0)
00079           lbvec[i] = (floattype)(nparts) *
00080           graph->gnpwgts[samax_strd(nparts, graph->gnpwgts+i, ncon)*ncon+i]/ftmp;
00081         else
00082           lbvec[i] = 1.0;
00083       }
00084       lbavg = savg(graph->ncon, lbvec);
00085 
00086       if (lbavg > ubavg + 0.035) {
00087         if (ctrl->dbglvl&DBG_PROGRESS) {
00088           Moc_ComputeParallelBalance(ctrl, graph, graph->where, lbvec);
00089           rprintf(ctrl, "nvtxs: %10d, cut: %8d, balance: ", graph->gnvtxs, graph->mincut);
00090           for (i=0; i<graph->ncon; i++) 
00091             rprintf(ctrl, "%.3f ", lbvec[i]);
00092           rprintf(ctrl, "\n");
00093         }
00094 
00095         Moc_KWayBalance(ctrl, graph, wspace, graph->ncon);
00096       }
00097     }
00098 
00099     Moc_KWayFM(ctrl, graph, wspace, NGR_PASSES);
00100 
00101     if (ctrl->dbglvl&DBG_PROGRESS) {
00102       Moc_ComputeParallelBalance(ctrl, graph, graph->where, lbvec);
00103       rprintf(ctrl, "nvtxs: %10d, cut: %8d, balance: ", graph->gnvtxs, graph->mincut);
00104       for (i=0; i<graph->ncon; i++) 
00105         rprintf(ctrl, "%.3f ", lbvec[i]);
00106       rprintf(ctrl, "\n");
00107     }
00108 
00109     if (graph->level != 0)
00110       GKfree((void **)&graph->lnpwgts, (void **)&graph->gnpwgts, LTERM);
00111   }
00112 
00113   return;
00114 }
00115 
00116
libs/ck-libs/parmetis/ParMETISLib/mdrivers.c
