X-Git-Url: https://bilbo.iut-bm.univ-fcomte.fr/and/gitweb/loba-papers.git/blobdiff_plain/afe1c7b0d8f0330df0fa2b5c0bd2717454336e1d..d5c9abbacc165803629a3edc02365177cbd79731:/supercomp11/supercomp11.tex

diff --git a/supercomp11/supercomp11.tex b/supercomp11/supercomp11.tex
index 4e1509f..3c07eff 100644
--- a/supercomp11/supercomp11.tex
+++ b/supercomp11/supercomp11.tex
@@ -31,7 +31,8 @@
 \begin{abstract}
 
 Most of the  time, asynchronous load balancing algorithms  have extensively been
-studied in a theoretical point  of view. The Bertsekas and Tsitsiklis' algorithm
+studied in a theoretical point  of view. The Bertsekas and Tsitsiklis'
+algorithm~\cite[section~7.4]{bertsekas+tsitsiklis.1997.parallel}
 is certainly  the most well known  algorithm for which the  convergence proof is
 given. From a  practical point of view, when  a node wants to balance  a part of
 its  load to some  of its  neighbors, the  strategy is  not described.   In this
@@ -51,7 +52,7 @@ based on SimGrid which allowed us to conduct many experiments.
 
 \end{abstract}
 
-
+\section{Introduction}
 
 Load  balancing algorithms  are  extensively used  in  parallel and  distributed
 applications in  order to  reduce the  execution times. They  can be  applied in
@@ -68,8 +69,78 @@ 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  \texttt{ping-pong}  effect,  an  asynchronous
 iterative algorithm  converge to  the uniform load  distribution. This  work has
-been extended by many authors. For example, DASUD propose a version working with
-integer load.
+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}.
+
+Although  the Bertsekas  and Tsitsiklis'  algorithm describes  the  condition to
+ensure the convergence,  there is no indication or  strategy to really implement
+the load distribution. In other word, a node  can send a part of its load to one
+or   many  of   its  neighbors   while  all   the  convergence   conditions  are
+followed. Consequently,  we propose a  new strategy called  \texttt{best effort}
+that 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, 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.  Formers  ones  allows  a  node to  inform  its
+neighbors of its  current load. These messages are very small,  they can be sent
+quite often.  For example, if an  computing iteration takes  a significant times
+(ranging from seconds to minutes), it is possible to send a new load information
+message at each  neighbor at each iteration. Latter  messages contains data that
+migrates from one node to another one. 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 nore longer that to  time to transfer a load information message. So,
+when a node receives the information  that later it will receive a data message,
+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 \texttt{virtual load} mecanism.
+
+
+
+So, in  this work, we propose a  new strategy for improving  the distribution of
+the  load  and  a  simple  but  efficient trick  that  also  improves  the  load
+balacing. Moreover, we have conducted  many simulations with simgrid in order to
+validate 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.
+
+In the  following of this  paper, Section~\ref{BT algo} describes  the Bertsekas
+and Tsitsiklis'  asynchronous load balancing  algorithm. Moreover, we  present a
+possible  problem  in  the  convergence  conditions.   Section~\ref{Best-effort}
+presents the best effort strategy which  provides an efficient way to reduce the
+execution  times. In Section~\ref{Virtual  load}, the  virtual load  mecanism is
+proposed. Simulations allowed to show that both our approaches are valid using a
+quite realistic  model detailed in  Section~\ref{Simulations}. Finally we  give a
+conclusion and some perspectives to this work.
+
+
+
+
+\section{Bertsekas  and Tsitsiklis' asynchronous load balancing algorithm}
+\label{BT algo}
+
+Comment on the problem in the convergence condition.
+
+\section{Best effort strategy}
+\label{Best-effort}
+
+
+
+\section{Virtual load}
+\label{Virtual load}
+
+\section{Simulations}
+\label{Simulations}
+
+\subsection{Simulation model}
+
+\subsection{Validation of our approaches}
+
+
+\section{Conclusion and perspectives}
 
 
 \bibliographystyle{spmpsci}