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