Fixing an issue when there are no chares on a processor
[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   bool resume_client_called;
122
123   struct AdaptiveData {
124     double iteration;
125     double max_load;
126     double avg_load;
127     double utilization;
128     double idle_time;
129   };
130
131   struct AdaptiveMetaBalancer {
132     CkVec<AdaptiveData> history_data;
133     int lb_iter_no;
134   } adaptive_lbdb;
135
136   struct AdaptiveLBInfo {
137     AdaptiveLBInfo() {
138       max_avg_ratio = 1;
139       remote_local_ratio = 1;
140     }
141     double max_avg_ratio;
142     double remote_local_ratio;
143   };
144
145   // TODO: Separate out the datastructure required by just the central and on all
146   // processors
147   struct AdaptiveLBStructure {
148     int tentative_period;
149     int final_lb_period;
150     // This is based on the linear extrapolation
151     int lb_calculated_period;
152     // Current maximum iteration no of any chare on this processor
153     int lb_iteration_no;
154     // This corresponds to the last iteration that was contributed
155     int finished_iteration_no;
156     // This is set when all the processor sends the maximum iteration no
157     int global_max_iter_no;
158     // This keeps track of what was the max iteration no we had previously
159     // received. TODO: Mostly global_max_iter_no should be sufficied.
160     int tentative_max_iter_no;
161     // true indicates it is in Inform->ReceiveMaxIter->FinalLBPeriod stage.
162     bool in_progress;
163     double lb_strategy_cost;
164     double lb_migration_cost;
165     bool doCommStrategy;
166     int lb_msg_send_no;
167     int lb_msg_recv_no;
168     // Total AtSync calls from all the chares residing on the processor
169     int total_syncs_called;
170     int last_lb_type;
171     AdaptiveLBInfo greedy_info;
172     AdaptiveLBInfo refine_info;
173     AdaptiveLBInfo comm_info;
174     AdaptiveLBInfo comm_refine_info;
175     AdaptiveLBInfo info_first_iter;
176   } adaptive_struct;
177
178 public:
179   bool lb_in_progress;
180
181 };
182
183 class MetaBalancerRedn : public CBase_MetaBalancerRedn {
184   public:
185     MetaBalancerRedn(void) {init();}
186     MetaBalancerRedn(CkMigrateMessage *m) : CBase_MetaBalancerRedn(m)  {init();}
187     ~MetaBalancerRedn()  {}
188     void pup(PUP::er& p);
189     void ReceiveIterNo(int max_iter);
190     void getMaxIter(int);
191
192   private:
193     MetaBalancer* metabalancer;
194     void init();
195 };
196
197 inline MetaBalancer* MetaBalancerObj() { return MetaBalancer::Object(); }
198
199 #endif /* LDATABASE_H */
200
201 /*@}*/