cputimer: use walltime when cputimer not available
[charm.git] / src / ck-ldb / OrbLB.C
1 /**
2  * \addtogroup CkLdb
3    Load balancer that use Orthogonal Recursive Bisection(ORB) to partition
4    objects and map to processors. In OrbLB, objects are treated to be enclosed 
5    by a rectangular box using their LDObjid as coordinates.
6
7    Written by Gengbin Zheng
8
9    ORB now takes background load into account
10    3/26/2010:        added support for avail_vector
11 */
12 /*@{*/
13
14 #include "OrbLB.h"
15
16 //#define DEBUG
17
18 CreateLBFunc_Def(OrbLB, "partition objects based on coordinates")
19
20 OrbLB::OrbLB(const CkLBOptions &opt): CentralLB(opt)
21 {
22   lbname = "OrbLB";
23   if (CkMyPe() == 0)
24     CkPrintf("[%d] OrbLB created\n",CkMyPe());
25 }
26
27 CmiBool OrbLB::QueryBalanceNow(int _step)
28 {
29   return CmiTrue;
30 }
31
32 void OrbLB::rec_divide(int n, Partition &p)
33 {
34   int i;
35   int midpos;
36   int n1, n2;
37   double load1, currentload;
38   int maxdir, count;
39   Partition p1, p2;
40
41   if (_lb_args.debug()>=2) {
42     CmiPrintf("rec_divide starts: 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]);
43   }
44
45   if (n==1) {           // we are done in this branch
46     partitions[currentp++] = p;
47     return;
48   }
49 /*
50   if (p.origin.x==p.corner.x && p.origin.y==p.corner.y && p.origin.z==p.corner.z) 
51      CmiAbort("AlgRecBisection failed in recursion.\n"); 
52 */
53   if (_lb_args.debug()>=2) {
54     CmiPrintf("{\n");
55   }
56
57   // divide into n1 and n2 two subpartitions
58   n2 = n/2;
59   n1 = n-n2;
60
61   // subpartition n1 should have this load
62   load1 = (1.0*n1/n) * p.load;
63   if (_lb_args.debug()>=2)
64     CmiPrintf("goal: n1: %d with load1: %f; n2: %d load2: %f\n", n1, load1, n2, p.load-load1);
65
66   p1 = p;
67   p1.refno = ++refno;
68   p1.bkpes.resize(0);
69
70   p2 = p;
71   p2.refno = ++refno;
72   p2.bkpes.resize(0);
73
74   // determine the best division direction
75   int maxSpan=-1;
76   maxdir = XDIR;
77   for (i=XDIR; i<=ZDIR; i++) {
78     int myspan = p.corner[i] - p.origin[i];
79     if (myspan > maxSpan) {
80       maxdir = i;
81       maxSpan = myspan;
82     }
83   }
84
85   // other two dimensions
86   int dir2 = (maxdir+1)%3;
87   int dir3 = (maxdir+2)%3;
88
89   currentload = 0.0;
90   // counting background load
91   if (!_lb_args.ignoreBgLoad()) {
92     CmiAssert(p.bkpes.size() == n);
93     // first n1 processors
94     for (i=0; i<n1; i++) currentload += statsData->procs[p.bkpes[i]].bg_walltime;
95   }
96
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 #ifdef DEBUG
124 //  CmiPrintf("X:cur:%d, prev:%d load:%f %f\n", cur, prev, currentload, prevload);
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
136   // assign first n1 copy of background to p1, and rest to p2
137   if (!_lb_args.ignoreBgLoad()) {
138     for (i=0; i<n; i++)
139       if (i<n1) p1.bkpes.push_back(p.bkpes[i]);
140       else p2.bkpes.push_back(p.bkpes[i]);
141   }
142
143   if (_lb_args.debug()>=2) {
144     CmiPrintf("p1: n:%d count:%d load:%f\n", n1, p1.count, p1.load);
145     CmiPrintf("p2: n:%d count:%d load:%f\n", n2, p2.count, p2.load);
146     CmiPrintf("}\n");
147   }
148
149   rec_divide(n1, p1);
150   rec_divide(n2, p2);
151 }
152
153 void OrbLB::setVal(int x, int y, int z)
154 {
155   int i;
156   for (i=0; i<nObjs; i++) {
157     computeLoad[i].tv = 1000000.0*computeLoad[i].v[x]+
158                         1000.0*computeLoad[i].v[y]+
159                         computeLoad[i].v[z];
160   }
161 #if 0
162   CmiPrintf("original:%d\n", x);
163   for (i=0; i<numComputes; i++) 
164     CmiPrintf("%d ", computeLoad[i].tv);
165   CmiPrintf("\n");
166 #endif
167 }
168
169 int OrbLB::sort_partition(int x, int p, int r)
170 {
171   double mid = computeLoad[vArray[x][p].id].tv;
172   int i= p;
173   int j= r;
174   while (1) {
175     while (computeLoad[vArray[x][j].id].tv > mid && j>i) j--;
176     while (computeLoad[vArray[x][i].id].tv < mid && i<j) i++;
177     if (i<j) {
178       if (computeLoad[vArray[x][i].id].tv == computeLoad[vArray[x][j].id].tv)
179       {
180         if (computeLoad[vArray[x][i].id].tv != mid) CmiAbort("my god!\n");
181         if (i-p < r-j) i++;
182         else j--;
183         continue;
184       }
185       VecArray tmp = vArray[x][i];
186       vArray[x][i] = vArray[x][j];
187       vArray[x][j] = tmp;
188     }
189     else
190       return j;
191   }
192 }
193
194 void OrbLB::qsort(int x, int p, int r)
195 {
196   if (p<r) {
197     int q = sort_partition(x, p, r);
198 //CmiPrintf("midpoint: %d %d %d\n", p,q,r);
199     qsort(x, p, q-1);
200     qsort(x, q+1, r);
201   }
202 }
203
204 void OrbLB::quicksort(int x)
205 {
206   int y = (x+1)%3;
207   int z = (x+2)%3;
208   setVal(x, y, z);
209   qsort(x, 0, nObjs-1);
210
211 #if 0
212   CmiPrintf("result for :%d\n", x);
213   for (int i=0; i<nObjs; i++) 
214     CmiPrintf("%d ", computeLoad[vArray[x][i].id].tv);
215   CmiPrintf("\n");
216 #endif
217 }
218
219 void OrbLB::mapPartitionsToNodes()
220 {
221   int i,j;
222 #if 1
223   if (!_lb_args.ignoreBgLoad()) {
224       // processor mapping has already been determined by the background load pe
225     for (i=0; i<npartition; i++) partitions[i].node = partitions[i].bkpes[0];
226   }
227   else {
228     int n = 0;
229     for (i=0; i<P; i++) { 
230       if (!statsData->procs[i].available) continue;
231       partitions[n++].node = i;
232     }
233   }
234 #else
235   PatchMap *patchMap = PatchMap::Object();
236
237   int **pool = new int *[P];
238   for (i=0; i<P; i++) pool[i] = new int[P];
239   for (i=0; i<P; i++) for (j=0; j<P; j++) pool[i][j] = 0;
240
241   // sum up the number of nodes that patches of computes are on
242   for (i=0; i<numComputes; i++)
243   {
244     for (j=0; j<P; j++)
245       if (computeLoad[i].refno == partitions[j].refno) 
246       {
247         int node1 = patchMap->node(computes[i].patch1);
248         int node2 = patchMap->node(computes[i].patch2);
249         pool[j][node1]++;
250         pool[j][node2]++;
251       }
252   }
253 #ifdef DEBUG
254   for (i=0; i<P; i++) {
255     for (j=0; j<P; j++) CmiPrintf("%d ", pool[i][j]);
256     CmiPrintf("\n");
257   }
258 #endif
259   while (1)
260   {
261     int index=-1, node=0, eager=-1;
262     for (j=0; j<npartition; j++) {
263       if (partitions[j].node != -1) continue;
264       int wantmost=-1, maxnodes=-1;
265       for (k=0; k<P; k++) if (pool[j][k] > maxnodes && !partitions[k].mapped) {wantmost=k; maxnodes = pool[j][k];}
266       if (maxnodes > eager) {
267         index = j; node = wantmost; eager = maxnodes;
268       }
269     }
270     if (eager == -1) break;
271     partitions[index].node = node;
272     partitions[node].mapped = 1;
273   }
274
275   for (i=0; i<P; i++) delete [] pool[i];
276   delete [] pool;
277 #endif
278
279 /*
280   if (_lb_args.debug()) {
281     CmiPrintf("partition load: ");
282     for (i=0; i<npartition; i++) CmiPrintf("%f ", partitions[i].load);
283     CmiPrintf("\n");
284     CmiPrintf("partitions to nodes mapping: ");
285     for (i=0; i<npartition; i++) CmiPrintf("%d ", partitions[i].node);
286     CmiPrintf("\n");
287   }
288 */
289   if (_lb_args.debug()) {
290     CmiPrintf("After partitioning: \n");
291     for (i=0; i<npartition; i++) {
292       double bgload = 0.0;
293       if (!_lb_args.ignoreBgLoad())
294         bgload = statsData->procs[partitions[i].bkpes[0]].bg_walltime;
295       CmiPrintf("[%d=>%d] (%d,%d,%d) (%d,%d,%d) load:%f count:%d objload:%f\n", i, partitions[i].node, 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, partitions[i].load-bgload);
296     }
297     for (i=npartition; i<P; i++) CmiPrintf("[%d] --------- \n", i);
298   }
299
300 }
301
302 void OrbLB::work(LDStats* stats)
303 {
304 #if CMK_LBDB_ON
305   int i,j;
306
307   statsData = stats;
308
309   P = stats->nprocs();
310
311   // calculate total number of migratable objects
312   nObjs = stats->n_migrateobjs;
313 #ifdef DEBUG
314   CmiPrintf("ORB: num objects:%d\n", nObjs);
315 #endif
316
317   // create computeLoad and calculate tentative computes coordinates
318   computeLoad = new ComputeLoad[nObjs];
319   for (i=XDIR; i<=ZDIR; i++) vArray[i] = new VecArray[nObjs];
320
321   // v[0] = XDIR  v[1] = YDIR v[2] = ZDIR
322   // vArray[XDIR] is an array holding the x vector for all computes
323   int objIdx = 0;
324   for (i=0; i<stats->n_objs; i++) {
325     LDObjData &odata = stats->objData[i];
326     if (odata.migratable == 0) continue;
327     computeLoad[objIdx].id = objIdx;
328     computeLoad[objIdx].v[XDIR] = odata.objID().id[0];
329     computeLoad[objIdx].v[YDIR] = odata.objID().id[1];
330     computeLoad[objIdx].v[ZDIR] = odata.objID().id[2];
331 #if CMK_LB_CPUTIMER
332     computeLoad[objIdx].load = _lb_args.useCpuTime()?odata.cpuTime:odata.wallTime;
333 #else
334     computeLoad[objIdx].load = odata.wallTime;
335 #endif
336     computeLoad[objIdx].refno = 0;
337     computeLoad[objIdx].partition = NULL;
338     for (int k=XDIR; k<=ZDIR; k++) {
339         vArray[k][objIdx].id = objIdx;
340         vArray[k][objIdx].v = computeLoad[objIdx].v[k];
341     }
342 #ifdef DEBUG
343     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);
344 #endif
345     objIdx ++;
346   }
347   CmiAssert(nObjs == objIdx);
348
349   double t = CkWallTimer();
350
351   quicksort(XDIR);
352   quicksort(YDIR);
353   quicksort(ZDIR);
354 #ifdef DEBUG
355   CmiPrintf("qsort time: %f\n", CkWallTimer() - t);
356 #endif
357
358   npartition = 0;
359   for (i=0; i<P; i++)
360     if (stats->procs[i].available == CmiTrue) npartition++;
361   partitions = new Partition[npartition];
362
363   double totalLoad = 0.0;
364   int minx, miny, minz, maxx, maxy, maxz;
365   minx = maxx= computeLoad[0].v[XDIR];
366   miny = maxy= computeLoad[0].v[YDIR];
367   minz = maxz= computeLoad[0].v[ZDIR];
368   for (i=1; i<nObjs; i++) {
369     totalLoad += computeLoad[i].load;
370     if (computeLoad[i].v[XDIR] < minx) minx = computeLoad[i].v[XDIR];
371     else if (computeLoad[i].v[XDIR] > maxx) maxx = computeLoad[i].v[XDIR];
372     if (computeLoad[i].v[YDIR] < miny) miny = computeLoad[i].v[YDIR];
373     else if (computeLoad[i].v[YDIR] > maxy) maxy = computeLoad[i].v[YDIR];
374     if (computeLoad[i].v[ZDIR] < minz) minz = computeLoad[i].v[ZDIR];
375     else if (computeLoad[i].v[ZDIR] > maxz) maxz = computeLoad[i].v[ZDIR];
376   }
377
378   top_partition.origin[XDIR] = minx;
379   top_partition.origin[YDIR] = miny;
380   top_partition.origin[ZDIR] = minz;
381   top_partition.corner[XDIR] = maxx;
382   top_partition.corner[YDIR] = maxy; 
383   top_partition.corner[ZDIR] = maxz;
384
385   top_partition.refno = 0;
386   top_partition.load = 0.0;
387   top_partition.count = nObjs;
388
389   // if we take background load into account
390   if (!_lb_args.ignoreBgLoad()) {
391     top_partition.bkpes.resize(0);
392     double total = totalLoad;
393     for (i=0; i<P; i++) {
394       if (!stats->procs[i].available) continue;
395       double bkload = stats->procs[i].bg_walltime;
396       total += bkload;
397     }
398     double averageLoad = total / npartition;
399     for (i=0; i<P; i++) {
400       if (!stats->procs[i].available) continue;
401       double bkload = stats->procs[i].bg_walltime;
402       if (bkload < averageLoad) top_partition.bkpes.push_back(i);
403       else CkPrintf("OrbLB Info> PE %d with %f background load will have 0 object.\n", i, bkload);
404     }
405     npartition = top_partition.bkpes.size();
406     // formally add these bg load to total load
407     for (i=0; i<npartition; i++) 
408       totalLoad += stats->procs[top_partition.bkpes[i]].bg_walltime; 
409     if (_lb_args.debug()>=2) {
410       CkPrintf("BG load: ");
411       for (i=0; i<P; i++)  CkPrintf(" %f", stats->procs[i].bg_walltime);
412       CkPrintf("\n");
413       CkPrintf("Partition BG load: ");
414       for (i=0; i<npartition; i++)  CkPrintf(" %f", stats->procs[top_partition.bkpes[i]].bg_walltime);
415       CkPrintf("\n");
416     }
417   }
418
419   top_partition.load = totalLoad;
420
421   currentp = 0;
422   refno = 0;
423
424   // recursively divide
425   rec_divide(npartition, top_partition);
426
427   // mapping partitions to nodes
428   mapPartitionsToNodes();
429
430   // this is for sanity check
431   int *num = new int[P];
432   for (i=0; i<P; i++) num[i] = 0;
433
434   for (i=0; i<nObjs; i++)
435   {
436     for (j=0; j<npartition; j++)
437       if (computeLoad[i].refno == partitions[j].refno)   {
438         computeLoad[i].partition = partitions+j;
439         num[j] ++;
440     }
441     CmiAssert(computeLoad[i].partition != NULL);
442   }
443
444   for (i=0; i<npartition; i++)
445     if (num[i] != partitions[i].count) 
446       CmiAbort("OrbLB: Compute counts don't agree!\n");
447
448   delete [] num;
449
450   // Save output
451   objIdx = 0;
452   for(int obj=0;obj<stats->n_objs;obj++) {
453       stats->to_proc[obj] = stats->from_proc[obj];
454       LDObjData &odata = stats->objData[obj];
455       if (odata.migratable == 0) { continue; }
456       int frompe = stats->from_proc[obj];
457       int tope = computeLoad[objIdx].partition->node;
458       if (frompe != tope) {
459         if (_lb_args.debug() >= 3) {
460               CkPrintf("[%d] Obj %d migrating from %d to %d\n",
461                      CkMyPe(),obj,frompe,tope);
462         }
463         stats->to_proc[obj] = tope;
464       }
465       objIdx ++;
466   }
467
468   // free memory
469   delete [] computeLoad;
470   for (i=0; i<3; i++) delete [] vArray[i];
471   delete [] partitions;
472
473   if (_lb_args.debug() >= 1)
474     CkPrintf("OrbLB finished time: %fs\n", CkWallTimer() - t);
475 #endif
476 }
477
478 #include "OrbLB.def.h"
479
480 /*@}*/