src/ck-ldb/MetisLB.C

   1 /** \file MetisLB.C
   2  *
   3  *  Updated by Abhinav Bhatele, 2010-11-26 to use ckgraph
   4  */
   5
   6 /**
   7  * \addtogroup CkLdb
   8 */
   9 /*@{*/
  10
  11 #include "MetisLB.h"
  12 #include "ckgraph.h"
  13 #include <metis.h>
  14
  15
  16 CreateLBFunc_Def(MetisLB, "Use Metis(tm) to partition object graph")
  17
  18 MetisLB::MetisLB(const CkLBOptions &opt): CBase_MetisLB(opt)
  19 {
  20   lbname = "MetisLB";
  21   if (CkMyPe() == 0)
  22     CkPrintf("[%d] MetisLB created\n",CkMyPe());
  23 }
  24
  25 void MetisLB::work(LDStats* stats)
  26 {
  27   /** ========================== INITIALIZATION ============================= */
  28   ProcArray *parr = new ProcArray(stats);
  29   ObjGraph *ogr = new ObjGraph(stats);
  30
  31   /** ============================= STRATEGY ================================ */
  32   if (_lb_args.debug() >= 2) {
  33     CkPrintf("[%d] In MetisLB Strategy...\n", CkMyPe());
  34   }
  35
  36   // convert ObjGraph to the adjacency structure
  37   int numVertices = ogr->vertices.size();       // number of vertices
  38   int numEdges = 0;                             // number of edges
  39
  40   double maxLoad = 0.0;
  41   int i, j, k, vert;
  42
  43   /** remove duplicate edges from recvFrom */
  44   for(i = 0; i < numVertices; i++) {
  45     for(j = 0; j < ogr->vertices[i].sendToList.size(); j++) {
  46       vert = ogr->vertices[i].sendToList[j].getNeighborId();
  47       for(k = 0; k < ogr->vertices[i].recvFromList.size(); k++) {
  48         if(ogr->vertices[i].recvFromList[k].getNeighborId() == vert) {
  49           ogr->vertices[i].sendToList[j].setNumBytes(ogr->vertices[i].sendToList[j].getNumBytes() + ogr->vertices[i].recvFromList[k].getNumBytes());
  50           ogr->vertices[i].recvFromList.erase(ogr->vertices[i].recvFromList.begin() + k);
  51         }
  52       }
  53     }
  54   }
  55
  56   /** the object load is normalized to an integer between 0 and 256 */
  57   for(i = 0; i < numVertices; i++) {
  58     if(ogr->vertices[i].getVertexLoad() > maxLoad)
  59       maxLoad = ogr->vertices[i].getVertexLoad();
  60     numEdges = numEdges + ogr->vertices[i].sendToList.size() + ogr->vertices[i].recvFromList.size();
  61   }
  62
  63   /* adjacency list */
  64   idx_t *xadj = new idx_t[numVertices + 1];
  65   /* id of the neighbors */
  66   idx_t *adjncy = new idx_t[numEdges];
  67   /* weights of the vertices */
  68   idx_t *vwgt = new idx_t[numVertices];
  69   /* weights of the edges */
  70   idx_t *adjwgt = new idx_t[numEdges];
  71
  72   int edgeNum = 0;
  73   double ratio = 256.0/maxLoad;
  74
  75   for(i = 0; i < numVertices; i++) {
  76     xadj[i] = edgeNum;
  77     vwgt[i] = (int)ceil(ogr->vertices[i].getVertexLoad() * ratio);
  78     for(j = 0; j < ogr->vertices[i].sendToList.size(); j++) {
  79       adjncy[edgeNum] = ogr->vertices[i].sendToList[j].getNeighborId();
  80       adjwgt[edgeNum] = ogr->vertices[i].sendToList[j].getNumBytes();
  81       edgeNum++;
  82     }
  83     for(j = 0; j < ogr->vertices[i].recvFromList.size(); j++) {
  84       adjncy[edgeNum] = ogr->vertices[i].recvFromList[j].getNeighborId();
  85       adjwgt[edgeNum] = ogr->vertices[i].recvFromList[j].getNumBytes();
  86       edgeNum++;
  87     }
  88   }
  89   xadj[i] = edgeNum;
  90   CkAssert(edgeNum == numEdges);
  91
  92   idx_t edgecut;                // number of edges cut by the partitioning
  93   idx_t *pemap;
  94
  95   idx_t options[METIS_NOPTIONS];
  96   METIS_SetDefaultOptions(options);
  97   //options[METIS_OPTION_PTYPE] = METIS_PTYPE_RB;
  98   // C style numbering
  99   options[METIS_OPTION_NUMBERING] = 0;
 100
 101   // number of constrains
 102   idx_t ncon = 1;
 103   // number of partitions
 104   idx_t numPes = parr->procs.size();
 105   real_t ubvec[ncon];
 106   // allow 10% imbalance
 107   ubvec[0] = 1.1;
 108
 109   // mapping of objs to partitions
 110   pemap = new idx_t[numVertices];
 111
 112   // Specifies size of vertices for computing the total communication volume
 113   idx_t *vsize = NULL;
 114   // This array of size nparts specifies the desired weight for each partition
 115   // and setting it to NULL indicates graph should be equally divided among
 116   // partitions
 117   real_t *tpwgts = NULL;
 118
 119   int option = 0;
 120   if (WEIGHTED == option) {
 121     // set up the different weights between 0 and 1
 122     tpwgts = new real_t[numPes];
 123     for (i = 0; i < numPes; i++) {
 124       tpwgts[i] = 1.0/(real_t)numPes;
 125     }
 126   } else if (MULTI_CONSTRAINT == option) {
 127     CkAbort("Multiple constraints not implemented.\n");
 128   }
 129
 130   // numVertices: num vertices in the graph; ncon: num balancing constrains
 131   // xadj, adjncy: of size n+1 and adjncy of 2m, adjncy[xadj[i]] through and
 132   // including adjncy[xadj[i+1]-1];
 133   // vwgt: weight of the vertices; vsize: amt of data that needs to be sent
 134   // for ith vertex is vsize[i]
 135   // adjwght: the weight of edges; numPes: total parts
 136   // tpwghts: target partition weight, can pass NULL to equally divide
 137   // ubvec: of size ncon to indicate allowed load imbalance tolerance (> 1.0)
 138   // options: array of options; edgecut: stores the edgecut; pemap: mapping
 139   METIS_PartGraphRecursive(&numVertices, &ncon,  xadj, adjncy, vwgt, vsize, adjwgt,
 140       &numPes, tpwgts, ubvec, options, &edgecut, pemap);
 141
 142   delete[] xadj;
 143   delete[] adjncy;
 144   delete[] vwgt;
 145   delete[] adjwgt;
 146   delete[] vsize;
 147   delete[] tpwgts;
 148
 149   if (_lb_args.debug() >= 1) {
 150    CkPrintf("[%d] MetisLB done! \n", CkMyPe());
 151   }
 152
 153   for(i = 0; i < numVertices; i++) {
 154     if(pemap[i] != ogr->vertices[i].getCurrentPe())
 155       ogr->vertices[i].setNewPe(pemap[i]);
 156   }
 157
 158   delete[] pemap;
 159
 160   /** ============================== CLEANUP ================================ */
 161   ogr->convertDecisions(stats);
 162   delete parr;
 163   delete ogr;
 164 }
 165
 166 #include "MetisLB.def.h"
 167
 168 /*@}*/