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