ignore idle timers for BigSim, changed CmiWallTimer to CkWallTimer() to better handle...
[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 #include "cklists.h"
19
20 #include "OrbLB.h"
21
22 //#define DEBUG
23
24 CreateLBFunc_Def(OrbLB);
25
26 static void lbinit(void) {
27   LBRegisterBalancer("OrbLB", CreateOrbLB, AllocateOrbLB, "partition objects based on coordinates");
28 }
29
30 #include "OrbLB.def.h"
31
32 OrbLB::OrbLB(const CkLBOptions &opt): CentralLB(opt)
33 {
34   lbname = "OrbLB";
35   if (CkMyPe() == 0)
36     CkPrintf("[%d] OrbLB created\n",CkMyPe());
37 }
38
39 CmiBool OrbLB::QueryBalanceNow(int _step)
40 {
41   return CmiTrue;
42 }
43
44 void OrbLB::rec_divide(int n, Partition &p)
45 {
46   int i;
47   int midpos;
48   int n1, n2;
49   double load1, currentload;
50   int maxdir, count;
51   Partition p1, p2;
52
53 #ifdef DEBUG
54   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]);
55 #endif
56
57   if (n==1) {
58     partitions[currentp++] = p;
59     return;
60   }
61 /*
62   if (p.origin.x==p.corner.x && p.origin.y==p.corner.y && p.origin.z==p.corner.z) 
63      NAMD_die("AlgRecBisection failed in recursion.\n"); 
64 */
65
66   n2 = n/2;
67   n1 = n-n2;
68
69   load1 = (1.0*n1/n) * p.load;
70 #ifdef DEBUG
71   CmiPrintf("divide goal: n1: %d load1: %f, n2: %d\n", n1, load1, n2);
72 #endif
73
74   p1 = p;
75   p1.refno = ++refno;
76   p2 = p;
77   p2.refno = ++refno;
78
79   // determine the best division direction
80   int maxSpan=-1;
81   maxdir = XDIR;
82   for (i=XDIR; i<=ZDIR; i++) {
83     int myspan = p.corner[i] - p.origin[i];
84     if (myspan > maxSpan) {
85       maxdir = i;
86       maxSpan = myspan;
87     }
88   }
89
90   // other two dimensions
91   int dir2 = (maxdir+1)%3;
92   int dir3 = (maxdir+2)%3;
93
94   currentload = 0.0;
95   count = 0;
96   midpos = p.origin[maxdir];
97   for (i=0; i<nObjs; i++) {
98     // not belong to this partition
99     if (computeLoad[vArray[maxdir][i].id].refno != p.refno) continue;
100     if (vArray[maxdir][i].v<p.origin[maxdir]) continue;
101     if (vArray[maxdir][i].v>p.corner[maxdir]) break;
102
103     int cid = vArray[maxdir][i].id;     // this compute ID
104     // check if this compute is within the partition
105     if ( computeLoad[cid].v[dir2] >= p.origin[dir2] &&
106          computeLoad[cid].v[dir2] <= p.corner[dir2] &&
107          computeLoad[cid].v[dir3] >= p.origin[dir3] &&
108          computeLoad[cid].v[dir3] <= p.corner[dir3]  ) {
109       // this compute is set to the first partition
110       if (currentload <= load1) {
111         computeLoad[cid].refno = p1.refno;
112         currentload += computeLoad[cid].load;
113         count ++;
114         midpos = computeLoad[cid].v[maxdir];
115       }
116       else {    // or the next partition
117         computeLoad[cid].refno = p2.refno;
118       }
119     }
120   }
121 #ifdef DEBUG
122 //  CmiPrintf("X:cur:%d, prev:%d load:%f %f\n", cur, prev, currentload, prevload);
123   CmiPrintf("DIR:%d %d load:%f\n", maxdir, midpos, currentload);
124 #endif
125
126   p1.corner[maxdir] = midpos;
127   p2.origin[maxdir] = midpos;
128
129   p1.load = currentload;
130   p1.count = count;
131   p2.load = p.load - p1.load;
132   p2.count = p.count - p1.count;
133 #ifdef DEBUG
134   CmiPrintf("p1: n:%d count:%d load:%f\n", n1, p1.count, p1.load);
135   CmiPrintf("p2: n:%d count:%d load:%f\n", n2, p2.count, p2.load);
136 #endif
137   rec_divide(n1, p1);
138   rec_divide(n2, p2);
139 }
140
141 void OrbLB::setVal(int x, int y, int z)
142 {
143   int i;
144   for (i=0; i<nObjs; i++) {
145     computeLoad[i].tv = 1000000.0*computeLoad[i].v[x]+
146                         1000.0*computeLoad[i].v[y]+
147                         computeLoad[i].v[z];
148   }
149 #if 0
150   CmiPrintf("original:%d\n", x);
151   for (i=0; i<numComputes; i++) 
152     CmiPrintf("%d ", computeLoad[i].tv);
153   CmiPrintf("\n");
154 #endif
155 }
156
157 int OrbLB::sort_partition(int x, int p, int r)
158 {
159   double mid = computeLoad[vArray[x][p].id].tv;
160   int i= p;
161   int j= r;
162   while (1) {
163     while (computeLoad[vArray[x][j].id].tv > mid && j>i) j--;
164     while (computeLoad[vArray[x][i].id].tv < mid && i<j) i++;
165     if (i<j) {
166       if (computeLoad[vArray[x][i].id].tv == computeLoad[vArray[x][j].id].tv)
167       {
168         if (computeLoad[vArray[x][i].id].tv != mid) CmiAbort("my god!\n");
169         if (i-p < r-j) i++;
170         else j--;
171         continue;
172       }
173       VecArray tmp = vArray[x][i];
174       vArray[x][i] = vArray[x][j];
175       vArray[x][j] = tmp;
176     }
177     else
178       return j;
179   }
180 }
181
182 void OrbLB::qsort(int x, int p, int r)
183 {
184   if (p<r) {
185     int q = sort_partition(x, p, r);
186 //CmiPrintf("midpoint: %d %d %d\n", p,q,r);
187     qsort(x, p, q-1);
188     qsort(x, q+1, r);
189   }
190 }
191
192 void OrbLB::quicksort(int x)
193 {
194   int y = (x+1)%3;
195   int z = (x+2)%3;
196   setVal(x, y, z);
197   qsort(x, 0, nObjs-1);
198
199 #if 0
200   CmiPrintf("result for :%d\n", x);
201   for (int i=0; i<nObjs; i++) 
202     CmiPrintf("%d ", computeLoad[vArray[x][i].id].tv);
203   CmiPrintf("\n");
204 #endif
205 }
206
207 void OrbLB::mapPartitionsToNodes()
208 {
209   int i,j;
210 #if 1
211   for (i=0; i<P; i++) partitions[i].node = i;
212 #else
213   PatchMap *patchMap = PatchMap::Object();
214
215   int **pool = new int *[P];
216   for (i=0; i<P; i++) pool[i] = new int[P];
217   for (i=0; i<P; i++) for (j=0; j<P; j++) pool[i][j] = 0;
218
219   // sum up the number of nodes that patches of computes are on
220   for (i=0; i<numComputes; i++)
221   {
222     for (j=0; j<P; j++)
223       if (computeLoad[i].refno == partitions[j].refno) 
224       {
225         int node1 = patchMap->node(computes[i].patch1);
226         int node2 = patchMap->node(computes[i].patch2);
227         pool[j][node1]++;
228         pool[j][node2]++;
229       }
230   }
231 #ifdef DEBUG
232   for (i=0; i<P; i++) {
233     for (j=0; j<P; j++) CmiPrintf("%d ", pool[i][j]);
234     CmiPrintf("\n");
235   }
236 #endif
237   while (1)
238   {
239     int index=-1, node=0, eager=-1;
240     for (j=0; j<P; j++) {
241       if (partitions[j].node != -1) continue;
242       int wantmost=-1, maxnodes=-1;
243       for (k=0; k<P; k++) if (pool[j][k] > maxnodes && !partitions[k].mapped) {wantmost=k; maxnodes = pool[j][k];}
244       if (maxnodes > eager) {
245         index = j; node = wantmost; eager = maxnodes;
246       }
247     }
248     if (eager == -1) break;
249     partitions[index].node = node;
250     partitions[node].mapped = 1;
251   }
252
253   for (i=0; i<P; i++) delete [] pool[i];
254   delete [] pool;
255 #endif
256
257   if (_lb_args.debug()) {
258     CmiPrintf("partitions to nodes mapping: ");
259     for (i=0; i<P; i++) CmiPrintf("%d ", partitions[i].node);
260     CmiPrintf("\n");
261   }
262 }
263
264 void OrbLB::work(CentralLB::LDStats* stats, int count)
265 {
266 #if CMK_LBDB_ON
267   int i,j;
268
269   P = count;
270   // calculate total number of objects
271   nObjs = stats->n_objs;
272 #ifdef DEBUG
273   CmiPrintf("ORB: num objects:%d\n", nObjs);
274 #endif
275
276   // create computeLoad and calculate tentative computes coordinates
277   computeLoad = new ComputeLoad[nObjs];
278   for (i=XDIR; i<=ZDIR; i++) vArray[i] = new VecArray[nObjs];
279
280   // v[0] = XDIR  v[1] = YDIR v[2] = ZDIR
281   // vArray[XDIR] is an array holding the x vector for all computes
282   int objIdx = 0;
283   for (i=0; i<nObjs; i++) {
284     LDObjData &odata = stats->objData[i];
285     computeLoad[objIdx].id = objIdx;
286     computeLoad[objIdx].v[XDIR] = odata.objID().id[0];
287     computeLoad[objIdx].v[YDIR] = odata.objID().id[1];
288     computeLoad[objIdx].v[ZDIR] = odata.objID().id[2];
289     computeLoad[objIdx].load = odata.wallTime;
290     computeLoad[objIdx].refno = 0;
291     computeLoad[objIdx].partition = NULL;
292     for (int k=XDIR; k<=ZDIR; k++) {
293         vArray[k][objIdx].id = objIdx;
294         vArray[k][objIdx].v = computeLoad[objIdx].v[k];
295     }
296 #ifdef DEBUG
297     CmiPrintf("Object %d: %d %d %d load:%f\n", objIdx, computeLoad[objIdx].v[XDIR], computeLoad[objIdx].v[YDIR], computeLoad[objIdx].v[ZDIR], computeLoad[objIdx].load);
298 #endif
299     objIdx ++;
300   }
301
302   double t = CkWallTimer();
303
304   quicksort(XDIR);
305   quicksort(YDIR);
306   quicksort(ZDIR);
307 #ifdef DEBUG
308   CmiPrintf("qsort time: %f\n", CkWallTimer() - t);
309 #endif
310
311   npartition = P;
312   partitions = new Partition[npartition];
313
314   double totalLoad = 0.0;
315   int minx, miny, minz, maxx, maxy, maxz;
316   minx = maxx= computeLoad[0].v[XDIR];
317   miny = maxy= computeLoad[0].v[YDIR];
318   minz = maxz= computeLoad[0].v[ZDIR];
319   for (i=1; i<nObjs; i++) {
320     totalLoad += computeLoad[i].load;
321     if (computeLoad[i].v[XDIR] < minx) minx = computeLoad[i].v[XDIR];
322     else if (computeLoad[i].v[XDIR] > maxx) maxx = computeLoad[i].v[XDIR];
323     if (computeLoad[i].v[YDIR] < miny) miny = computeLoad[i].v[YDIR];
324     else if (computeLoad[i].v[YDIR] > maxy) maxy = computeLoad[i].v[YDIR];
325     if (computeLoad[i].v[ZDIR] < minz) minz = computeLoad[i].v[ZDIR];
326     else if (computeLoad[i].v[ZDIR] > maxz) maxz = computeLoad[i].v[ZDIR];
327   }
328
329   top_partition.origin[XDIR] = minx;
330   top_partition.origin[YDIR] = miny;
331   top_partition.origin[ZDIR] = minz;
332   top_partition.corner[XDIR] = maxx;
333   top_partition.corner[YDIR] = maxy; 
334   top_partition.corner[ZDIR] = maxz;
335
336   top_partition.refno = 0;
337   top_partition.load = 0.0;
338   top_partition.count = nObjs;
339   top_partition.load = totalLoad;
340
341   currentp = 0;
342   refno = 0;
343
344   // recursively divide
345   rec_divide(npartition, top_partition);
346
347   if (_lb_args.debug()) {
348     CmiPrintf("After partitioning: \n");
349     for (i=0; i<P; i++) {
350       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);
351   }
352   }
353
354   // mapping partitions to nodes
355   mapPartitionsToNodes();
356
357   // this is for debugging
358   int *num = new int[P];
359   for (i=0; i<P; i++) num[i] = 0;
360
361   for (i=0; i<nObjs; i++)
362   {
363     for (j=0; j<count; j++)
364       if (computeLoad[i].refno == partitions[j].refno)   {
365         computeLoad[i].partition = partitions+j;
366         num[j] ++;
367     }
368     CmiAssert(computeLoad[i].partition != NULL);
369   }
370
371   for (i=0; i<P; i++)
372     if (num[i] != partitions[i].count) 
373       CmiAbort("OrbLB: Compute counts don't agree!\n");
374
375   delete [] num;
376
377   // Save output
378   for(int obj=0;obj<stats->n_objs;obj++) {
379       int frompe = stats->from_proc[obj];
380       if (frompe != computeLoad[obj].partition->node) {
381         //      CkPrintf("[%d] Obj %d migrating from %d to %d\n",
382         //             CkMyPe(),obj,frompe,computeLoad[obj].partition->node);
383         CmiAssert(frompe == stats->from_proc[obj]);
384         stats->to_proc[obj] = computeLoad[obj].partition->node;
385       }
386   }
387
388   delete [] computeLoad;
389   for (i=0; i<3; i++) delete [] vArray[i];
390   delete [] partitions;
391
392   CmiPrintf("OrbLB finished time: %f\n", CkWallTimer() - t);
393 #endif
394 }
395
396
397
398
399 /*@}*/