cleanup
[charm.git] / src / ck-ldb / MetaBalancer.h
1 /**
2 * Meta-Balancer is for automating the load balancing decisions based on the
3 * application characteristics. The decision of when to call the load balancer is
4 * handled by the MetaBalancer if +MetaLB flag is set when launching the
5 * application. AtSync should be called very often (every couple of iterations).
6 *
7 * Meta-Balancer is not aware of the application iteration so it depends on
8 * AtSync calls to count the iterations. At every AtSync call, if +MetaLB is
9 * set, the chare sends its object load to the MetaBalancer on its local
10 * processor and resumes its work. Once all the chares residing on the processor
11 * has contributed their load information, this information is collected at the
12 * central processor(root) using reduction. The root calculates the ideal period
13 * based on linear extrapolation and informs a tentative lb period to all the
14 * processors via broadcast. The Meta-Balancer residing on each processor then
15 * informs the root about the maximum iteration of any chare on their processor.
16 * The root then informs the final lb period, which is the max of calculated and
17 * max. Meanwhile, chares can be in various states. Chare goes to LOAD_BALANCE
18 * state when it enters load balancing phase. It goes to PAUSE state when the
19 * chare has reached the tentative period and is waiting for the final period to
20 * be announced.
21 *
22 * To handle the case of no objects on a particular processor, a timer call is
23 * set which checks for the number of objects and if found to be == 0,
24 * contributes to the reduction which collects minimum statistics.
25 */
26
27 #ifndef METABALANCER_H
28 #define METABALANCER_H
29
30 #include "LBDatabase.h"
31
32 #include <vector>
33
34 #include "MetaBalancer.decl.h"
35
36 extern CkGroupID _metalb;
37 extern CkGroupID _metalbred;
38
39 CkpvExtern(int, metalbInited);
40
41 void _MetaLBInit();
42
43 // main chare
44 class MetaLBInit : public Chare {
45   public:
46     MetaLBInit(CkArgMsg*);
47     MetaLBInit(CkMigrateMessage *m):Chare(m) {}
48 };
49
50 class MetaBalancer : public CBase_MetaBalancer {
51 public:
52   MetaBalancer(void) { init(); }
53   MetaBalancer(CkMigrateMessage *m) : CBase_MetaBalancer(m) { init(); }
54   ~MetaBalancer()  {}
55  
56 private:
57   void init();
58   MetaBalancerRedn* metaRdnGroup;
59
60 public:
61   inline static MetaBalancer * Object() {
62     return CkpvAccess(metalbInited)?(MetaBalancer *)CkLocalBranch(_metalb):NULL;
63   }
64
65   static void initnodeFn(void);
66
67   void pup(PUP::er& p);
68
69   void ResumeClients();
70
71   void ResetAdaptive();
72   int get_iteration();
73   int get_finished_iteration();
74   bool AddLoad(int iteration, double load);
75   void ReceiveMinStats(CkReductionMsg *);
76   void TriggerSoon(int iteration_no, double imbalance_ratio, double tolerate_imb);
77   void LoadBalanceDecision(int, int);
78   void LoadBalanceDecisionFinal(int, int);
79   void MetaLBCallLBOnChares();
80   void ReceiveIterationNo(int); // Receives the current iter no
81   static void periodicCall(void *ad);
82   static void checkForNoObj(void *ad);
83   void HandleAdaptiveNoObj();
84   void RegisterNoObjCallback(int index);
85   void TriggerAdaptiveReduction();
86
87   bool generatePlan(int& period, double& ratio_at_t);
88   bool getLineEq(double new_load_percent, double& aslope, double& ac,
89       double& mslope, double& mc);
90   bool getPeriodForLinear(double a, double b, double c, int& period);
91   bool getPeriodForStrategy(double new_load, double overhead_percent,
92       int& period, double& ratio_at_t);
93   int getPredictedLBPeriod(bool& is_tentative);
94
95   bool isStrategyComm();
96
97   void UpdateAfterLBData(int is_lb_refine, double lb_max, double lb_avg, double
98       local_comm, double remote_comm);
99
100   void UpdateAfterLBData(double max_load, double max_cpu, double avg_load);
101   void UpdateAfterLBComm(double alpha_beta_cost);
102   void GetPrevLBData(int& lb_type, double& lb_max_avg_ratio, double&
103       local_remote_comm_ratio);
104   void GetLBDataForLB(int lb_type, double& lb_max_avg_ratio, double&
105       local_remote_comm_ratio);
106
107   void SetMigrationCost(double lb_migration_cost);
108   void SetStrategyCost(double lb_strategy_cost);
109
110 private:
111   //CProxy_MetaBalancer thisProxy;
112   LBDatabase* lbdatabase;
113   std::vector<double> total_load_vec;
114   // Keeps track of how many local chares contributed
115   std::vector<int> total_count_vec;
116   std::vector<int> lbdb_no_obj_callback;
117
118   double prev_idle;
119   double alpha_beta_cost_to_load;
120   int is_prev_lb_refine;
121
122   struct AdaptiveData {
123     double iteration;
124     double max_load;
125     double avg_load;
126     double utilization;
127     double idle_time;
128   };
129
130   struct AdaptiveMetaBalancer {
131     CkVec<AdaptiveData> history_data;
132     int lb_iter_no;
133   } adaptive_lbdb;
134
135   struct AdaptiveLBInfo {
136     AdaptiveLBInfo() {
137       max_avg_ratio = 1;
138       remote_local_ratio = 1;
139     }
140     double max_avg_ratio;
141     double remote_local_ratio;
142   };
143
144   // TODO: Separate out the datastructure required by just the central and on all
145   // processors
146   struct AdaptiveLBStructure {
147     int tentative_period;
148     int final_lb_period;
149     // This is based on the linear extrapolation
150     int lb_calculated_period;
151     // Current maximum iteration no of any chare on this processor
152     int lb_iteration_no;
153     // This corresponds to the last iteration that was contributed
154     int finished_iteration_no;
155     // This is set when all the processor sends the maximum iteration no
156     int global_max_iter_no;
157     // This keeps track of what was the max iteration no we had previously
158     // received. TODO: Mostly global_max_iter_no should be sufficied.
159     int tentative_max_iter_no;
160     // true indicates it is in Inform->ReceiveMaxIter->FinalLBPeriod stage.
161     bool in_progress;
162     double lb_strategy_cost;
163     double lb_migration_cost;
164     bool doCommStrategy;
165     int lb_msg_send_no;
166     int lb_msg_recv_no;
167     // Total AtSync calls from all the chares residing on the processor
168     int total_syncs_called;
169     int last_lb_type;
170     AdaptiveLBInfo greedy_info;
171     AdaptiveLBInfo refine_info;
172     AdaptiveLBInfo comm_info;
173     AdaptiveLBInfo comm_refine_info;
174     AdaptiveLBInfo info_first_iter;
175   } adaptive_struct;
176
177 public:
178   bool lb_in_progress;
179
180 };
181
182 class MetaBalancerRedn : public CBase_MetaBalancerRedn {
183   public:
184     MetaBalancerRedn(void) {init();}
185     MetaBalancerRedn(CkMigrateMessage *m) : CBase_MetaBalancerRedn(m)  {init();}
186     ~MetaBalancerRedn()  {}
187     void pup(PUP::er& p);
188     void ReceiveIterNo(int max_iter);
189     void getMaxIter(int);
190
191   private:
192     MetaBalancer* metabalancer;
193     void init();
194 };
195
196 inline MetaBalancer* MetaBalancerObj() { return MetaBalancer::Object(); }
197
198 #endif /* LDATABASE_H */
199
200 /*@}*/