Detailed documentation of how Meta-Balancer functions
[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 ReceiveIterationNo(int); // Receives the current iter no
80   static void periodicCall(void *ad);
81   static void checkForNoObj(void *ad);
82   void HandleAdaptiveNoObj();
83   void RegisterNoObjCallback(int index);
84   void TriggerAdaptiveReduction();
85
86   bool generatePlan(int& period, double& ratio_at_t);
87   bool getLineEq(double new_load_percent, double& aslope, double& ac,
88       double& mslope, double& mc);
89   bool getPeriodForLinear(double a, double b, double c, int& period);
90   bool getPeriodForStrategy(double new_load, double overhead_percent,
91       int& period, double& ratio_at_t);
92   int getPredictedLBPeriod(bool& is_tentative);
93
94   bool isStrategyComm();
95
96   void UpdateAfterLBData(int is_lb_refine, double lb_max, double lb_avg, double
97       local_comm, double remote_comm);
98
99   void UpdateAfterLBData(double max_load, double max_cpu, double avg_load);
100   void UpdateAfterLBComm(double alpha_beta_cost);
101   void GetPrevLBData(int& lb_type, double& lb_max_avg_ratio, double&
102       local_remote_comm_ratio);
103   void GetLBDataForLB(int lb_type, double& lb_max_avg_ratio, double&
104       local_remote_comm_ratio);
105
106   void SetMigrationCost(double lb_migration_cost);
107   void SetStrategyCost(double lb_strategy_cost);
108
109 private:
110   //CProxy_MetaBalancer thisProxy;
111   LBDatabase* lbdatabase;
112   std::vector<double> total_load_vec;
113   // Keeps track of how many local chares contributed
114   std::vector<int> total_count_vec;
115   std::vector<int> lbdb_no_obj_callback;
116
117   double prev_idle;
118   double alpha_beta_cost_to_load;
119   int is_prev_lb_refine;
120
121   struct AdaptiveData {
122     double iteration;
123     double max_load;
124     double avg_load;
125     double utilization;
126     double idle_time;
127   };
128
129   struct AdaptiveMetaBalancer {
130     CkVec<AdaptiveData> history_data;
131     int lb_iter_no;
132   } adaptive_lbdb;
133
134   struct AdaptiveLBInfo {
135     AdaptiveLBInfo() {
136       max_avg_ratio = 1;
137       remote_local_ratio = 1;
138     }
139     double max_avg_ratio;
140     double remote_local_ratio;
141   };
142
143   // TODO: Separate out the datastructure required by just the central and on all
144   // processors
145   struct AdaptiveLBStructure {
146     int tentative_period;
147     int final_lb_period;
148     // This is based on the linear extrapolation
149     int lb_calculated_period;
150     // Current maximum iteration no of any chare on this processor
151     int lb_iteration_no;
152     // This corresponds to the last iteration that was contributed
153     int finished_iteration_no;
154     // This is set when all the processor sends the maximum iteration no
155     int global_max_iter_no;
156     // This keeps track of what was the max iteration no we had previously
157     // received. TODO: Mostly global_max_iter_no should be sufficied.
158     int tentative_max_iter_no;
159     // true indicates it is in Inform->ReceiveMaxIter->FinalLBPeriod stage.
160     bool in_progress;
161     double lb_strategy_cost;
162     double lb_migration_cost;
163     bool doCommStrategy;
164     int lb_msg_send_no;
165     int lb_msg_recv_no;
166     // Total AtSync calls from all the chares residing on the processor
167     int total_syncs_called;
168     int last_lb_type;
169     AdaptiveLBInfo greedy_info;
170     AdaptiveLBInfo refine_info;
171     AdaptiveLBInfo comm_info;
172     AdaptiveLBInfo comm_refine_info;
173     AdaptiveLBInfo info_first_iter;
174   } adaptive_struct;
175
176 public:
177   bool lb_in_progress;
178
179 };
180
181 class MetaBalancerRedn : public CBase_MetaBalancerRedn {
182   public:
183     MetaBalancerRedn(void) {init();}
184     MetaBalancerRedn(CkMigrateMessage *m) : CBase_MetaBalancerRedn(m)  {init();}
185     ~MetaBalancerRedn()  {}
186     void pup(PUP::er& p);
187     void ReceiveIterNo(int max_iter);
188     void getMaxIter(int);
189
190   private:
191     MetaBalancer* metabalancer;
192     void init();
193 };
194
195 inline MetaBalancer* MetaBalancerObj() { return MetaBalancer::Object(); }
196
197 #endif /* LDATABASE_H */
198
199 /*@}*/