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