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