Merging
[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 typedef int idxtype;
16
17 extern "C" void METIS_PartGraphRecursive(int*, int*, int*, int*, int*,
18                               int*, int*, int*, int*, int*, int*);
19 extern "C" void METIS_PartGraphKway(int*, int*, int*, int*, int*,
20                               int*, int*, int*, int*, int*, int*);
21 extern "C" void METIS_PartGraphVKway(int*, int*, int*, int*, int*,
22                               int*, int*, int*, int*, int*, int*);
23
24 // the following are to compute a partitioning with a given partition weights
25 // "W" means giving weights
26 extern "C" void METIS_WPartGraphRecursive(int*, int*, int*, int*, int*,
27                               int*, int*, int*, float*, int*, int*, int*);
28 extern "C" void METIS_WPartGraphKway(int*, int*, int*, int*, int*,
29                               int*, int*, int*, float*, int*, int*, int*);
30
31 // the following are for multiple constraint partition "mC"
32 extern "C" void METIS_mCPartGraphRecursive(int*, int*, int*, int*, int*, int*,
33                               int*, int*, int*, int*, int*, int*);
34 extern "C" void METIS_mCPartGraphKway(int*, int*, int*, int*, int*, int*,
35                               int*, int*, int*, int*, int*, int*, int*);
36
37
38 CreateLBFunc_Def(MetisLB, "Use Metis(tm) to partition object graph")
39
40 MetisLB::MetisLB(const CkLBOptions &opt): CentralLB(opt)
41 {
42   lbname = "MetisLB";
43   if (CkMyPe() == 0)
44     CkPrintf("[%d] MetisLB created\n",CkMyPe());
45 }
46
47 void MetisLB::work(LDStats* stats)
48 {
49   /** ========================== INITIALIZATION ============================= */
50   ProcArray *parr = new ProcArray(stats);
51   ObjGraph *ogr = new ObjGraph(stats);
52
53   /** ============================= STRATEGY ================================ */
54   if (_lb_args.debug() >= 2) {
55     CkPrintf("[%d] In MetisLB Strategy...\n", CkMyPe());
56   }
57
58   // convert ObjGraph to the adjacency structure
59   int numVertices = ogr->vertices.size();       // number of vertices
60   int numEdges = 0;                             // number of edges
61
62   double maxLoad = 0.0;
63   int i, j, k, vert;
64
65   /** remove duplicate edges from recvFrom */
66   for(i = 0; i < numVertices; i++) {
67     for(j = 0; j < ogr->vertices[i].sendToList.size(); j++) {
68       vert = ogr->vertices[i].sendToList[j].getNeighborId();
69       for(k = 0; k < ogr->vertices[i].recvFromList.size(); k++) {
70         if(ogr->vertices[i].recvFromList[k].getNeighborId() == vert) {
71           ogr->vertices[i].sendToList[j].setNumBytes(ogr->vertices[i].sendToList[j].getNumBytes() + ogr->vertices[i].recvFromList[k].getNumBytes());
72           ogr->vertices[i].recvFromList.erase(ogr->vertices[i].recvFromList.begin() + k);
73         }
74       }
75     }
76   }
77
78   /** the object load is normalized to an integer between 0 and 256 */
79   for(i = 0; i < numVertices; i++) {
80     if(ogr->vertices[i].getVertexLoad() > maxLoad)
81       maxLoad = ogr->vertices[i].getVertexLoad();
82     numEdges = numEdges + ogr->vertices[i].sendToList.size() + ogr->vertices[i].recvFromList.size();
83   }
84
85   /* adjacency list */
86   idxtype *xadj = new idxtype[numVertices + 1];
87   /* id of the neighbors */
88   idxtype *adjncy = new idxtype[numEdges];
89   /* weights of the vertices */
90   idxtype *vwgt = new idxtype[numVertices];
91   /* weights of the edges */
92   idxtype *adjwgt = new idxtype[numEdges];
93
94   int edgeNum = 0;
95   double ratio = 256.0/maxLoad;
96
97   for(i = 0; i < numVertices; i++) {
98     xadj[i] = edgeNum;
99     vwgt[i] = (int)ceil(ogr->vertices[i].getVertexLoad() * ratio);
100     for(j = 0; j < ogr->vertices[i].sendToList.size(); j++) {
101       adjncy[edgeNum] = ogr->vertices[i].sendToList[j].getNeighborId();
102       adjwgt[edgeNum] = ogr->vertices[i].sendToList[j].getNumBytes();
103       edgeNum++;
104     }
105     for(j = 0; j < ogr->vertices[i].recvFromList.size(); j++) {
106       adjncy[edgeNum] = ogr->vertices[i].recvFromList[j].getNeighborId();
107       adjwgt[edgeNum] = ogr->vertices[i].recvFromList[j].getNumBytes();
108       edgeNum++;
109     }
110   }
111   xadj[i] = edgeNum;
112   CkAssert(edgeNum == numEdges);
113
114   int wgtflag = 3;      // weights both on vertices and edges
115   int numflag = 0;      // C Style numbering
116   int options[5];
117   options[0] = 0;       // use default values
118   int edgecut;          // number of edges cut by the partitioning
119   idxtype *pemap;
120
121   int option = 0;
122   int numPes = parr->procs.size();
123   pemap = new idxtype[numVertices];
124
125   if (0 == option) {
126     /** I intended to follow the instruction in the Metis 4.0 manual
127      *  which said that METIS_PartGraphKway is preferable to
128      *  METIS_PartGraphRecursive, when nparts > 8. However, it turned out that
129      *  there is a bug in METIS_PartGraphKway, and the function seg faulted when
130      *  nparts = 4 or 9. So right now I just comment that function out and
131      *  always use the other one.
132      */
133
134     /* if (n_pes > 8)
135       METIS_PartGraphKway(&numobjs, xadj, adjncy, objwt, edgewt,
136                 &wgtflag, &numflag, &n_pes, options, &edgecut, newmap);
137     else
138       METIS_PartGraphRecursive(&numVertices, xadj, adjncy, vwgt, adjwgt,
139                 &wgtflag, &numflag, &numPes, options, &edgecut, pemap); */
140
141     METIS_PartGraphRecursive(&numVertices, xadj, adjncy, vwgt, adjwgt,
142                 &wgtflag, &numflag, &numPes, options, &edgecut, pemap);
143   } else if (WEIGHTED == option) {
144     // set up the different weights between 0 and 1
145     float *tpwgts = new float[numPes];
146     for (i = 0; i < numPes; i++) {
147       tpwgts[i] = 1.0/(float)numPes;
148     }
149
150     if (numPes > 8)
151       METIS_WPartGraphKway(&numVertices, xadj, adjncy, vwgt, adjwgt,
152               &wgtflag, &numflag, &numPes, tpwgts, options, &edgecut, pemap);
153     else
154       METIS_WPartGraphRecursive(&numVertices, xadj, adjncy, vwgt, adjwgt,
155               &wgtflag, &numflag, &numPes, tpwgts, options, &edgecut, pemap);
156     delete[] tpwgts;
157   } else if (MULTI_CONSTRAINT == option) {
158     CkPrintf("Metis load balance strategy: ");
159     CkPrintf("multiple constraints not implemented yet.\n");
160   }
161
162   delete[] xadj;
163   delete[] adjncy;
164   delete[] vwgt;
165   delete[] adjwgt;
166
167   if (_lb_args.debug() >= 1) {
168    CkPrintf("[%d] MetisLB done! \n", CkMyPe());
169   }
170
171   for(i = 0; i < numVertices; i++) {
172     if(pemap[i] != ogr->vertices[i].getCurrentPe())
173       ogr->vertices[i].setNewPe(pemap[i]);
174   }
175   stats->is_prev_lb_refine = 3;
176   stats->after_lb_max = 0;
177   stats->after_lb_avg = 0;
178
179   delete[] pemap;
180
181   /** ============================== CLEANUP ================================ */
182   ogr->convertDecisions(stats);
183   delete parr;
184   delete ogr;
185 }
186
187 #include "MetisLB.def.h"
188
189 /*@}*/