Changed to use macro
[charm.git] / src / ck-ldb / LBDatabase.C
1 /**
2  * \addtogroup CkLdb
3 */
4 /*@{*/
5
6 #include "converse.h"
7
8 /*
9  * This C++ file contains the Charm stub functions
10  */
11
12 #include "LBDatabase.h"
13 #include "LBSimulation.h"
14 #include "topology.h"
15
16 #include "limits.h"
17
18 #include "NullLB.h"
19
20 #define VEC_SIZE 500
21 #define IMB_TOLERANCE 1.1
22 #define IDLE_LOAD_TOLERANCE 0.3
23
24 struct AdaptiveData {
25   int iteration;
26   double max_load;
27   double avg_load;
28   double max_idle_load_ratio;
29   double idle_time;
30 };
31
32 struct AdaptiveLBDatabase {
33   std::vector<AdaptiveData> history_data;
34 } adaptive_lbdb;
35
36 struct AdaptiveLBInfo {
37   double max_avg_ratio;
38 };
39
40 struct AdaptiveLBStructure {
41   int lb_ideal_period;
42   int lb_calculated_period;
43   int lb_no_iterations;
44   int global_max_iter_no;
45   int global_recv_iter_counter;
46   bool in_progress;
47   double lb_strategy_cost;
48   double lb_migration_cost;
49   bool lb_period_informed;
50   bool doCommStrategy;
51   int lb_msg_send_no;
52   int lb_msg_recv_no;
53   int total_syncs_called;
54   int last_lb_type;
55   AdaptiveLBInfo greedy_info;
56   AdaptiveLBInfo refine_info;
57   AdaptiveLBInfo metis_info;
58 } adaptive_struct;
59
60
61 CkReductionMsg* lbDataCollection(int nMsg, CkReductionMsg** msgs) {
62   double lb_data[6];
63   lb_data[1] = 0.0;
64   lb_data[2] = 0.0;
65   lb_data[3] = 0.0;
66   lb_data[4] = 0.0;
67   lb_data[5] = 0.0;
68   for (int i = 0; i < nMsg; i++) {
69     CkAssert(msgs[i]->getSize() == 6*sizeof(double));
70     if (msgs[i]->getSize() != 6*sizeof(double)) {
71       CkPrintf("Error!!! Reduction not correct. Msg size is %d\n", msgs[i]->getSize());
72     }
73     double* m = (double *)msgs[i]->getData();
74     // Total count
75     lb_data[1] += m[1];
76     // Avg load
77     lb_data[2] += m[2];
78     // Max load
79     lb_data[3] = ((m[3] > lb_data[3])? m[3] : lb_data[3]);
80     // Avg idle
81     lb_data[4] += m[4];
82     // Max idle
83     lb_data[5] = ((m[5] > lb_data[5]) ? m[5] : lb_data[5]);
84     if (i == 0) {
85       // Iteration no
86       lb_data[0] = m[0];
87     }
88     if (m[0] != lb_data[0]) {
89       CkPrintf("Error!!! Reduction is intermingled between iteration %lf and\
90       %lf\n", lb_data[0], m[0]);
91     }
92   }
93   return CkReductionMsg::buildNew(6*sizeof(double), lb_data);
94 }
95
96 /*global*/ CkReduction::reducerType lbDataCollectionType;
97 /*initcall*/ void registerLBDataCollection(void) {
98   lbDataCollectionType = CkReduction::addReducer(lbDataCollection);
99 }
100
101 CkGroupID _lbdb;
102
103 CkpvDeclare(int, numLoadBalancers);  /**< num of lb created */
104 CkpvDeclare(int, hasNullLB);         /**< true if NullLB is created */
105 CkpvDeclare(int, lbdatabaseInited);  /**< true if lbdatabase is inited */
106
107 // command line options
108 CkLBArgs _lb_args;
109 int _lb_predict=0;
110 int _lb_predict_delay=10;
111 int _lb_predict_window=20;
112
113 // registry class stores all load balancers linked and created at runtime
114 class LBDBRegistry {
115 friend class LBDBInit;
116 friend class LBDatabase;
117 private:
118   // table for all available LBs linked in
119   struct LBDBEntry {
120     const char *name;
121     LBCreateFn  cfn;
122     LBAllocFn   afn;
123     const char *help;
124     int         shown;          // if 0, donot show in help page
125     LBDBEntry(): name(0), cfn(0), afn(0), help(0), shown(1) {}
126     LBDBEntry(int) {}
127     LBDBEntry(const char *n, LBCreateFn cf, LBAllocFn af, 
128               const char *h, int show=1):
129       name(n), cfn(cf), afn(af), help(h), shown(show) {};
130   };
131   CkVec<LBDBEntry> lbtables;            // a list of available LBs linked
132   CkVec<const char *>   compile_lbs;    // load balancers at compile time
133   CkVec<const char *>   runtime_lbs;    // load balancers at run time
134 public:
135   LBDBRegistry() {}
136   void displayLBs()
137   {
138     CmiPrintf("\nAvailable load balancers:\n");
139     for (int i=0; i<lbtables.length(); i++) {
140       LBDBEntry &entry = lbtables[i];
141       if (entry.shown) CmiPrintf("* %s: %s\n", entry.name, entry.help);
142     }
143     CmiPrintf("\n");
144   }
145   void addEntry(const char *name, LBCreateFn fn, LBAllocFn afn, const char *help, int shown) {
146     lbtables.push_back(LBDBEntry(name, fn, afn, help, shown));
147   }
148   void addCompiletimeBalancer(const char *name) {
149     compile_lbs.push_back(name); 
150   }
151   void addRuntimeBalancer(const char *name) {
152     runtime_lbs.push_back(name); 
153   }
154   LBCreateFn search(const char *name) {
155     char *ptr = strpbrk((char *)name, ":,");
156     int slen = ptr!=NULL?ptr-name:strlen(name);
157     for (int i=0; i<lbtables.length(); i++)
158       if (0==strncmp(name, lbtables[i].name, slen)) return lbtables[i].cfn;
159     return NULL;
160   }
161   LBAllocFn getLBAllocFn(const char *name) {
162     char *ptr = strpbrk((char *)name, ":,");
163     int slen = ptr-name;
164     for (int i=0; i<lbtables.length(); i++)
165       if (0==strncmp(name, lbtables[i].name, slen)) return lbtables[i].afn;
166     return NULL;
167   }
168 };
169
170 static LBDBRegistry lbRegistry;
171
172 void LBDefaultCreate(const char *lbname)
173 {
174   lbRegistry.addCompiletimeBalancer(lbname);
175 }
176
177 // default is to show the helper
178 void LBRegisterBalancer(const char *name, LBCreateFn fn, LBAllocFn afn, const char *help, int shown)
179 {
180   lbRegistry.addEntry(name, fn, afn, help, shown);
181 }
182
183 LBAllocFn getLBAllocFn(char *lbname) {
184     return lbRegistry.getLBAllocFn(lbname);
185 }
186
187 LBCreateFn getLBCreateFn(const char *lbname) {
188     return lbRegistry.search(lbname);
189 }
190 // create a load balancer group using the strategy name
191 static void createLoadBalancer(const char *lbname)
192 {
193     LBCreateFn fn = lbRegistry.search(lbname);
194     if (!fn) {    // invalid lb name
195       CmiPrintf("Abort: Unknown load balancer: '%s'!\n", lbname);
196       lbRegistry.displayLBs();    // display help page
197       CkAbort("Abort");
198     }
199     // invoke function to create load balancer 
200     fn();
201 }
202
203 // mainchare
204 LBDBInit::LBDBInit(CkArgMsg *m)
205 {
206 #if CMK_LBDB_ON
207   _lbdb = CProxy_LBDatabase::ckNew();
208
209   // runtime specified load balancer
210   if (lbRegistry.runtime_lbs.size() > 0) {
211     for (int i=0; i<lbRegistry.runtime_lbs.size(); i++) {
212       const char *balancer = lbRegistry.runtime_lbs[i];
213       createLoadBalancer(balancer);
214     }
215   }
216   else if (lbRegistry.compile_lbs.size() > 0) {
217     for (int i=0; i<lbRegistry.compile_lbs.size(); i++) {
218       const char* balancer = lbRegistry.compile_lbs[i];
219       createLoadBalancer(balancer);
220     }
221   }
222   else {
223     // NullLB is the default when none of above lb created
224     // note user may create his own load balancer in his code manually like
225     // in NAMD, but never mind NullLB can disable itself if there is 
226     // a non NULL LB.
227     createLoadBalancer("NullLB");
228   }
229
230   // simulation mode
231   if (LBSimulation::doSimulation) {
232     CmiPrintf("Charm++> Entering Load Balancer Simulation Mode ... \n");
233     CProxy_LBDatabase(_lbdb).ckLocalBranch()->StartLB();
234   }
235 #endif
236   delete m;
237 }
238
239 // called from init.C
240 void _loadbalancerInit()
241 {
242   CkpvInitialize(int, lbdatabaseInited);
243   CkpvAccess(lbdatabaseInited) = 0;
244   CkpvInitialize(int, numLoadBalancers);
245   CkpvAccess(numLoadBalancers) = 0;
246   CkpvInitialize(int, hasNullLB);
247   CkpvAccess(hasNullLB) = 0;
248
249   char **argv = CkGetArgv();
250   char *balancer = NULL;
251   CmiArgGroup("Charm++","Load Balancer");
252   while (CmiGetArgStringDesc(argv, "+balancer", &balancer, "Use this load balancer")) {
253     if (CkMyRank() == 0)                
254       lbRegistry.addRuntimeBalancer(balancer);   /* lbRegistry is a static */
255   }
256
257   // set up init value for LBPeriod time in seconds
258   // it can also be set by calling LDSetLBPeriod()
259   CmiGetArgDoubleDesc(argv,"+LBPeriod", &_lb_args.lbperiod(),"the minimum time period in seconds allowed for two consecutive automatic load balancing");
260   _lb_args.loop() = CmiGetArgFlagDesc(argv, "+LBLoop", "Use multiple load balancing strategies in loop");
261
262   // now called in cldb.c: CldModuleGeneralInit()
263   // registerLBTopos();
264   CmiGetArgStringDesc(argv, "+LBTopo", &_lbtopo, "define load balancing topology");
265   //Read the K parameter for RefineKLB
266   CmiGetArgIntDesc(argv, "+LBNumMoves", &_lb_args.percentMovesAllowed() , "Percentage of chares to be moved (used by RefineKLB) [0-100]");
267
268   /**************** FUTURE PREDICTOR ****************/
269   _lb_predict = CmiGetArgFlagDesc(argv, "+LBPredictor", "Turn on LB future predictor");
270   CmiGetArgIntDesc(argv, "+LBPredictorDelay", &_lb_predict_delay, "Number of balance steps before learning a model");
271   CmiGetArgIntDesc(argv, "+LBPredictorWindow", &_lb_predict_window, "Number of steps to use to learn a model");
272   if (_lb_predict_window < _lb_predict_delay) {
273     CmiPrintf("LB> [%d] Argument LBPredictorWindow (%d) less than LBPredictorDelay (%d) , fixing\n", CkMyPe(), _lb_predict_window, _lb_predict_delay);
274     _lb_predict_delay = _lb_predict_window;
275   }
276
277   /******************* SIMULATION *******************/
278   // get the step number at which to dump the LB database
279   CmiGetArgIntDesc(argv, "+LBVersion", &_lb_args.lbversion(), "LB database file version number");
280   CmiGetArgIntDesc(argv, "+LBCentPE", &_lb_args.central_pe(), "CentralLB processor");
281   int _lb_dump_activated = 0;
282   if (CmiGetArgIntDesc(argv, "+LBDump", &LBSimulation::dumpStep, "Dump the LB state from this step"))
283     _lb_dump_activated = 1;
284   if (_lb_dump_activated && LBSimulation::dumpStep < 0) {
285     CmiPrintf("LB> Argument LBDump (%d) negative, setting to 0\n",LBSimulation::dumpStep);
286     LBSimulation::dumpStep = 0;
287   }
288   CmiGetArgIntDesc(argv, "+LBDumpSteps", &LBSimulation::dumpStepSize, "Dump the LB state for this amount of steps");
289   if (LBSimulation::dumpStepSize <= 0) {
290     CmiPrintf("LB> Argument LBDumpSteps (%d) too small, setting to 1\n",LBSimulation::dumpStepSize);
291     LBSimulation::dumpStepSize = 1;
292   }
293   CmiGetArgStringDesc(argv, "+LBDumpFile", &LBSimulation::dumpFile, "Set the LB state file name");
294   // get the simulation flag and number. Now the flag can also be avoided by the presence of the number
295   LBSimulation::doSimulation = CmiGetArgIntDesc(argv, "+LBSim", &LBSimulation::simStep, "Read LB state from LBDumpFile since this step");
296   // check for stupid LBSim parameter
297   if (LBSimulation::doSimulation && LBSimulation::simStep < 0) {
298     CmiPrintf("LB> Argument LBSim (%d) invalid, should be >= 0\n");
299     CkExit();
300     return;
301   }
302   CmiGetArgIntDesc(argv, "+LBSimSteps", &LBSimulation::simStepSize, "Read LB state for this number of steps");
303   if (LBSimulation::simStepSize <= 0) {
304     CmiPrintf("LB> Argument LBSimSteps (%d) too small, setting to 1\n",LBSimulation::simStepSize);
305     LBSimulation::simStepSize = 1;
306   }
307
308
309   LBSimulation::simProcs = 0;
310   CmiGetArgIntDesc(argv, "+LBSimProcs", &LBSimulation::simProcs, "Number of target processors.");
311
312   LBSimulation::showDecisionsOnly = 
313     CmiGetArgFlagDesc(argv, "+LBShowDecisions",
314                       "Write to File: Load Balancing Object to Processor Map decisions during LB Simulation");
315
316   // force a global barrier after migration done
317   _lb_args.syncResume() = CmiGetArgFlagDesc(argv, "+LBSyncResume", 
318                   "LB performs a barrier after migration is finished");
319
320   // both +LBDebug and +LBDebug level should work
321   if (!CmiGetArgIntDesc(argv, "+LBDebug", &_lb_args.debug(), 
322                                           "Turn on LB debugging printouts"))
323     _lb_args.debug() = CmiGetArgFlagDesc(argv, "+LBDebug", 
324                                              "Turn on LB debugging printouts");
325
326   // getting the size of the team with +teamSize
327   if (!CmiGetArgIntDesc(argv, "+teamSize", &_lb_args.teamSize(), 
328                                           "Team size"))
329     _lb_args.teamSize() = 1;
330
331   // ask to print summary/quality of load balancer
332   _lb_args.printSummary() = CmiGetArgFlagDesc(argv, "+LBPrintSummary",
333                 "Print load balancing result summary");
334
335   // to ignore baclground load
336   _lb_args.ignoreBgLoad() = CmiGetArgFlagDesc(argv, "+LBNoBackground", 
337                       "Load balancer ignores the background load.");
338 #ifdef __BIGSIM__
339   _lb_args.ignoreBgLoad() = 1;
340 #endif
341   _lb_args.migObjOnly() = CmiGetArgFlagDesc(argv, "+LBObjOnly", 
342                       "Only load balancing migratable objects, ignoring all others.");
343   if (_lb_args.migObjOnly()) _lb_args.ignoreBgLoad() = 1;
344
345   // assume all CPUs are identical
346   _lb_args.testPeSpeed() = CmiGetArgFlagDesc(argv, "+LBTestPESpeed", 
347                       "Load balancer test all CPUs speed.");
348   _lb_args.samePeSpeed() = CmiGetArgFlagDesc(argv, "+LBSameCpus", 
349                       "Load balancer assumes all CPUs are of same speed.");
350   if (!_lb_args.testPeSpeed()) _lb_args.samePeSpeed() = 1;
351
352   _lb_args.useCpuTime() = CmiGetArgFlagDesc(argv, "+LBUseCpuTime", 
353                       "Load balancer uses CPU time instead of wallclock time.");
354
355   // turn instrumentation off at startup
356   _lb_args.statsOn() = !CmiGetArgFlagDesc(argv, "+LBOff",
357                         "Turn load balancer instrumentation off");
358
359   // turn instrumentation of communicatin off at startup
360   _lb_args.traceComm() = !CmiGetArgFlagDesc(argv, "+LBCommOff",
361                 "Turn load balancer instrumentation of communication off");
362
363   // set alpha and beeta
364   _lb_args.alpha() = PER_MESSAGE_SEND_OVERHEAD_DEFAULT;
365   _lb_args.beeta() = PER_BYTE_SEND_OVERHEAD_DEFAULT;
366   CmiGetArgDoubleDesc(argv,"+LBAlpha", &_lb_args.alpha(),
367                            "per message send overhead");
368   CmiGetArgDoubleDesc(argv,"+LBBeta", &_lb_args.beeta(),
369                            "per byte send overhead");
370
371   if (CkMyPe() == 0) {
372     if (_lb_args.debug()) {
373       CmiPrintf("CharmLB> Verbose level %d, load balancing period: %g seconds\n", _lb_args.debug(), _lb_args.lbperiod());
374     }
375     if (_lb_args.debug() > 1) {
376       CmiPrintf("CharmLB> Topology %s alpha: %es beta: %es.\n", _lbtopo, _lb_args.alpha(), _lb_args.beeta());
377     }
378     if (_lb_args.printSummary())
379       CmiPrintf("CharmLB> Load balancer print summary of load balancing result.\n");
380     if (_lb_args.ignoreBgLoad())
381       CmiPrintf("CharmLB> Load balancer ignores processor background load.\n");
382     if (_lb_args.samePeSpeed())
383       CmiPrintf("CharmLB> Load balancer assumes all CPUs are same.\n");
384     if (_lb_args.useCpuTime())
385       CmiPrintf("CharmLB> Load balancer uses CPU time instead of wallclock time.\n");
386     if (LBSimulation::doSimulation)
387       CmiPrintf("CharmLB> Load balancer running in simulation mode on file '%s' version %d.\n", LBSimulation::dumpFile, _lb_args.lbversion());
388     if (_lb_args.statsOn()==0)
389       CkPrintf("CharmLB> Load balancing instrumentation is off.\n");
390     if (_lb_args.traceComm()==0)
391       CkPrintf("CharmLB> Load balancing instrumentation for communication is off.\n");
392     if (_lb_args.migObjOnly())
393       CkPrintf("LB> Load balancing strategy ignores non-migratable objects.\n");
394   }
395 }
396
397 int LBDatabase::manualOn = 0;
398 char *LBDatabase::avail_vector = NULL;
399 CmiNodeLock avail_vector_lock;
400
401 static LBRealType * _expectedLoad = NULL;
402
403 void LBDatabase::initnodeFn()
404 {
405   int proc;
406   int num_proc = CkNumPes();
407   avail_vector= new char[num_proc];
408   for(proc = 0; proc < num_proc; proc++)
409       avail_vector[proc] = 1;
410   avail_vector_lock = CmiCreateLock();
411
412   _expectedLoad = new LBRealType[num_proc];
413   for (proc=0; proc<num_proc; proc++) _expectedLoad[proc]=0.0;
414 }
415
416 // called my constructor
417 void LBDatabase::init(void) 
418 {
419   //thisProxy = CProxy_LBDatabase(thisgroup);
420   myLDHandle = LDCreate();
421   mystep = 0;
422   nloadbalancers = 0;
423   new_ld_balancer = 0;
424
425   CkpvAccess(lbdatabaseInited) = 1;
426 #if CMK_LBDB_ON
427   if (manualOn) TurnManualLBOn();
428 #endif
429   
430   max_load_vec.resize(VEC_SIZE, 0.0);
431   total_load_vec.resize(VEC_SIZE, 0.0);
432   total_contrib_vec.resize(VEC_SIZE, 0.0);
433   max_iteration = -1;
434
435   // If metabalancer enabled, initialize the variables
436   adaptive_struct.lb_ideal_period =  INT_MAX;
437   adaptive_struct.lb_calculated_period = INT_MAX;
438   adaptive_struct.lb_no_iterations = -1;
439   adaptive_struct.global_max_iter_no = 0;
440   adaptive_struct.global_recv_iter_counter = 0;
441   adaptive_struct.in_progress = false;
442   adaptive_struct.lb_strategy_cost = 0.0;
443   adaptive_struct.lb_migration_cost = 0.0;
444   adaptive_struct.lb_msg_send_no = 0;
445   adaptive_struct.lb_msg_recv_no = 0;
446   adaptive_struct.total_syncs_called = 0;
447   adaptive_struct.last_lb_type = -1;
448
449   is_prev_lb_refine = -1;
450 }
451
452 LBDatabase::LastLBInfo::LastLBInfo()
453 {
454   expectedLoad = _expectedLoad;
455 }
456
457 void LBDatabase::get_avail_vector(char * bitmap) {
458     CmiAssert(bitmap && avail_vector);
459     const int num_proc = CkNumPes();
460     for(int proc = 0; proc < num_proc; proc++){
461       bitmap[proc] = avail_vector[proc];
462     }
463 }
464
465 // new_ld == -1(default) : calcualte a new ld
466 //           -2 : ignore new ld
467 //           >=0: given a new ld
468 void LBDatabase::set_avail_vector(char * bitmap, int new_ld){
469     int assigned = 0;
470     const int num_proc = CkNumPes();
471     if (new_ld == -2) assigned = 1;
472     else if (new_ld >= 0) {
473       CmiAssert(new_ld < num_proc);
474       new_ld_balancer = new_ld;
475       assigned = 1;
476     }
477     CmiAssert(bitmap && avail_vector);
478     for(int count = 0; count < num_proc; count++){
479         avail_vector[count] = bitmap[count];
480         if((bitmap[count] == 1) && !assigned){
481             new_ld_balancer = count;
482             assigned = 1;
483         }
484     }
485 }
486
487 // called in CreateFooLB() when multiple load balancers are created
488 // on PE0, BaseLB of each load balancer applies a ticket number
489 // and broadcast the ticket number to all processors
490 int LBDatabase::getLoadbalancerTicket()  { 
491   int seq = nloadbalancers;
492   nloadbalancers ++;
493   loadbalancers.resize(nloadbalancers); 
494   loadbalancers[seq] = NULL;
495   return seq; 
496 }
497
498 void LBDatabase::addLoadbalancer(BaseLB *lb, int seq) {
499 //  CmiPrintf("[%d] addLoadbalancer for seq %d\n", CkMyPe(), seq);
500   if (seq == -1) return;
501   if (CkMyPe() == 0) {
502     CmiAssert(seq < nloadbalancers);
503     if (loadbalancers[seq]) {
504       CmiPrintf("Duplicate load balancer created at %d\n", seq);
505       CmiAbort("LBDatabase");
506     }
507   }
508   else
509     nloadbalancers ++;
510   loadbalancers.resize(seq+1);
511   loadbalancers[seq] = lb;
512 }
513
514 // switch strategy in order
515 void LBDatabase::nextLoadbalancer(int seq) {
516   if (seq == -1) return;                // -1 means this is the only LB
517   int next = seq+1;
518   if (_lb_args.loop()) {
519     if (next == nloadbalancers) next = 0;
520   }
521   else {
522     if (next == nloadbalancers) next --;  // keep using the last one
523   }
524   if (seq != next) {
525     loadbalancers[seq]->turnOff();
526     CmiAssert(loadbalancers[next]);
527     loadbalancers[next]->turnOn();
528   }
529 }
530
531 // return the seq-th load balancer string name of
532 // it can be specified in either compile time or runtime
533 // runtime has higher priority
534 const char *LBDatabase::loadbalancer(int seq) {
535   if (lbRegistry.runtime_lbs.length()) {
536     CmiAssert(seq < lbRegistry.runtime_lbs.length());
537     return lbRegistry.runtime_lbs[seq];
538   }
539   else {
540     CmiAssert(seq < lbRegistry.compile_lbs.length());
541     return lbRegistry.compile_lbs[seq];
542   }
543 }
544
545 void LBDatabase::pup(PUP::er& p)
546
547         IrrGroup::pup(p); 
548         // the memory should be already allocated
549         int np;
550         if (!p.isUnpacking()) np = CkNumPes();
551         p|np;
552         CmiAssert(avail_vector);
553         // in case number of processors changes
554         if (p.isUnpacking() && np > CkNumPes()) {
555                 CmiLock(avail_vector_lock);
556                 delete [] avail_vector;
557                 avail_vector = new char[np];
558                 for (int i=0; i<np; i++) avail_vector[i] = 1;
559                 CmiUnlock(avail_vector_lock);
560         }
561         p(avail_vector, np);
562         p|mystep;
563         if(p.isUnpacking()) nloadbalancers = 0;
564 }
565
566
567 void LBDatabase::EstObjLoad(const LDObjHandle &_h, double cputime)
568 {
569 #if CMK_LBDB_ON
570   LBDB *const db = (LBDB*)(_h.omhandle.ldb.handle);
571   LBObj *const obj = db->LbObj(_h);
572
573   CmiAssert(obj != NULL);
574   obj->setTiming(cputime);
575 #endif
576 }
577
578 void LBDatabase::ResumeClients() {
579   // If metabalancer enabled, initialize the variables
580   adaptive_lbdb.history_data.clear();
581
582   adaptive_struct.lb_ideal_period =  INT_MAX;
583   adaptive_struct.lb_calculated_period = INT_MAX;
584   adaptive_struct.lb_no_iterations = -1;
585   adaptive_struct.global_max_iter_no = 0;
586   adaptive_struct.global_recv_iter_counter = 0;
587   adaptive_struct.in_progress = false;
588   adaptive_struct.lb_strategy_cost = 0.0;
589   adaptive_struct.lb_migration_cost = 0.0;
590   adaptive_struct.lb_msg_send_no = 0;
591   adaptive_struct.lb_msg_recv_no = 0;
592   adaptive_struct.total_syncs_called = 0;
593   
594   max_load_vec.clear();
595   total_load_vec.clear();
596   total_contrib_vec.clear();
597
598   max_load_vec.resize(VEC_SIZE, 0.0);
599   total_load_vec.resize(VEC_SIZE, 0.0);
600   total_contrib_vec.resize(VEC_SIZE, 0.0);
601
602   LDResumeClients(myLDHandle);
603 }
604
605 bool LBDatabase::AddLoad(int iteration, double load) {
606   total_contrib_vec[iteration]++;
607   adaptive_struct.total_syncs_called++;
608   //CkPrintf("At PE %d Total contribution for iteration %d is %lf total objs %d\n", CkMyPe(), iteration,
609   //total_contrib_vec[iteration], getLBDB()->ObjDataCount());
610
611   if (iteration > adaptive_struct.lb_no_iterations) {
612     adaptive_struct.lb_no_iterations = iteration;
613   }
614   total_load_vec[iteration] += load;
615  // if (max_load_vec[iteration] < load) {
616  //   max_load_vec[iteration] = load;
617  // }
618   if (total_contrib_vec[iteration] == getLBDB()->ObjDataCount()) {
619     double idle_time;
620     IdleTime(&idle_time);
621     //CkPrintf("[%d] Idle time %lf for iteration %d\n", CkMyPe(), idle_time, iteration);
622     // Skips the 0th iteration collection of stats hence...
623     idle_time = idle_time * getLBDB()->ObjDataCount() /
624        (adaptive_struct.total_syncs_called + getLBDB()->ObjDataCount());
625
626     double lb_data[6];
627     lb_data[0] = iteration;
628     lb_data[1] = 1;
629     lb_data[2] = total_load_vec[iteration];
630     //lb_data[2] = max_load_vec[iteration];
631     lb_data[3] = total_load_vec[iteration];
632     //lb_data[3] = getLBDB()->ObjDataCount();
633     lb_data[4] = idle_time;
634     if (total_load_vec[iteration] == 0.0) {
635       lb_data[5] = idle_time;
636     } else {
637       lb_data[5] = idle_time/total_load_vec[iteration];
638     }
639
640    // CkPrintf("[%d] sends total load %lf idle time %lf ratio of idle/load %lf at iter %d\n", CkMyPe(),
641    //     total_load_vec[iteration], idle_time,
642    //     idle_time/total_load_vec[iteration], adaptive_struct.lb_no_iterations);
643
644     CkCallback cb(CkIndex_LBDatabase::ReceiveMinStats((CkReductionMsg*)NULL), thisProxy[0]);
645     contribute(6*sizeof(double), lb_data, lbDataCollectionType, cb);
646   }
647   return true;
648 }
649
650 void LBDatabase::ReceiveMinStats(CkReductionMsg *msg) {
651   double* load = (double *) msg->getData();
652   double avg = load[2]/load[1];
653   double max = load[3];
654   double avg_idle = load[4]/load[1];
655   double max_idle_load_ratio = load[5];
656   int iteration_n = load[0];
657   CkPrintf("** [%d] Iteration Avg load: %lf Max load: %lf Avg Idle : %lf Max Idle : %lf for %lf procs\n",iteration_n, avg, max, avg_idle, max_idle_load_ratio, load[1]);
658   delete msg;
659  
660   // Store the data for this iteration
661   adaptive_struct.lb_no_iterations = iteration_n;
662   AdaptiveData data;
663   data.iteration = adaptive_struct.lb_no_iterations;
664   data.max_load = max;
665   data.avg_load = avg;
666   data.max_idle_load_ratio = max_idle_load_ratio;
667   data.idle_time = avg_idle;
668   adaptive_lbdb.history_data.push_back(data);
669
670   // If lb period inform is in progress, dont inform again
671   if (adaptive_struct.in_progress) {
672     return;
673   }
674
675 //  if (adaptive_struct.lb_period_informed) {
676 //    return;
677 //  }
678
679   // If the max/avg ratio is greater than the threshold and also this is not the
680   // step immediately after load balancing, carry out load balancing
681   //if (max/avg >= 1.1 && adaptive_lbdb.history_data.size() > 4) {
682   int tmp1;
683   double tmp2;
684   GetPrevLBData(tmp1, tmp2);
685   double tolerate_imb = IMB_TOLERANCE * tmp2;
686
687   if ((max_idle_load_ratio >= IDLE_LOAD_TOLERANCE || max/avg >= tolerate_imb) && adaptive_lbdb.history_data.size() > 4) {
688     CkPrintf("Carry out load balancing step at iter max/avg(%lf) and max_idle_load_ratio ratio (%lf)\n", max/avg, max_idle_load_ratio);
689 //    if (!adaptive_struct.lb_period_informed) {
690 //      // Just for testing
691 //      adaptive_struct.lb_calculated_period = 40;
692 //      adaptive_struct.lb_period_informed = true;
693 //      thisProxy.LoadBalanceDecision(adaptive_struct.lb_calculated_period);
694 //      return;
695 //    }
696
697
698
699     // If the new lb period is less than current set lb period
700     if (adaptive_struct.lb_calculated_period > iteration_n + 1) {
701       if (max/avg < tolerate_imb) {
702         adaptive_struct.doCommStrategy = true;
703         CkPrintf("No load imbalance but idle time\n");
704       } else {
705         adaptive_struct.doCommStrategy = false;
706         CkPrintf("load imbalance \n");
707       }
708       adaptive_struct.lb_calculated_period = iteration_n + 1;
709       adaptive_struct.lb_period_informed = true;
710       adaptive_struct.in_progress = true;
711       CkPrintf("Informing everyone the lb period is %d\n",
712           adaptive_struct.lb_calculated_period);
713       thisProxy.LoadBalanceDecision(adaptive_struct.lb_msg_send_no++, adaptive_struct.lb_calculated_period);
714     }
715     return;
716   }
717
718   // Generate the plan for the adaptive strategy
719   int period;
720   if (generatePlan(period)) {
721     //CkPrintf("Carry out load balancing step at iter\n");
722
723     // If the new lb period is less than current set lb period
724     if (adaptive_struct.lb_calculated_period > period) {
725       adaptive_struct.doCommStrategy = false;
726       adaptive_struct.lb_calculated_period = period;
727       adaptive_struct.in_progress = true;
728       adaptive_struct.lb_period_informed = true;
729       CkPrintf("Informing everyone the lb period is %d\n",
730           adaptive_struct.lb_calculated_period);
731       thisProxy.LoadBalanceDecision(adaptive_struct.lb_msg_send_no++, adaptive_struct.lb_calculated_period);
732     }
733   }
734 }
735
736 bool LBDatabase::generatePlan(int& period) {
737   if (adaptive_lbdb.history_data.size() <= 8) {
738     return false;
739   }
740
741   // Some heuristics for lbperiod
742   // If constant load or almost constant,
743   // then max * new_lb_period > avg * new_lb_period + lb_cost
744   double max = 0.0;
745   double avg = 0.0;
746   AdaptiveData data;
747   for (int i = 0; i < adaptive_lbdb.history_data.size(); i++) {
748     data = adaptive_lbdb.history_data[i];
749     max += data.max_load;
750     avg += data.avg_load;
751     CkPrintf("max (%d, %lf) avg (%d, %lf)\n", i, data.max_load, i, data.avg_load);
752   }
753 //  max /= (adaptive_struct.lb_no_iterations - adaptive_lbdb.history_data[0].iteration);
754 //  avg /= (adaptive_struct.lb_no_iterations - adaptive_lbdb.history_data[0].iteration);
755 //
756 //  adaptive_struct.lb_ideal_period = (adaptive_struct.lb_strategy_cost +
757 //  adaptive_struct.lb_migration_cost) / (max - avg);
758 //  CkPrintf("max : %lf, avg: %lf, strat cost: %lf, migration_cost: %lf, idealperiod : %d \n",
759 //      max, avg, adaptive_struct.lb_strategy_cost, adaptive_struct.lb_migration_cost, adaptive_struct.lb_ideal_period);
760 //
761
762   // If linearly varying load, then find lb_period
763   // area between the max and avg curve 
764   // If we can attain perfect balance, then the new load is close to the
765   // average. Hence we pass 1, else pass in some other value which would be the
766   // new max_load after load balancing.
767   int tmp1;
768   double tmp2;
769   GetPrevLBData(tmp1, tmp2);
770   
771   double tolerate_imb = tmp2;
772   if (max/avg < tolerate_imb) {
773     tolerate_imb = 1.0;
774   }
775
776   return getPeriodForStrategy(tolerate_imb, 1, period);
777
778 //  int refine_period, scratch_period;
779 //  bool obtained_refine, obtained_scratch;
780 //  obtained_refine = getPeriodForStrategy(1, 1, refine_period);
781 //  obtained_scratch = getPeriodForStrategy(1, 1, scratch_period);
782 //
783 //  if (obtained_refine) {
784 //    if (!obtained_scratch) {
785 //      period = refine_period;
786 //      adaptive_struct.isRefine = true;
787 //      return true;
788 //    }
789 //    if (scratch_period < 1.1*refine_period) {
790 //      adaptive_struct.isRefine = false;
791 //      period = scratch_period;
792 //      return true;
793 //    }
794 //    period = refine_period;
795 //    adaptive_struct.isRefine = true;
796 //    return true;
797 //  }
798 //
799 //  if (obtained_scratch) {
800 //    period = scratch_period;
801 //    adaptive_struct.isRefine = false;
802 //    return true;
803 //  }
804 //  return false;
805 }
806
807 bool LBDatabase::getPeriodForStrategy(double new_load_percent, double overhead_percent, int& period) {
808   double mslope, aslope, mc, ac;
809   getLineEq(new_load_percent, aslope, ac, mslope, mc);
810   CkPrintf("new load percent %lf\n", new_load_percent);
811   CkPrintf("\n max: %fx + %f; avg: %fx + %f\n", mslope, mc, aslope, ac);
812   double a = (mslope - aslope)/2;
813   double b = (mc - ac);
814   double c = -(adaptive_struct.lb_strategy_cost +
815       adaptive_struct.lb_migration_cost) * overhead_percent;
816   //c = -2.5;
817   bool got_period = getPeriodForLinear(a, b, c, period);
818   if (!got_period) {
819     return false;
820   }
821   
822   if (mslope < 0) {
823     if (period > (-mc/mslope)) {
824       CkPrintf("Max < 0 Period set when max load is -ve\n");
825       return false;
826     }
827   }
828
829   if (aslope < 0) {
830     if (period > (-ac/aslope)) {
831       CkPrintf("Avg < 0 Period set when avg load is -ve\n");
832       return false;
833     }
834   }
835
836   int intersection_t = (mc-ac) / (aslope - mslope);
837   if (intersection_t > 0 && period > intersection_t) {
838     CkPrintf("Avg | Max Period set when curves intersect\n");
839     return false;
840   }
841   return true;
842 }
843
844 bool LBDatabase::getPeriodForLinear(double a, double b, double c, int& period) {
845   CkPrintf("Quadratic Equation %lf X^2 + %lf X + %lf\n", a, b, c);
846   if (a == 0.0) {
847     period = (-c / b);
848     CkPrintf("Ideal period for linear load %d\n", period);
849     return true;
850   }
851   int x;
852   double t = (b * b) - (4*a*c);
853   if (t < 0) {
854     CkPrintf("(b * b) - (4*a*c) is -ve sqrt : %lf\n", sqrt(t));
855     return false;
856   }
857   t = (-b + sqrt(t)) / (2*a);
858   x = t;
859   if (x < 0) {
860     CkPrintf("boo!!! x (%d) < 0\n", x);
861     x = 0;
862     return false;
863   }
864   period = x;
865   CkPrintf("Ideal period for linear load %d\n", period);
866   return true;
867 }
868
869 bool LBDatabase::getLineEq(double new_load_percent, double& aslope, double& ac, double& mslope, double& mc) {
870   int total = adaptive_lbdb.history_data.size();
871   int iterations = 1 + adaptive_lbdb.history_data[total - 1].iteration -
872       adaptive_lbdb.history_data[0].iteration;
873   double a1 = 0;
874   double m1 = 0;
875   double a2 = 0;
876   double m2 = 0;
877   AdaptiveData data;
878   int i = 0;
879   for (i = 0; i < total/2; i++) {
880     data = adaptive_lbdb.history_data[i];
881     m1 += data.max_load;
882     a1 += data.avg_load;
883   }
884   m1 /= i;
885   a1 = (a1 * new_load_percent) / i;
886
887   for (i = total/2; i < total; i++) {
888     data = adaptive_lbdb.history_data[i];
889     m2 += data.max_load;
890     a2 += data.avg_load;
891   }
892   m2 /= (i - total/2);
893   a2 = (a2 * new_load_percent) / (i - total/2);
894
895   aslope = 2 * (a2 - a1) / iterations;
896   mslope = 2 * (m2 - m1) / iterations;
897   ac = adaptive_lbdb.history_data[0].avg_load * new_load_percent;
898   mc = adaptive_lbdb.history_data[0].max_load;
899
900   //ac = (adaptive_lbdb.history_data[1].avg_load * new_load_percent - aslope);
901   //mc = (adaptive_lbdb.history_data[1].max_load - mslope);
902
903   return true;
904 }
905
906 void LBDatabase::LoadBalanceDecision(int req_no, int period) {
907   if (req_no < adaptive_struct.lb_msg_recv_no) {
908     CkPrintf("Error!!! Received a request which was already sent or old\n");
909     return;
910   }
911   //CkPrintf("[%d] Load balance decision made cur iteration: %d period:%d state: %d\n",CkMyPe(), adaptive_struct.lb_no_iterations, period, local_state);
912   adaptive_struct.lb_ideal_period = period;
913   //local_state = ON;
914   adaptive_struct.lb_msg_recv_no = req_no;
915   thisProxy[0].ReceiveIterationNo(req_no, adaptive_struct.lb_no_iterations);
916 }
917
918 void LBDatabase::LoadBalanceDecisionFinal(int req_no, int period) {
919   if (req_no < adaptive_struct.lb_msg_recv_no) {
920     return;
921   }
922 //  CkPrintf("[%d] Final Load balance decision made cur iteration: %d period:%d \n",CkMyPe(), adaptive_struct.lb_no_iterations, period);
923   adaptive_struct.lb_ideal_period = period;
924   LDOMAdaptResumeSync(myLDHandle, period);
925
926 //  if (local_state == ON) {
927 //    local_state = DECIDED;
928 //    return;
929 //  }
930
931   // If the state is PAUSE, then its waiting for the final decision from central
932   // processor. If the decision is that the ideal period is in the future,
933   // resume. If the ideal period is now, then carry out load balancing.
934 //  if (local_state == PAUSE) {
935 //    if (adaptive_struct.lb_no_iterations < adaptive_struct.lb_ideal_period) {
936 //      local_state = DECIDED;
937 //      //SendMinStats();
938 //      //FIX ME!!! ResumeClients(0);
939 //    } else {
940 //      local_state = LOAD_BALANCE;
941 //      //FIX ME!!! ProcessAtSync();
942 //    }
943 //    return;
944 //  }
945 //  CkPrintf("Error!!! Final decision received but the state is invalid %d\n", local_state);
946 }
947
948
949 void LBDatabase::ReceiveIterationNo(int req_no, int local_iter_no) {
950   CmiAssert(CkMyPe() == 0);
951
952   adaptive_struct.global_recv_iter_counter++;
953   if (local_iter_no > adaptive_struct.global_max_iter_no) {
954     adaptive_struct.global_max_iter_no = local_iter_no;
955   }
956   if (CkNumPes() == adaptive_struct.global_recv_iter_counter) {
957     adaptive_struct.lb_ideal_period = (adaptive_struct.lb_ideal_period > adaptive_struct.global_max_iter_no) ? adaptive_struct.lb_ideal_period : adaptive_struct.global_max_iter_no + 1;
958     thisProxy.LoadBalanceDecisionFinal(req_no, adaptive_struct.lb_ideal_period);
959     CkPrintf("Final lb_period %d\n", adaptive_struct.lb_ideal_period);
960     adaptive_struct.in_progress = false;
961     adaptive_struct.global_max_iter_no = 0;
962     adaptive_struct.global_recv_iter_counter = 0;
963   }
964 }
965
966 int LBDatabase::getPredictedLBPeriod() {
967   return adaptive_struct.lb_ideal_period;
968 }
969
970 bool LBDatabase::isStrategyComm() {
971   return adaptive_struct.doCommStrategy;
972 }
973
974 void LBDatabase::SetMigrationCost(double lb_migration_cost) {
975   adaptive_struct.lb_migration_cost = lb_migration_cost;
976 }
977
978 void LBDatabase::SetStrategyCost(double lb_strategy_cost) {
979   adaptive_struct.lb_strategy_cost = lb_strategy_cost;
980 }
981
982 void LBDatabase::UpdateAfterLBData(int lb, double lb_max, double lb_avg) {
983   adaptive_struct.last_lb_type = lb;
984   if (lb == 0) {
985     adaptive_struct.greedy_info.max_avg_ratio = lb_max/lb_avg;
986   } else if (lb == 1) {
987     adaptive_struct.refine_info.max_avg_ratio = lb_max/lb_avg;
988   }
989 }
990
991 void LBDatabase::GetPrevLBData(int& lb_type, double& lb_max_avg_ratio) {
992   lb_type = adaptive_struct.last_lb_type;
993   lb_max_avg_ratio = 1;
994   if (lb_type == 0) {
995     lb_max_avg_ratio = adaptive_struct.greedy_info.max_avg_ratio;
996   } else if (lb_type == 1) {
997     lb_max_avg_ratio = adaptive_struct.refine_info.max_avg_ratio;
998   }
999 }
1000
1001 /*
1002   callable from user's code
1003 */
1004 void TurnManualLBOn()
1005 {
1006 #if CMK_LBDB_ON
1007    LBDatabase * myLbdb = LBDatabase::Object();
1008    if (myLbdb) {
1009      myLbdb->TurnManualLBOn();
1010    }
1011    else {
1012      LBDatabase::manualOn = 1;
1013    }
1014 #endif
1015 }
1016
1017 void TurnManualLBOff()
1018 {
1019 #if CMK_LBDB_ON
1020    LBDatabase * myLbdb = LBDatabase::Object();
1021    if (myLbdb) {
1022      myLbdb->TurnManualLBOff();
1023    }
1024    else {
1025      LBDatabase::manualOn = 0;
1026    }
1027 #endif
1028 }
1029
1030 extern "C" void LBTurnInstrumentOn() { 
1031 #if CMK_LBDB_ON
1032   if (CkpvAccess(lbdatabaseInited))
1033     LBDatabase::Object()->CollectStatsOn(); 
1034   else
1035     _lb_args.statsOn() = 1;
1036 #endif
1037 }
1038
1039 extern "C" void LBTurnInstrumentOff() { 
1040 #if CMK_LBDB_ON
1041   if (CkpvAccess(lbdatabaseInited))
1042     LBDatabase::Object()->CollectStatsOff(); 
1043   else
1044     _lb_args.statsOn() = 0;
1045 #endif
1046 }
1047 void LBClearLoads() {
1048 #if CMK_LBDB_ON
1049   LBDatabase::Object()->ClearLoads(); 
1050 #endif
1051 }
1052
1053 void LBTurnPredictorOn(LBPredictorFunction *model) {
1054 #if CMK_LBDB_ON
1055   LBDatabase::Object()->PredictorOn(model);
1056 #endif
1057 }
1058
1059 void LBTurnPredictorOn(LBPredictorFunction *model, int wind) {
1060 #if CMK_LBDB_ON
1061   LBDatabase::Object()->PredictorOn(model, wind);
1062 #endif
1063 }
1064
1065 void LBTurnPredictorOff() {
1066 #if CMK_LBDB_ON
1067   LBDatabase::Object()->PredictorOff();
1068 #endif
1069 }
1070
1071 void LBChangePredictor(LBPredictorFunction *model) {
1072 #if CMK_LBDB_ON
1073   LBDatabase::Object()->ChangePredictor(model);
1074 #endif
1075 }
1076
1077 void LBSetPeriod(double second) {
1078 #if CMK_LBDB_ON
1079   if (CkpvAccess(lbdatabaseInited))
1080     LBDatabase::Object()->SetLBPeriod(second); 
1081   else
1082     _lb_args.lbperiod() = second;
1083 #endif
1084 }
1085
1086 #include "LBDatabase.def.h"
1087
1088 /*@}*/