src/libs/ck-libs/metis/libmetis/kmetis.c

   1 /*!
   2 \file
   3 \brief The top-level routines for  multilevel k-way partitioning that minimizes
   4        the edge cut.
   5
   6 \date   Started 7/28/1997
   7 \author George
   8 \author Copyright 1997-2011, Regents of the University of Minnesota
   9 \version\verbatim $Id: kmetis.c 13905 2013-03-25 13:21:20Z karypis $ \endverbatim
  10 */
  11
  12 #include "metislib.h"
  13
  14
  15 /*************************************************************************/
  16 /*! This function is the entry point for MCKMETIS */
  17 /*************************************************************************/
  18 int METIS_PartGraphKway(idx_t *nvtxs, idx_t *ncon, idx_t *xadj, idx_t *adjncy,
  19           idx_t *vwgt, idx_t *vsize, idx_t *adjwgt, idx_t *nparts,
  20           real_t *tpwgts, real_t *ubvec, idx_t *options, idx_t *objval,
  21           idx_t *part)
  22 {
  23   int sigrval=0, renumber=0;
  24   graph_t *graph;
  25   ctrl_t *ctrl;
  26
  27   /* set up malloc cleaning code and signal catchers */
  28   if (!gk_malloc_init())
  29     return METIS_ERROR_MEMORY;
  30
  31   gk_sigtrap();
  32
  33   if ((sigrval = gk_sigcatch()) != 0)
  34     goto SIGTHROW;
  35
  36
  37   /* set up the run parameters */
  38   ctrl = SetupCtrl(METIS_OP_KMETIS, options, *ncon, *nparts, tpwgts, ubvec);
  39   if (!ctrl) {
  40     gk_siguntrap();
  41     return METIS_ERROR_INPUT;
  42   }
  43
  44   /* if required, change the numbering to 0 */
  45   if (ctrl->numflag == 1) {
  46     Change2CNumbering(*nvtxs, xadj, adjncy);
  47     renumber = 1;
  48   }
  49
  50   /* set up the graph */
  51   graph = SetupGraph(ctrl, *nvtxs, *ncon, xadj, adjncy, vwgt, vsize, adjwgt);
  52
  53   /* set up multipliers for making balance computations easier */
  54   SetupKWayBalMultipliers(ctrl, graph);
  55
  56   /* set various run parameters that depend on the graph */
  57   ctrl->CoarsenTo = gk_max((*nvtxs)/(20*gk_log2(*nparts)), 30*(*nparts));
  58   ctrl->nIparts   = (ctrl->CoarsenTo == 30*(*nparts) ? 4 : 5);
  59
  60   /* take care contiguity requests for disconnected graphs */
  61   if (ctrl->contig && !IsConnected(graph, 0))
  62     gk_errexit(SIGERR, "METIS Error: A contiguous partition is requested for a non-contiguous input graph.\n");
  63
  64   /* allocate workspace memory */
  65   AllocateWorkSpace(ctrl, graph);
  66
  67   /* start the partitioning */
  68   IFSET(ctrl->dbglvl, METIS_DBG_TIME, InitTimers(ctrl));
  69   IFSET(ctrl->dbglvl, METIS_DBG_TIME, gk_startcputimer(ctrl->TotalTmr));
  70
  71   *objval = MlevelKWayPartitioning(ctrl, graph, part);
  72
  73   IFSET(ctrl->dbglvl, METIS_DBG_TIME, gk_stopcputimer(ctrl->TotalTmr));
  74   IFSET(ctrl->dbglvl, METIS_DBG_TIME, PrintTimers(ctrl));
  75
  76   /* clean up */
  77   FreeCtrl(&ctrl);
  78
  79 SIGTHROW:
  80   /* if required, change the numbering back to 1 */
  81   if (renumber)
  82     Change2FNumbering(*nvtxs, xadj, adjncy, part);
  83
  84   gk_siguntrap();
  85   gk_malloc_cleanup(0);
  86
  87   return metis_rcode(sigrval);
  88 }
  89
  90
  91 /*************************************************************************/
  92 /*! This function computes a k-way partitioning of a graph that minimizes
  93     the specified objective function.
  94
  95     \param ctrl is the control structure
  96     \param graph is the graph to be partitioned
  97     \param part is the vector that on return will store the partitioning
  98
  99     \returns the objective value of the partitoning. The partitioning
 100              itself is stored in the part vector.
 101 */
 102 /*************************************************************************/
 103 idx_t MlevelKWayPartitioning(ctrl_t *ctrl, graph_t *graph, idx_t *part)
 104 {
 105   idx_t i, j, objval=0, curobj=0, bestobj=0;
 106   real_t curbal=0.0, bestbal=0.0;
 107   graph_t *cgraph;
 108   int status;
 109
 110
 111   for (i=0; i<ctrl->ncuts; i++) {
 112     cgraph = CoarsenGraph(ctrl, graph);
 113
 114     IFSET(ctrl->dbglvl, METIS_DBG_TIME, gk_startcputimer(ctrl->InitPartTmr));
 115     AllocateKWayPartitionMemory(ctrl, cgraph);
 116
 117     /* Release the work space */
 118     FreeWorkSpace(ctrl);
 119
 120     /* Compute the initial partitioning */
 121     InitKWayPartitioning(ctrl, cgraph);
 122
 123     /* Re-allocate the work space */
 124     AllocateWorkSpace(ctrl, graph);
 125     AllocateRefinementWorkSpace(ctrl, 2*cgraph->nedges);
 126
 127     IFSET(ctrl->dbglvl, METIS_DBG_TIME, gk_stopcputimer(ctrl->InitPartTmr));
 128     IFSET(ctrl->dbglvl, METIS_DBG_IPART,
 129         printf("Initial %"PRIDX"-way partitioning cut: %"PRIDX"\n", ctrl->nparts, objval));
 130
 131     RefineKWay(ctrl, graph, cgraph);
 132
 133     switch (ctrl->objtype) {
 134       case METIS_OBJTYPE_CUT:
 135         curobj = graph->mincut;
 136         break;
 137
 138       case METIS_OBJTYPE_VOL:
 139         curobj = graph->minvol;
 140         break;
 141
 142       default:
 143         gk_errexit(SIGERR, "Unknown objtype: %d\n", ctrl->objtype);
 144     }
 145
 146     curbal = ComputeLoadImbalanceDiff(graph, ctrl->nparts, ctrl->pijbm, ctrl->ubfactors);
 147
 148     if (i == 0
 149         || (curbal <= 0.0005 && bestobj > curobj)
 150         || (bestbal > 0.0005 && curbal < bestbal)) {
 151       icopy(graph->nvtxs, graph->where, part);
 152       bestobj = curobj;
 153       bestbal = curbal;
 154     }
 155
 156     FreeRData(graph);
 157
 158     if (bestobj == 0)
 159       break;
 160   }
 161
 162   FreeGraph(&graph);
 163
 164   return bestobj;
 165 }
 166
 167
 168 /*************************************************************************/
 169 /*! This function computes the initial k-way partitioning using PMETIS
 170 */
 171 /*************************************************************************/
 172 void InitKWayPartitioning(ctrl_t *ctrl, graph_t *graph)
 173 {
 174   idx_t i, ntrials, options[METIS_NOPTIONS], curobj=0, bestobj=0;
 175   idx_t *bestwhere=NULL;
 176   real_t *ubvec=NULL;
 177   int status;
 178
 179   METIS_SetDefaultOptions(options);
 180   options[METIS_OPTION_NITER]   = 10;
 181   options[METIS_OPTION_OBJTYPE] = METIS_OBJTYPE_CUT;
 182   options[METIS_OPTION_NO2HOP]  = ctrl->no2hop;
 183
 184
 185   ubvec = rmalloc(graph->ncon, "InitKWayPartitioning: ubvec");
 186   for (i=0; i<graph->ncon; i++)
 187     ubvec[i] = (real_t)pow(ctrl->ubfactors[i], 1.0/log(ctrl->nparts));
 188
 189
 190   switch (ctrl->objtype) {
 191     case METIS_OBJTYPE_CUT:
 192     case METIS_OBJTYPE_VOL:
 193       options[METIS_OPTION_NCUTS] = ctrl->nIparts;
 194       status = METIS_PartGraphRecursive(&graph->nvtxs, &graph->ncon,
 195                    graph->xadj, graph->adjncy, graph->vwgt, graph->vsize,
 196                    graph->adjwgt, &ctrl->nparts, ctrl->tpwgts, ubvec,
 197                    options, &curobj, graph->where);
 198
 199       if (status != METIS_OK)
 200         gk_errexit(SIGERR, "Failed during initial partitioning\n");
 201
 202       break;
 203
 204 #ifdef XXX /* This does not seem to help */
 205     case METIS_OBJTYPE_VOL:
 206       bestwhere = imalloc(graph->nvtxs, "InitKWayPartitioning: bestwhere");
 207       options[METIS_OPTION_NCUTS] = 2;
 208
 209       ntrials = (ctrl->nIparts+1)/2;
 210       for (i=0; i<ntrials; i++) {
 211         status = METIS_PartGraphRecursive(&graph->nvtxs, &graph->ncon,
 212                      graph->xadj, graph->adjncy, graph->vwgt, graph->vsize,
 213                      graph->adjwgt, &ctrl->nparts, ctrl->tpwgts, ubvec,
 214                      options, &curobj, graph->where);
 215         if (status != METIS_OK)
 216           gk_errexit(SIGERR, "Failed during initial partitioning\n");
 217
 218         curobj = ComputeVolume(graph, graph->where);
 219
 220         if (i == 0 || bestobj > curobj) {
 221           bestobj = curobj;
 222           if (i < ntrials-1)
 223             icopy(graph->nvtxs, graph->where, bestwhere);
 224         }
 225
 226         if (bestobj == 0)
 227           break;
 228       }
 229       if (bestobj != curobj)
 230         icopy(graph->nvtxs, bestwhere, graph->where);
 231
 232       break;
 233 #endif
 234
 235     default:
 236       gk_errexit(SIGERR, "Unknown objtype: %d\n", ctrl->objtype);
 237   }
 238
 239   gk_free((void **)&ubvec, &bestwhere, LTERM);
 240
 241 }
 242
 243