virtual load

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

diff --git a/supercomp11/supercomp11.tex b/supercomp11/supercomp11.tex
index b0d23b080740698df6c117c5aa157db9436d6888..2d6b32f9fe83416293c196b9ed81a48505003692 100644 (file)
--- a/supercomp11/supercomp11.tex
+++ b/supercomp11/supercomp11.tex
@@ -49,7 +49,7 @@ Moreover,  asynchronous  iterative  algorithms  in which  an  asynchronous  load
 balancing  algorithm is  implemented most  of the  time can  dissociate messages
 concerning load transfers and message  concerning load information.  In order to
 increase  the  converge of  a  load balancing  algorithm,  we  propose a  simple
 balancing  algorithm is  implemented most  of the  time can  dissociate 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 called \emph{virtual load} which allows a node that receives an load
+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 simulator
 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 simulator


@@ -75,9 +75,11 @@ 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
 iterative algorithm  converge to  the uniform load  distribution. This  work has
 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

-been extended by many authors. For example,
-DASUD~\cite{cortes+ripoll+cedo+al.2002.asynchronous} propose a version working
-with integer load. {\bf Rajouter des choses ici}.
+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
+the same authors in \cite{cedo+cortes+ripoll+al.2007.convergence}.
+{\bf Rajouter des choses ici}.

 
 Although  the Bertsekas  and Tsitsiklis'  algorithm describes  the  condition to
 ensure the convergence,  there is no indication or  strategy to really implement
 
 Although  the Bertsekas  and Tsitsiklis'  algorithm describes  the  condition to
 ensure the convergence,  there is no indication or  strategy to really implement


@@ -183,12 +185,13 @@ condition or with a weaker condition.
 \section{Best effort strategy}
 \label{Best-effort}
 
 \section{Best effort strategy}
 \label{Best-effort}
 

-We will describe here a new load-balancing strategy that we called
-\emph{best effort}.  The general idea behind this strategy is, for a
-processor, to send some load to the most of its neighbors, doing its
+In this section we  describe  a new load-balancing strategy that we call
+\emph{best effort}.  The general idea behind this strategy is that each
+processor, that detects it has more load than some of its neighbors, 
+sends some load to the most of its less loaded neighbors, doing its

 best to reach the equilibrium between those neighbors and himself.
 
 best to reach the equilibrium between those neighbors and himself.
 

-More precisely, when a processors $i$ is in its load-balancing phase,
+More precisely, when a processor $i$ is in its load-balancing phase,

 he proceeds as following.
 \begin{enumerate}
 \item First, the neighbors are sorted in non-decreasing order of their
 he proceeds as following.
 \begin{enumerate}
 \item First, the neighbors are sorted in non-decreasing order of their


@@ -265,6 +268,31 @@ C'est l'algorithme~2 dans~\cite{bahi+giersch+makhoul.2008.scalable}.
 \section{Virtual load}
 \label{Virtual load}
 
 \section{Virtual load}
 \label{Virtual load}
 

+In this section,  we present the concept of \texttt{virtual  load}.  In order to
+use this concept, load balancing messages must be sent using two different kinds
+of  messages:  load information  messages  and  load  balancing messages.   More
+precisely, a node  wanting to send a part  of its load to one  of its neighbors,
+can first send  a load information message containing the load  it will send and
+then it  can send the load  balancing message containing data  to be transfered.
+Load information  message are really  short, consequently they will  be received
+very quickly.  In opposition, load  balancing messages are often bigger and thus
+require more time to be transfered.
+
+The  concept  of  \texttt{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
+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
+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.
+
+Doing  this, we  can  expect a  faster  convergence since  nodes  have a  faster
+information of the load they will receive, so they can take in into account.
+
+\textbf{Question} Est ce qu'on donne l'algo avec virtual load?
+

 \section{Simulations}
 \label{Simulations}
 
 \section{Simulations}
 \label{Simulations}