Issue #423: Modify MetisLB and TeamLB to use Metis v5.1 32/132/3
authorHarshitha <gplkrsh2@illinois.edu>
Sun, 9 Mar 2014 23:51:13 +0000 (18:51 -0500)
committerGerrit Code Review <gerrit2@charm.cs.uiuc.edu>
Mon, 10 Mar 2014 15:56:43 +0000 (10:56 -0500)
Change-Id: I2d46669ef7ec9a80cae6ccac4bbb5b3170475fc8

src/ck-ldb/MetisLB.C
src/ck-ldb/TeamLB.C

index 9c7b7338e23877dfd1b307f7d1ee979102f8d8e4..da45c04bd27d227740346de842452da24f2e033c 100644 (file)
 #include "ckgraph.h"
 #include "metis.h"
 
-/*extern "C" void METIS_PartGraphRecursive(int*, int*, int*, int*, int*,
-                             int*, int*, int*, int*, int*, int*);
-extern "C" void METIS_PartGraphKway(int*, int*, int*, int*, int*,
-                              int*, int*, int*, int*, int*, int*);
-extern "C" void METIS_PartGraphVKway(int*, int*, int*, int*, int*,
-                             int*, int*, int*, int*, int*, int*);
-
-// the following are to compute a partitioning with a given partition weights
-// "W" means giving weights
-extern "C" void METIS_WPartGraphRecursive(int*, int*, int*, int*, int*,
-                             int*, int*, int*, float*, int*, int*, int*);
-extern "C" void METIS_WPartGraphKway(int*, int*, int*, int*, int*,
-                             int*, int*, int*, float*, int*, int*, int*);
-
-// the following are for multiple constraint partition "mC"
-extern "C" void METIS_mCPartGraphRecursive(int*, int*, int*, int*, int*, int*,
-                             int*, int*, int*, int*, int*, int*);
-extern "C" void METIS_mCPartGraphKway(int*, int*, int*, int*, int*, int*,
-                              int*, int*, int*, int*, int*, int*, int*);
-*/
 
 CreateLBFunc_Def(MetisLB, "Use Metis(tm) to partition object graph")
 
@@ -81,13 +61,13 @@ void MetisLB::work(LDStats* stats)
   }
 
   /* adjacency list */
-  idxtype *xadj = new idxtype[numVertices + 1];
+  idx_t *xadj = new idx_t[numVertices + 1];
   /* id of the neighbors */
-  idxtype *adjncy = new idxtype[numEdges];
+  idx_t *adjncy = new idx_t[numEdges];
   /* weights of the vertices */
-  idxtype *vwgt = new idxtype[numVertices];
+  idx_t *vwgt = new idx_t[numVertices];
   /* weights of the edges */
-  idxtype *adjwgt = new idxtype[numEdges];
+  idx_t *adjwgt = new idx_t[numEdges];
 
   int edgeNum = 0;
   double ratio = 256.0/maxLoad;
@@ -109,58 +89,62 @@ void MetisLB::work(LDStats* stats)
   xadj[i] = edgeNum;
   CkAssert(edgeNum == numEdges);
 
-  int wgtflag = 3;     // weights both on vertices and edges
-  int numflag = 0;     // C Style numbering
-  int options[5];
-  options[0] = 0;      // use default values
-  int edgecut;         // number of edges cut by the partitioning
-  idxtype *pemap;
+  idx_t edgecut;               // number of edges cut by the partitioning
+  idx_t *pemap;
+
+  idx_t options[METIS_NOPTIONS];
+  METIS_SetDefaultOptions(options);
+  //options[METIS_OPTION_PTYPE] = METIS_PTYPE_RB;
+  // C style numbering
+  options[METIS_OPTION_NUMBERING] = 0;
+
+  // number of constrains
+  idx_t ncon = 1;
+  // number of partitions
+  idx_t numPes = parr->procs.size();
+  real_t ubvec[ncon];
+  // allow 10% imbalance
+  ubvec[0] = 1.1;
+
+  // mapping of objs to partitions
+  pemap = new idx_t[numVertices];
+
+  // Specifies size of vertices for computing the total communication volume
+  idx_t *vsize = NULL;
+  // This array of size nparts specifies the desired weight for each partition
+  // and setting it to NULL indicates graph should be equally divided among
+  // partitions
+  real_t *tpwgts = NULL;
 
   int option = 0;
-  int numPes = parr->procs.size();
-  pemap = new idxtype[numVertices];
-
-  if (0 == option) {
-    /** I intended to follow the instruction in the Metis 4.0 manual
-     *  which said that METIS_PartGraphKway is preferable to
-     *  METIS_PartGraphRecursive, when nparts > 8. However, it turned out that
-     *  there is a bug in METIS_PartGraphKway, and the function seg faulted when
-     *  nparts = 4 or 9. So right now I just comment that function out and
-     *  always use the other one.
-     */
-
-    /* if (n_pes > 8)
-      METIS_PartGraphKway(&numobjs, xadj, adjncy, objwt, edgewt,
-               &wgtflag, &numflag, &n_pes, options, &edgecut, newmap);
-    else
-      METIS_PartGraphRecursive(&numVertices, xadj, adjncy, vwgt, adjwgt,
-               &wgtflag, &numflag, &numPes, options, &edgecut, pemap); */
-
-    METIS_PartGraphRecursive(&numVertices, xadj, adjncy, vwgt, adjwgt,
-               &wgtflag, &numflag, &numPes, options, &edgecut, pemap);
-  } else if (WEIGHTED == option) {
+  if (WEIGHTED == option) {
     // set up the different weights between 0 and 1
-    float *tpwgts = new float[numPes];
+    tpwgts = new real_t[numPes];
     for (i = 0; i < numPes; i++) {
-      tpwgts[i] = 1.0/(float)numPes;
+      tpwgts[i] = 1.0/(real_t)numPes;
     }
-
-    if (numPes > 8)
-      METIS_WPartGraphKway(&numVertices, xadj, adjncy, vwgt, adjwgt,
-             &wgtflag, &numflag, &numPes, tpwgts, options, &edgecut, pemap);
-    else
-      METIS_WPartGraphRecursive(&numVertices, xadj, adjncy, vwgt, adjwgt,
-             &wgtflag, &numflag, &numPes, tpwgts, options, &edgecut, pemap);
-    delete[] tpwgts;
   } else if (MULTI_CONSTRAINT == option) {
-    CkPrintf("Metis load balance strategy: ");
-    CkPrintf("multiple constraints not implemented yet.\n");
+    CkAbort("Multiple constraints not implemented.\n");
   }
 
+  // numVertices: num vertices in the graph; ncon: num balancing constrains
+  // xadj, adjncy: of size n+1 and adjncy of 2m, adjncy[xadj[i]] through and
+  // including adjncy[xadj[i+1]-1];
+  // vwgt: weight of the vertices; vsize: amt of data that needs to be sent
+  // for ith vertex is vsize[i]
+  // adjwght: the weight of edges; numPes: total parts
+  // tpwghts: target partition weight, can pass NULL to equally divide
+  // ubvec: of size ncon to indicate allowed load imbalance tolerance (> 1.0)
+  // options: array of options; edgecut: stores the edgecut; pemap: mapping
+  METIS_PartGraphRecursive(&numVertices, &ncon,  xadj, adjncy, vwgt, vsize, adjwgt,
+      &numPes, tpwgts, ubvec, options, &edgecut, pemap);
+
   delete[] xadj;
   delete[] adjncy;
   delete[] vwgt;
   delete[] adjwgt;
+  delete[] vsize;
+  delete[] tpwgts;
 
   if (_lb_args.debug() >= 1) {
    CkPrintf("[%d] MetisLB done! \n", CkMyPe());
index 6d0613645c1df396e8c4b382cffa2d34da60632b..894583f54241de256702e5a77169dfa337e744b6 100644 (file)
@@ -73,13 +73,13 @@ void TeamLB::work(LDStats* stats)
   }
 
   /* adjacency list */
-  idxtype *xadj = new idxtype[numVertices + 1];
+  idx_t *xadj = new idx_t[numVertices + 1];
   /* id of the neighbors */
-  idxtype *adjncy = new idxtype[numEdges];
+  idx_t *adjncy = new idx_t[numEdges];
   /* weights of the vertices */
-  idxtype *vwgt = new idxtype[numVertices];
+  idx_t *vwgt = new idx_t[numVertices];
   /* weights of the edges */
-  idxtype *adjwgt = new idxtype[numEdges];
+  idx_t *adjwgt = new idx_t[numEdges];
 
   int edgeNum = 0;
 
@@ -95,28 +95,46 @@ void TeamLB::work(LDStats* stats)
   xadj[i] = edgeNum;
   CkAssert(edgeNum == numEdges);
 
-  int wgtflag = 3;      // weights both on vertices and edges
-  int numflag = 0;      // C Style numbering
-  int options[5];
-  options[0] = 0;       // use default values
-  int edgecut;          // number of edges cut by the partitioning
-  idxtype *pemap = new idxtype[numVertices];
+  idx_t options[METIS_NOPTIONS];
+  METIS_SetDefaultOptions(options);
+  //options[METIS_OPTION_PTYPE] = METIS_PTYPE_RB;
+  // C style numbering
+  options[METIS_OPTION_NUMBERING] = 0;
+
+  idx_t edgecut;          // number of edges cut by the partitioning
+  // mapping of objs to partitions
+  idx_t *pemap = new idx_t[numVertices];
+
+  // number of constrains
+  idx_t ncon = 1;
+  real_t ubvec[ncon];
+  // allow 10% imbalance tolerance
+  ubvec[0] = 1.1;
+
+  // Specifies size of vertices for computing the total communication volume
+  idx_t *vsize = NULL;
+  // This array of size nparts specifies the desired weight for each partition
+  // and setting it to NULL indicates graph should be equally divided among
+  // partitions
+  real_t *tpwgts = NULL;
 
   if (_lb_args.debug() >= 1)
   CkPrintf("[%d] calling METIS_PartGraphRecursive.\n", CkMyPe());
 
-  METIS_PartGraphRecursive(&numVertices, xadj, adjncy, vwgt, adjwgt,
-           &wgtflag, &numflag, &numberTeams, options, &edgecut, pemap);
+  METIS_PartGraphRecursive(&numVertices, &ncon, xadj, adjncy, vwgt, vsize,
+      adjwgt, &numberTeams, tpwgts, ubvec, options, &edgecut, pemap);
 
   int *global_pemap = new int[numVertices];
 
   // partitioning each team
   if(teamSize > 1) {
-    idxtype *team_xadj = new idxtype[numVertices + 1];
-    idxtype *team_adjncy = new idxtype[numEdges];
-    idxtype *team_vwgt = new idxtype[numVertices];
-    idxtype *team_adjwgt = new idxtype[numEdges];
-    idxtype *team_pemap = new idxtype[numVertices];
+    idx_t *team_xadj = new idx_t[numVertices + 1];
+    idx_t *team_adjncy = new idx_t[numEdges];
+    idx_t *team_vwgt = new idx_t[numVertices];
+    idx_t *team_adjwgt = new idx_t[numEdges];
+    idx_t *team_pemap = new idx_t[numVertices];
+    idx_t *team_vsize = NULL;
+    real_t *team_tpwgts = NULL;
 
     int teamEdgecut, node;
     int *mapping = new int[numVertices];
@@ -154,9 +172,9 @@ void TeamLB::work(LDStats* stats)
       team_xadj[teamMembers] = teamIndex;
 
       // calling METIS library
-      METIS_PartGraphRecursive(&teamMembers, team_xadj, team_adjncy, team_vwgt,
-                 team_adjwgt, &wgtflag, &numflag, &teamSize, options,
-                 &teamEdgecut, team_pemap);
+      METIS_PartGraphRecursive(&teamMembers, &ncon, team_xadj, team_adjncy,
+        team_vwgt, team_vsize, team_adjwgt, &teamSize, team_tpwgts, ubvec,
+        options, &teamEdgecut, team_pemap);
 
       // converting local mapping into global mapping
       for(j = 0; j < teamMembers; j++) {
@@ -170,6 +188,8 @@ void TeamLB::work(LDStats* stats)
     delete[] team_vwgt;
     delete[] team_adjwgt;
     delete[] team_pemap;
+    delete[] team_vsize;
+    delete[] team_tpwgts;
 
     delete[] mapping;
     delete[] invMapping;
@@ -182,6 +202,9 @@ void TeamLB::work(LDStats* stats)
   delete[] adjncy;
   delete[] vwgt;
   delete[] adjwgt;
+  delete[] vsize;
+  delete[] tpwgts;
+
 
   if (_lb_args.debug() >= 1) {
    CkPrintf("[%d] TeamLB done! \n", CkMyPe());