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