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