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