src/ck-ldb/TeamLB.C

   1 /** \file TeamLB.C
   2  *  Written by Esteban Meneses, 2010-11-24
   3  *  Updated by Abhinav Bhatele, 2010-12-09 to use ckgraph
   4  */
   5
   6 /**
   7  * \addtogroup CkLdb
   8 */
   9 /*@{*/
  10
  11 #include "TeamLB.h"
  12 #include "ckgraph.h"
  13 #include "metis.h"
  14
  15 CreateLBFunc_Def(TeamLB, "Use Metis(tm) to partition object graph at two levels: team level and processor level")
  16
  17 TeamLB::TeamLB(const CkLBOptions &opt): CentralLB(opt)
  18 {
  19   lbname = "TeamLB";
  20   if (CkMyPe() == 0)
  21     CkPrintf("[%d] TeamLB created\n",CkMyPe());
  22
  23   // setting number of teams and team size
  24   teamSize = _lb_args.teamSize();
  25   numberTeams = CkNumPes() / teamSize;
  26 }
  27
  28 /**
  29  * @brief METIS function that performs a balanced k-way partitioning of the
  30  * graph, considering the communication volume (hence the "V" in the name of
  31  * the function).
  32
  33    extern "C" void METIS_PartGraphRecursive(int*, int*, int*, int*, int*, int*,
  34                               int*, int*, int*, int*, int*);
  35  */
  36
  37
  38 /**
  39  * @brief Load balancing function. It uses METIS in a two step approach. The
  40  * first step consists in splitting the objects into teams. METIS is able to
  41  * minimize the communication volume across the teams while balancing the load
  42  * among the different teams. The second step goes deep in each team to balance
  43  * the load in the processors belonging to that particular team.
  44  */
  45 void TeamLB::work(LDStats* stats)
  46 {
  47   /** ========================== INITIALIZATION ============================= */
  48   ProcArray *parr = new ProcArray(stats);
  49   ObjGraph *ogr = new ObjGraph(stats);
  50
  51   /** ============================= STRATEGY ================================ */
  52   if (_lb_args.debug() >= 2) {
  53     CkPrintf("[%d] In TeamLB Strategy...\n", CkMyPe());
  54   }
  55
  56   // convert ObjGraph to the adjacency structure
  57   int numVertices = ogr->vertices.size();       // number of vertices
  58   int numEdges = 0;                             // number of edges
  59
  60   double maxLoad = 0.0;
  61   int maxBytes = 0, i, j, k;
  62
  63   /** both object load and number of bytes exchanged are normalized to an
  64    *  integer between 0 and 256 */
  65   for(i = 0; i < numVertices; i++) {
  66     if(ogr->vertices[i].getVertexLoad() > maxLoad)
  67       maxLoad = ogr->vertices[i].getVertexLoad();
  68     numEdges += ogr->vertices[i].sendToList.size();
  69     for(j = 0; j < ogr->vertices[i].sendToList.size(); j++) {
  70       if(ogr->vertices[i].sendToList[j].getNumBytes() > maxBytes)
  71         maxBytes = ogr->vertices[i].sendToList[j].getNumBytes();
  72     }
  73   }
  74
  75   /* adjacency list */
  76   idx_t *xadj = new idx_t[numVertices + 1];
  77   /* id of the neighbors */
  78   idx_t *adjncy = new idx_t[numEdges];
  79   /* weights of the vertices */
  80   idx_t *vwgt = new idx_t[numVertices];
  81   /* weights of the edges */
  82   idx_t *adjwgt = new idx_t[numEdges];
  83
  84   int edgeNum = 0;
  85
  86   for(i = 0; i < numVertices; i++) {
  87     xadj[i] = edgeNum;
  88     vwgt[i] = (int)( (ogr->vertices[i].getVertexLoad() * 128) /maxLoad );
  89     for(j = 0; j < ogr->vertices[i].sendToList.size(); j++) {
  90       adjncy[edgeNum] = ogr->vertices[i].sendToList[j].getNeighborId();
  91       adjwgt[edgeNum] = (int)( (ogr->vertices[i].sendToList[j].getNumBytes() * 128) / maxBytes );
  92       edgeNum++;
  93     }
  94   }
  95   xadj[i] = edgeNum;
  96   CkAssert(edgeNum == numEdges);
  97
  98   idx_t options[METIS_NOPTIONS];
  99   METIS_SetDefaultOptions(options);
 100   //options[METIS_OPTION_PTYPE] = METIS_PTYPE_RB;
 101   // C style numbering
 102   options[METIS_OPTION_NUMBERING] = 0;
 103
 104   idx_t edgecut;          // number of edges cut by the partitioning
 105   // mapping of objs to partitions
 106   idx_t *pemap = new idx_t[numVertices];
 107
 108   // number of constrains
 109   idx_t ncon = 1;
 110   real_t ubvec[ncon];
 111   // allow 10% imbalance tolerance
 112   ubvec[0] = 1.1;
 113
 114   // Specifies size of vertices for computing the total communication volume
 115   idx_t *vsize = NULL;
 116   // This array of size nparts specifies the desired weight for each partition
 117   // and setting it to NULL indicates graph should be equally divided among
 118   // partitions
 119   real_t *tpwgts = NULL;
 120
 121   if (_lb_args.debug() >= 1)
 122   CkPrintf("[%d] calling METIS_PartGraphRecursive.\n", CkMyPe());
 123
 124   METIS_PartGraphRecursive(&numVertices, &ncon, xadj, adjncy, vwgt, vsize,
 125       adjwgt, &numberTeams, tpwgts, ubvec, options, &edgecut, pemap);
 126
 127   int *global_pemap = new int[numVertices];
 128
 129   // partitioning each team
 130   if(teamSize > 1) {
 131     idx_t *team_xadj = new idx_t[numVertices + 1];
 132     idx_t *team_adjncy = new idx_t[numEdges];
 133     idx_t *team_vwgt = new idx_t[numVertices];
 134     idx_t *team_adjwgt = new idx_t[numEdges];
 135     idx_t *team_pemap = new idx_t[numVertices];
 136     idx_t *team_vsize = NULL;
 137     real_t *team_tpwgts = NULL;
 138
 139     int teamEdgecut, node;
 140     int *mapping = new int[numVertices];
 141     int *invMapping = new int[numVertices];
 142
 143     // traversing the list of teams and load balancing each one
 144     for(i=0; i<numberTeams; i++) {
 145       int teamMembers = 0;      // number of vertices in a team
 146
 147       // collecting all the elements of a particular team
 148       // mapping stores the association of local to global index
 149       // invMapping stores the inverse association
 150       for(j = 0; j < numVertices; j++) {
 151         if(pemap[j] == i) {
 152           mapping[teamMembers] = j;
 153           invMapping[j] = teamMembers;
 154           team_vwgt[teamMembers] = vwgt[j];
 155           teamMembers++;
 156         }
 157       }
 158
 159       // building up the adjacency data structures
 160       int teamIndex = 0;
 161       for(j = 0; j < teamMembers; j++) {
 162         team_xadj[j] = teamIndex;
 163         for(k = xadj[mapping[j]]; k < xadj[mapping[j]+1]; k++) {
 164           node = adjncy[k];
 165           if(pemap[node] == i) {
 166             team_adjncy[teamIndex] = invMapping[node];
 167             team_adjwgt[teamIndex] = adjwgt[k];
 168             teamIndex++;
 169           }
 170         }
 171       }
 172       team_xadj[teamMembers] = teamIndex;
 173
 174       // calling METIS library
 175       METIS_PartGraphRecursive(&teamMembers, &ncon, team_xadj, team_adjncy,
 176         team_vwgt, team_vsize, team_adjwgt, &teamSize, team_tpwgts, ubvec,
 177         options, &teamEdgecut, team_pemap);
 178
 179       // converting local mapping into global mapping
 180       for(j = 0; j < teamMembers; j++) {
 181         global_pemap[mapping[j]] = i*teamSize + team_pemap[j];
 182       }
 183
 184     } // end for
 185
 186     delete[] team_xadj;
 187     delete[] team_adjncy;
 188     delete[] team_vwgt;
 189     delete[] team_adjwgt;
 190     delete[] team_pemap;
 191     delete[] team_vsize;
 192     delete[] team_tpwgts;
 193
 194     delete[] mapping;
 195     delete[] invMapping;
 196   } else {
 197     delete[] global_pemap;
 198     global_pemap = pemap;
 199   }
 200
 201   delete[] xadj;
 202   delete[] adjncy;
 203   delete[] vwgt;
 204   delete[] adjwgt;
 205   delete[] vsize;
 206   delete[] tpwgts;
 207
 208
 209   if (_lb_args.debug() >= 1) {
 210    CkPrintf("[%d] TeamLB done! \n", CkMyPe());
 211   }
 212
 213   for(i = 0; i < numVertices; i++) {
 214     if(pemap[i] != ogr->vertices[i].getCurrentPe())
 215       ogr->vertices[i].setNewPe(pemap[i]);
 216   }
 217
 218   delete[] pemap;
 219
 220   /** ============================== CLEANUP ================================ */
 221   ogr->convertDecisions(stats);
 222 }
 223
 224 #include "TeamLB.def.h"
 225
 226 /*@}*/