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