doc/charm/loadbalance
[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 80's. 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 desktop
36 machines), one can use a combination of the two kinds of strategies. The
37 baseline 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 runtime. 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 a 
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 balance the 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}:      Uses METIS\texttrademark\hspace{0mm} to partitioning object communication graph.
117 \item {\bf GreedyLB}:   Uses a greedy algorithm that always assigns the heaviest object to the least loaded processor.
118 \item {\bf GreedyCommLB}:  Extends the greedy algorithm to take the communication graph into account.
119 \item {\bf TopoCentLB}:    Extends the greedy algorithm to take processor topology into account.
120 \item {\bf RefineLB}:     Moves 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 takes communication into account.
122 \item {\bf RefineTopoLB}:       Same idea as in RefineLB, but takes 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 interfering 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 appropriate for their
139 application. The compiler and runtime 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 is done automatically and APIs are provided
155 for users to trigger the load balancing.  To use the load balancer, you must
156 make your array elements migratable (see migration section above) and choose a
157 \kw{load balancing strategy} (see the section \ref{lbStrategy} for a
158 description of available load balancing strategies).
159
160 There are three different ways to use load balancing for chare arrays to meet
161 different needs of the applications. These methods are different in how and
162 when a load balancing phase starts. The three methods are: {\bf periodic load
163 balancing mode}, {\bf at sync mode} and {\bf manual mode}.
164
165 In {\em periodic load balancing mode}, a user just needs to specify how often
166 he wants the load balancing to occur, using +LBPeriod runtime option to specify
167 a time interval.
168
169 In {\em sync mode}, users can tell the load balancer explicitly when is a good
170 time to trigger load balancing by inserting a function call (AtSync) in the
171 user code.
172
173 In the above two load balancing modes, users do not need to worry about how to
174 start load balancing.  However, in one scenario, the above automatic load
175 balancers will fail to work - when array elements are created by dynamic insertion.
176 This is because the above two load balancing modes require an application to
177 have fixed number of objects at the time of load balancing.  The array manager
178 needs to maintain a head count of local array elements for the local barrier.
179 In this case, users have to use the {\em manual mode} to trigger load balancer
180 themselves.
181
182 The detailed APIs of these three methods are described as follows:
183 %
184 \begin{enumerate}
185 %
186 \item {\bf Periodical load balancing mode}: In the default setting, load
187 balancing happens whenever the array elements are ready, with an interval of 1
188 second. It is desirable for the application to set a larger interval using
189 +LBPeriod runtime option. For example ``+LBPeriod 5.0'' can be used to start load
190 balancing roughly every 5 seconds. By default, array elements may be asked to
191 migrate at any time provided that they are not in the middle of executing an
192 entry method. The array element's variable \kw{usesAtSync} being CmiFalse
193 attributes to this default behavior.
194 %
195 \item {\bf At sync mode}: Using this method, elements can only be migrated at
196 certain points in the execution when user calls \kw{AtSync()}. For using the at
197 sync mode, one should set \kw{usesAtSync} to CmiTrue in the array element
198 constructor.  When an element is ready to migrate, call
199 \kw{AtSync()}~\footnote{AtSync() is a member function of class ArrayElement}.
200 When all local elements call \kw{AtSync}, the load balancer is triggered.  Once
201 all migrations are completed, the load balancer calls the virtual function
202 \kw{ArrayElement::ResumeFromSync()} on each of the array elements. This
203 function can be redefined in the application.
204
205 Note that the minimum time for \kw{AtSync()} load balancing to occur
206 is controlled by the LBPeriod.  Unusually high frequency load
207 balancing (more frequent than 500ms) will perform better if this value
208 is set via +LBPeriod or \kw{SetLBPeriod()} to a number shorter than your load
209 balancing interval.
210
211 Note that {\em AtSync()} is not a blocking call, it just gives a hint to load
212 balancing that it is time for load balancing. During the time between {\em
213 AtSync} and {\em ResumeFromSync}, the object may be migrated. One can choose
214 to let objects continue working with incoming messages, however keep in mind
215 the object may suddenly show up in another processor and make sure no
216 operations that could possibly prevent migration be performed. This is the automatic way of doing load balancing where the application does not need to define ResumeFromSync().
217
218 The more commonly used approach is to force the object to be idle until load
219 balancing finishes. The user places an AtSync call at the end of some iteration
220 and when all elements reach that call load balancing is triggered. The objects
221 can start executing again when \kw{ResumeFromSync()} is called. In this case,
222 the user redefines ResumeFromSync() to trigger the next iteration of the
223 application. This manual way of using the at sync mode results in a barrier at
224 load balancing (see example here~\ref{lbexample}).
225 %
226 \item {\bf Manual mode}: The load balancer can be programmed to be started
227 manually. To switch to the manual mode, you should call {\em TurnManualLBOn()}
228 on every processor to prevent load balancer from starting automatically. {\em
229 TurnManualLBOn()} should be called as early as possible in the program. It
230 could be called at the initialization part of the program, for example from a
231 global variable constructor, or in an initcall~\ref{initcall}.  It can also be
232 called in the constructor of a static array and definitely before the {\em
233 doneInserting} call for a dynamic array.  It can be called multiple times on
234 one processor, but only the last one takes effect.
235
236 The function call {\em StartLB()} starts load balancing immediately. This call
237 should be made at only one place on only one processor. This function is also
238 not blocking, the object will continue to process messages and the load
239 balancing when triggered happens at the background.
240
241 {\em TurnManualLBOff()} turns off manual load balancing and switches back to
242 the automatic Load balancing mode.
243 %
244 \end{enumerate}
245
246 \subsubsection{Migrating objects}
247
248 \label{lbmigobj}
249
250 Load balancers migrate objects automatically.
251 For an array element to migrate, user can refer to section~\ref{arraymigratable}
252 for how to write a ``pup'' for an array element.
253
254 In general one needs to pack the whole snapshot of the member data in an 
255 array element in the pup subroutine. This is because the migration of
256 the object may happen at any time. In certain load balancing schemes where
257  the user explicitly controls when the load balancing happens, the user may choose
258 to pack only a part of the data and may skip those temporary data.
259
260 An array element can migrate by calling the \kw{migrateMe}(\uw{destination
261 processor}) member function-- this call must be the last action
262 in an element entry point.  The system can also migrate array elements
263 for load balancing (see the section~\ref{lbarray}).
264
265 To migrate your array element to another processor, the \charmpp{}
266 runtime will:
267
268 \begin{itemize}
269 \item Call your \kw{ckAboutToMigrate} method
270 \item Call your \uw{pup} method with a sizing \kw{PUP::er} to determine how 
271 big a message it needs to hold your element.
272 \item Call your \uw{pup} method again with a packing \kw{PUP::er} to pack 
273 your element into a message.
274 \item Call your element's destructor (killing off the old copy).
275 \item Send the message (containing your element) across the network.
276 \item Call your element's migration constructor on the new processor.
277 \item Call your \uw{pup} method on with an unpacking \kw{PUP::er} to unpack 
278 the element.
279 \item Call your \kw{ckJustMigrated} method
280 \end{itemize}
281
282 Migration constructors, then, are normally empty-- all the unpacking
283 and allocation of the data items is done in the element's \uw{pup} routine.
284 Deallocation is done in the element destructor as usual.
285
286
287 \subsubsection{Other utility functions}
288
289 There are several utility functions that can be called in applications to
290 configure the load balancer, etc. These functions are:
291
292 \begin{itemize}
293 \item {\bf LBTurnInstrumentOn()} and {\bf LBTurnInstrumentOff()}: are plain C
294       functions to control the load balancing statistics instrumentation
295       on or off on the calling processor. No implicit broadcast or 
296       synchronization exists in these functions.
297       Fortran interface: {\bf FLBTURNINSTRUMENTON()} and {\bf FLBTURNINSTRUMENTOFF()}.
298 \item {\bf setMigratable(CmiBool migratable)}: is a member function of array
299       element. This function can be called 
300       in an array element constructor to tell the load balancer whether this object
301       is migratable or not\footnote{Currently not all load balancers 
302       recognize this setting though.}.
303 \item {\bf LBSetPeriod(double s)}: this function can be called
304       anywhere (even in Charm++ initcalls) to specify 
305       the load balancing period time in seconds. 
306       It tells load balancer not to start next 
307       load balancing in less than $s$ seconds. This can be used to prevent 
308       load balancing from occurring too often in 
309       {\em automatic without sync mode}. Here is how to use it:
310       \begin{alltt}
311 // if used in an array element
312 LBDatabase *lbdb = getLBDB();
313 lbdb->SetLBPeriod(5.0);
314
315 // if used outside of an array element
316 LBSetPeriod(5.0);
317 \end{alltt}
318       Alternatively, one can specify +LBPeriod \{seconds\} at command line.
319 \end{itemize}
320
321 \subsubsection{Compiler and runtime options to use load balancing module}
322
323 \label{lbOption}
324
325 Load balancing strategies are implemented as libraries in \charmpp{}. This
326 allows programmers to easily experiment with different existing strategies 
327 by simply linking a pool of strategy modules and choosing
328 one to use at runtime via a command line option.
329
330 Please note that linking a load balancing module is different from activating it:
331 \begin{itemize}
332 \item link an LB module: is to link an Load Balancer module(library) at 
333    compile time. You can link against multiple LB libraries as candidates.
334 \item activate an LB: is to actually ask the runtime to create an LB strategy and 
335    start it. You can only activate load balancers that have been linked at
336    compile time.
337 \end{itemize}
338
339
340 Below are the descriptions about the compiler and runtime options:
341
342 \begin{enumerate}
343 \item {\bf compile time options:}
344
345 \begin{itemize}
346 \item {\em -module NeighborLB -module GreedyCommLB ...}  \\
347   links the modules NeighborLB, GreedyCommLB etc into an application, but these
348 load balancers will remain inactive at execution time unless overridden by other
349 runtime options.
350 \item {\em -module CommonLBs} \\
351   links a special module CommonLBs which includes some commonly used charmpp{}
352 built-in load balancers.
353 \item {\em -balancer GreedyCommLB} \\
354   links the load balancer GreedyCommLB and invokes it at runtime.
355 \item {\em -balancer GreedyCommLB -balancer RefineLB} \\
356   invokes GreedyCommLB at the first load balancing step and RefineLB in all
357 subsequent load balancing steps.
358 \item {\em -balancer ComboCentLB:GreedyLB,RefineLB}  \\
359   You can create a new combination load balancer made of multiple
360 load balancers. In the above example, GreedyLB and RefineLB strategies are
361 applied one after the other in each load balancing step.
362 \end{itemize}
363
364 The list of existing load balancers are in section \ref{lbStrategy}. Note: you
365 can have multiple -module *LB options. LB modules are linked into a program,
366 but they are not activated automatically at runtime.  Using -balancer A at
367 compile time will activate load balancer A automatically at runtime.
368 Having -balancer A implies -module A, so you don't have to write -module A
369 again, although it does not hurt.  Using CommonLBs is a convenient way to link
370 against the commonly used existing load balancers.  One of the load balancers
371 called MetisLB requires the METIS library which is located at:
372 charm/src/libs/ck-libs/parmetis/METISLib/.  You need to compile METIS library
373 by "make METIS" under charm/tmp after you compile Charm++.
374
375 \item {\bf runtime options:}
376
377 Runtime options are similar to the compile time options as described above,
378 but they can override compile time options.
379
380 \begin{itemize}
381 \item {\em +balancer help} \\
382   displays all available balancers that have been linked in.
383 \item {\em +balancer GreedyCommLB} \\
384   invokes GreedyCommLB
385 \item {\em +balancer GreedyCommLB +balancer RefineLB} \\
386   invokes GreedyCommLB at the first load balancing step and RefineLB in all
387 subsequent load balancing steps.
388 \item {\em +balancer ComboCentLB:GreedyLB,RefineLB}  \\
389   same as the example in the -balancer compile time option.
390 \end{itemize}
391
392 Note: +balancer option works only if you have already linked the corresponding 
393 load balancers module at compile time. 
394 Giving +balancer with a wrong LB name will result in a runtime error.
395 When you have used -balancer A as compile time option, you don't need to use 
396 +balancer A again to activate it at runtime. However, you can 
397 use +balancer B to override the compile time option and choose to
398 activate B instead of A.
399
400 \item {\bf Handling the case that no load balancer is activated by users}
401
402 Wen no balancer is linked by users, 
403 but the program counts on a load balancer because you use {\em AtSync()}
404 and expect {\em ResumeFromSync()} to be called to continue,
405 a special load balancer called {\em NullLB} will be 
406 automatically created in this case in order to run the program.
407 This default load balancer calls {\em ResumeFromSync()} after {\em AtSync()}. 
408 It keeps a program from hanging after calling {\em AtSync()}.
409 The {\em NullLB} is smart enough to keep silent if another 
410 load balancer is created.
411
412 \item {\bf Other useful runtime options}
413
414 There are a few other runtime options for load balancing that may be useful:
415
416 \begin{itemize}
417 \item {\em +LBDebug \{verbose level\}} \\
418      \{verbose level\} can be any positive integer number. 0 is to turn off the verbose. 
419      This option asks load balancer to output load balancing information to stdout.
420      The bigger the verbose level is, the more verbose the output is.
421 \item {\em +LBPeriod \{seconds\}} \\
422      \{Seconds\} can be any float number. This option sets the minimum period time in 
423 seconds between two consecutive load balancing steps. The default value is 
424 1 second. That is to say that a load balancing step will not happen until
425 1 second after the last load balancing step.
426 \item {\em +LBSameCpus} \\
427      This option simply tells load balancer that all processors are of same speed.
428      The load balancer will then skip the measurement of CPU speed at runtime.
429 \item {\em +LBObjOnly} \\
430      This tells load balancer to ignore processor background load when making migration decisions.
431 \item {\em +LBSyncResume} \\
432      After load balancing step, normally a processor can resume computation 
433 once all objects are received on that processor, even when other processors
434 are still working on migrations.  If this turns out to be a problem, 
435 that is when some processors start working on computation while the other 
436 processors are still busy migrating objects, then this option can be used to force 
437 a global barrier on all processors to make sure that processors can only resume 
438 computation after migrations are completed on all processors.
439 \item {\em +LBOff} \\
440      This option turns off load balancing instrumentation 
441      of both CPU and communication usageat startup time. 
442 \item {\em +LBCommOff} \\
443      This option turns off load balancing instrumentation of communication at startup time. 
444      The instrument of CPU usage is left on.
445 \end{itemize}
446
447 \end{enumerate}
448
449 \subsubsection{Seed load balancers - load balancing Chares at creation time}
450
451 \label{seedlb}
452
453 Seed load balancing involves the movement of object creation messages, or
454 "seeds", to create a balance of work across a set of processors. 
455 This seed load balancing scheme is used to balance chares  at creation time.
456 After the chare constructor is executed on a processor, the seed balancer does not
457 migrate it.
458 %the seed load balancer. The measurement based load balancer described in
459 %previous subsection perform the task of moving chares during work to achieve
460 %load balance.
461 Depending on the movement strategy, several seed load balancers are available now. 
462 \begin{enumerate}
463 \item {\em random}\\  
464  A strategy that places seeds randomly when they are created and does
465 no movement of seeds thereafter. This is used as the default seed 
466 load balancer.
467 \item {\em neighbor}\\  
468  A strategy which imposes a virtual topology on the processors,
469  load exchange happens among neighbors only. The overloaded processors
470  initiate the load balancing and send work to its neighbors
471  when it becomes overloaded. The default topology is mesh2D, one can use
472  command line option to choose other topology such as ring, mesh3D and 
473  dense graph.
474 \item {\em spray}\\  
475  A strategy which imposes a spanning tree organization on the processors,
476  results in communication via global reduction among all processors 
477  to compute global average load via periodic reduction. 
478  It uses averaging of loads to determine how seeds should be
479 distributed.
480 \item  {\em workstealing} \\
481  A strategy that the idle processor requests a random processor and steal 
482  chares.
483 \end{enumerate}
484
485 Other strategies can also be explored follow the simple API of the 
486 seed load balancer.
487 \linebreak
488
489 %{\bf Seed load balancers for Chares:}
490 %
491 %Seed load balancers can be directly used for load balancing Chares.
492 %The default seed load balancer which is always linked is the random seed load balancer.
493 %Users can choose another strategy listed above and link as a plugin
494 %module into binary as described below.
495 %
496 %{\bf Seed load balancers for Array Elements:}
497 %
498 %Seed load balancers can also be used for array elements in the same way 
499 %as they are used for individual chares.
500 %Chare array is a collection of individual Chares in Charm++.
501 %Since Chare Array has its internal strategy of static mapping of individual
502 %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}, 
503 %a special CkArrayMap called {\em CldMap} must be created and passed into
504 %array creation calls to interface with seed load balancer.
505 %
506 %For creating an empty array and then inserting chares into it, the API is as follows:
507 %
508 %\begin{alltt}
509 %  CkArrayOptions opt;
510 %  CkGroupID cldmapID = CProxy_CldMap::ckNew();
511 %  opt.setMap(cldmapID);
512 %  CProxy_WorkUnit arr = CProxy_WorkUnit::ckNew(param, opt); 
513 %  for (int i=0; i<numChares; i++) 
514 %    arr[i].insert(param);
515 %\end{alltt}
516 %
517 %For initially populating the array with chares at time of creation the API is as follows:
518 %\begin{alltt}
519 %  CkArrayOptions opt(numChares);
520 %  CkGroupID cldmapID = CProxy_CldMap::ckNew();
521 %  opt.setMap(cldmapID);
522 %  CProxy_WorkUnit arr = CProxy_WorkUnit::ckNew(param, opt); 
523 %\end{alltt}
524 %
525 %The details about array creation are explained in section~\ref{advanced arrays} of the manual.
526 %
527 {\bf Compile and run time options for seed load balancers}
528
529 To choose a seed load balancer other than the default {\em rand} strategy,
530 use link time command line option {\bf -balance foo}. 
531
532 When using {\rm neighbor} seed load balancer, one can also specify
533 the virtual topology at runtime. Use {\bf +LBTopo topo}, where {\em topo}
534 can be one of: (a) ring, (b) mesh2d, (c) mesh3d and (d) graph.
535
536 To write a seed load balancer, name your file as {\em cldb.foo.c},
537 where {\em foo} is the strategy name.  Compile it in the form of library
538 under charm/lib, named as {\em libcldb-foo.a}, where {\em foo} is the strategy 
539 name used above. Now one can use {\bf -balance foo} as compile time option
540 to {\bf charmc} to link with the {\em foo} seed load balancer.
541
542 \subsubsection{Simple Load Balancer Usage Example - Automatic with Sync LB}
543 \label{lbexample}
544
545 A simple example of how to use a load balancer in sync mode in one's
546 application is presented below.
547
548 \begin{alltt}
549 /*** lbexample.ci ***/
550 mainmodule lbexample {
551   readonly CProxy_Main mainProxy;
552   readonly int nElements;
553
554   mainchare Main {
555     entry Main(CkArgMsg *m);
556     entry void done(void);
557   };
558
559   array [1D] LBExample {
560     entry LBExample(void);
561     entry void doWork();
562   };
563 };
564 \end{alltt}
565
566 --------------------------------------------------------------------------------
567
568 \begin{alltt}
569 /*** lbexample.C ***/
570 #include <stdio.h>
571 #include "lbexample.decl.h"
572
573 /*readonly*/ CProxy_Main mainProxy;
574 /*readonly*/ int nElements;
575
576 #define MAX_WORK_CNT 50
577 #define LB_INTERVAL 5
578
579 /*mainchare*/
580 class Main : public CBase_Main
581 \{
582 private:
583   int count;
584 public:
585   Main(CkArgMsg* m)
586   \{
587     /*....Initialization....*/
588     mainProxy = thisProxy;
589     CProxy_LBExample arr = CProxy_LBExample::ckNew(nElements);
590     arr.doWork();
591   \};
592
593   void done(void)
594   \{
595     count++;
596     if(count==nElements){
597       CkPrintf("All done");
598       CkExit();
599     \}
600   \};
601 \};
602
603 /*array [1D]*/
604 class LBExample : public CBase_LBExample
605 \{
606 private:
607   int workcnt;
608 public:
609   LBExample()
610   \{
611     workcnt=0;
612     /* May initialize some variables to be used in doWork */
613     //Must be set to CmiTrue to make AtSync work
614     usesAtSync=CmiTrue;
615   \}
616
617   LBExample(CkMigrateMessage *m) \{ /* Migration constructor -- invoked when chare migrates */ }
618   
619   /* Must be written for migration to succeed */
620   void pup(PUP::er &p)\{
621     CBase_LBExample::pup(p);
622     p|workcnt;
623     /* There may be some more variables used in doWork */
624   }
625         
626   void doWork()
627   \{
628     /* Do work proportional to the chare index to see the effects of LB */
629     
630     workcnt++;
631     if(workcnt==MAX_WORK_CNT)
632       mainProxy.done();
633     
634     if(workcnt\%LB_INTERVAL==0)
635       AtSync();
636     else
637       doWork();
638   \}
639   
640   void ResumeFromSync()\{
641     doWork();
642   \}
643 \};
644
645 #include "lbexample.def.h"
646 \end{alltt}