docs: expand on load balancing modes
authorAbhinav S Bhatele <bhatele@illinois.edu>
Thu, 30 Dec 2010 00:28:59 +0000 (18:28 -0600)
committerAbhinav S Bhatele <bhatele@illinois.edu>
Thu, 30 Dec 2010 00:28:59 +0000 (18:28 -0600)
doc/charm++/loadb.tex

index 5c6b5fd2e432307b048207592d0493208df498b9..babd17c0f0042fd24829f9b98752058d5bfbd962 100644 (file)
@@ -160,118 +160,79 @@ 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 automatic with sync mode} and {\bf manual mode}.
-
-In {\em periodic load balancing mode}, a user just needs to specify how
-often he wants the load balancing to occur, using +LBPeriod runtime
-option to specify a time interval. 
-
-In {\em sync mode}, users can tell load balancer explicitly when is a good 
-time to trigger load balancing by inserting a function call in the user
-code.
-
-
-%In this mode, load balancer works in parallel with 
-%the application so application doesn't need to stop waiting for load 
-%balancing to complete. However, in most cases, 
-%application does not want load balancing to occur arbitrarily because it 
-%has better idea about when a load balancing should 
-%happen\footnote{For example, in the application with multiple iterations, 
-%load balancing should happens in every a few iterations}. 
-%{\em Automatic with sync} mode is designed for this 
-%scenario. In this mode, user inserts {\em AtSync()} calls at certain points 
-%in application where he thinks the load balancing is desired. 
-%Load balancing is then triggered after all the local array elements on 
-%the processor reach the sync point\footnote{It is implemented as a local 
-%barrier of all the array elements on one processor}. 
-%However, {\em AtSync()} is not a blocking call, 
-%load balancing does not force the application to block until it  
-%finishes. When load balancing finishes, load balancer notifies every array
-%element by calling {\em ResumeFromSync()}
-%\footnote{{\em ResumeFromSync()} is a virtual function of array element
-%base class which can be redefined in application.}. In many applications,
-%it is often desirable that application waits for load balancing complete since
-%there may be migration occurs when load balancing and application may want to
-%respond to the migration. Thus, one of the commonly applied strategy is 
-%that array elements stop sending message after {\em AtSync()} is called, 
-%and resume work after load balancer calls back {\em ResumeFromSync()}.
-
-In the above two load balancing modes, users don't need 
-to worry about how to start load balancing. 
-However, in one scenario, the above automatic load balancers will fail to
-work - array elements are created by dynamic insertion.
-This is because the above two load balancing modes require an application
-to have fixed 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, users have to use the {\em manual mode} to trigger 
-load balancer themselves. The API is described below.
-
-%A few notes about {\em ResumeFromSync()}\footnote{It used to 
-%only work in automatic with sync mode.}. It can be used in all above three
-%load balancing modes. For an array element(whether it is migrated or not), 
-%it is more like getting a notification from load
-%balancer about the completeness of load balancing phase.
-%Users can choose to handle it by writing their own
-%code for {\em ResumeFromSync()}, or just ignore it. The proper use of both 
-%{\em AtSync()} and {\em ResumeFromSync()} gives you the effect of 
-%load balancing barrier. 
+balancing mode}, {\bf at sync mode} and {\bf manual mode}.
+
+In {\em periodic load balancing mode}, a user just needs to specify how often
+he wants the load balancing to occur, using +LBPeriod runtime option to specify
+a time interval. 
+
+In {\em sync mode}, users can tell the load balancer explicitly when is a good
+time to trigger load balancing by inserting a function call (AtSync) in the
+user code.
+
+In the above two load balancing modes, users do not need to worry about how to
+start load balancing.  However, in one scenario, the above 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 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, users have to use the {\em manual mode} to trigger load balancer
+themselves.
 
 The detailed APIs of these three methods are described as follows:
 \begin{enumerate}
 
-\item {\bf periodical load balancing mode}: By default, the 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 CmiFalse attributes
-to this default behavior. In the default setting, load balancing happens
-whenever the array elements are ready with interval of 1 second. It is 
-desirable for the application to set a larger interval using +LBPeriod
-runtime option. For example "+LBPeriod 5" to start load balancing roughly
-every 5 seconds.
-
-\item {\bf automatic with Sync}: Using the AtSync method, elements can 
-only be migrated at certain points in the execution when user calls 
-\kw{AtSync()}. 
-For the AtSync method, set \kw{usesAtSync} to CmiTrue in your 
-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.  
+\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" 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 CmiFalse
+attributes to this default behavior. 
+
+\item {\bf At sync mode}: Using this method, elements can only be migrated at
+certain points in the execution when user calls \kw{AtSync()}. For using the at
+sync mode, one should set \kw{usesAtSync} to CmiTrue 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 {\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. The most commonly used approach is to force the object to 
-be idle until load balancing finishes, the object can start working again
-when \kw{ResumeFromSync()} is called.
+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.
 
 \item {\bf manual mode}: The load balancer can be programmed to be started
-manually. To switch to the manual mode, you should call
-{\em TurnManualLBOn()} on every processor to prevent 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 initcall~\ref{initcall}.
-It can also be called in the constructor of a static array and
-definitely 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 StartLB()} starts load balancing immediately. 
-This call should be made at only one place on only one processor.
-This function is also not blocking, the object will continue to process
-messages and the load balancing when triggered
-happens at the background.
-
-{\em TurnManualLBOff()} turns off manual load balancing and 
-switches back to the automatic Load balancing mode.
-
+manually. To switch to the manual mode, you should call {\em TurnManualLBOn()}
+on every processor to prevent 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 initcall~\ref{initcall}.  It can also be
+called in the constructor of a static array and definitely 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 StartLB()} starts load balancing immediately. This call
+should be made at only one place on only one processor. This function is also
+not blocking, the object will continue to process messages and the load
+balancing when triggered happens at the background.
+
+{\em TurnManualLBOff()} turns off manual load balancing and switches back to
+the automatic Load balancing mode.
 \end{enumerate}
 
 \subsubsection{Migrating objects}
@@ -487,10 +448,10 @@ As an example, we can collect the data for a 1000 processor run of a program usi
 ./charmrun pgm +p 1000 +balancer RandCentLB +LBDump 2 +LBDumpSteps 4 +LBDumpFile dump.dat
 \end{alltt}
 This will collect data on files data.dat.{2,3,4,5}. Then, we can use this data to observe various centralized strategies using:
-\begin{verbatim}
+\begin{alltt}
 ./charmrun pgm +balancer <Strategy to test> +LBSim 2 +LBSimSteps 4 
                +LBDumpFile dump.dat [+LBSimProcs 900]
-\end{verbatim}
+\end{alltt}
 
 \subsubsection{Future load predictor}
 
@@ -501,7 +462,7 @@ function to the load balancer to predict what will be the future workload, given
 the past, instrumented one. As said, the user might provide a specific class
 which inherits from {\tt LBPredictorFunction} and implement the appropriate functions. 
 Here is the abstract class:
-\begin{verbatim}
+\begin{alltt}
 class LBPredictorFunction {
 public:
   int num_params;
@@ -512,28 +473,28 @@ public:
   virtual void print(double *params) {PredictorPrintf("LB: unknown model\n");};
   virtual void function(double x, double *param, double &y, double *dyda) =0;
 };
-\end{verbatim}
+\end{alltt}
 \begin{itemize}
 \item {\tt initialize\_params} by default initializes the parameters randomly. If the user
 knows how they should be, this function can be reimplemented.
 \item {\tt predict} is the function the model implements. For example, if the function is
 $y=ax+b$, the method in the implemented class should be like:
-\begin{verbatim}
+\begin{alltt}
 double predict(double x, double *param) {return (param[0]*x + param[1]);}
-\end{verbatim}
+\end{alltt}
 \item {\tt print} is a debugging function and it can be reimplemented to have a meaningful
 print of the learnt model
 \item {\tt function} is a function internally needed to learn the parameters, {\tt x} and
 {\tt param} are input, {\tt y} and {\tt dyda} are output (the computed function and
 all its derivatives with respect to the parameters, respectively).
 For the function in the example should look like:
-\begin{verbatim}
+\begin{alltt}
 void function(double x, double *param, double &y, double *dyda) {
   y = predict(x, param);
   dyda[0] = x;
   dyda[1] = 1;
 }
-\end{verbatim}
+\end{alltt}
 \end{itemize}
 Other than these function, the user should provide a constructor which must initialize
 {\tt num\_params} to the number of parameters the model has to learn. This number is
@@ -661,12 +622,13 @@ 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.
 
-\subsubsection{Simple Load Balancer Usage Example - Automatic with Sync LB}
-
+\subsubsection{Simple Load Balancing Usage Example - at sync mode}
 \label{lbexample}
-A simple example of how to use a load balancer in sync mode in one's application is presented below.
 
-\begin{verbatim}
+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;
@@ -682,9 +644,11 @@ mainmodule lbexample {
     entry void doWork();
   };
 };
-\end{verbatim}
-----------------------------------------------------------------------------------------------------------
-\begin{verbatim}
+\begin{alltt}
+
+--------------------------------------------------------------------------------
+
+\begin{alltt}
 /*** lbexample.C ***/
 #include <stdio.h>
 #include "lbexample.decl.h"
@@ -762,4 +726,4 @@ public:
 };
 
 #include "lbexample.def.h"
-\end{verbatim}
+\end{alltt}