Revert "Drop requirement for user code to call CBase_foo::pup(p)"
[charm.git] / doc / charm++ / loadb.tex
1
2 \subsection{Load Balancing}
3
4 \label{loadbalancing}
5
6 %(This introduction added on 11/12/2003)
7
8 Charm++ supports load balancing, enabled by the fact there are a large
9 number of chares or chare-array-elements typically available to map to
10 existing processors, and that they can be migrated at runtime.
11
12 Many parallel applications, especially physical simulations, are
13 iterative in nature. They may contain a series of time-steps, and/or
14 iterative solvers that run to convergence. For such computations,
15 typically, the heuristic principle that we call "principle of
16 persistence" holds: the computational loads and communication patterns
17 between objects (chares) tend to persist over time, even in dynamic
18 applications. In such cases, recent past is a good predictor of near
19 future. Measurement-based chare migration strategies are useful in
20 this context. Currently these apply to chare-array elements, but they
21 may be extended to chares in the future.
22
23 For applications without such iterative structure, or with iterative structure
24 but without the predictability (i.e. where the principle of persistence does
25 not apply), Charm++ supports "seed balancers" that move seeds for new chares
26 among processors (possibly repeatedly) to achieve load balance. These
27 strategies are currently available for both chares and chare-arrays.  Seed
28 balancers were the original load balancers provided in Charm since the late
29 '80s. They are extremely useful for state-space search applications, and are
30 also useful in other computations, as well as in conjunction with migration
31 strategies.
32
33 For iterative computations when there is a correlation between iterations/steps
34 but either it is not strong or the machine environment is not predictable
35 (noise due to OS interrupts on small time steps, or time-shared desk-top
36 machines), one can use a combination of the two kinds of strategies. The
37 base-line load balancing is provided by migration strategies; But in each
38 iteration one also spawns off work in the form of chares that can run on any
39 processor. The seed balancer will handle such work as it arises.
40
41 \subsubsection{Measurement-based Object Migration Strategies}
42
43 \label{lbFramework}
44 \label{migrationlb}
45
46 In \charmpp{}, objects (except groups, nodegroups) can migrate from 
47 processor to processor at run-time. Object migration can potentially 
48 improve the performance of the parallel program by migrating objects from 
49 overloaded processors to underloaded ones. 
50
51 %However, it is not
52 %trivial to decide which objects to move and where to move them in 
53 %order to achieve load balance in a fashion without the knowledge about the 
54 %application. The strategy used in \charmpp{} load balancing framework
55 %is a measurement-based one.
56
57  \charmpp{} implements a generic, measurement-based load balancing framework
58 which automatically instruments all \charmpp{} objects, collects computation
59 load and communication structure during execution and stores them into a
60 \kw{load balancing database}. \charmpp{} then provides a collection of \kw{load
61 balancing strategies} whose job is to decide on a new mapping of objects to
62 processors based on the information from the database.  Such measurement based
63 strategies are efficient when we can reasonably assume that objects in
64 \charmpp{} application tend to exhibit temporal correlation in their
65 computation and communication patterns, i.e. future can be to some extent
66 predicted using the historical measurement data, allowing effective
67 measurement-based load balancing without application-specific knowledge.
68
69 Here are the two terms often used in \charmpp{} load balancing framework:
70 \begin{itemize}
71 %
72 \item \kw{Load balancing database} provides the interface of almost all load
73 balancing calls. On each processor, it stores the load balancing instrumented
74 data and coordinates the load balancing manager and balancer. it is implemented
75 as a Chare Group called \kw{LBDatabase}.
76 %
77 \item \kw{Load balancer or strategy} takes the load balancing database and
78 produces the new mapping of the objects. In \charmpp{}, it is implemented as
79 Chare Group inherited from BaseLB. Three kinds of schemes are implemented: (a)
80 centralized load balancers, (b) fully distributed load balancers and (c)
81 hierarchical load balancers.
82 %
83 \end{itemize}
84
85 \subsubsection{Available Load Balancing Strategies}
86
87 \label{lbStrategy}
88
89 Load balancing can be performed in either a centralized, fully distributed
90 or hierarchical fashion.
91
92 In centralized approaches, the entire machine's load and communication
93 structure are accumulated to a single point, typically processor 0, followed by
94 a decision making process to determine the new distribution of \charmpp
95 objects. Centralized load balancing requires synchronization which may incur an
96 overhead and delay. However, due to the fact that the decision process has a
97 high degree of the knowledge about the entire machine, it tends to be more
98 accurate.
99
100 In distributed approaches, machine states are only exchanged among 
101 neighboring processors. There is no global synchronization. However,
102 they will not, in general, provide an immediate restoration for load balance -
103 the process is iterated until the load balance can be achieved.
104
105 In hierarchical approaches, processors are divided into independent autonomous
106 sets of processor groups and these groups are organized in hierarchies,
107 therefore decentralizing the load balancing task. Different strategies can be
108 used to load balancing load on processors inside each processor group, and
109 processors across groups in a hierarchical fashion.
110
111 Listed below are some of the available non-trivial centralized load balancers
112 and their brief descriptions:
113 \begin{itemize}
114 \item {\bf RandCentLB}:   Randomly assigns objects to processors;
115 %\item {\bf RecBisectBfLB}:        Recursively partition with Breadth first enumeration;
116 \item {\bf MetisLB}:      Use Metis(tm) to partitioning object communication graph;
117 \item {\bf GreedyLB}:   Use greedy algorithm, always pick the heaviest object to the least loaded processor.
118 \item {\bf GreedyCommLB}:       Greedy algorithm which also takes communication graph into account;
119 \item {\bf TopoCentLB}:       Greedy algorithm which also takes processor topology into account;
120 \item {\bf RefineLB}:     Move objects away from the most overloaded processors to reach average, limits the number of objects migrated;
121 \item {\bf RefineCommLB}:     Same idea as in RefineLB, but take communication into account;
122 \item {\bf RefineTopoLB}:       Same idea as in RefineLB, but take processor topology into account;
123 \item {\bf ComboCentLB}:  A special load balancer that can be used to combine any number of above centralized load balancers;
124 \end{itemize}
125
126 Listed below are the distributed load balancers:
127 \begin{itemize}
128 \item {\bf NeighborLB}:   A neighborhood load balancer in which each processor tries to average out its load only among its neighbors.
129 \item {\bf WSLB}:   A load balancer for workstation clusters, which can detect load changes on desktops (and other timeshared processors) and adjust load without interferes with other's use of the desktop.
130 \end{itemize}
131
132 An example of a hierarchical strategy can be found in:
133 \begin{itemize}
134 \item {\bf HybridLB}: This calls GreedyLB at the lower level and RefineLB at
135 the root.
136 \end{itemize}
137
138 Users can choose any load balancing strategy they think is good for their
139 application. The compiler and run-time options are described in
140 section~\ref{lbOption}.
141
142 %In some cases, one may need to create and invoke multiple load balancing
143 %strategies/algorithms at the different phases. \charmpp{} now supports
144 %multiple load balancers created at runtime. For example, one can use 
145 %an aggressive load balancer such as GreedyRefLB in the first load balancing
146 %step, and use RefineLB for the later load balancing steps.
147
148 \subsubsection{Load Balancing Chare Arrays}
149 \label{lbarray}
150
151 The load balancing framework is well integrated with chare array implementation
152 -- when a chare array is created, it automatically registers its elements with
153 the load balancing framework. The instrumentation of compute time (wall/cpu
154 time) and communication pattern are done automatically and APIs are provided
155 for users to trigger the load balancing.  To use the load balancer, you must
156 make your array elements migratable (see migration section above) and choose a
157 \kw{load balancing strategy} (see the section \ref{lbStrategy} for a
158 description of available load balancing strategies).
159
160 There are three different ways to use load balancing for chare arrays to meet
161 different needs of the applications. These methods are different in how and
162 when a load balancing phase starts. The three methods are: {\bf periodic load
163 balancing mode}, {\bf at sync mode} and {\bf manual mode}.
164
165 In {\em periodic load balancing mode}, a user just needs to specify how often
166 he wants the load balancing to occur, using +LBPeriod runtime option to specify
167 a time interval.
168
169 In {\em sync mode}, users can tell the load balancer explicitly when is a good
170 time to trigger load balancing by inserting a function call (AtSync) in the
171 user code.
172
173 In the above two load balancing modes, users do not need to worry about how to
174 start load balancing.  However, in one scenario, the above automatic load
175 balancers will fail to work - when array elements are created by dynamic insertion.
176 This is because the above two load balancing modes require an application to
177 have fixed number of objects at the time of load balancing.  The array manager
178 needs to maintain a head count of local array elements for the local barrier.
179 In this case, users have to use the {\em manual mode} to trigger load balancer
180 themselves.
181
182 The detailed APIs of these three methods are described as follows:
183 %
184 \begin{enumerate}
185 %
186 \item {\bf Periodical load balancing mode}: In the default setting, load
187 balancing happens whenever the array elements are ready, with an interval of 1
188 second. It is desirable for the application to set a larger interval using
189 +LBPeriod runtime option. For example "+LBPeriod 5.0" can be used to start load
190 balancing roughly every 5 seconds. By default, array elements may be asked to
191 migrate at any time provided that they are not in the middle of executing an
192 entry method. The array element's variable \kw{usesAtSync} being CmiFalse
193 attributes to this default behavior.
194 %
195 \item {\bf At sync mode}: Using this method, elements can only be migrated at
196 certain points in the execution when user calls \kw{AtSync()}. For using the at
197 sync mode, one should set \kw{usesAtSync} to CmiTrue in the array element
198 constructor.  When an element is ready to migrate, call
199 \kw{AtSync()}~\footnote{AtSync() is a member function of class ArrayElement}.
200 When all local elements call \kw{AtSync}, the load balancer is triggered.  Once
201 all migrations are completed, the load balancer calls the virtual function
202 \kw{ArrayElement::ResumeFromSync()} on each of the array elements. This
203 function can be redefined in the application.
204
205 Note that the minimum time for \kw{AtSync()} load balancing to occur
206 is controlled by the LBPeriod.  Unusually high frequency load
207 balancing (more frequent than 500ms) will perform better if this value
208 is set via +LBPeriod or \kw{SetLBPeriod()} to a number shorter than your load
209 balancing interval.
210
211 Note that {\em AtSync()} is not a blocking call, it just gives a hint to load
212 balancing that it is time for load balancing. During the time between {\em
213 AtSync} and {\em ResumeFromSync}, the object may be migrated. One can choose
214 to let objects continue working with incoming messages, however keep in mind
215 the object may suddenly show up in another processor and make sure no
216 operations that could possibly prevent migration be performed. This is the automatic way of doing load balancing where the application does not need to define ResumeFromSync().
217
218 The more commonly used approach is to force the object to be idle until load
219 balancing finishes. The user places an AtSync call at the end of some iteration
220 and when all elements reach that call load balancing is triggered. The objects
221 can start executing again when \kw{ResumeFromSync()} is called. In this case,
222 the user redefines ResumeFromSync() to trigger the next iteration of the
223 application. This manual way of using the at sync mode results in a barrier at
224 load balancing (see example here~\ref{lbexample}).
225 %
226 \item {\bf Manual mode}: The load balancer can be programmed to be started
227 manually. To switch to the manual mode, you should call {\em TurnManualLBOn()}
228 on every processor to prevent load balancer from starting automatically. {\em
229 TurnManualLBOn()} should be called as early as possible in the program. It
230 could be called at the initialization part of the program, for example from a
231 global variable constructor, or in an initcall~\ref{initcall}.  It can also be
232 called in the constructor of a static array and definitely before the {\em
233 doneInserting} call for a dynamic array.  It can be called multiple times on
234 one processor, but only the last one takes effect.
235
236 The function call {\em StartLB()} starts load balancing immediately. This call
237 should be made at only one place on only one processor. This function is also
238 not blocking, the object will continue to process messages and the load
239 balancing when triggered happens at the background.
240
241 {\em TurnManualLBOff()} turns off manual load balancing and switches back to
242 the automatic Load balancing mode.
243 %
244 \end{enumerate}
245
246 \subsubsection{Migrating objects}
247
248 \label{lbmigobj}
249
250 Load balancers migrate objects automatically.
251 For an array element to migrate, user can refer to section~\ref{arraymigratable}
252 for how to write a ``pup'' for an array element.
253
254 In general one needs to pack the whole snapshot of the member data in an 
255 array element in the pup subroutine. This is because the migration of
256 the object may happen at any time. In certain load balancing scheme where
257 user explicitly control when the load balancing happens, user may choose
258 to pack only a part of the data and may skip those temporary data.
259
260 \subsubsection{Other utility functions}
261
262 There are several utility functions that can be called in applications to
263 configure the load balancer, etc. These functions are:
264
265 \begin{itemize}
266 \item {\bf LBTurnInstrumentOn()} and {\bf LBTurnInstrumentOff()}: are plain C
267       functions to control the load balancing statistics instrumentation
268       on or off on the calling processor. No implicit broadcast or 
269       synchronization exists in these functions.
270       Fortran interface: {\bf FLBTURNINSTRUMENTON()} and {\bf FLBTURNINSTRUMENTOFF()}.
271 \item {\bf setMigratable(CmiBool migratable)}: is a member function of array
272       element. This function can be called 
273       in an array element constructor to tell load balancer whether this object
274       is migratable or not\footnote{Currently not all load balancers 
275       recognize this setting though.}.
276 \item {\bf LBSetPeriod(double s)}: this function can be called
277       anywhere (even in Charm++ initcalls) to specify 
278       the load balancing period time in seconds. 
279       It tells load balancer not to start next 
280       load balancing in less than $s$ seconds. This can be used to prevent 
281       load balancing from occurring too often in 
282       {\em automatic without sync mode}. Here is how to use it:
283       \begin{alltt}
284 // if used in an array element
285 LBDatabase *lbdb = getLBDB();
286 lbdb->SetLBPeriod(5.0);
287
288 // if used outside of an array element
289 LBSetPeriod(5.0);
290 \end{alltt}
291       Alternatively, one can specify +LBPeriod \{seconds\} at command line.
292 \end{itemize}
293
294 \subsubsection{Compiler and run-time options to use load balancing module}
295
296 \label{lbOption}
297
298 Load balancing strategies are implemented as libraries in \charmpp{}. This
299 allows programmers to easily experiment with different existing strategies 
300 by simply linking a pool of strategy modules and choosing
301 one to use at run-time via a command line option.
302
303 Please note that linking a load balancing module is different from activating it:
304 \begin{itemize}
305 \item link a LB module: is to link a Load Balancer module(library) at 
306    compile time; You can link against multiple LB libraries as candidates.
307 \item activate a LB: is to actually ask at run-time to create a LB strategy and 
308    start it. You can only activate load balancers that have been linked at
309    compile time.
310 \end{itemize}
311
312
313 Below are the descriptions about the compiler and run-time options:
314
315 \begin{enumerate}
316 \item {\bf compile time options:}
317
318 \begin{itemize}
319 \item {\em -module NeighborLB -module GreedyCommLB ...}  \\
320   links the modules NeighborLB, GreedyCommLB etc into an application, but these
321 load balancers will remain inactive at execution time unless overriden by other
322 runtime options.
323 \item {\em -module CommonLBs} \\
324   links a special module CommonLBs which includes some commonly used charmpp{}
325 built-in load balancers.
326 \item {\em -balancer GreedyCommLB} \\
327   links the load balancer GreedyCommLB and invokes this load balancer at
328 runtime.
329 \item {\em -balancer GreedyCommLB -balancer RefineLB} \\
330   invokes GreedyCommLB at the first load balancing step and RefineLB in all
331 subsequent load balancing steps.
332 \item {\em -balancer ComboCentLB:GreedyLB,RefineLB}  \\
333   One can choose to create a new combination load balancer made of multiple
334 load balancers. In the above example, GreedyLB and RefineLB strategies are
335 applied one after the other in each load balancing step.
336 \end{itemize}
337
338 The list of existing load balancers are in section \ref{lbStrategy}. Note: you
339 can have multiple -module *LB options. LB modules are linked into a program,
340 but they are not activated automatically at runtime.  Using -balancer at
341 compile time in order to activate load balancers automatically at run time.
342 Having -balancer A implies -module A, so you don't have to write -module A
343 again, although it does not hurt.  Using CommonLBs is a convenient way to link
344 against the commonly used existing load balancers.  One of the load balancers
345 called MetisLB requires the METIS library which is located at:
346 charm/src/libs/ck-libs/parmetis/METISLib/.  You need to compile METIS library
347 by "make METIS" under charm/tmp after you compile Charm++.
348
349 \item {\bf run-time options:}
350
351 Run-time options are similar to the compile time options as described above,
352 but they can override compile time options.
353
354 \begin{itemize}
355 \item {\em +balancer help} \\
356   displays all available balancers that have been linked in.
357 \item {\em +balancer GreedyCommLB} \\
358   invoked GreedyCommLB
359 \item {\em +balancer GreedyCommLB +balancer RefineLB} \\
360   invokes GreedyCommLB at the first load balancing step and RefineLB in all
361 subsequent load balancing steps.
362 \item {\em +balancer ComboCentLB:GreedyLB,RefineLB}  \\
363   same as the example in the -balancer compile time option.
364 \end{itemize}
365
366 Note: +balancer option works only if you have already linked the load balancers module at compile time. 
367 Giving +balancer with a wrong LB name will result in a runtime error.
368 When you have used -balancer A as compile time option, you don't need to use 
369 +balancer A again to activate it at runtime. However, you can 
370 use +balancer B to override the compile time option and choose to
371 activate B instead of A.
372
373 \item {\bf When there is no load balancer activated}
374
375 When you don't activate any of the load balancers at compile time or run time, 
376 and your program counts on a load balancer because you use {\em AtSync()}
377 and expect {\em ResumeFromSync()} to be called to continue,
378 be assured that your program can still run. 
379 A special load balancer called {\em NullLB} is 
380 automatically created in this case which just
381 calls {\em ResumeFromSync()} after {\em AtSync()}. 
382 This default load balancer keeps a program from hanging after calling {\em AtSync()}.
383 The {\em NullLB} is smart enough to keep silent if another 
384 load balancer is created.
385
386 \item {\bf Other useful run-time options}
387
388 There are a few other run-time options for load balancing that may be useful:
389
390 \begin{itemize}
391 \item {\em +LBDebug \{verbose level\}} \\
392      \{verbose level\} can be any positive integer number. 0 to turn off. 
393      This option asks load balancer to output more information to stdout 
394 about load balancing. The bigger the verbose level, the more verbose the output is.
395 \item {\em +LBPeriod \{seconds\}} \\
396      \{seconds\} can be any float number. This sets the minimum period time in 
397 seconds between two consecutive load balancing steps. The default value is 
398 1 second. That is to say a second load balancing step won't happen until
399 after 1 second since the last load balancing step.
400 \item {\em +LBSameCpus} \\
401      this option simply tells load balancer that all processors are of same speed. The load balancer will then skip the measurement of CPU speed at run-time.
402 \item {\em +LBObjOnly} \\
403      this tells load balancer to ignore processor background load when making migration decisions.
404 \item {\em +LBSyncResume} \\
405      after load balancing step, normally a processor can resume computation 
406 once all objects are received on that processor, even when other processors
407 are still working on migrations.  If this turns out to be a problem, 
408 that is when some processors start working on computation while the other 
409 processors are still busy migrating objects, then use this option to force 
410 a global barrier on all processors to make sure processors can only resume 
411 computation after migrations finish on all processors.
412 \item {\em +LBOff} \\
413      Turns off load balancing instrumentation at startup time. This call turns
414 off the instrument of both CPU and communication usage.
415 \item {\em +LBCommOff} \\
416      Turns off load balancing instrumentation of communication at startup time. 
417 The instrument of CPU usage is left on.
418 \end{itemize}
419
420 \end{enumerate}
421
422 \subsubsection{Load Balancing Simulation}
423
424 The simulation feature of load balancing framework allows the users to collect information
425 about the compute wall/cpu time and communication of the chares during a particular run of
426 the program and use this information to later test different load balancing strategies to
427 see which one is suitable for the programs behaviour. Currently, this feature is supported only for
428 the centralized load balancing strategies. For this, the load balancing framework
429 accepts the following command line options:
430 \begin{enumerate}
431 \item {\em +LBDump StepStart}\\
432         This will dump the instrument/communication data collected by the load balancing framework
433         starting from the load balancing step {\em StepStart} into a file on the disk. The name of the file
434         is given by the {\em +LBDumpFile} option. The first step in the program is number 0. Negative
435         numbers will be converted to 0.
436 \item {\em +LBDumpSteps StepsNo}\\
437         This option specifies the number of steps for which data will be dumped to disk. If omitted, default value is 1.
438         The program will exit after StepsNo files are dumped.
439 \item {\em +LBDumpFile FileName}\\
440         This option specifies the base name of the file into which the load balancing data is dumped. If this
441         option is not specified, the framework uses the default file {\tt lbdata.dat}. Since multiple steps are allowed,
442         a number is appended to the filename in the form {\tt Filename.\#}; this applies to both dump and
443         simulation.
444 \item {\em +LBSim StepStart}\\
445         This option instructs the framework to do the simulation during the first load balancing step.
446         When this option is specified, the load balancing data from the file specified in the {\em +LBDumpFile}
447         option, with the addition of the step number, will be read and this data
448         will be used for the load balancing. The program will print the results
449         of the balancing for a number of steps given by the {\em +LBSimSteps} option, and then will exit.
450 \item {\em +LBSimSteps StepsNo}\\
451         This option has the same meaning of {\em +LBDumpSteps}, except that apply for the simulation mode.
452         Default value is 1.
453 \item {\em +LBSimProcs}\\
454         This option may change the number of processors target of the load balancer strategy. It may be used to test
455         the load balancer in conditions where some processor crashes or someone becomes available. If this number is not
456         changed since the original run, starting from the second step file the program will print other additional
457         information about how the simulated load differs from the real load during the run (considering all
458         strategies that were applied while running). This may be used to test the validity of a load balancer
459         prediction over the reality. If the strategies used during run and simulation differ, the additional data
460         printed may not be useful.
461 \end{enumerate}
462 As an example, we can collect the data for a 1000 processor run of a program using:
463 \begin{alltt}
464 ./charmrun pgm +p 1000 +balancer RandCentLB +LBDump 2 +LBDumpSteps 4 +LBDumpFile dump.dat
465 \end{alltt}
466 This will collect data on files data.dat.{2,3,4,5}. Then, we can use this data to observe various centralized strategies using:
467 \begin{alltt}
468 ./charmrun pgm +balancer <Strategy to test> +LBSim 2 +LBSimSteps 4 +LBDumpFile dump.dat [+LBSimProcs 900]
469 \end{alltt}
470
471 \subsubsection{Future load predictor}
472
473 When objects do not follow the assumption that the future workload will be the
474 same as the past, the load balancer might not have the correct information to do
475 a correct rebalancing job. To prevent this the user can provide a transition
476 function to the load balancer to predict what will be the future workload, given
477 the past, instrumented one. As said, the user might provide a specific class
478 which inherits from {\tt LBPredictorFunction} and implement the appropriate functions. 
479 Here is the abstract class:
480 \begin{alltt}
481 class LBPredictorFunction {
482 public:
483   int num_params;
484  
485   virtual void initialize_params(double *x);
486
487   virtual double predict(double x, double *params) =0;
488   virtual void print(double *params) {PredictorPrintf("LB: unknown model");};
489   virtual void function(double x, double *param, double &y, double *dyda) =0;
490 };
491 \end{alltt}
492 \begin{itemize}
493 \item {\tt initialize\_params} by default initializes the parameters randomly. If the user
494 knows how they should be, this function can be reimplemented.
495 \item {\tt predict} is the function the model implements. For example, if the function is
496 $y=ax+b$, the method in the implemented class should be like:
497 \begin{verbatim}
498 double predict(double x, double *param) {return (param[0]*x + param[1]);}
499 \end{verbatim}
500 \item {\tt print} is a debugging function and it can be reimplemented to have a meaningful
501 print of the learnt model
502 \item {\tt function} is a function internally needed to learn the parameters, {\tt x} and
503 {\tt param} are input, {\tt y} and {\tt dyda} are output (the computed function and
504 all its derivatives with respect to the parameters, respectively).
505 For the function in the example should look like:
506 \begin{verbatim}
507 void function(double x, double *param, double &y, double *dyda) {
508   y = predict(x, param);
509   dyda[0] = x;
510   dyda[1] = 1;
511 }
512 \end{verbatim}
513 \end{itemize}
514 Other than these function, the user should provide a constructor which must initialize
515 {\tt num\_params} to the number of parameters the model has to learn. This number is
516 the dimension of {\tt param} and {\tt dyda} in the previous functions. For the given
517 example, the constructor is {\tt \{num\_params = 2;\}}.
518
519 If the model behind the computation is not known, the user can leave the system to
520 use a predefined default function.
521
522 As seen, the function can have several parameters which will be learned during
523 the execution of the program. For this, two parameters can be setup at command
524 line to specify the learning behaviour:
525 \begin{enumerate}
526 \item {\em +LBPredictorWindow size}\\
527 This parameter will specify how many statistics the load balancer will keep. 
528 The greater this number is, the better the
529 approximation of the workload will be, but more memory is required to store
530 the intermediate information. The default is 20.
531 \item {\em +LBPredictorDelay steps}\\
532 This will tell how many load balancer steps to wait before considering the
533 function parameters learnt and start using the mode. The load balancer will
534 collect statistics for a {\em +LBPredictorWindow} steps, but it will start using
535 the model as soon as {\em +LBPredictorDelay} information are collected. The
536 default is 10.
537 \end{enumerate}
538 Moreover another flag can be set to enable the predictor from command line: {\em
539 +LBPredictor}.\\
540 Other than the command line options, there are some methods
541 callable from user program to modify the predictor. These methods are:
542 \begin{itemize}
543 \item {\tt void PredictorOn(LBPredictorFunction *model);}
544 \item {\tt void PredictorOn(LBPredictorFunction *model,int wind);}
545 \item {\tt void PredictorOff();}
546 \item {\tt void ChangePredictor(LBPredictorFunction *model);}
547 \end{itemize}
548
549
550 \subsubsection{Seed load balancers - load balancing Chares at creation time}
551
552 \label{seedlb}
553
554 Seed load balancing involves the movement of object creation messages, or
555 "seeds", to create a balance of work across a set of processors. This load
556 balancing scheme is used for load balancing chares only at creation time. When
557 the chare is created on a processor, there is no movement of the chare due to
558 the seed load balancer. The measurement based load balancer described in
559 previous subsection perform the task of moving chares during work to achieve
560 load balance.
561
562 Several variations of strategies have been designed and analyzed. 
563 \begin{enumerate}
564 \item {\em random}\\  
565  A strategy that places seeds randomly when they are created and does
566 no movement of seeds thereafter. This is used as the default seed 
567 load balancer.
568 \item {\em neighbor}\\  
569  a strategy which imposes a virtual topology on the processors,
570  load exchange happens to neighbors only. The overloaded processors
571  initiate the load balancing, where a processor sends work to its neighbors
572  when it becomes overloaded. The default topology is mesh2D, one can use
573  command line option to choose other topology such as ring, mesh3D and 
574  dense graph.
575 \item {\em spray}\\  
576  a strategy which imposes a spanning tree organization on the processors,
577  results in communication via global reduction among all processors 
578  to compute global average load via periodic reduction. 
579  It uses averaging of loads to determine how seeds should be
580 distributed.
581 \end{enumerate}
582
583 Other strategies can also be explored follow the simple API of the 
584 seed load balancer.
585 \linebreak
586
587 {\bf Seed load balancers for Chares:}
588
589 Seed load balancers can be directly used for load balancing Chares.
590 The default seed load balancer which is always linked is the random seed load balancer.
591 Users can choose another strategy listed above and link as a plugin
592 module into binary as described below.
593
594 {\bf Seed load balancers for Array Elements:}
595
596 Seed load balancers can also be used for array elements in the same way 
597 as they are used for individual chares.
598 Chare array is a collection of individual Chares in Charm++.
599 Since Chare Array has its internal strategy of static mapping of individual
600 array elements to processors using {\em CkArrayMap}~\ref{array map}~\footnote{by default it always distributed array elements to processors in Round-Robin fashion unless a different CkArrayMap is used}, 
601 a special CkArrayMap called {\em CldMap} must be created and passed into
602 array creation calls to interface with seed load balancer.
603
604 For creating an empty array and then inserting chares into it, the API is as follows:
605
606 \begin{alltt}
607   CkArrayOptions opt;
608   CkGroupID cldmapID = CProxy_CldMap::ckNew();
609   opt.setMap(cldmapID);
610   CProxy_WorkUnit arr = CProxy_WorkUnit::ckNew(param, opt); 
611   for (int i=0; i<numChares; i++) 
612     arr[i].insert(param);
613 \end{alltt}
614
615 For initially populating the array with chares at time of creation the API is as follows:
616 \begin{alltt}
617   CkArrayOptions opt(numChares);
618   CkGroupID cldmapID = CProxy_CldMap::ckNew();
619   opt.setMap(cldmapID);
620   CProxy_WorkUnit arr = CProxy_WorkUnit::ckNew(param, opt); 
621 \end{alltt}
622
623 The details about array creation are explained in section~\ref{advanced arrays} of the manual.
624
625 {\bf Compile and run time options for seed load balancers}
626
627 To choose a seed load balancer other than the default {\em rand} strategy,
628 use link time command line option {\bf -balance foo}. 
629
630 When using {\rm neighbor} seed load balancer, one can also specify
631 the virtual topology at runtime. Use {\bf +LBTopo topo}, where {\em topo}
632 can be one of: (a) ring, (b) mesh2d, (c) mesh3d and (d) graph.
633
634 To write a seed load balancer, name your file as {\em cldb.foo.c},
635 where {\em foo} is the strategy name.  Compile it in the form of library
636 under charm/lib, named as {\em libcldb-foo.a}, where {\em foo} is the strategy 
637 name used above. Now one can use {\bf -balance foo} as compile time option
638 to {\bf charmc} to link with the {\em foo} seed load balancer.
639
640 \subsubsection{Simple Load Balancer Usage Example - Automatic with Sync LB}
641 \label{lbexample}
642
643 A simple example of how to use a load balancer in sync mode in one's
644 application is presented below.
645
646 \begin{alltt}
647 /*** lbexample.ci ***/
648 mainmodule lbexample {
649   readonly CProxy_Main mainProxy;
650   readonly int nElements;
651
652   mainchare Main {
653     entry Main(CkArgMsg *m);
654     entry void done(void);
655   };
656
657   array [1D] LBExample {
658     entry LBExample(void);
659     entry void doWork();
660   };
661 };
662 \end{alltt}
663
664 --------------------------------------------------------------------------------
665
666 \begin{alltt}
667 /*** lbexample.C ***/
668 #include <stdio.h>
669 #include "lbexample.decl.h"
670
671 /*readonly*/ CProxy_Main mainProxy;
672 /*readonly*/ int nElements;
673
674 #define MAX_WORK_CNT 50
675 #define LB_INTERVAL 5
676
677 /*mainchare*/
678 class Main : public CBase_Main
679 {
680 private:
681   int count;
682 public:
683   Main(CkArgMsg* m)
684   {
685     /*....Initialization....*/
686     mainProxy = thisProxy;
687     CProxy_LBExample arr = CProxy_LBExample::ckNew(nElements);
688     arr.doWork();
689   };
690
691   void done(void)
692   {
693     count++;
694     if(count==nElements){
695       CkPrintf("All done");
696       CkExit();
697     }
698   };
699 };
700
701 /*array [1D]*/
702 class LBExample : public CBase_LBExample
703 {
704 private:
705   int workcnt;
706 public:
707   LBExample()
708   {
709     workcnt=0;
710     /* May initialize some variables to be used in doWork */
711     //Must be set to CmiTrue to make AtSync work
712     usesAtSync=CmiTrue;
713   }
714
715   LBExample(CkMigrateMessage *m) { /* Migration constructor -- invoked when chare migrates */ }
716   
717   /* Must be written for migration to succeed */
718   void pup(PUP::er &p){
719     CBase_LBExample::pup(p);
720     p|workcnt;
721     /* There may be some more variables used in doWork */
722   }
723         
724   void doWork()
725   {
726     /* Do work proportional to the chare index to see the effects of LB */
727     
728     workcnt++;
729     if(workcnt==MAX_WORK_CNT)
730       mainProxy.done();
731     
732     if(workcnt\%LB_INTERVAL==0)
733       AtSync();
734     else
735       doWork();
736   }
737   
738   void ResumeFromSync(){
739     doWork();
740   }
741 };
742
743 #include "lbexample.def.h"
744 \end{alltt}