Bug #1267: Integrate METIS graph partitioning library

[charm.git] / doc / charm++ / loadb.tex

Load balancing in \charmpp{} is enabled by its ability to place, or
migrate, chares or chare array elements.  Typical application usage to
exploit this feature will construct many more chares than processors, and
enable their runtime migration.

Iterative applications, which are commonplace in physical simulations,
are the most suitable target for \charmpp{}'s measurement based load
balancing techniques.  Such applications may contain a series of
time-steps, and/or iterative solvers that run to convergence. For such
computations, typically, the heuristic principle that we call
``principle of persistence'' holds: the computational loads and
communication patterns between objects (chares) tend to persist over
multiple iterations, even in dynamic applications. In such cases,
the recent past is a good predictor of the near future. Measurement-based
chare migration strategies are useful in this context. Currently these
apply to chare-array elements, but they may be extended to chares in
the future.

For applications without such iterative structure, or with iterative
structure, but without predictability (i.e. where the principle of
persistence does not apply), Charm++ supports ``seed balancers'' that
move ``seeds'' for new chares among processors (possibly repeatedly)
to achieve load balance. These strategies are currently available for
both chares and chare-arrays.  Seed balancers were the original load
balancers provided in Charm since the late 80's. They are extremely
useful for state-space search applications, and are also useful in
other computations, as well as in conjunction with migration
strategies.

For iterative computations when there is a correlation between iterations/steps,
but either it is not strong, or the machine environment is not predictable
(due to noise from OS interrupts on small time steps, or time-shared desktop
machines), one can use a combination of the two kinds of strategies. The
baseline load balancing is provided by migration strategies, but in each
iteration one also spawns off work in the form of chares that can run on any
processor. The seed balancer will handle such work as it arises.

Examples are in \examplerefdir{load\_balancing} and
\testrefdir{load\_balancing}

\section{Measurement-based Object Migration Strategies}
\label{lbFramework}
\label{migrationlb}

In \charmpp{}, objects (except groups, nodegroups) can migrate from 
processor to processor at runtime. Object migration can potentially 
improve the performance of the parallel program by migrating objects from 
overloaded processors to underloaded ones. 

%However, it is not
%trivial to decide which objects to move and where to move them in 
%order to achieve load balance in a fashion without the knowledge about the 
%application. The strategy used in \charmpp{} load balancing framework
%is a measurement-based one.

 \charmpp{} implements a generic, measurement-based load balancing framework
which automatically instruments all \charmpp{} objects, collects computation
load and communication structure during execution and stores them into a
\kw{load balancing database}. \charmpp{} then provides a collection of \kw{load
balancing strategies} whose job it is to decide on a new mapping of objects to
processors based on the information from the database.  Such measurement based
strategies are efficient when we can reasonably assume that objects in a 
\charmpp{} application tend to exhibit temporal correlation in their
computation and communication patterns, i.e. future can be to some extent
predicted using the historical measurement data, allowing effective
measurement-based load balancing without application-specific knowledge.

Two key terms in the \charmpp{} load balancing framework are:
\begin{itemize}
%
\item \kw{Load balancing database} provides the interface of almost all load
balancing calls. On each processor, it stores the load balancing instrumented
data and coordinates the load balancing manager and balancer. It is implemented
as a Chare Group called \kw{LBDatabase}.
%
\item \kw{Load balancer or strategy} takes the load balancing database and
produces the new mapping of the objects. In \charmpp{}, it is implemented as
Chare Group inherited from BaseLB. Three kinds of schemes are implemented: (a)
centralized load balancers, (b) fully distributed load balancers and (c)
hierarchical load balancers.
%
\end{itemize}

\section{Available Load Balancing Strategies}
\label{lbStrategy}

Load balancing can be performed in either a centralized, a fully distributed,
or an hierarchical fashion.

In centralized approaches, the entire machine's load and communication
structure are accumulated to a single point, typically processor 0, followed by
a decision making process to determine the new distribution of \charmpp
objects. Centralized load balancing requires synchronization which may incur an
overhead and delay. However, due to the fact that the decision process has a
high degree of the knowledge about the entire platform, it tends to be more
accurate.

In distributed approaches, load data is only exchanged among 
neighboring processors. There is no global synchronization. However,
they will not, in general, provide an immediate restoration for load balance -
the process is iterated until the load balance can be achieved.

In hierarchical approaches, processors are divided into independent autonomous
sets of processor groups and these groups are organized in hierarchies,
thereby decentralizing the load balancing task. Different strategies can be
used to balance the load on processors inside each processor group, and
processors across groups in a hierarchical fashion.

Listed below are some of the available non-trivial centralized load balancers
and their brief descriptions:
\begin{itemize}
\item {\bf RandCentLB}:   Randomly assigns objects to processors;
%\item {\bf RecBisectBfLB}:        Recursively partition with Breadth first enumeration;
\item {\bf MetisLB}:      Uses METIS\texttrademark\hspace{0mm} to partitioning object communication graph.
\item {\bf GreedyLB}:   Uses a greedy algorithm that always assigns the heaviest object to the least loaded processor.
\item {\bf GreedyCommLB}:  Extends the greedy algorithm to take the communication graph into account.
\item {\bf TopoCentLB}:    Extends the greedy algorithm to take processor topology into account.
\item {\bf RefineLB}:     Moves objects away from the most overloaded processors to reach average, limits the number of objects migrated.
\item {\bf RefineSwapLB}:     Moves objects away from the most overloaded processors
to reach average. In case it cannot migrate an object from an overloaded
processor to an underloaded processor, it swaps objects to reduce the load on
the overloaded processor. This strategy limits the number of objects migrated.
\item {\bf RefineCommLB}:     Same idea as in RefineLB, but takes communication into account.
\item {\bf RefineTopoLB}:       Same idea as in RefineLB, but takes processor topology into account.
\item {\bf BlockLB}: This strategy does a blocked distribution of objects to
processors.
\item {\bf ComboCentLB}:  A special load balancer that can be used to combine any number of centralized load balancers mentioned above.
\end{itemize}

Listed below are the distributed load balancers:
\begin{itemize}
\item {\bf NeighborLB}:   A neighborhood load balancer in which each processor tries to average out its load only among its neighbors.
\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.
\item {\bf DistributedLB}: A load balancer which uses partial information about
underloaded and overloaded processors in the system to do probabilistic transfer
of load. This is a refinement based strategy.
\end{itemize}

An example of a hierarchical strategy can be found in:
\begin{itemize}
\item {\bf HybridLB}: This calls GreedyLB at the lower level and RefineLB at
the root.
\end{itemize}

Users can choose any load balancing strategy they think is appropriate for their
application. The compiler and runtime options are described in
section~\ref{lbOption}.
\linebreak

{\bf Metabalancer to automatically schedule load balancing}

Metabalancer can be invoked to automatically decide when to
invoke the load balancer, given the load-balancing strategy.
Metabalancer uses a linear prediction model
to set the load balancing period based on observed load imbalance.

The runtime option {\em +MetaLB} can be used to invoke this feature to automatically invoke
the load balancing strategy based on the imbalance observed.
This option needs to be specified alongside the {\em +balancer} option to specify the
load balancing strategy to use. Metabalancer relies on the AtSync() calls specified
in Section~\ref{lbarray} to collect load statistics.

{\em +MetaLBModelDir} \verb|<path-to-model>|
can be used to invoke the Metabalancer feature
to automatically decide which load balancing strategy to invoke. A model trained on a
generic representative load imbalance benchmark can be found in
 \verb|charm/src/ck-ldb/rf_model|.
Metabalancer makes a decision on which load balancing strategy
to invoke out of a subset of strategies, namely GreedyLB, RefineLB,
HybridLB, DistributedLB, MetisLB and ScotchLB.
For using the model based prediction in Metabalancer, \charmpp{} needs to be built with
all the above load balancing strategies, including ScotchLB that relies
on the external partitioning library SCOTCH specified
in the Section~\ref{lbOption}.


%In some cases, one may need to create and invoke multiple load balancing
%strategies/algorithms at the different phases. \charmpp{} now supports
%multiple load balancers created at runtime. For example, one can use 
%an aggressive load balancer such as GreedyRefLB in the first load balancing
%step, and use RefineLB for the later load balancing steps.

\section{Load Balancing Chare Arrays}
\label{lbarray}

The load balancing framework is well integrated with chare array implementation
-- when a chare array is created, it automatically registers its elements with
the load balancing framework. The instrumentation of compute time (WALL/CPU
time) and communication pattern is done automatically and APIs are provided
for users to trigger the load balancing.  To use the load balancer, you must
make your array elements migratable (see migration section above) and choose a
\kw{load balancing strategy} (see the section \ref{lbStrategy} for a
description of available load balancing strategies).

There are three different ways to use load balancing for chare arrays to meet
different needs of the applications. These methods are different in how and
when a load balancing phase starts. The three methods are: {\bf periodic load
balancing mode}, {\bf at sync mode} and {\bf manual mode}.

In {\em periodic load balancing mode}, a user specifies only how often
load balancing is to occur, using +LBPeriod runtime option to specify
the time interval.

In {\em at sync mode}, the application invokes the load balancer
explicitly at appropriate (generally at a pre-existing synchronization
boundary) to trigger load balancing by inserting a function call
(AtSync) in the application source code.

In the prior two load balancing modes, users do not need to worry
about how to start load balancing.  However, in one scenario, those
automatic load balancers will fail to work - when array elements are
created by dynamic insertion.  This is because the above two load
balancing modes require an application to have fixed the number of
objects at the time of load balancing.  The array manager needs to
maintain a head count of local array elements for the local barrier.
In this case, the application must use the {\em manual mode} to
trigger load balancer.

The detailed APIs of these three methods are described as follows:
%
\begin{enumerate}
%
\item {\bf Periodical load balancing mode}: In the default setting, load
balancing happens whenever the array elements are ready, with an interval of 1
second. It is desirable for the application to set a larger interval using
+LBPeriod runtime option. For example ``+LBPeriod 5.0'' can be used to start load
balancing roughly every 5 seconds. By default, array elements may be asked to
migrate at any time, provided that they are not in the middle of executing an
entry method. The array element's variable \kw{usesAtSync} being false
attributes to this default behavior.
%
\item {\bf At sync mode}: Using this method, elements can be migrated only at
certain points in the execution when the application invokes \kw{AtSync()}. In order to use the at
sync mode, one should set \kw{usesAtSync} to true in the array element
constructor.  When an element is ready to migrate, call
\kw{AtSync()}~\footnote{AtSync() is a member function of class ArrayElement}.
When all local elements call \kw{AtSync}, the load balancer is triggered.  Once
all migrations are completed, the load balancer calls the virtual function
\kw{ArrayElement::ResumeFromSync()} on each of the array elements. This
function can be redefined in the application.

Note that the minimum time for \kw{AtSync()} load balancing to occur
is controlled by the LBPeriod.  Unusually high frequency load
balancing (more frequent than 500ms) will perform better if this value
is set via +LBPeriod or \kw{SetLBPeriod()} to a number shorter than your load
balancing interval.

Note that {\em AtSync()} is not a blocking call, it just gives a hint to load
balancing that it is time for load balancing. During the time between {\em
AtSync} and {\em ResumeFromSync}, the object may be migrated. One can choose
to let objects continue working with incoming messages, however keep in mind
the object may suddenly show up in another processor and make sure no
operations that could possibly prevent migration be performed. This is 
the automatic way of doing load balancing where the application does not need to define ResumeFromSync().

The more commonly used approach is to force the object to be idle until load
balancing finishes. The user places an AtSync call at the end of some iteration
and when all elements reach that call load balancing is triggered. The objects
can start executing again when \kw{ResumeFromSync()} is called. In this case,
the user redefines ResumeFromSync() to trigger the next iteration of the
application. This manual way of using the at sync mode results in a barrier at
load balancing (see example here~\ref{lbexample}).
%
\item {\bf Manual mode}: The load balancer can be programmed to be started
manually. To switch to the manual mode, the application calls {\em TurnManualLBOn()}
on every processor to prevent the load balancer from starting automatically. {\em
TurnManualLBOn()} should be called as early as possible in the program. It
could be called at the initialization part of the program, for example from a
global variable constructor, or in an initproc call (Section~\ref{initproc}).  It can also be
called in the constructor of a static array or before the {\em
doneInserting} call for a dynamic array.  It can be called multiple times on
one processor, but only the last one takes effect.

The function call {\em CkStartLB()} starts load balancing immediately. This call
should be made at only one place on only one processor. This function is
not blocking, the object will continue to process messages and the load
balancing, when triggered, happens in the background.

{\em TurnManualLBOff()} turns off manual load balancing and switches back to
the automatic load balancing mode.
%
\end{enumerate}

\section{Migrating objects}
\label{lbmigobj}

Load balancers migrate objects automatically.
For an array element to migrate, user can refer to Section~\ref{arraymigratable}
for how to write a ``pup'' for an array element.

In general one needs to pack the whole snapshot of the member data in an 
array element in the pup subroutine. This is because the migration of
the object may happen at any time. In certain load balancing schemes where
 the user explicitly controls when load balancing occurs, the user may choose
to pack only a part of the data and may skip temporary data.

An array element can migrate by calling the \kw{migrateMe}(\uw{destination
processor}) member function-- this call must be the last action
in an element entry method.  The system can also migrate array elements
for load balancing (see the section~\ref{lbarray}).

To migrate your array element to another processor, the \charmpp{}
runtime will:

\begin{itemize}
\item Call your \kw{ckAboutToMigrate} method
\item Call your \uw{pup} method with a sizing \kw{PUP::er} to determine how 
big a message it needs to hold your element.
\item Call your \uw{pup} method again with a packing \kw{PUP::er} to pack 
your element into a message.
\item Call your element's destructor (deleting the old copy).
\item Send the message (containing your element) across the network.
\item Call your element's migration constructor on the new processor.
\item Call your \uw{pup} method on with an unpacking \kw{PUP::er} to unpack 
the element.
\item Call your \kw{ckJustMigrated} method
\end{itemize}

Migration constructors, then, are normally empty-- all the unpacking
and allocation of the data items is done in the element's \uw{pup} routine.
Deallocation is done in the element destructor as usual.


\section{Other utility functions}

There are several utility functions that can be called in applications to
configure the load balancer, etc. These functions are:

\begin{itemize}
\item {\bf LBTurnInstrumentOn()} and {\bf LBTurnInstrumentOff()}: are plain C
      functions to control the load balancing statistics instrumentation
      on or off on the calling processor. No implicit broadcast or 
      synchronization exists in these functions.
      Fortran interface: {\bf FLBTURNINSTRUMENTON()} and {\bf FLBTURNINSTRUMENTOFF()}.
\item {\bf setMigratable(bool migratable)}: is a member function of array
      element. This function can be called 
      in an array element constructor to tell the load balancer whether this object
      is migratable or not\footnote{Currently not all load balancers 
      recognize this setting though.}.
\item {\bf LBSetPeriod(double s)}: this function can be called
      anywhere (even in Charm++ initnodes or initprocs) to specify 
      the load balancing period time in seconds. 
      It tells load balancer not to start next 
      load balancing in less than $s$ seconds. This can be used to prevent 
      load balancing from occurring too often in 
      {\em automatic without sync mode}. Here is how to use it:
      \begin{alltt}
// if used in an array element
LBDatabase *lbdb = getLBDB();
lbdb->SetLBPeriod(5.0);

// if used outside of an array element
LBSetPeriod(5.0);
\end{alltt}
      Alternatively, one can specify +LBPeriod \{seconds\} at command line.
\end{itemize}

\section{Compiler and runtime options to use load balancing module}
\label{lbOption}

Load balancing strategies are implemented as libraries in \charmpp{}. This
allows programmers to easily experiment with different existing strategies 
by simply linking a pool of strategy modules and choosing
one to use at runtime via a command line option.

{\bf Note:} linking a load balancing module is different from activating it:
\begin{itemize}
\item link an LB module: is to link a Load Balancer module(library) at 
   compile time. You can link against multiple LB libraries as candidates.
\item activate an LB: is to actually ask the runtime to create an LB strategy and 
   start it. You can only activate load balancers that have been linked at
   compile time.
\end{itemize}


Below are the descriptions about the compiler and runtime options:

\begin{enumerate}
\item {\bf compile time options:}

\begin{itemize}
\item {\em -module NeighborLB -module GreedyCommLB ...}  \\
  links the modules NeighborLB, GreedyCommLB etc into an application, but these
load balancers will remain inactive at execution time unless overridden by other
runtime options.
\item {\em -module CommonLBs} \\
  links a special module CommonLBs which includes some commonly used \charmpp{}
built-in load balancers. The commonly used load balancers include {\tt
DummyLB, GreedyLB, CommLB, RandCentLB, RefineLB, RefineCommLB, RotateLB, DistributedLB, HybridLB, ComboCentLB, RefineSwapLB, NeighborLB, OrbLB, BlockLB, GreedyCommLB}
\item {\em -balancer GreedyCommLB} \\
  links the load balancer GreedyCommLB and invokes it at runtime.
\item {\em -balancer GreedyCommLB -balancer RefineLB} \\
  invokes GreedyCommLB at the first load balancing step and RefineLB in all
subsequent load balancing steps.
\item {\em -balancer ComboCentLB:GreedyLB,RefineLB}  \\
  You can create a new combination load balancer made of multiple
load balancers. In the above example, GreedyLB and RefineLB strategies are
applied one after the other in each load balancing step.
\end{itemize}

The list of existing load balancers is given in Section
\ref{lbStrategy}. Note: you can have multiple -module *LB options. LB
modules are linked into a program, but they are not activated
automatically at runtime.  Using -balancer A at compile time will
activate load balancer A automatically at runtime.  Having -balancer A
implies -module A, so you don't have to write -module A again,
although that is not invalid.  Using CommonLBs is a convenient way to
link against the commonly used existing load balancers.  

The SCOTCH-based load balancer(s) use an external partitioning library requiring 3rd party software:

SCOTCH can be downloaded from:
\url{http://www.labri.fr/perso/pelegrin/scotch/}

Use the {\em --incdir and --libdir} build time option to add your installation of any third party libraries you wish to use to the \charmpp{} search paths.  

\item {\bf Building individual load balancers}

Load balancers can be built individually by changing the current working directory to the {\em tmp} subdirectory of your build and making them by name.

\begin{alltt}
 cd netlrts-linux-x86\_64/tmp
 make PhasebyArrayLB
\end{alltt}

\item {\bf Write and use your own load balancer}

Refer Section~\ref{lbWriteNewLB} for writing a new load balancer. Compile it in
the form of library and name it {\em libmoduleFooLB.a} where {\em FooLB} is the
new load balancer. Add the path to the library and link the load balancer into
an application using {\em -module FooLB}. 

You can create a library by modifying the Makefile in the following way. This
will create {\em libmoduleFooLB.a}.
\begin{alltt}
libmoduleFooLB.a: FooLB.o
  $(CHARMC) -o libmoduleFooLB.a FooLB.o
\end{alltt}

To include this balancer in your application, the Makefile can be changed in the
following way
\begin{alltt}
$(TARGET): $(OBJECTS)
  $(CHARMC) -o $(TARGET) -L/path-to-the-lib $(OBJS) -module FooLB 
\end{alltt}


\item {\bf runtime options:}

Runtime balancer selection options are similar to the compile time
options as described above, but they can be used to override those
compile time options.

\begin{itemize}
\item {\em +balancer help} \\
  displays all available balancers that have been linked in.
\item {\em +balancer GreedyCommLB} \\
  invokes GreedyCommLB
\item {\em +balancer GreedyCommLB +balancer RefineLB} \\
  invokes GreedyCommLB at the first load balancing step and RefineLB in all
subsequent load balancing steps.
\item {\em +balancer ComboCentLB:GreedyLB,RefineLB}  \\
  same as the example in the -balancer compile time option.
\end{itemize}

Note: +balancer option works only if you have already linked the corresponding 
load balancers module at compile time. 
Giving +balancer with a wrong LB name will result in a runtime error.
When you have used -balancer A as compile time option, you do not need to use 
+balancer A again to activate it at runtime. However, you can 
use +balancer B to override the compile time option and choose to
activate B instead of A.

\item {\bf Handling the case that no load balancer is activated by users}

When no balancer is linked by users, 
but the program counts on a load balancer because it used {\em AtSync()}
and expect {\em ResumeFromSync()} to be called to continue,
a special load balancer called {\em NullLB} will be 
automatically created to run the program.
This default load balancer calls {\em ResumeFromSync()} after {\em AtSync()}. 
It keeps a program from hanging after calling {\em AtSync()}.
{\em NullLB} will be suppressed if another load balancer is created.

\item {\bf Other useful runtime options}

There are a few other runtime options for load balancing that may be useful:

\begin{itemize}
\item {\em +LBDebug \{verbose level\}} \\
     \{verbose level\} can be any positive integer number. 0 is to turn off the verbose. 
     This option asks load balancer to output load balancing information to stdout.
     The bigger the verbose level is, the more verbose the output is.
\item {\em +LBPeriod \{seconds\}} \\
     \{Seconds\} can be any float number. This option sets the minimum period time in 
seconds between two consecutive load balancing steps. The default value is 
1 second. That is to say that a load balancing step will not happen until
1 second after the last load balancing step.
\item {\em +LBSameCpus} \\
     This option simply tells load balancer that all processors are of same speed.
     The load balancer will then skip the measurement of CPU speed at runtime. This is the default.
\item {\em +LBTestPESpeed} \\
     This option tells the load balancer to test the speed of all processors at runtime.
     The load balancer may use this measurement to perform speed-aware load balancing.
\item {\em +LBObjOnly} \\
     This tells load balancer to ignore processor background load when making migration decisions.
\item {\em +LBSyncResume} \\
     After load balancing step, normally a processor can resume computation 
once all objects are received on that processor, even when other processors
are still working on migrations.  If this turns out to be a problem, 
that is when some processors start working on computation while the other 
processors are still busy migrating objects, then this option can be used to force 
a global barrier on all processors to make sure that processors can only resume 
computation after migrations are completed on all processors.
\item {\em +LBOff} \\
     This option turns off load balancing instrumentation 
     of both CPU and communication usage at startup time. 
\item {\em +LBCommOff} \\
     This option turns off load balancing instrumentation of communication at startup time. 
     The instrument of CPU usage is left on.
\end{itemize}

\end{enumerate}

\section{Seed load balancers - load balancing Chares at creation time}
\label{seedlb}

Seed load balancing involves the movement of object creation messages, or
"seeds", to create a balance of work across a set of processors. 
This seed load balancing scheme is used to balance chares  at creation time.
After the chare constructor is executed on a processor, the seed balancer does not
migrate it.
%the seed load balancer. The measurement based load balancer described in
%previous subsection perform the task of moving chares during work to achieve
%load balance.
Depending on the movement strategy, several seed load balancers are available now.
Examples can be found \examplerefdir{NQueen}.
\begin{enumerate}
\item {\em random}\\  
 A strategy that places seeds randomly when they are created and does
no movement of seeds thereafter. This is used as the default seed 
load balancer.
\item {\em neighbor}\\  
 A strategy which imposes a virtual topology on the processors,
 load exchange happens among neighbors only. The overloaded processors
 initiate the load balancing and send work to its neighbors
 when it becomes overloaded. The default topology is mesh2D, one can use
 command line option to choose other topology such as ring, mesh3D and 
 dense graph.
\item {\em spray}\\  
 A strategy which imposes a spanning tree organization on the processors,
 results in communication via global reduction among all processors 
 to compute global average load via periodic reduction. 
 It uses averaging of loads to determine how seeds should be
distributed.
\item  {\em workstealing} \\
 A strategy that the idle processor requests a random processor and steal 
 chares.
\end{enumerate}

Other strategies can also be explored by following the simple API of the 
seed load balancer.
\linebreak

\zap{
{\bf Seed load balancers for Chares:}

Seed load balancers can be directly used for load balancing Chares.
The default seed load balancer which is always linked is the random seed load balancer.
Users can choose another strategy listed above and link as a plugin
module into binary as described below.

{\bf Seed load balancers for Array Elements:}

Seed load balancers can also be used for array elements in the same way 
as they are used for individual chares.
Chare array is a collection of individual Chares in Charm++.
Since Chare Array has its internal strategy of static mapping of individual
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}, 
a special CkArrayMap called {\em CldMap} must be created and passed into
array creation calls to interface with seed load balancer.

For creating an empty array and then inserting chares into it, the API is as follows:

\begin{alltt}
  CkArrayOptions opt;
  CkGroupID cldmapID = CProxy_CldMap::ckNew();
  opt.setMap(cldmapID);
  CProxy_WorkUnit arr = CProxy_WorkUnit::ckNew(param, opt); 
  for (int i=0; i<numChares; i++) 
    arr[i].insert(param);
\end{alltt}

For initially populating the array with chares at time of creation the API is as follows:
\begin{alltt}
  CkArrayOptions opt(numChares);
  CkGroupID cldmapID = CProxy_CldMap::ckNew();
  opt.setMap(cldmapID);
  CProxy_WorkUnit arr = CProxy_WorkUnit::ckNew(param, opt); 
\end{alltt}

The details about array creation are explained in section~\ref{advanced arrays} of the manual.

} % end zap


{\bf Compile and run time options for seed load balancers}


To choose a seed load balancer other than the default {\em rand} strategy,
use link time command line option {\bf -balance foo}. 

When using {\rm neighbor} seed load balancer, one can also specify
the virtual topology at runtime. Use {\bf +LBTopo topo}, where {\em topo}
can be one of: (a) ring, (b) mesh2d, (c) mesh3d and (d) graph.

To write a seed load balancer, name your file as {\em cldb.foo.c},
where {\em foo} is the strategy name.  Compile it in the form of library
under charm/lib, named as {\em libcldb-foo.a}, where {\em foo} is the strategy 
name used above. Now one can use {\bf -balance foo} as compile time option
to {\bf charmc} to link with the {\em foo} seed load balancer.

\section{Simple Load Balancer Usage Example - Automatic with Sync LB}
\label{lbexample}

A simple example of how to use a load balancer in sync mode in one's
application is presented below.

\begin{alltt}
/*** lbexample.ci ***/
mainmodule lbexample \{
  readonly CProxy_Main mainProxy;
  readonly int nElements;

  mainchare Main \{
    entry Main(CkArgMsg *m);
    entry void done(void);
  \};

  array [1D] LBExample \{
    entry LBExample(void);
    entry void doWork();
  \};
\};
\end{alltt}

--------------------------------------------------------------------------------

\begin{alltt}
/*** lbexample.C ***/
#include <stdio.h>
#include "lbexample.decl.h"

/*readonly*/ CProxy_Main mainProxy;
/*readonly*/ int nElements;

#define MAX_WORK_CNT 50
#define LB_INTERVAL 5

/*mainchare*/
class Main : public CBase_Main
\{
private:
  int count;
public:
  Main(CkArgMsg* m)
  \{
    /*....Initialization....*/
    mainProxy = thisProxy;
    CProxy_LBExample arr = CProxy_LBExample::ckNew(nElements);
    arr.doWork();
  \};

  void done(void)
  \{
    count++;
    if(count==nElements)\{
      CkPrintf("All done");
      CkExit();
    \}
  \};
\};

/*array [1D]*/
class LBExample : public CBase_LBExample
\{
private:
  int workcnt;
public:
  LBExample()
  \{
    workcnt=0;
    /* May initialize some variables to be used in doWork */
    //Must be set to true to make AtSync work
    usesAtSync = true;
  \}

  LBExample(CkMigrateMessage *m) \{ /* Migration constructor -- invoked when chare migrates */ \}
  
  /* Must be written for migration to succeed */
  void pup(PUP::er &p)\{
    p|workcnt;
    /* There may be some more variables used in doWork */
  \}
        
  void doWork()
  \{
    /* Do work proportional to the chare index to see the effects of LB */
    
    workcnt++;
    if(workcnt==MAX_WORK_CNT)
      mainProxy.done();
    
    if(workcnt\%LB_INTERVAL==0)
      AtSync();
    else
      doWork();
  \}
  
  void ResumeFromSync()\{
    doWork();
  \}
\};

#include "lbexample.def.h"
\end{alltt}