minor changes, removed warnings.
[charm.git] / src / ck-ldb / OrbLB.C
1 /*****************************************************************************
2  * $Source$
3  * $Author$
4  * $Date$
5  * $Revision$
6  *****************************************************************************/
7
8 /**
9  * \addtogroup CkLdb
10    Load balancer that use Orthogonal Recursive Bisection(ORB) to partition
11    objects and map to processors. In OrbLB, objects are treated to be enclosed 
12    by a rectangular box using their LDObjid as coordinates.
13 */
14 /*@{*/
15
16 #include <charm++.h>
17
18 #if CMK_LBDB_ON
19
20 #include "cklists.h"
21
22 #include "OrbLB.h"
23
24 //#define DEBUG
25
26 void CreateOrbLB()
27 {
28   loadbalancer = CProxy_OrbLB::ckNew();
29 }
30
31 static void lbinit(void) {
32   LBRegisterBalancer("OrbLB", CreateOrbLB, "partition objects based on coordinates");
33 }
34
35 #include "OrbLB.def.h"
36
37 OrbLB::OrbLB()
38 {
39   lbname = "OrbLB";
40   if (CkMyPe() == 0)
41     CkPrintf("[%d] OrbLB created\n",CkMyPe());
42 }
43
44 CmiBool OrbLB::QueryBalanceNow(int _step)
45 {
46   return CmiTrue;
47 }
48
49 void OrbLB::rec_divide(int n, Partition &p)
50 {
51   int i;
52   int midpos;
53   int n1, n2;
54   double load1, currentload;
55   int maxdir, count;
56   Partition p1, p2;
57
58 #ifdef DEBUG
59   CmiPrintf("rec_divide: partition n:%d count:%d load:%f (%d %d %d, %d %d %d)\n", n, p.count, p.load, p.origin[0], p.origin[1], p.origin[2], p.corner[0], p.corner[1], p.corner[2]);
60 #endif
61
62   if (n==1) {
63     partitions[currentp++] = p;
64     return;
65   }
66 /*
67   if (p.origin.x==p.corner.x && p.origin.y==p.corner.y && p.origin.z==p.corner.z) 
68      NAMD_die("AlgRecBisection failed in recursion.\n"); 
69 */
70
71   n2 = n/2;
72   n1 = n-n2;
73
74   load1 = (1.0*n1/n) * p.load;
75
76   p1 = p;
77   p1.refno = ++refno;
78   p2 = p;
79   p2.refno = ++refno;
80
81   // determine the best division direction
82   int maxSpan=-1;
83   maxdir = XDIR;
84   for (i=XDIR; i<=ZDIR; i++) {
85     int myspan = p.corner[i] - p.origin[i];
86     if (myspan > maxSpan) {
87       maxdir = i;
88       maxSpan = myspan;
89     }
90   }
91
92   // other two dimensions
93   int dir2 = (maxdir+1)%3;
94   int dir3 = (maxdir+2)%3;
95
96   currentload = 0.0;
97   count = 0;
98   midpos = p.origin[maxdir];
99   for (i=0; i<nObjs; i++) {
100     // not belong to this partition
101     if (computeLoad[vArray[maxdir][i].id].refno != p.refno) continue;
102     if (vArray[maxdir][i].v<p.origin[maxdir]) continue;
103     if (vArray[maxdir][i].v>p.corner[maxdir]) break;
104
105     int cid = vArray[maxdir][i].id;     // this compute ID
106     // check if this compute is within the partition
107     if ( computeLoad[cid].v[dir2] >= p.origin[dir2] &&
108          computeLoad[cid].v[dir2] <= p.corner[dir2] &&
109          computeLoad[cid].v[dir3] >= p.origin[dir3] &&
110          computeLoad[cid].v[dir3] <= p.corner[dir3]  ) {
111       // this compute is set to the first partition
112       if (currentload <= load1) {
113         computeLoad[cid].refno = p1.refno;
114         currentload += computeLoad[cid].load;
115         count ++;
116         midpos = computeLoad[cid].v[maxdir];
117       }
118       else {    // or the next partition
119         computeLoad[cid].refno = p2.refno;
120       }
121     }
122   }
123 //  CmiPrintf("X:cur:%d, prev:%d load:%f %f\n", cur, prev, currentload, prevload);
124 #ifdef DEBUG
125   CmiPrintf("DIR:%d %d load:%f\n", maxdir, midpos, currentload);
126 #endif
127
128   p1.corner[maxdir] = midpos;
129   p2.origin[maxdir] = midpos;
130
131   p1.load = currentload;
132   p1.count = count;
133   p2.load = p.load - p1.load;
134   p2.count = p.count - p1.count;
135 #ifdef DEBUG
136   CmiPrintf("p1: n:%d count:%d load:%f\n", n1, p1.count, p1.load);
137   CmiPrintf("p2: n:%d count:%d load:%f\n", n2, p2.count, p2.load);
138 #endif
139   rec_divide(n1, p1);
140   rec_divide(n2, p2);
141 }
142
143 void OrbLB::setVal(int x, int y, int z)
144 {
145   int i;
146   for (i=0; i<nObjs; i++) {
147     computeLoad[i].tv = 1000000*computeLoad[i].v[x]+
148                         1000*computeLoad[i].v[y]+
149                         computeLoad[i].v[z];
150   }
151 #if 0
152   CmiPrintf("original:%d\n", x);
153   for (i=0; i<numComputes; i++) 
154     CmiPrintf("%d ", computeLoad[i].tv);
155   CmiPrintf("\n");
156 #endif
157 }
158
159 int OrbLB::sort_partition(int x, int p, int r)
160 {
161   int mid = computeLoad[vArray[x][p].id].tv;
162   int i= p;
163   int j= r;
164   while (1) {
165     while (computeLoad[vArray[x][j].id].tv > mid && j>i) j--;
166     while (computeLoad[vArray[x][i].id].tv < mid && i<j) i++;
167     if (i<j) {
168       if (computeLoad[vArray[x][i].id].tv == computeLoad[vArray[x][j].id].tv)
169       {
170         if (computeLoad[vArray[x][i].id].tv != mid) CmiAbort("my god!\n");
171         if (i-p < r-j) i++;
172         else j--;
173         continue;
174       }
175       VecArray tmp = vArray[x][i];
176       vArray[x][i] = vArray[x][j];
177       vArray[x][j] = tmp;
178     }
179     else
180       return j;
181   }
182 }
183
184 void OrbLB::qsort(int x, int p, int r)
185 {
186   if (p<r) {
187     int q = sort_partition(x, p, r);
188 //CmiPrintf("midpoint: %d %d %d\n", p,q,r);
189     qsort(x, p, q-1);
190     qsort(x, q+1, r);
191   }
192 }
193
194 void OrbLB::quicksort(int x)
195 {
196   int y = (x+1)%3;
197   int z = (x+2)%3;
198   setVal(x, y, z);
199   qsort(x, 0, nObjs-1);
200
201 #if 0
202   CmiPrintf("result:%d\n", x);
203   for (int i=0; i<numComputes; i++) 
204     CmiPrintf("%d ", computeLoad[vArray[x][i].id].tv);
205   CmiPrintf("\n");
206 #endif
207 }
208
209 void OrbLB::mapPartitionsToNodes()
210 {
211   int i,j;
212 #if 1
213   for (i=0; i<P; i++) partitions[i].node = i;
214 #else
215   PatchMap *patchMap = PatchMap::Object();
216
217   int **pool = new int *[P];
218   for (i=0; i<P; i++) pool[i] = new int[P];
219   for (i=0; i<P; i++) for (j=0; j<P; j++) pool[i][j] = 0;
220
221   // sum up the number of nodes that patches of computes are on
222   for (i=0; i<numComputes; i++)
223   {
224     for (j=0; j<P; j++)
225       if (computeLoad[i].refno == partitions[j].refno) 
226       {
227         int node1 = patchMap->node(computes[i].patch1);
228         int node2 = patchMap->node(computes[i].patch2);
229         pool[j][node1]++;
230         pool[j][node2]++;
231       }
232   }
233 #ifdef DEBUG
234   for (i=0; i<P; i++) {
235     for (j=0; j<P; j++) CmiPrintf("%d ", pool[i][j]);
236     CmiPrintf("\n");
237   }
238 #endif
239   while (1)
240   {
241     int index=-1, node=0, eager=-1;
242     for (j=0; j<P; j++) {
243       if (partitions[j].node != -1) continue;
244       int wantmost=-1, maxnodes=-1;
245       for (k=0; k<P; k++) if (pool[j][k] > maxnodes && !partitions[k].mapped) {wantmost=k; maxnodes = pool[j][k];}
246       if (maxnodes > eager) {
247         index = j; node = wantmost; eager = maxnodes;
248       }
249     }
250     if (eager == -1) break;
251     partitions[index].node = node;
252     partitions[node].mapped = 1;
253   }
254
255   for (i=0; i<P; i++) delete [] pool[i];
256   delete [] pool;
257 #endif
258
259   CmiPrintf("partitions to nodes mapping: ");
260   for (i=0; i<P; i++) CmiPrintf("%d ", partitions[i].node);
261   CmiPrintf("\n");
262 }
263
264 LBMigrateMsg* OrbLB::Strategy(CentralLB::LDStats* stats, int count)
265 {
266   int i,j;
267
268   P = count;
269   // calculate total number of objects
270   nObjs = stats->n_objs;
271 #ifdef DEBUG
272   CmiPrintf("ORB: num objects:%d\n", nObjs);
273 #endif
274
275   // create computeLoad and calculate tentative computes coordinates
276   computeLoad = new ComputeLoad[nObjs];
277   for (i=XDIR; i<=ZDIR; i++) vArray[i] = new VecArray[nObjs];
278
279   // v[0] = XDIR  v[1] = YDIR v[2] = ZDIR
280   // vArray[XDIR] is an array holding the x vector for all computes
281   int objIdx = 0;
282   for (i=0; i<nObjs; i++) {
283     LDObjData &odata = stats->objData[i];
284     computeLoad[objIdx].id = objIdx;
285     computeLoad[objIdx].v[XDIR] = odata.objID().id[0];
286     computeLoad[objIdx].v[YDIR] = odata.objID().id[1];
287     computeLoad[objIdx].v[ZDIR] = odata.objID().id[2];
288     computeLoad[objIdx].load = odata.wallTime;
289     computeLoad[objIdx].refno = 0;
290     computeLoad[objIdx].partition = NULL;
291     for (int k=XDIR; k<=ZDIR; k++) {
292         vArray[k][objIdx].id = objIdx;
293         vArray[k][objIdx].v = computeLoad[objIdx].v[k];
294     }
295     objIdx ++;
296   }
297
298   double t = CmiWallTimer();
299
300   quicksort(XDIR);
301   quicksort(YDIR);
302   quicksort(ZDIR);
303 #ifdef DEBUG
304   CmiPrintf("qsort time: %f\n", CmiWallTimer() - t);
305 #endif
306
307   npartition = P;
308   partitions = new Partition[npartition];
309
310   double totalLoad = 0.0;
311   int minx, miny, minz, maxx, maxy, maxz;
312   minx = maxx= computeLoad[0].v[XDIR];
313   miny = maxy= computeLoad[0].v[YDIR];
314   minz = maxz= computeLoad[0].v[ZDIR];
315   for (i=1; i<nObjs; i++) {
316     totalLoad += computeLoad[i].load;
317     if (computeLoad[i].v[XDIR] < minx) minx = computeLoad[i].v[XDIR];
318     else if (computeLoad[i].v[XDIR] > maxx) maxx = computeLoad[i].v[XDIR];
319     if (computeLoad[i].v[YDIR] < miny) miny = computeLoad[i].v[YDIR];
320     else if (computeLoad[i].v[YDIR] > maxy) maxy = computeLoad[i].v[YDIR];
321     if (computeLoad[i].v[ZDIR] < minz) minz = computeLoad[i].v[ZDIR];
322     else if (computeLoad[i].v[ZDIR] > maxz) maxz = computeLoad[i].v[ZDIR];
323   }
324
325   top_partition.origin[XDIR] = minx;
326   top_partition.origin[YDIR] = miny;
327   top_partition.origin[ZDIR] = minz;
328   top_partition.corner[XDIR] = maxx;
329   top_partition.corner[YDIR] = maxy; 
330   top_partition.corner[ZDIR] = maxz;
331
332   top_partition.refno = 0;
333   top_partition.load = 0.0;
334   top_partition.count = nObjs;
335   top_partition.load = totalLoad;
336
337   currentp = 0;
338   refno = 0;
339
340   // recursively divide
341   rec_divide(npartition, top_partition);
342
343   CmiPrintf("After partitioning: \n");
344   for (i=0; i<P; i++) {
345     CmiPrintf("[%d] (%d,%d,%d) (%d,%d,%d) load:%f count:%d\n", i, partitions[i].origin[0], partitions[i].origin[1], partitions[i].origin[2], partitions[i].corner[0], partitions[i].corner[1], partitions[i].corner[2], partitions[i].load, partitions[i].count);
346   }
347
348   // mapping partitions to nodes
349   mapPartitionsToNodes();
350
351   // this is for debugging
352   int *num = new int[P];
353   for (i=0; i<P; i++) num[i] = 0;
354
355   for (i=0; i<nObjs; i++)
356   {
357     for (j=0; j<count; j++)
358       if (computeLoad[i].refno == partitions[j].refno)   {
359         computeLoad[i].partition = partitions+j;
360         num[j] ++;
361     }
362     CmiAssert(computeLoad[i].partition != NULL);
363   }
364
365   for (i=0; i<P; i++)
366     if (num[i] != partitions[i].count) 
367       CmiAbort("OrbLB: Compute counts don't agree!\n");
368
369   delete [] num;
370
371   CkVec<MigrateInfo*> migrateInfo;
372
373   // Save output
374   objIdx = 0;
375   for(int obj=0;obj<stats->n_objs;obj++) {
376       int frompe = stats->from_proc[obj];
377       if (frompe != computeLoad[objIdx].partition->node) {
378         //      CkPrintf("[%d] Obj %d migrating from %d to %d\n",
379         //               CkMyPe(),obj,pe,to_procs[pe][obj]);
380         MigrateInfo *migrateMe = new MigrateInfo;
381         migrateMe->obj = stats->objData[obj].handle;
382         migrateMe->from_pe = frompe;
383         migrateMe->to_pe = computeLoad[objIdx].partition->node;
384         migrateInfo.insertAtEnd(migrateMe);
385       }
386       objIdx ++;
387   }
388
389   int migrate_count=migrateInfo.length();
390   LBMigrateMsg* msg = new(&migrate_count,1) LBMigrateMsg;
391   msg->n_moves = migrate_count;
392   for(i=0; i < migrate_count; i++) {
393     MigrateInfo* item = (MigrateInfo*)migrateInfo[i];
394     msg->moves[i] = *item;
395     delete item;
396     migrateInfo[i] = 0;
397   }
398
399   delete [] computeLoad;
400   for (i=0; i<3; i++) delete [] vArray[i];
401   delete [] partitions;
402
403   CmiPrintf("OrbLB finished time: %f\n", CmiWallTimer() - t);
404
405   return msg;
406 }
407
408
409 #if 0
410 /*@}*/
411 LBMigrateMsg* OrbLB::Strategy(CentralLB::LDStats* stats, int count)
412 {
413   int obj, pe;
414
415   //  CkPrintf("[%d] RefineLB strategy\n",CkMyPe());
416
417   // remove non-migratable objects
418   RemoveNonMigratable(stats, count);
419
420
421   CkVec<MigrateInfo*> migrateInfo;
422
423   // Save output
424   objIdx = 0;
425   for(pe=0;pe < count; pe++) {
426     for(obj=0;obj<stats[pe].n_objs;obj++) {
427       if (to_procs[pe][obj] != pe) {
428         //      CkPrintf("[%d] Obj %d migrating from %d to %d\n",
429         //               CkMyPe(),obj,pe,to_procs[pe][obj]);
430         MigrateInfo *migrateMe = new MigrateInfo;
431         migrateMe->obj = stats[pe].objData[obj].handle;
432         migrateMe->from_pe = pe;
433         migrateMe->to_pe = to_procs[pe][obj];
434         migrateInfo.insertAtEnd(migrateMe);
435       }
436     }
437   }
438
439   int migrate_count=migrateInfo.length();
440   LBMigrateMsg* msg = new(&migrate_count,1) LBMigrateMsg;
441   msg->n_moves = migrate_count;
442   for(int i=0; i < migrate_count; i++) {
443     MigrateInfo* item = (MigrateInfo*)migrateInfo[i];
444     msg->moves[i] = *item;
445     delete item;
446     migrateInfo[i] = 0;
447   }
448
449   return msg;
450 };
451 #endif
452
453 #endif
454
455
456 /*@}*/