MetisLB: transformed to use ckgraph: the new ObjGraph
[charm.git] / 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 /*extern "C" void METIS_PartGraphRecursive(int*, int*, int*, int*, int*,
16                               int*, int*, int*, int*, int*, int*);
17 extern "C" void METIS_PartGraphKway(int*, int*, int*, int*, int*,
18                               int*, int*, int*, int*, int*, int*);
19 extern "C" void METIS_PartGraphVKway(int*, int*, int*, int*, int*,
20                               int*, int*, int*, int*, int*, int*);
21
22 // the following are to compute a partitioning with a given partition weights
23 // "W" means giving weights
24 extern "C" void METIS_WPartGraphRecursive(int*, int*, int*, int*, int*,
25                               int*, int*, int*, float*, int*, int*, int*);
26 extern "C" void METIS_WPartGraphKway(int*, int*, int*, int*, int*,
27                               int*, int*, int*, float*, int*, int*, int*);
28
29 // the following are for multiple constraint partition "mC"
30 extern "C" void METIS_mCPartGraphRecursive(int*, int*, int*, int*, int*, int*,
31                               int*, int*, int*, int*, int*, int*);
32 extern "C" void METIS_mCPartGraphKway(int*, int*, int*, int*, int*, int*,
33                               int*, int*, int*, int*, int*, int*, int*);
34 */
35
36 CreateLBFunc_Def(MetisLB, "Use Metis(tm) to partition object graph")
37
38 MetisLB::MetisLB(const CkLBOptions &opt): CentralLB(opt)
39 {
40   lbname = "MetisLB";
41   if (CkMyPe() == 0)
42     CkPrintf("[%d] MetisLB created\n",CkMyPe());
43 }
44
45 void MetisLB::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 MetisLB 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;
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].getObjLoad() > maxLoad)
67       maxLoad = ogr->vertices[i].getObjLoad();
68     numEdges += ogr->vertices[i].edgeList.size();
69     for(j = 0; j < ogr->vertices[i].edgeList.size(); j++) {
70       if(ogr->vertices[i].edgeList[j].getNumBytes() > maxBytes)
71         maxBytes = ogr->vertices[i].edgeList[j].getNumBytes();
72     }
73   }
74
75   /* adjacency list */
76   idxtype *xadj = new idxtype[numVertices + 1];
77   /* id of the neighbors */
78   idxtype *adjncy = new idxtype[numEdges];
79   /* weights of the vertices */
80   idxtype *vwgt = new idxtype[numVertices];
81   /* weights of the edges */
82   idxtype *adjwgt = new idxtype[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].getObjLoad() * 128) /maxLoad );
89     for(j = 0; j < ogr->vertices[i].edgeList.size(); j++) {
90       adjncy[edgeNum] = ogr->vertices[i].edgeList[j].getNeighborId();
91       adjwgt[edgeNum] = (int)( (ogr->vertices[i].edgeList[j].getNumBytes() * 128) / maxBytes );
92       edgeNum++;
93     }
94   }
95   xadj[i] = edgeNum;
96   CkAssert(edgeNum == numEdges);
97
98   int wgtflag = 3;      // weights both on vertices and edges
99   int numflag = 0;      // C Style numbering
100   int options[5];
101   options[0] = 0;       // use default values
102   int edgecut;          // number of edges cut by the partitioning
103   idxtype *pemap;
104
105   int option = 0;
106   int numPes = parr->procs.size();
107   pemap = new idxtype[numVertices];
108
109   if (0 == option) {
110     /** I intended to follow the instruction in the Metis 4.0 manual
111      *  which said that METIS_PartGraphKway is preferable to
112      *  METIS_PartGraphRecursive, when nparts > 8. However, it turned out that
113      *  there is a bug in METIS_PartGraphKway, and the function seg faulted when
114      *  nparts = 4 or 9. So right now I just comment that function out and
115      *  always use the other one.
116      */
117
118     /* if (n_pes > 8)
119       METIS_PartGraphKway(&numobjs, xadj, adjncy, objwt, edgewt,
120                 &wgtflag, &numflag, &n_pes, options, &edgecut, newmap);
121     else
122       METIS_PartGraphRecursive(&numVertices, xadj, adjncy, vwgt, adjwgt,
123                 &wgtflag, &numflag, &numPes, options, &edgecut, pemap); */
124
125     METIS_PartGraphRecursive(&numVertices, xadj, adjncy, vwgt, adjwgt,
126                 &wgtflag, &numflag, &numPes, options, &edgecut, pemap);
127   } else if (WEIGHTED == option) {
128     // set up the different weights between 0 and 1
129     float *tpwgts = new float[numPes];
130     for (i = 0; i < numPes; i++) {
131       tpwgts[i] = 1.0/(float)numPes;
132     }
133
134     if (numPes > 8)
135       METIS_WPartGraphKway(&numVertices, xadj, adjncy, vwgt, adjwgt,
136               &wgtflag, &numflag, &numPes, tpwgts, options, &edgecut, pemap);
137     else
138       METIS_WPartGraphRecursive(&numVertices, xadj, adjncy, vwgt, adjwgt,
139               &wgtflag, &numflag, &numPes, tpwgts, options, &edgecut, pemap);
140     delete[] tpwgts;
141   } else if (MULTI_CONSTRAINT == option) {
142     CkPrintf("Metis load balance strategy: ");
143     CkPrintf("multiple constraints not implemented yet.\n");
144   }
145
146   delete[] xadj;
147   delete[] adjncy;
148   delete[] vwgt;
149   delete[] adjwgt;
150
151   if (_lb_args.debug() >= 1) {
152    CkPrintf("[%d] MetisLB done! \n", CkMyPe());
153   }
154
155   for(i = 0; i < numVertices; i++) {
156     if(pemap[i] != ogr->vertices[i].getCurrentPe())
157       ogr->vertices[i].setNewPe(pemap[i]);
158   }
159
160   delete[] pemap;
161
162   /** ============================== CLEANUP ================================ */
163   ogr->convertDecisions(stats);
164 }
165
166 #include "MetisLB.def.h"
167
168 /*@}*/