updated
[charm.git] / doc / charm++ / loadb.tex
index 512f4de62af3ee1c1ecb008b03ddc653397713fb..f9f281761114a412ff0cb0d361e611fc0f80dc8b 100644 (file)
@@ -20,24 +20,22 @@ 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 the 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 '80s. 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 (noise due to OS interrupts on small
-time steps, or time-shared desk-top machines), one can use a
-combination of the two kinds of strategies. The base-line 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
+For applications without such iterative structure, or with iterative structure
+but without the 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
+'80s. 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
+(noise due to OS interrupts on small time steps, or time-shared desk-top
+machines), one can use a combination of the two kinds of strategies. The
+base-line 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.
 
 \subsubsection{Measurement-based Object Migration Strategies}
@@ -56,17 +54,16 @@ overloaded processors to underloaded ones.
 %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 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 \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
+ \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 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
+\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.
 
 Here are the two terms often used in \charmpp{} load balancing framework:
@@ -86,32 +83,40 @@ Here are the two terms often used in \charmpp{} load balancing framework:
 
 \label{lbStrategy}
 
-Load balancing can be performed in either a centralized or distributed
-fashion.
+Load balancing can be performed in either a centralized, fully distributed
+or hierarchical (or hybrid) 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
-machine, it tends to be more accurate.
+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 machine, it tends to be more
+accurate.
 
 In distributed approaches, machine states are 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.
 
-Listed below are the available centralized load balancers and their brief 
-descriptions:
+
+In hierarchical approaches, processors are divided into independent autonomous
+sets of processor groups and these groups are organized in hierarchies,
+therefore decentralizing the load balancing task. Hybrid strategies are used to
+load balancing load on processors inside each processor group, and processors
+across groups in a hierarchical fashion. 
+
+Listed below are some of the available nontrivial centralized load balancers and their brief descriptions:
 \begin{itemize}
-\item {\bf RefineLB}:     Move objects away from the most overloaded processors to reach average, limits the number of objects migrated;
-\item {\bf RefineCommLB}:     Same idea as in RefineLB, but take communication into account;
 \item {\bf RandCentLB}:   Randomly assigns objects to processors;
 \item {\bf RecBisectBfLB}:        Recursively partition with Breadth first enumeration;
 \item {\bf MetisLB}:      Use Metis(tm) to partitioning object communication graph;
 \item {\bf GreedyLB}:   Use greedy algorithm, always pick the heaviest object to the least loaded processor.
 \item {\bf GreedyCommLB}:       Greedy algorithm which also takes communication graph into account;
+\item {\bf TopoCentLB}:       Greedy algorithm which also takes processor topology into account;
+\item {\bf RefineLB}:     Move objects away from the most overloaded processors to reach average, limits the number of objects migrated;
+\item {\bf RefineCommLB}:     Same idea as in RefineLB, but take communication into account;
+\item {\bf RefineTopoLB}:       Same idea as in RefineLB, but take processor topology into account;
 \item {\bf ComboCentLB}:  A special load balancer that can be used to combine any number of above centralized load balancers;
 \end{itemize}
 
@@ -121,10 +126,9 @@ Listed below are the distributed load balancers:
 \item {\bf WSLB}:   A load balancer for workstation clusters, which can detect load changes on desktops (and other timeshared processors) and adjust load without interferes with other's use of the desktop.
 \end{itemize}
 
-User can choose any load balancing strategy he or she thinks is the good
-for the application. 
-The compiler and run-time options
-are described in section \ref{lbOption}.
+User can choose any load balancing strategy he or she thinks is good for the
+application.  The compiler and run-time options are described in 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