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