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