[sharelatex-git-integration Best effort strategy and virtual load for asynchronous...

[loba-papers.git] / loba-besteffort / loba-besteffort.tex

diff --git a/loba-besteffort/loba-besteffort.tex b/loba-besteffort/loba-besteffort.tex
index c387ad6e62bee5e66175f1220104360944bb12e4..9f262377c4ceb0dc8003984fd2d85e9d3df8d23d 100644 (file)
--- a/loba-besteffort/loba-besteffort.tex
+++ b/loba-besteffort/loba-besteffort.tex
@@ -40,18 +40,16 @@
   asynchronous iterative load balancing}
 
 \author{Raphaël Couturier}
   asynchronous iterative load balancing}
 
 \author{Raphaël Couturier}

-\ead{raphael.couturier@femto-st.fr}
+\ead{raphael.couturier@univ-fcomte.fr}

 
 \author{Arnaud Giersch\corref{cor}}
 
 \author{Arnaud Giersch\corref{cor}}

-\ead{arnaud.giersch@femto-st.fr}
+\ead{arnaud.giersch@univ-fcomte.fr}
+
+\author{Mourad Hakem}
+\ead{mourad.hakem@univ-fcomte.fr}

 
 \address{%
 
 \address{%

-  Institut FEMTO-ST (UMR 6174),
-  Université de Franche-Comté (UFC),
-  Centre National de la Recherche Scientifique (CNRS),
-  École Nationale Supérieure de Mécanique et des Microtechniques (ENSMM),
-  Université de Technologie de Belfort Montbéliard (UTBM)\\
-  19 avenue du Maréchal Juin, BP 527, 90016 Belfort cedex, France}
+  FEMTO-ST Institute, Univ Bourgogne Franche-Comté, Belfort, France}

 
 \cortext[cor]{Corresponding author.}
 
 
 \cortext[cor]{Corresponding author.}
 


@@ -65,14 +63,13 @@
   propose a strategy called \besteffort{} which tries to balance the load
   of a node to all its less loaded neighbors while ensuring that all the nodes
   concerned by the load balancing phase have the same amount of load.  Moreover,
   propose a strategy called \besteffort{} which tries to balance the load
   of a node to all its less loaded neighbors while ensuring that all the nodes
   concerned by the load balancing phase have the same amount of load.  Moreover,

-  asynchronous iterative algorithms in which an asynchronous load balancing
-  algorithm is implemented most of the time can dissociate messages concerning
+  asynchronous iterative algorithms, in which an asynchronous load balancing
+  algorithm is implemented, can dissociate, most of the time, messages concerning

   load transfers and message concerning load information.  In order to increase
   the converge of a load balancing algorithm, we propose a simple heuristic
   load transfers and message concerning load information.  In order to increase
   the converge of a load balancing algorithm, we propose a simple heuristic

-  called \emph{virtual load} which allows a node that receives a load
-  information message to integrate the load that it will receive later in its
-  load (virtually) and consequently sends a (real) part of its load to some of
-  its neighbors.  In order to validate our approaches, we have defined a
+  called \emph{virtual load}. This heuristic allows a node that receives a load
+  information message to integrate this information, even if the load has not been received yet. Consequently the node sends a (real) part of its load to some of
+  its neighbors taking into account the virtual load it will receive soon.  In order to validate our approaches, we have defined a

   simulator based on SimGrid which allowed us to conduct many experiments.
 \end{abstract}
 
   simulator based on SimGrid which allowed us to conduct many experiments.
 \end{abstract}
 


@@ -87,19 +84,19 @@
 Load  balancing algorithms  are  extensively used  in  parallel and  distributed
 applications in  order to  reduce the  execution times. They  can be  applied in
 different scientific  fields from high  performance computation to  micro sensor
 Load  balancing algorithms  are  extensively used  in  parallel and  distributed
 applications in  order to  reduce the  execution times. They  can be  applied in
 different scientific  fields from high  performance computation to  micro sensor

-networks.   They are  iterative by  nature.\FIXME{really?}
+networks.   In a distributed context (i.e. without centralization), they are  iterative by  nature.

 In  literature many  kinds  of load
 balancing  algorithms  have been  studied.   They  can  be classified  according
 different  criteria:   centralized  or  decentralized,  in   static  or  dynamic
 environment,  with  homogeneous  or  heterogeneous load,  using  synchronous  or
 asynchronous iterations, with  a static topology or a  dynamic one which evolves
 during time.  In  this work, we focus on  asynchronous load balancing algorithms
 In  literature many  kinds  of load
 balancing  algorithms  have been  studied.   They  can  be classified  according
 different  criteria:   centralized  or  decentralized,  in   static  or  dynamic
 environment,  with  homogeneous  or  heterogeneous load,  using  synchronous  or
 asynchronous iterations, with  a static topology or a  dynamic one which evolves
 during time.  In  this work, we focus on  asynchronous load balancing algorithms

-where computer nodes  are considered homogeneous and with  homogeneous load with
+where computing nodes  are considered homogeneous and with  homogeneous load with

 no external  load. In  this context, Bertsekas  and Tsitsiklis have  proposed an
 no external  load. In  this context, Bertsekas  and Tsitsiklis have  proposed an

-algorithm which is definitively a reference  for many works. In their work, they
+algorithm which is definitively a reference for many works. In their work, they

 proved that under classical  hypotheses of asynchronous iterative algorithms and
 a  special  constraint   avoiding  \emph{ping-pong}  effect,  an  asynchronous
 proved that under classical  hypotheses of asynchronous iterative algorithms and
 a  special  constraint   avoiding  \emph{ping-pong}  effect,  an  asynchronous

-iterative algorithm  converge to  the uniform load  distribution. This  work has
+iterative algorithm  converges to  the uniform load  distribution. This  work has

 been extended by many authors. For example, Cortés et al., with
 DASUD~\cite{cortes+ripoll+cedo+al.2002.asynchronous}, propose a
 version working with integer load.  This work was later generalized by
 been extended by many authors. For example, Cortés et al., with
 DASUD~\cite{cortes+ripoll+cedo+al.2002.asynchronous}, propose a
 version working with integer load.  This work was later generalized by


@@ -117,11 +114,10 @@ amount of  load.  Moreover, when real asynchronous  applications are considered,
 using  asynchronous   load  balancing   algorithms  can  reduce   the  execution
 times. Most of the times, it is simpler to distinguish load information messages
 from  data  migration  messages.  Former  ones  allow  a  node to  inform  its
 using  asynchronous   load  balancing   algorithms  can  reduce   the  execution
 times. Most of the times, it is simpler to distinguish load information messages
 from  data  migration  messages.  Former  ones  allow  a  node to  inform  its

-neighbors of its  current load. These messages are very small,  they can be sent
-quite often.  For example, if a computing iteration takes  a significant times
+neighbors of its  current load. These messages are very small,  they can be sent 
+often and very quickly.  For example, if a computing iteration takes  a significant times

 (ranging from seconds to minutes), it is possible to send a new load information
 (ranging from seconds to minutes), it is possible to send a new load information

-message to each  neighbor at each iteration. Latter  messages contain data that
-migrates from one node to another one. Depending on the application, it may have
+message to each  neighbor at each iteration. Then the load is sent, but the reception may take time when the amount of load is huge and when communication links are slow.  Depending on the application, it may have

 sense or not  that nodes try to balance  a part of their load  at each computing
 iteration. But the time to transfer a load message from a node to another one is
 often much more longer that to  time to transfer a load information message. So,
 sense or not  that nodes try to balance  a part of their load  at each computing
 iteration. But the time to transfer a load message from a node to another one is
 often much more longer that to  time to transfer a load information message. So,


@@ -130,17 +126,21 @@ it can take this information into account  and it can consider that its new load
 is larger.   Consequently, it can  send a part  of it real  load to some  of its
 neighbors if required. We call this trick the \emph{virtual load} mechanism.
 
 is larger.   Consequently, it can  send a part  of it real  load to some  of its
 neighbors if required. We call this trick the \emph{virtual load} mechanism.
 

-So, in this work, we propose a new strategy to improve the distribution of the
+{\bf The contributions of this paper are the following:}
+\begin{itemize}
+\item We propose a new strategy to improve the distribution of the

 load and a simple but efficient trick that also improves the load
 load and a simple but efficient trick that also improves the load

-balancing. Moreover, we have conducted many simulations with SimGrid in order to
+balancing.
+\item we have conducted many simulations with SimGrid in order to

 validate that our improvements are really efficient. Our simulations consider
 that in order to send a message, a latency delays the sending and according to
 the network performance and the message size, the time of the reception of the
 message also varies.
 validate that our improvements are really efficient. Our simulations consider
 that in order to send a message, a latency delays the sending and according to
 the network performance and the message size, the time of the reception of the
 message also varies.

+\end{itemize}

 
 In the following of this paper, Section~\ref{sec.bt-algo} describes the
 Bertsekas and Tsitsiklis' asynchronous load balancing algorithm. Moreover, we
 
 In the following of this paper, Section~\ref{sec.bt-algo} describes the
 Bertsekas and Tsitsiklis' asynchronous load balancing algorithm. Moreover, we

-present a possible problem in the convergence conditions.
+present a possible problem in the convergence conditions. In Section~\ref{sec.related.works}, related works are presented.

 Section~\ref{sec.besteffort} presents the best effort strategy which provides an
 efficient way to reduce the execution times.  This strategy will be compared
 with other ones, presented in Section~\ref{sec.other}.  In
 Section~\ref{sec.besteffort} presents the best effort strategy which provides an
 efficient way to reduce the execution times.  This strategy will be compared
 with other ones, presented in Section~\ref{sec.other}.  In


@@ -168,7 +168,7 @@ each  of its  neighbors $j  \in V(i)$  represented by  $x_j^i(t)$.  According to
 asynchronism and communication  delays, this estimate may be  outdated.  We also
 consider that the load is described by a continuous variable.
 
 asynchronism and communication  delays, this estimate may be  outdated.  We also
 consider that the load is described by a continuous variable.
 

-When a processor  send a part of its  load to one or some of  its neighbors, the
+When a processor  sends a part of its  load to one or some of  its neighbors, the

 transfer takes time to be completed.  Let $s_{ij}(t)$ be the amount of load that
 processor $i$ has transferred to processor $j$ at time $t$ and let $r_{ij}(t)$ be the
 amount of  load received by processor $j$  from processor $i$ at  time $t$. Then
 transfer takes time to be completed.  Let $s_{ij}(t)$ be the amount of load that
 processor $i$ has transferred to processor $j$ at time $t$ and let $r_{ij}(t)$ be the
 amount of  load received by processor $j$  from processor $i$ at  time $t$. Then


@@ -198,6 +198,8 @@ chain which 3 processors). Now consider we have the following values at time $t$
   x_3(t)   &= 99.99 \\
   x_3^2(t) &= 99.99 \\
 \end{align*}
   x_3(t)   &= 99.99 \\
   x_3^2(t) &= 99.99 \\
 \end{align*}

+{\bf RAPH, pourquoi il y a $x_3^2$?. Sinon il faudra reformuler la suite, c'est mal dit}
+

 In this case, processor $2$ can either sends load to processor $1$ or processor
 $3$.  If it sends load to processor $1$ it will not satisfy condition
 \eqref{eq.ping-pong} because after the sending it will be less loaded that
 In this case, processor $2$ can either sends load to processor $1$ or processor
 $3$.  If it sends load to processor $1$ it will not satisfy condition
 \eqref{eq.ping-pong} because after the sending it will be less loaded that


@@ -213,6 +215,13 @@ It may be the subject of future work to express weaker conditions, and to prove
 that they are sufficient to ensure the convergence of the load-balancing
 algorithm.
 
 that they are sufficient to ensure the convergence of the load-balancing
 algorithm.
 

+
+\section{Related works}
+\label{sec.related.works}
+{\bf A FAIRE}
+
+
+

 \section{Best effort strategy}
 \label{sec.besteffort}
 
 \section{Best effort strategy}
 \label{sec.besteffort}
 


@@ -233,21 +242,20 @@ he proceeds as following.
 \item First, the neighbors are sorted in non-decreasing order of their
   known loads $x^i_j(t)$.
 
 \item First, the neighbors are sorted in non-decreasing order of their
   known loads $x^i_j(t)$.
 

-\item Then, this sorted list is traversed in order to find its largest
-  prefix such as the load of each selected neighbor is lesser than:
+\item Then, this sorted list is used to find its largest
+  prefix such as the load of each selected neighbor is smaller than:

   \begin{itemize}
   \begin{itemize}

-  \item the processor's own load, and
+  \item the load of processor $i$, and

   \item the mean of the loads of the selected neighbors and of the
     processor's load.
   \end{itemize}
   \item the mean of the loads of the selected neighbors and of the
     processor's load.
   \end{itemize}

-  Let's call $S_i(t)$ the set of the selected neighbors, and
-  $\bar{x}(t)$ the mean of the loads of the selected neighbors and of
-  the processor load:
+  Let $S_i(t)$ be the set of the selected neighbors, and
+  $\bar{x}(t)$ be the mean of the loads of the selected neighbors plus the load of processor $i$:

   \begin{equation*}
     \bar{x}(t) = \frac{1}{\abs{S_i(t)} + 1}
       \left( x_i(t) + \sum_{j\in S_i(t)} x^i_j(t) \right)
   \end{equation*}
   \begin{equation*}
     \bar{x}(t) = \frac{1}{\abs{S_i(t)} + 1}
       \left( x_i(t) + \sum_{j\in S_i(t)} x^i_j(t) \right)
   \end{equation*}

-  The following properties hold:
+  The following properties hold: {\bf RAPH : la suite tombe du ciel :-)}

   \begin{equation*}
     \begin{cases}
       S_i(t) \subset V(i) \\
   \begin{equation*}
     \begin{cases}
       S_i(t) \subset V(i) \\


@@ -284,8 +292,8 @@ In order to reduce this effect, we add the ability to level the amount to send.
 The idea, here, is to make smaller steps toward the equilibrium, such that a
 potentially wrong decision has a lower impact.
 
 The idea, here, is to make smaller steps toward the equilibrium, such that a
 potentially wrong decision has a lower impact.
 

-Concretely, once $s_{ij}$ has been evaluated as before, it is simply divided by
-some configurable factor.  That's what we named the ``parameter $k$'' in
+Roughtly speaking, once $s_{ij}$ has been evaluated as previously explained, it is simply divided by
+a given factor.  This parameter is called $k$ in

 Section~\ref{sec.results}.  The amount of data to send is then $s_{ij}(t) =
 (\bar{x} - x^i_j(t))/k$.
 \FIXME[check that it's still named $k$ in Sec.~\ref{sec.results}]{}
 Section~\ref{sec.results}.  The amount of data to send is then $s_{ij}(t) =
 (\bar{x} - x^i_j(t))/k$.
 \FIXME[check that it's still named $k$ in Sec.~\ref{sec.results}]{}


@@ -326,10 +334,10 @@ require more time to be transferred.
 
 The  concept  of  \emph{virtual load}  allows  a  node  that received  a  load
 information message to integrate the load that it will receive later in its load
 
 The  concept  of  \emph{virtual load}  allows  a  node  that received  a  load
 information message to integrate the load that it will receive later in its load

-(virtually)  and consequently send  a (real)  part of  its load  to some  of its
+(virtually). Consequently the considered node can send  a (real)  part of  its load  to some  of its

 neighbors. In fact,  a node that receives a load  information message knows that
 later it  will receive the  corresponding load balancing message  containing the
 neighbors. In fact,  a node that receives a load  information message knows that
 later it  will receive the  corresponding load balancing message  containing the

-corresponding data.  So  if this node detects it is too  loaded compared to some
+corresponding data.  So, if this node detects it is too  loaded compared to some

 of its neighbors  and if it has enough  load (real load), then it  can send more
 load  to  some of  its  neighbors  without waiting  the  reception  of the  load
 balancing message.
 of its neighbors  and if it has enough  load (real load), then it  can send more
 load  to  some of  its  neighbors  without waiting  the  reception  of the  load
 balancing message.


@@ -339,6 +347,8 @@ information of the load they will receive, so they can take it into account.
 
 \FIXME{Est ce qu'on donne l'algo avec virtual load?}
 
 
 \FIXME{Est ce qu'on donne l'algo avec virtual load?}
 

+With integer load, we adapt this algorithm by .... {\bf RAPH a faire}
+

 \FIXME{describe integer mode}
 
 \section{Simulations}
 \FIXME{describe integer mode}
 
 \section{Simulations}