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