Charm++: Charm Source Code Documentation

00001 /*
00002  * Copyright 1997, Regents of the University of Minnesota
00003  *
00004  * adrivers.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 for the adaptive refinement mode of ParMETIS
00022 **************************************************************************/
00023 void Adaptive_Partition(CtrlType *ctrl, GraphType *graph, WorkSpaceType *wspace)
00024 {
00025   int i;
00026   int tewgt, tvsize;
00027   floattype gtewgt, gtvsize;
00028   floattype ubavg, lbavg, lbvec[MAXNCON];
00029 
00030   /************************************/
00031   /* Set up important data structures */
00032   /************************************/
00033   SetUp(ctrl, graph, wspace);
00034 
00035   ubavg   = savg(graph->ncon, ctrl->ubvec);
00036   tewgt   = idxsum(graph->nedges, graph->adjwgt);
00037   tvsize  = idxsum(graph->nvtxs, graph->vsize);
00038   gtewgt  = (floattype) GlobalSESum(ctrl, tewgt) + 1.0;  /* The +1 were added to remove any FPE */
00039   gtvsize = (floattype) GlobalSESum(ctrl, tvsize) + 1.0;
00040   ctrl->redist_factor = ctrl->redist_base * ((gtewgt/gtvsize)/ ctrl->edge_size_ratio);
00041 
00042   IFSET(ctrl->dbglvl, DBG_PROGRESS, rprintf(ctrl, "[%6d %8d %5d %5d][%d]\n", 
00043         graph->gnvtxs, GlobalSESum(ctrl, graph->nedges), GlobalSEMin(ctrl, graph->nvtxs), GlobalSEMax(ctrl, graph->nvtxs), ctrl->CoarsenTo));
00044 
00045   if (graph->gnvtxs < 1.3*ctrl->CoarsenTo ||
00046      (graph->finer != NULL && graph->gnvtxs > graph->finer->gnvtxs*COARSEN_FRACTION)) {
00047 
00048     /***********************************************/
00049     /* Balance the partition on the coarsest graph */
00050     /***********************************************/
00051     graph->where = idxsmalloc(graph->nvtxs+graph->nrecv, -1, "graph->where");
00052     idxcopy(graph->nvtxs, graph->home, graph->where);
00053 
00054     Moc_ComputeParallelBalance(ctrl, graph, graph->where, lbvec);
00055     lbavg = savg(graph->ncon, lbvec);
00056 
00057     if (lbavg > ubavg + 0.035 && ctrl->partType != REFINE_PARTITION)
00058       Balance_Partition(ctrl, graph, wspace);
00059 
00060     if (ctrl->dbglvl&DBG_PROGRESS) {
00061       Moc_ComputeParallelBalance(ctrl, graph, graph->where, lbvec);
00062       rprintf(ctrl, "nvtxs: %10d, balance: ", graph->gnvtxs);
00063       for (i=0; i<graph->ncon; i++) 
00064         rprintf(ctrl, "%.3f ", lbvec[i]);
00065       rprintf(ctrl, "\n");
00066     }
00067 
00068     /* check if no coarsening took place */
00069     if (graph->finer == NULL) {
00070       Moc_ComputePartitionParams(ctrl, graph, wspace);
00071       Moc_KWayBalance(ctrl, graph, wspace, graph->ncon);
00072       Moc_KWayAdaptiveRefine(ctrl, graph, wspace, NGR_PASSES);
00073     }
00074   }
00075   else {
00076     /*******************************/
00077     /* Coarsen it and partition it */
00078     /*******************************/
00079     switch (ctrl->ps_relation) {
00080       case COUPLED:
00081         Mc_LocalMatch_HEM(ctrl, graph, wspace);
00082         break;
00083       case DISCOUPLED:
00084       default:
00085         Moc_GlobalMatch_Balance(ctrl, graph, wspace);
00086         break;
00087     }
00088 
00089     Adaptive_Partition(ctrl, graph->coarser, wspace);
00090 
00091     /********************************/
00092     /* project partition and refine */
00093     /********************************/
00094     Moc_ProjectPartition(ctrl, graph, wspace);
00095     Moc_ComputePartitionParams(ctrl, graph, wspace);
00096 
00097     if (graph->ncon > 1 && graph->level < 4) {
00098       Moc_ComputeParallelBalance(ctrl, graph, graph->where, lbvec);
00099       lbavg = savg(graph->ncon, lbvec);
00100 
00101       if (lbavg > ubavg + 0.025) {
00102         Moc_KWayBalance(ctrl, graph, wspace, graph->ncon);
00103       }
00104     }
00105 
00106     Moc_KWayAdaptiveRefine(ctrl, graph, wspace, NGR_PASSES);
00107 
00108     if (ctrl->dbglvl&DBG_PROGRESS) {
00109       Moc_ComputeParallelBalance(ctrl, graph, graph->where, lbvec);
00110       rprintf(ctrl, "nvtxs: %10d, cut: %8d, balance: ", graph->gnvtxs, graph->mincut);
00111       for (i=0; i<graph->ncon; i++) 
00112         rprintf(ctrl, "%.3f ", lbvec[i]);
00113       rprintf(ctrl, "\n");
00114     }
00115   }
00116 }
00117
libs/ck-libs/parmetis/ParMETISLib/adrivers.c
