eb57e86a47193e9d156ea5b800b450a9929e85f6
[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 i, j, k, vert;
62
63   /** remove duplicate edges from recvFrom */
64   for(i = 0; i < numVertices; i++) {
65     for(j = 0; j < ogr->vertices[i].sendToList.size(); j++) {
66       vert = ogr->vertices[i].sendToList[j].getNeighborId();
67       for(k = 0; k < ogr->vertices[i].recvFromList.size(); k++) {
68         if(ogr->vertices[i].recvFromList[k].getNeighborId() == vert) {
69           ogr->vertices[i].sendToList[j].setNumBytes(ogr->vertices[i].sendToList[j].getNumBytes() + ogr->vertices[i].recvFromList[k].getNumBytes());
70           ogr->vertices[i].recvFromList.erase(ogr->vertices[i].recvFromList.begin() + k);
71         }
72       }
73     }
74   }
75
76   /** the object load is normalized to an integer between 0 and 256 */
77   for(i = 0; i < numVertices; i++) {
78     if(ogr->vertices[i].getVertexLoad() > maxLoad)
79       maxLoad = ogr->vertices[i].getVertexLoad();
80     numEdges = numEdges + ogr->vertices[i].sendToList.size() + ogr->vertices[i].recvFromList.size();
81   }
82
83   /* adjacency list */
84   idxtype *xadj = new idxtype[numVertices + 1];
85   /* id of the neighbors */
86   idxtype *adjncy = new idxtype[numEdges];
87   /* weights of the vertices */
88   idxtype *vwgt = new idxtype[numVertices];
89   /* weights of the edges */
90   idxtype *adjwgt = new idxtype[numEdges];
91
92   int edgeNum = 0;
93   double ratio = 256.0/maxLoad;
94
95   for(i = 0; i < numVertices; i++) {
96     xadj[i] = edgeNum;
97     vwgt[i] = (int)ceil(ogr->vertices[i].getVertexLoad() * ratio);
98     for(j = 0; j < ogr->vertices[i].sendToList.size(); j++) {
99       adjncy[edgeNum] = ogr->vertices[i].sendToList[j].getNeighborId();
100       adjwgt[edgeNum] = ogr->vertices[i].sendToList[j].getNumBytes();
101       edgeNum++;
102     }
103     for(j = 0; j < ogr->vertices[i].recvFromList.size(); j++) {
104       adjncy[edgeNum] = ogr->vertices[i].recvFromList[j].getNeighborId();
105       adjwgt[edgeNum] = ogr->vertices[i].recvFromList[j].getNumBytes();
106       edgeNum++;
107     }
108   }
109   xadj[i] = edgeNum;
110   CkAssert(edgeNum == numEdges);
111
112   int wgtflag = 3;      // weights both on vertices and edges
113   int numflag = 0;      // C Style numbering
114   int options[5];
115   options[0] = 0;       // use default values
116   int edgecut;          // number of edges cut by the partitioning
117   idxtype *pemap;
118
119   int option = 0;
120   int numPes = parr->procs.size();
121   pemap = new idxtype[numVertices];
122
123   if (0 == option) {
124     /** I intended to follow the instruction in the Metis 4.0 manual
125      *  which said that METIS_PartGraphKway is preferable to
126      *  METIS_PartGraphRecursive, when nparts > 8. However, it turned out that
127      *  there is a bug in METIS_PartGraphKway, and the function seg faulted when
128      *  nparts = 4 or 9. So right now I just comment that function out and
129      *  always use the other one.
130      */
131
132     /* if (n_pes > 8)
133       METIS_PartGraphKway(&numobjs, xadj, adjncy, objwt, edgewt,
134                 &wgtflag, &numflag, &n_pes, options, &edgecut, newmap);
135     else
136       METIS_PartGraphRecursive(&numVertices, xadj, adjncy, vwgt, adjwgt,
137                 &wgtflag, &numflag, &numPes, options, &edgecut, pemap); */
138
139     METIS_PartGraphRecursive(&numVertices, xadj, adjncy, vwgt, adjwgt,
140                 &wgtflag, &numflag, &numPes, options, &edgecut, pemap);
141   } else if (WEIGHTED == option) {
142     // set up the different weights between 0 and 1
143     float *tpwgts = new float[numPes];
144     for (i = 0; i < numPes; i++) {
145       tpwgts[i] = 1.0/(float)numPes;
146     }
147
148     if (numPes > 8)
149       METIS_WPartGraphKway(&numVertices, xadj, adjncy, vwgt, adjwgt,
150               &wgtflag, &numflag, &numPes, tpwgts, options, &edgecut, pemap);
151     else
152       METIS_WPartGraphRecursive(&numVertices, xadj, adjncy, vwgt, adjwgt,
153               &wgtflag, &numflag, &numPes, tpwgts, options, &edgecut, pemap);
154     delete[] tpwgts;
155   } else if (MULTI_CONSTRAINT == option) {
156     CkPrintf("Metis load balance strategy: ");
157     CkPrintf("multiple constraints not implemented yet.\n");
158   }
159
160   delete[] xadj;
161   delete[] adjncy;
162   delete[] vwgt;
163   delete[] adjwgt;
164
165   if (_lb_args.debug() >= 1) {
166    CkPrintf("[%d] MetisLB done! \n", CkMyPe());
167   }
168
169   for(i = 0; i < numVertices; i++) {
170     if(pemap[i] != ogr->vertices[i].getCurrentPe())
171       ogr->vertices[i].setNewPe(pemap[i]);
172   }
173
174   delete[] pemap;
175
176   /** ============================== CLEANUP ================================ */
177   ogr->convertDecisions(stats);
178 }
179
180 #include "MetisLB.def.h"
181
182 /*@}*/