d5346a1987dbcfa2ebd210f0a3da8fc22f7b91c7
[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" 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 {\em AtSync()} is not a blocking call, it just gives a hint to load
206 balancing that it is time for load balancing. During the time between {\em
207 AtSync} and {\em ResumeFromSync}, the object may be migrated. One can choose
208 to let objects continue working with incoming messages, however keep in mind
209 the object may suddenly show up in another processor and make sure no
210 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().
211
212 The more commonly used approach is to force the object to be idle until load
213 balancing finishes. The user places an AtSync call at the end of some iteration
214 and when all elements reach that call load balancing is triggered. The objects
215 can start executing again when \kw{ResumeFromSync()} is called. In this case,
216 the user redefines ResumeFromSync() to trigger the next iteration of the
217 application. This manual way of using the at sync mode results in a barrier at
218 load balancing (see example here~\ref{lbexample}).
219 %
220 \item {\bf Manual mode}: The load balancer can be programmed to be started
221 manually. To switch to the manual mode, you should call {\em TurnManualLBOn()}
222 on every processor to prevent load balancer from starting automatically. {\em
223 TurnManualLBOn()} should be called as early as possible in the program. It
224 could be called at the initialization part of the program, for example from a
225 global variable constructor, or in an initcall~\ref{initcall}.  It can also be
226 called in the constructor of a static array and definitely before the {\em
227 doneInserting} call for a dynamic array.  It can be called multiple times on
228 one processor, but only the last one takes effect.
229
230 The function call {\em StartLB()} starts load balancing immediately. This call
231 should be made at only one place on only one processor. This function is also
232 not blocking, the object will continue to process messages and the load
233 balancing when triggered happens at the background.
234
235 {\em TurnManualLBOff()} turns off manual load balancing and switches back to
236 the automatic Load balancing mode.
237 %
238 \end{enumerate}
239
240 \subsubsection{Migrating objects}
241
242 \label{lbmigobj}
243
244 Load balancers migrate objects automatically.
245 For an array element to migrate, user can refer to section~\ref{arraymigratable}
246 for how to write a ``pup'' for an array element.
247
248 In general one needs to pack the whole snapshot of the member data in an 
249 array element in the pup subroutine. This is because the migration of
250 the object may happen at any time. In certain load balancing scheme where
251 user explicitly control when the load balancing happens, user may choose
252 to pack only a part of the data and may skip those temporary data.
253
254 \subsubsection{Other utility functions}
255
256 There are several utility functions that can be called in applications to
257 configure the load balancer, etc. These functions are:
258
259 \begin{itemize}
260 \item {\bf LBTurnInstrumentOn()} and {\bf LBTurnInstrumentOff()}: are plain C
261       functions to control the load balancing statistics instrumentation
262       on or off on the calling processor. No implicit broadcast or 
263       synchronization exists in these functions.
264       Fortran interface: {\bf FLBTURNINSTRUMENTON()} and {\bf FLBTURNINSTRUMENTOFF()}.
265 \item {\bf setMigratable(CmiBool migratable)}: is a member function of array
266       element. This function can be called 
267       in an array element constructor to tell load balancer whether this object
268       is migratable or not\footnote{Currently not all load balancers 
269       recognize this setting though.}.
270 \item {\bf LBSetPeriod(double s)}: this function can be called
271       anywhere (even in Charm++ initcalls) to specify 
272       the load balancing period time in seconds. 
273       It tells load balancer not to start next 
274       load balancing in less than $s$ seconds. This can be used to prevent 
275       load balancing from occurring too often in 
276       {\em automatic without sync mode}. Here is how to use it:
277       \begin{alltt}
278 // if used in an array element
279 LBDatabase *lbdb = getLBDB();
280 lbdb->SetLBPeriod(5.0);
281
282 // if used outside of an array element
283 LBSetPeriod(5.0);
284 \end{alltt}
285       Alternatively, one can specify +LBPeriod \{seconds\} at command line.
286 \end{itemize}
287
288 \subsubsection{Compiler and run-time options to use load balancing module}
289
290 \label{lbOption}
291
292 Load balancing strategies are implemented as libraries in \charmpp{}. This
293 allows programmers to easily experiment with different existing strategies 
294 by simply linking a pool of strategy modules and choosing
295 one to use at run-time via a command line option.
296
297 Please note that linking a load balancing module is different from activating it:
298 \begin{itemize}
299 \item link a LB module: is to link a Load Balancer module(library) at 
300    compile time; You can link against multiple LB libraries as candidates.
301 \item activate a LB: is to actually ask at run-time to create a LB strategy and 
302    start it. You can only activate load balancers that have been linked at
303    compile time.
304 \end{itemize}
305
306
307 Below are the descriptions about the compiler and run-time options:
308
309 \begin{enumerate}
310 \item {\bf compile time options:}
311
312 \begin{itemize}
313 \item {\em -module NeighborLB -module GreedyCommLB ...}  \\
314   links the modules NeighborLB, GreedyCommLB etc into an application, but these
315 load balancers will remain inactive at execution time unless overriden by other
316 runtime options.
317 \item {\em -module CommonLBs} \\
318   links a special module CommonLBs which includes some commonly used charmpp{}
319 built-in load balancers.
320 \item {\em -balancer GreedyCommLB} \\
321   links the load balancer GreedyCommLB and invokes this load balancer at
322 runtime.
323 \item {\em -balancer GreedyCommLB -balancer RefineLB} \\
324   invokes GreedyCommLB at the first load balancing step and RefineLB in all
325 subsequent load balancing steps.
326 \item {\em -balancer ComboCentLB:GreedyLB,RefineLB}  \\
327   One can choose to create a new combination load balancer made of multiple
328 load balancers. In the above example, GreedyLB and RefineLB strategies are
329 applied one after the other in each load balancing step.
330 \end{itemize}
331
332 The list of existing load balancers are in section \ref{lbStrategy}. Note: you
333 can have multiple -module *LB options. LB modules are linked into a program,
334 but they are not activated automatically at runtime.  Using -balancer at
335 compile time in order to activate load balancers automatically at run time.
336 Having -balancer A implies -module A, so you don't have to write -module A
337 again, although it does not hurt.  Using CommonLBs is a convenient way to link
338 against the commonly used existing load balancers.  One of the load balancers
339 called MetisLB requires the METIS library which is located at:
340 charm/src/libs/ck-libs/parmetis/METISLib/.  You need to compile METIS library
341 by "make METIS" under charm/tmp after you compile Charm++.
342
343 \item {\bf run-time options:}
344
345 Run-time options are similar to the compile time options as described above,
346 but they can override compile time options.
347
348 \begin{itemize}
349 \item {\em +balancer help} \\
350   displays all available balancers that have been linked in.
351 \item {\em +balancer GreedyCommLB} \\
352   invoked GreedyCommLB
353 \item {\em +balancer GreedyCommLB +balancer RefineLB} \\
354   invokes GreedyCommLB at the first load balancing step and RefineLB in all
355 subsequent load balancing steps.
356 \item {\em +balancer ComboCentLB:GreedyLB,RefineLB}  \\
357   same as the example in the -balancer compile time option.
358 \end{itemize}
359
360 Note: +balancer option works only if you have already linked the load balancers module at compile time. 
361 Giving +balancer with a wrong LB name will result in a runtime error.
362 When you have used -balancer A as compile time option, you don't need to use 
363 +balancer A again to activate it at runtime. However, you can 
364 use +balancer B to override the compile time option and choose to
365 activate B instead of A.
366
367 \item {\bf When there is no load balancer activated}
368
369 When you don't activate any of the load balancers at compile time or run time, 
370 and your program counts on a load balancer because you use {\em AtSync()}
371 and expect {\em ResumeFromSync()} to be called to continue,
372 be assured that your program can still run. 
373 A special load balancer called {\em NullLB} is 
374 automatically created in this case which just
375 calls {\em ResumeFromSync()} after {\em AtSync()}. 
376 This default load balancer keeps a program from hanging after calling {\em AtSync()}.
377 The {\em NullLB} is smart enough to keep silent if another 
378 load balancer is created.
379
380 \item {\bf Other useful run-time options}
381
382 There are a few other run-time options for load balancing that may be useful:
383
384 \begin{itemize}
385 \item {\em +LBDebug \{verbose level\}} \\
386      \{verbose level\} can be any positive integer number. 0 to turn off. 
387      This option asks load balancer to output more information to stdout 
388 about load balancing. The bigger the verbose level, the more verbose the output is.
389 \item {\em +LBPeriod \{seconds\}} \\
390      \{seconds\} can be any float number. This sets the minimum period time in 
391 seconds between two consecutive load balancing steps. The default value is 
392 1 second. That is to say a second load balancing step won't happen until
393 after 1 second since the last load balancing step.
394 \item {\em +LBSameCpus} \\
395      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.
396 \item {\em +LBObjOnly} \\
397      this tells load balancer to ignore processor background load when making migration decisions.
398 \item {\em +LBSyncResume} \\
399      after load balancing step, normally a processor can resume computation 
400 once all objects are received on that processor, even when other processors
401 are still working on migrations.  If this turns out to be a problem, 
402 that is when some processors start working on computation while the other 
403 processors are still busy migrating objects, then use this option to force 
404 a global barrier on all processors to make sure processors can only resume 
405 computation after migrations finish on all processors.
406 \item {\em +LBOff} \\
407      Turns off load balancing instrumentation at startup time. This call turns
408 off the instrument of both CPU and communication usage.
409 \item {\em +LBCommOff} \\
410      Turns off load balancing instrumentation of communication at startup time. 
411 The instrument of CPU usage is left on.
412 \end{itemize}
413
414 \end{enumerate}
415
416 \subsubsection{Load Balancing Simulation}
417
418 The simulation feature of load balancing framework allows the users to collect information
419 about the compute wall/cpu time and communication of the chares during a particular run of
420 the program and use this information to later test different load balancing strategies to
421 see which one is suitable for the programs behaviour. Currently, this feature is supported only for
422 the centralized load balancing strategies. For this, the load balancing framework
423 accepts the following command line options:
424 \begin{enumerate}
425 \item {\em +LBDump StepStart}\\
426         This will dump the instrument/communication data collected by the load balancing framework
427         starting from the load balancing step {\em StepStart} into a file on the disk. The name of the file
428         is given by the {\em +LBDumpFile} option. The first step in the program is number 0. Negative
429         numbers will be converted to 0.
430 \item {\em +LBDumpSteps StepsNo}\\
431         This option specifies the number of steps for which data will be dumped to disk. If omitted, default value is 1.
432         The program will exit after StepsNo files are dumped.
433 \item {\em +LBDumpFile FileName}\\
434         This option specifies the base name of the file into which the load balancing data is dumped. If this
435         option is not specified, the framework uses the default file {\tt lbdata.dat}. Since multiple steps are allowed,
436         a number is appended to the filename in the form {\tt Filename.\#}; this applies to both dump and
437         simulation.
438 \item {\em +LBSim StepStart}\\
439         This option instructs the framework to do the simulation during the first load balancing step.
440         When this option is specified, the load balancing data from the file specified in the {\em +LBDumpFile}
441         option, with the addition of the step number, will be read and this data
442         will be used for the load balancing. The program will print the results
443         of the balancing for a number of steps given by the {\em +LBSimSteps} option, and then will exit.
444 \item {\em +LBSimSteps StepsNo}\\
445         This option has the same meaning of {\em +LBDumpSteps}, except that apply for the simulation mode.
446         Default value is 1.
447 \item {\em +LBSimProcs}\\
448         This option may change the number of processors target of the load balancer strategy. It may be used to test
449         the load balancer in conditions where some processor crashes or someone becomes available. If this number is not
450         changed since the original run, starting from the second step file the program will print other additional
451         information about how the simulated load differs from the real load during the run (considering all
452         strategies that were applied while running). This may be used to test the validity of a load balancer
453         prediction over the reality. If the strategies used during run and simulation differ, the additional data
454         printed may not be useful.
455 \end{enumerate}
456 As an example, we can collect the data for a 1000 processor run of a program using:
457 \begin{alltt}
458 ./charmrun pgm +p 1000 +balancer RandCentLB +LBDump 2 +LBDumpSteps 4 +LBDumpFile dump.dat
459 \end{alltt}
460 This will collect data on files data.dat.{2,3,4,5}. Then, we can use this data to observe various centralized strategies using:
461 \begin{alltt}
462 ./charmrun pgm +balancer <Strategy to test> +LBSim 2 +LBSimSteps 4 +LBDumpFile dump.dat [+LBSimProcs 900]
463 \end{alltt}
464
465 \subsubsection{Future load predictor}
466
467 When objects do not follow the assumption that the future workload will be the
468 same as the past, the load balancer might not have the correct information to do
469 a correct rebalancing job. To prevent this the user can provide a transition
470 function to the load balancer to predict what will be the future workload, given
471 the past, instrumented one. As said, the user might provide a specific class
472 which inherits from {\tt LBPredictorFunction} and implement the appropriate functions. 
473 Here is the abstract class:
474 \begin{alltt}
475 class LBPredictorFunction {
476 public:
477   int num_params;
478  
479   virtual void initialize_params(double *x);
480
481   virtual double predict(double x, double *params) =0;
482   virtual void print(double *params) {PredictorPrintf("LB: unknown model");};
483   virtual void function(double x, double *param, double &y, double *dyda) =0;
484 };
485 \end{alltt}
486 \begin{itemize}
487 \item {\tt initialize\_params} by default initializes the parameters randomly. If the user
488 knows how they should be, this function can be reimplemented.
489 \item {\tt predict} is the function the model implements. For example, if the function is
490 $y=ax+b$, the method in the implemented class should be like:
491 \begin{verbatim}
492 double predict(double x, double *param) {return (param[0]*x + param[1]);}
493 \end{verbatim}
494 \item {\tt print} is a debugging function and it can be reimplemented to have a meaningful
495 print of the learnt model
496 \item {\tt function} is a function internally needed to learn the parameters, {\tt x} and
497 {\tt param} are input, {\tt y} and {\tt dyda} are output (the computed function and
498 all its derivatives with respect to the parameters, respectively).
499 For the function in the example should look like:
500 \begin{verbatim}
501 void function(double x, double *param, double &y, double *dyda) {
502   y = predict(x, param);
503   dyda[0] = x;
504   dyda[1] = 1;
505 }
506 \end{verbatim}
507 \end{itemize}
508 Other than these function, the user should provide a constructor which must initialize
509 {\tt num\_params} to the number of parameters the model has to learn. This number is
510 the dimension of {\tt param} and {\tt dyda} in the previous functions. For the given
511 example, the constructor is {\tt \{num\_params = 2;\}}.
512
513 If the model behind the computation is not known, the user can leave the system to
514 use a predefined default function.
515
516 As seen, the function can have several parameters which will be learned during
517 the execution of the program. For this, two parameters can be setup at command
518 line to specify the learning behaviour:
519 \begin{enumerate}
520 \item {\em +LBPredictorWindow size}\\
521 This parameter will specify how many statistics the load balancer will keep. 
522 The greater this number is, the better the
523 approximation of the workload will be, but more memory is required to store
524 the intermediate information. The default is 20.
525 \item {\em +LBPredictorDelay steps}\\
526 This will tell how many load balancer steps to wait before considering the
527 function parameters learnt and start using the mode. The load balancer will
528 collect statistics for a {\em +LBPredictorWindow} steps, but it will start using
529 the model as soon as {\em +LBPredictorDelay} information are collected. The
530 default is 10.
531 \end{enumerate}
532 Moreover another flag can be set to enable the predictor from command line: {\em
533 +LBPredictor}.\\
534 Other than the command line options, there are some methods
535 callable from user program to modify the predictor. These methods are:
536 \begin{itemize}
537 \item {\tt void PredictorOn(LBPredictorFunction *model);}
538 \item {\tt void PredictorOn(LBPredictorFunction *model,int wind);}
539 \item {\tt void PredictorOff();}
540 \item {\tt void ChangePredictor(LBPredictorFunction *model);}
541 \end{itemize}
542
543
544 \subsubsection{Seed load balancers - load balancing Chares at creation time}
545
546 \label{seedlb}
547
548 Seed load balancing involves the movement of object creation messages, or
549 "seeds", to create a balance of work across a set of processors. This load
550 balancing scheme is used for load balancing chares only at creation time. When
551 the chare is created on a processor, there is no movement of the chare due to
552 the seed load balancer. The measurement based load balancer described in
553 previous subsection perform the task of moving chares during work to achieve
554 load balance.
555
556 Several variations of strategies have been designed and analyzed. 
557 \begin{enumerate}
558 \item {\em random}\\  
559  A strategy that places seeds randomly when they are created and does
560 no movement of seeds thereafter. This is used as the default seed 
561 load balancer.
562 \item {\em neighbor}\\  
563  a strategy which imposes a virtual topology on the processors,
564  load exchange happens to neighbors only. The overloaded processors
565  initiate the load balancing, where a processor sends work to its neighbors
566  when it becomes overloaded. The default topology is mesh2D, one can use
567  command line option to choose other topology such as ring, mesh3D and 
568  dense graph.
569 \item {\em spray}\\  
570  a strategy which imposes a spanning tree organization on the processors,
571  results in communication via global reduction among all processors 
572  to compute global average load via periodic reduction. 
573  It uses averaging of loads to determine how seeds should be
574 distributed.
575 \end{enumerate}
576
577 Other strategies can also be explored follow the simple API of the 
578 seed load balancer.
579 \linebreak
580
581 {\bf Seed load balancers for Chares:}
582
583 Seed load balancers can be directly used for load balancing Chares.
584 The default seed load balancer which is always linked is the random seed load balancer.
585 Users can choose another strategy listed above and link as a plugin
586 module into binary as described below.
587
588 {\bf Seed load balancers for Array Elements:}
589
590 Seed load balancers can also be used for array elements in the same way 
591 as they are used for individual chares.
592 Chare array is a collection of individual Chares in Charm++.
593 Since Chare Array has its internal strategy of static mapping of individual
594 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}, 
595 a special CkArrayMap called {\em CldMap} must be created and passed into
596 array creation calls to interface with seed load balancer.
597
598 For creating an empty array and then inserting chares into it, the API is as follows:
599
600 \begin{alltt}
601   CkArrayOptions opt;
602   CkGroupID cldmapID = CProxy_CldMap::ckNew();
603   opt.setMap(cldmapID);
604   CProxy_WorkUnit arr = CProxy_WorkUnit::ckNew(param, opt); 
605   for (int i=0; i<numChares; i++) 
606     arr[i].insert(param);
607 \end{alltt}
608
609 For initially populating the array with chares at time of creation the API is as follows:
610 \begin{alltt}
611   CkArrayOptions opt(numChares);
612   CkGroupID cldmapID = CProxy_CldMap::ckNew();
613   opt.setMap(cldmapID);
614   CProxy_WorkUnit arr = CProxy_WorkUnit::ckNew(param, opt); 
615 \end{alltt}
616
617 The details about array creation are explained in section~\ref{advanced arrays} of the manual.
618
619 {\bf Compile and run time options for seed load balancers}
620
621 To choose a seed load balancer other than the default {\em rand} strategy,
622 use link time command line option {\bf -balance foo}. 
623
624 When using {\rm neighbor} seed load balancer, one can also specify
625 the virtual topology at runtime. Use {\bf +LBTopo topo}, where {\em topo}
626 can be one of: (a) ring, (b) mesh2d, (c) mesh3d and (d) graph.
627
628 To write a seed load balancer, name your file as {\em cldb.foo.c},
629 where {\em foo} is the strategy name.  Compile it in the form of library
630 under charm/lib, named as {\em libcldb-foo.a}, where {\em foo} is the strategy 
631 name used above. Now one can use {\bf -balance foo} as compile time option
632 to {\bf charmc} to link with the {\em foo} seed load balancer.
633
634 \subsubsection{Simple Load Balancer Usage Example - Automatic with Sync LB}
635 \label{lbexample}
636
637 A simple example of how to use a load balancer in sync mode in one's
638 application is presented below.
639
640 \begin{alltt}
641 /*** lbexample.ci ***/
642 mainmodule lbexample {
643   readonly CProxy_Main mainProxy;
644   readonly int nElements;
645
646   mainchare Main {
647     entry Main(CkArgMsg *m);
648     entry void done(void);
649   };
650
651   array [1D] LBExample {
652     entry LBExample(void);
653     entry void doWork();
654   };
655 };
656 \end{alltt}
657
658 --------------------------------------------------------------------------------
659
660 \begin{alltt}
661 /*** lbexample.C ***/
662 #include <stdio.h>
663 #include "lbexample.decl.h"
664
665 /*readonly*/ CProxy_Main mainProxy;
666 /*readonly*/ int nElements;
667
668 #define MAX_WORK_CNT 50
669 #define LB_INTERVAL 5
670
671 /*mainchare*/
672 class Main : public CBase_Main
673 {
674 private:
675   int count;
676 public:
677   Main(CkArgMsg* m)
678   {
679     /*....Initialization....*/
680     mainProxy = thisProxy;
681     CProxy_LBExample arr = CProxy_LBExample::ckNew(nElements);
682     arr.doWork();
683   };
684
685   void done(void)
686   {
687     count++;
688     if(count==nElements){
689       CkPrintf("All done");
690       CkExit();
691     }
692   };
693 };
694
695 /*array [1D]*/
696 class LBExample : public CBase_LBExample
697 {
698 private:
699   int workcnt;
700 public:
701   LBExample()
702   {
703     workcnt=0;
704     /* May initialize some variables to be used in doWork */
705     //Must be set to CmiTrue to make AtSync work
706     usesAtSync=CmiTrue;
707   }
708
709   LBExample(CkMigrateMessage *m) { /* Migration constructor -- invoked when chare migrates */ }
710   
711   /* Must be written for migration to succeed */
712   void pup(PUP::er &p){
713     CBase_LBExample::pup(p);
714     p|workcnt;
715     /* There may be some more variables used in doWork */
716   }
717         
718   void doWork()
719   {
720     /* Do work proportional to the chare index to see the effects of LB */
721     
722     workcnt++;
723     if(workcnt==MAX_WORK_CNT)
724       mainProxy.done();
725     
726     if(workcnt\%LB_INTERVAL==0)
727       AtSync();
728     else
729       doWork();
730   }
731   
732   void ResumeFromSync(){
733     doWork();
734   }
735 };
736
737 #include "lbexample.def.h"
738 \end{alltt}