Removed all STL template code from load balancer. Too bad STL doesn't work
[charm.git] / src / ck-ldb / MetisLB.C
1 #include <charm++.h>
2
3 #if CMK_LBDB_ON
4
5 #include "CkLists.h"
6
7 #include "MetisLB.h"
8 #include "MetisLB.def.h"
9
10 void CreateMetisLB()
11 {
12   // CkPrintf("[%d] creating MetisLB %d\n",CkMyPe(),loadbalancer);
13   loadbalancer = CProxy_MetisLB::ckNew();
14   // CkPrintf("[%d] created MetisLB %d\n",CkMyPe(),loadbalancer);
15 }
16
17 MetisLB::MetisLB()
18 {
19   // CkPrintf("[%d] MetisLB created\n",CkMyPe());
20 }
21
22 CmiBool MetisLB::QueryBalanceNow(int _step)
23 {
24   // CkPrintf("[%d] Balancing on step %d\n",CkMyPe(),_step);
25   return CmiTrue;
26 }
27
28 static void printStats(int count, int numobjs, double *cputimes, 
29                        int **comm, int *map)
30 {
31   int i, j;
32   double *petimes = new double[count];
33   for(i=0;i<count;i++) {
34     petimes[i] = 0.0;
35   }
36   for(i=0;i<numobjs;i++) {
37     petimes[map[i]] += cputimes[i];
38   }
39   double maxpe = petimes[0], minpe = petimes[0];
40   CkPrintf("\tPE\tTime\n");
41   for(i=0;i<count;i++) {
42     CkPrintf("\t%d\t%lf\n",i,petimes[i]);
43     if(maxpe < petimes[i])
44       maxpe = petimes[i];
45     if(minpe > petimes[i])
46       minpe = petimes[i];
47   }
48   delete[] petimes;
49   CkPrintf("\tLoad Imbalance=%lf seconds\n", maxpe-minpe);
50   int ncomm = 0;
51   for(i=0;i<numobjs;i++) {
52     for(j=0;j<numobjs;j++) {
53       if(map[i] != map[j])
54         ncomm += comm[i][j];
55     }
56   }
57   CkPrintf("\tCommunication (off proc msgs) = %d\n", ncomm/2);
58 }
59
60 extern "C" void METIS_PartGraphKway(int*, int*, int*, int*, int*,
61                                     int*, int*, int*, int*,
62                                     int*, int*);
63 extern "C" void METIS_PartGraphRecursive(int*, int*, int*, int*, int*,
64                                     int*, int*, int*, int*,
65                                     int*, int*);
66 extern "C" void METIS_PartGraphVKway(int*, int*, int*, int*, int*,
67                                     int*, int*, int*, int*,
68                                     int*, int*);
69
70 CLBMigrateMsg* MetisLB::Strategy(CentralLB::LDStats* stats, int count)
71 {
72   // CkPrintf("[%d] MetisLB strategy\n",CkMyPe());
73
74   CkVector migrateInfo;
75
76   int i, j;
77   int numobjs = 0;
78   for (j=0; j < count; j++) {
79     numobjs += stats[j].n_objs;
80   }
81
82   // allocate space for the computing data
83   double *cputime = new double[numobjs];
84   int *objwt = new int[numobjs];
85   int *origmap = new int[numobjs];
86   LDObjHandle *handles = new LDObjHandle[numobjs];
87   for(i=0;i<numobjs;i++) {
88     cputime[i] = 0.0;
89     objwt[i] = 0;
90     origmap[i] = 0;
91   }
92
93   for (j=0; j<count; j++) {
94     for (i=0; i<stats[j].n_objs; i++) {
95       LDObjData *odata = stats[j].objData;
96       origmap[odata[i].id.id[0]] = j;
97       cputime[odata[i].id.id[0]] = odata[i].cpuTime;
98       handles[odata[i].id.id[0]] = odata[i].handle;
99     }
100   }
101   double max_cputime = cputime[0];
102   for(i=0; i<numobjs; i++) {
103     if(max_cputime < cputime[i])
104       max_cputime = cputime[i];
105   }
106   double ratio = 1000.0/max_cputime;
107   for(i=0; i<numobjs; i++) {
108     objwt[i] = (int)(cputime[i]*ratio);
109   }
110   int **comm = new int*[numobjs];
111   for (i=0; i<numobjs; i++) {
112     comm[i] = new int[numobjs];
113     for (j=0; j<numobjs; j++)  {
114       comm[i][j] = 0;
115     }
116   }
117
118   for(j=0; j<count; j++) {
119     LDCommData *cdata = stats[j].commData;
120     const int csz = stats[j].n_comm;
121     for(i=0; i<csz; i++) {
122       if(cdata[i].from_proc || cdata[i].to_proc)
123         continue;
124       int senderID = cdata[i].sender.id[0];
125       int recverID = cdata[i].receiver.id[0];
126       comm[senderID][recverID] += cdata[i].messages;
127       comm[recverID][senderID] += cdata[i].messages;
128     }
129   }
130   // ignore messages sent from an object to itself
131   for (i=0; i<numobjs; i++)
132     comm[i][i] = 0;
133
134   // construct the graph in CSR format
135   int *xadj = new int[numobjs+1];
136   int numedges = 0;
137   for(i=0;i<numobjs;i++) {
138     for(j=0;j<numobjs;j++) {
139       if(comm[i][j] != 0)
140         numedges++;
141     }
142   }
143   int *adjncy = new int[numedges];
144   int *edgewt = new int[numedges];
145   xadj[0] = 0;
146   int count4all = 0;
147   for (i=0; i<numobjs; i++) {
148     for (j=0; j<numobjs; j++) { 
149       if (comm[i][j] != 0) { 
150         adjncy[count4all] = j;
151         edgewt[count4all++] = comm[i][j];
152       }
153     }
154     xadj[i+1] = count4all;
155   }
156
157   CkPrintf("Pre-LDB Statistics step %d\n", step());
158   printStats(count, numobjs, cputime, comm, origmap);
159
160   int wgtflag = 3; // Weights both on vertices and edges
161   int numflag = 0; // C Style numbering
162   int options[5];
163   options[0] = 0;
164   int edgecut;
165   int *newmap;
166
167   if(count > 1) {
168     newmap = new int[numobjs];
169     for(i=0;i<(numobjs+1);i++)
170       xadj[i] = 0;
171     delete[] edgewt;
172     edgewt = 0;
173     wgtflag = 2;
174     METIS_PartGraphRecursive(&numobjs, xadj, adjncy, objwt, edgewt, 
175                          &wgtflag, &numflag, &count, options, 
176                          &edgecut, newmap);
177   } else {
178     newmap = origmap;
179   }
180   CkPrintf("Post-LDB Statistics step %d\n", step());
181   printStats(count, numobjs, cputime, comm, newmap);
182
183   for(i=0;i<numobjs;i++)
184     delete[] comm[i];
185   delete[] comm;
186   delete[] cputime;
187   delete[] xadj;
188   delete[] adjncy;
189   if(objwt) delete[] objwt;
190   if(edgewt) delete[] edgewt;
191
192   for(i=0; i<numobjs; i++) {
193     if(origmap[i] != newmap[i]) {
194       MigrateInfo* migrateMe = new MigrateInfo;
195       migrateMe->obj = handles[i];
196       migrateMe->from_pe = origmap[i];
197       migrateMe->to_pe = newmap[i];
198       migrateInfo.push_back((void*)migrateMe);
199     }
200   }
201
202   delete[] origmap;
203   if(newmap != origmap)
204     delete[] newmap;
205
206   int migrate_count=migrateInfo.size();
207   CkPrintf("Migration Count = %d\n", migrate_count);
208   CLBMigrateMsg* msg = new(&migrate_count,1) CLBMigrateMsg;
209   msg->n_moves = migrate_count;
210   for(i=0; i < migrate_count; i++) {
211     MigrateInfo* item = (MigrateInfo*)migrateInfo[i];
212     msg->moves[i] = *item;
213     delete item;
214     migrateInfo[i] = 0;
215   }
216
217   return msg;
218 }
219
220 #endif