Docs: refer to illinois.edu, not uiuc.edu
[charm.git] / doc / charm++ / advancedlb.tex
1 \section{Load Balancing Simulation}
2
3 The simulation feature of load balancing framework allows the users to collect information
4 about the compute WALL/CPU time and communication of the chares during a particular run of
5 the program and use this information later to test different load balancing strategies to
6 see which one is suitable for the program behavior. Currently, this feature is supported only for
7 the centralized load balancing strategies. For this, the load balancing framework
8 accepts the following command line options:
9 \begin{enumerate}
10 \item {\em +LBDump StepStart}\\
11         This will dump the instrument/communication data collected by the load balancing framework
12         starting from the load balancing step {\em StepStart} into a file on the disk. The name of the file
13         is given by the {\em +LBDumpFile} option. The first step in the program is number 0. Negative
14         numbers will be converted to 0.
15 \item {\em +LBDumpSteps StepsNo}\\
16         This option specifies the number of steps for which data will be dumped to disk. If omitted, default value is 1.
17         The program will exit after StepsNo files are dumped.
18 \item {\em +LBDumpFile FileName}\\
19         This option specifies the base name of the file into which the load balancing data is dumped. If this
20         option is not specified, the framework uses the default file {\tt lbdata.dat}. Since multiple steps are allowed,
21         a number is appended to the filename in the form {\tt Filename.\#}; this applies to both dump and
22         simulation.
23 \item {\em +LBSim StepStart}\\
24         This option instructs the framework to do the simulation from {\em StepStart} step.
25         When this option is specified, the load balancing data from the file specified in the {\em +LBDumpFile}
26         option, with the addition of the step number, will be read and this data
27         will be used for the load balancing. The program will print the results
28         of the balancing for a number of steps given by the {\em +LBSimSteps} option, and then will exit.
29 \item {\em +LBSimSteps StepsNo}\\
30         This option has the same meaning of {\em +LBDumpSteps}, except that apply for the simulation mode.
31         Default value is 1.
32 \item {\em +LBSimProcs}\\
33         This option may change the number of processors target of the load balancer strategy. It may be used to test
34         the load balancer in conditions where some processor crashes or someone becomes available. If this number is not
35         changed since the original run, starting from the second step file the program will print other additional
36         information about how the simulated load differs from the real load during the run (considering all
37         strategies that were applied while running). This may be used to test the validity of a load balancer
38         prediction over the reality. If the strategies used during run and simulation differ, the additional data
39         printed may not be useful.
40 \end{enumerate}
41 As an example, we can collect the data for a 1000 processor run of a program using:
42 \begin{alltt}
43 ./charmrun pgm +p1000 +balancer RandCentLB +LBDump 2 +LBDumpSteps 4 +LBDumpFile dump.dat
44 \end{alltt}
45 This will collect data on files data.dat.{2,3,4,5}. Then, we can use this data to observe various centralized strategies using:
46 \begin{alltt}
47 ./charmrun pgm +balancer <Strategy to test> +LBSim 2 +LBSimSteps 4 +LBDumpFile dump.dat
48 [+LBSimProcs 900]
49 \end{alltt}
50 Please note that this does not invoke any real application run. Actually
51  ''pgm'' can be replaced with any generic application which calls centralized load balancer.
52 An example can be found in \testrefdir{load\_balancing/lb\_test}.
53
54 \section{Future load predictor}
55
56 When objects do not follow the assumption that the future workload will be the
57 same as the past, the load balancer might not have the correct information to do
58 a correct rebalancing job. To prevent this the user can provide a transition
59 function to the load balancer to predict what will be the future workload, given
60 the past, instrumented one. As said, the user might provide a specific class
61 which inherits from {\tt LBPredictorFunction} and implement the appropriate functions. 
62 Here is the abstract class:
63 \begin{alltt}
64 class LBPredictorFunction \{
65 public:
66   int num_params;
67  
68   virtual void initialize_params(double *x);
69
70   virtual double predict(double x, double *params) =0;
71   virtual void print(double *params) {PredictorPrintf("LB: unknown model");};
72   virtual void function(double x, double *param, double &y, double *dyda) =0;
73 \};
74 \end{alltt}
75 \begin{itemize}
76 \item {\tt initialize\_params} by default initializes the parameters randomly. If the user
77 knows how they should be, this function can be re-implemented.
78 \item {\tt predict} is the function that predicts the load according to the factors in parameters.
79 For example, if the function is
80 $y=ax+b$, the method in the implemented class should be like:
81 \begin{verbatim}
82 double predict(double x, double *param) {return (param[0]*x + param[1]);}
83 \end{verbatim}
84 \item {\tt print} is a debugging function and it can be re-implemented to have a meaningful
85 print of the learnt model
86 \item {\tt function} is a function internally needed to learn the parameters, {\tt x} and
87 {\tt param} are input, {\tt y} and {\tt dyda} are output (the computed function and
88 all its derivatives with respect to the parameters, respectively).
89 For the function in the example should look like:
90 \begin{verbatim}
91 void function(double x, double *param, double &y, double *dyda) {
92   y = predict(x, param);
93   dyda[0] = x;
94   dyda[1] = 1;
95 }
96 \end{verbatim}
97 \end{itemize}
98 Other than these function, the user should provide a constructor which must initialize
99 {\tt num\_params} to the number of parameters the model has to learn. This number is
100 the dimension of {\tt param} and {\tt dyda} in the previous functions. For the given
101 example, the constructor is {\tt \{num\_params = 2;\}}.
102
103 If the model behind the computation is not known, the user can leave the system to
104 use a predefined default function.
105
106 As seen, the function can have several parameters which will be learned during
107 the execution of the program. For this, two parameters can be setup at command
108 line to specify the learning behavior:
109 \begin{enumerate}
110 \item {\em +LBPredictorWindow size}\\
111 This parameter will specify how many statistics steps the load balancer will keep. 
112 The greater this number is, the better the
113 approximation of the workload will be, but more memory is required to store
114 the intermediate information. The default is 20.
115 \item {\em +LBPredictorDelay steps}\\
116 This will tell how many load balancer steps to wait before considering the
117 function parameters learnt and starting to use the mode. The load balancer will
118 collect statistics for a {\em +LBPredictorWindow} steps, but it will start using
119 the model as soon as {\em +LBPredictorDelay} information are collected. The
120 default is 10.
121 \end{enumerate}
122 Moreover another flag can be set to enable the predictor from command line: {\em
123 +LBPredictor}.\\
124 Other than the command line options, there are some methods
125 callable from user program to modify the predictor. These methods are:
126 \begin{itemize}
127 \item {\tt void PredictorOn(LBPredictorFunction *model);}
128 \item {\tt void PredictorOn(LBPredictorFunction *model,int wind);}
129 \item {\tt void PredictorOff();}
130 \item {\tt void ChangePredictor(LBPredictorFunction *model);}
131 \end{itemize}
132
133 \section{Control CPU Load Statistics}
134
135 \charmpp{} programmers can control CPU load data in the load balancing database
136 before a load balancing phase is started (which is the time when load balancing
137 database is collected and used by load balancing strategies).
138
139 In an array element, the following function can be invoked to overwrite the 
140 CPU load that is measured by load balancing framework.
141
142 \begin{alltt}
143    double newTiming;
144    setObjTime(newTiming);
145 \end{alltt}
146
147 {\em setObjTime()} is defined as a method of class {\em CkMigratable}, which is
148 the superclass of all array elements.
149
150 The users can also retrieve the current timing that the load balancing runtime
151 has measured for the current array element. 
152  
153 \begin{alltt} 
154    double measuredTiming; 
155    measuredTiming = getObjTime(); 
156 \end{alltt}
157
158 This is useful when the users want to derive a new CPU load based on the 
159 existing one.
160
161 \section{Model-based Load Balancing}
162
163 You can also choose to feed load balancer with their own CPU
164 timing of each Chare based on certain computational model of the applications.
165
166 To do so, first you need to turn off automatic CPU load measurement completely
167 by setting:
168
169 \begin{alltt}
170    usesAutoMeasure = CmiFalse;
171 \end{alltt}
172
173 in array element's constructor.
174
175 Then the you need to implement the following function to the chare array
176 classes:
177
178 \begin{alltt}
179    virtual void CkMigratable::UserSetLBLoad();      // defined in base class
180 \end{alltt}
181
182 This function serves as a callback that is called on each chare object when
183 {\em AtSync()} is called and ready to do load balancing. The implementation of
184 {\em UserSetLBLoad()} is simply to set the current chare object's CPU load to
185 load balancer framework. {\em setObjTime()} described above can be used for
186 this.
187
188 \section{Writing a new load balancing strategy}
189
190 \charmpp{} programmers can choose an existing load balancing strategy from
191 \charmpp{}'s built-in strategies(see ~\ref{lbStrategy}) for the best performance
192 based on the characteristics of their applications. However, they can also
193 choose to write their own load balancing strategies.
194
195 The \charmpp{} load balancing framework provides a simple scheme to incorporate
196 new load balancing strategies. The programmer needs to write their strategy for
197 load balancing based on the instrumented ProcArray and ObjGraph provided by the
198 load balancing framework. This strategy is implemented within this
199 function:
200
201 \begin{alltt}
202 void FooLB::work(LDStats *stats) \{
203   /** ========================== INITIALIZATION ============================= */
204   ProcArray *parr = new ProcArray(stats);
205   ObjGraph *ogr = new ObjGraph(stats);
206
207   /** ============================= STRATEGY ================================ */
208   /// The strategy goes here
209   /// The strategy goes here
210   /// The strategy goes here
211   /// The strategy goes here
212   /// The strategy goes here
213
214   /** ============================== CLEANUP ================================ */
215   ogr->convertDecisions(stats);
216 \}
217 \end{alltt}
218
219 Figure~\ref{fig:ckgraph} explains the two data structures available to the
220 strategy: ProcArray and ObjGraph. Using them, the strategy should assign objects 
221 to new processors  where it wants to be migrated through the setNewPe() method.
222 {\tt src/ck-ldb/GreedyLB.C} can be referred.
223 \begin{figure}[h]
224 \centering
225 \includegraphics[width=6.0in]{fig/ckgraph.png}
226 \caption{ProcArray and ObjGraph data structures to be used when writing a load
227 balancing strategy}
228 \label{fig:ckgraph}
229 \end{figure}
230
231 Incorporating this strategy into the \charmpp{} build framework is explained in
232 the next section.
233
234 \section{Adding a load balancer to \charmpp{}}
235
236 Let us assume that we are writing a new centralized load balancer called FooLB.
237 The next few steps explain the steps of adding the load balancer to the \charmpp{}
238 build system:
239
240 \begin{enumerate}
241 \item Create files named {\em FooLB.ci, FooLB.h and FooLB.C} in directory of {\tt src/ck-ldb}.
242 One can choose to copy and rename the files GraphPartLB.* and rename the class name in those
243 files.
244
245 \item Implement the strategy in the {\em FooLB} class method --- {\bf
246 FooLB::work(LDStats* stats)} as described in the previous section.
247 %This method takes the load balancing database ({\em stats}) as an input, and
248 %output the new mapping of objects to processors in {\em stats->to\_proc}
249 %array.
250
251 \item Build charm for your platform (This will create the required links in the
252 tmp directory).
253
254 \item To compile the strategy files, first add {\em FooLB} in the ALL\_LDBS
255 list in charm/tmp/Makefile\_lb.sh. Also comment out the line containing
256 UNCOMMON\_LDBS in Makefile\_lb.sh.  If FooLB will require some libraries at
257 link time, you also need to create the dependency file called
258 libmoduleFooLB.dep. Run the script in charm/tmp, which creates the new Makefile
259 named ``Make.lb''.
260
261 \item Run ``make depends'' to update dependence rule of \charmpp{} files.  And run
262 ``make charm++'' to compile \charmpp{} which includes the new load balancing
263 strategy files.
264 \end{enumerate}
265
266
267 \section{Understand Load Balancing Database Data Structure}
268 \label{lbdatabase}
269
270 To write a load balancing strategy, you need to know 
271 what information is measured during the runtime and how it is represented in
272 the load balancing database data structure.
273
274 There are mainly 3 categories of information: a) processor information including processor speed, background load; b) object information including per object
275 CPU/WallClock compute time and c) communication information .
276
277 The database data structure named {\kw LDStats} is defined in {\em CentralLB.h}:
278
279 \begin{verbatim}
280
281   struct ProcStats {  // per processor
282     LBRealType total_walltime;
283     LBRealType total_cputime;
284     LBRealType idletime;
285     LBRealType bg_walltime;
286     LBRealType bg_cputime;
287     int pe_speed;
288     double utilization;
289     CmiBool available;
290     int   n_objs;
291   }
292
293   struct LDStats { // load balancing database
294     ProcStats  *procs;
295     int count;
296
297     int   n_objs;
298     int   n_migrateobjs;
299     LDObjData* objData;
300
301     int   n_comm;
302     LDCommData* commData;
303
304     int  *from_proc, *to_proc;
305   }
306
307 \end{verbatim}
308
309 \begin{enumerate}
310 \item {\em LBRealType} is the data type for load balancer measured time. It is "double" by default. User can specify the type to float at \charmpp{} compile time if want. For example, ./build charm++ net-linux-x86\_64 {-}{-}with-lbtime-type=float;
311 \item {\em procs} array defines processor attributes and usage data for each
312 processor;
313 \item {\em objData} array records per object information, {\em LDObjData} is defined in {\em lbdb.h};
314 \item {\em commData} array records per communication information. {\em LDCommData} is defined in {\em lbdb.h}.
315 \end{enumerate}
316