X-Git-Url: https://bilbo.iut-bm.univ-fcomte.fr/and/gitweb/loba-papers.git/blobdiff_plain/e3080a36717b6b9710daaec8c4d1e529b19c3176..c8b7a837b49a20dcbce655c5c891aea3f25542f5:/supercomp11/supercomp11.tex?ds=inline

diff --git a/supercomp11/supercomp11.tex b/supercomp11/supercomp11.tex
index 7daaa52..49477d7 100644
--- a/supercomp11/supercomp11.tex
+++ b/supercomp11/supercomp11.tex
@@ -1,25 +1,40 @@
-
 \documentclass[smallextended]{svjour3}
+\usepackage[utf8]{inputenc}
+\usepackage[T1]{fontenc}
+\usepackage{mathptmx}
+\usepackage{amsmath}
+\usepackage{courier}
 \usepackage{graphicx}
+\usepackage{url}
+\usepackage[ruled,lined]{algorithm2e}
+
+\newcommand{\abs}[1]{\lvert#1\rvert} % \abs{x} -> |x|
+
+\newenvironment{algodata}{%
+  \begin{tabular}[t]{@{}l@{:~}l@{}}}{%
+  \end{tabular}}
+
+\newcommand{\FIXME}[1]{%
+  \textbf{$\triangleright$\marginpar{\textbf{[FIXME]}}~#1}}
+
+\newcommand{\VAR}[1]{\textit{#1}}
 
 \begin{document}
 
-\title{Best effort strategy and virtual load for asynchronous iterative load balancing}
+\title{Best effort strategy and virtual load
+  for asynchronous iterative load balancing}
 
 \author{RaphaÃ«l Couturier \and
-        Arnaud Giersch \and
-        Abderrahmane Sider
+        Arnaud Giersch
 }
 
-\institute{F. Author \at
-              first address \\
-              Tel.: +123-45-678910\\
-              Fax: +123-45-678910\\
-              \email{fauthor@example.com}           %  \\
-%             \emph{Present address:} of F. Author  %  if needed
-           \and
-           S. Author \at
-              second address
+\institute{R. Couturier \and A. Giersch \at
+              LIFC, University of Franche-ComtÃ©, Belfort, France \\
+              % Tel.: +123-45-678910\\
+              % Fax: +123-45-678910\\
+              \email{%
+                raphael.couturier@univ-fcomte.fr,
+                arnaud.giersch@univ-fcomte.fr}
 }
 
 \maketitle
@@ -28,32 +43,572 @@
 \begin{abstract}
 
 Most of the  time, asynchronous load balancing algorithms  have extensively been
-studied in  a theoretical point of  view. The Bertsekas'  algorithm 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 paper,  we propose a
-strategy called \texttt{best  effort} 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 load transfers
-and message concerning load information.  In order to increase the converge of a
-load balancing  algorithm, we propose a simple  heuristic called \texttt{virtual
-  load}  which  allows a  node  that receives  an  load  information message  to
-integrate  the load  that it  will receive  latter 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  based on SimGrid which
-allowed us to conduct many experiments.
+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
+paper, we propose a strategy  called \emph{best effort} 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 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 simulator
+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
+different scientific  fields from high  performance computation to  micro sensor
+networks.   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
+where computer nodes  are considered homogeneous and with  homogeneous load with
+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
+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, 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}.
+\FIXME{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  \emph{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.  Former  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 more 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 \emph{virtual load} mechanism.
+
+
+
+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
+balancing. 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.  This strategy will be compared with other ones, presented in
+Section~\ref{Other}.  In Section~\ref{Virtual load}, the virtual load mechanism
+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}
+
+In  order  prove  the  convergence  of  asynchronous  iterative  load  balancing
+Bertsekas         and        Tsitsiklis         proposed         a        model
+in~\cite{bertsekas+tsitsiklis.1997.parallel}.   Here we  recall  some notations.
+Consider  that  $N={1,...,n}$  processors   are  connected  through  a  network.
+Communication links  are represented by  a connected undirected  graph $G=(N,V)$
+where $V$ is the set of links connecting different processors. In this work, we
+consider that  processors are  homogeneous for sake  of simplicity. It  is quite
+easy to tackle the  heterogeneous case~\cite{ElsMonPre02}. Load of processor $i$
+at  time $t$  is  represented  by $x_i(t)\geq  0$.   Let $V(i)$  be  the set  of
+neighbors of processor  $i$.  Each processor $i$ has an estimate  of the load of
+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.
+
+When a processor  send 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
+the amount of load of processor $i$ at time $t+1$ is given by:
+\begin{equation}
+x_i(t+1)=x_i(t)-\sum_{j\in V(i)} s_{ij}(t) + \sum_{j\in V(i)} r_{ji}(t)
+\label{eq:ping-pong}
+\end{equation}
+
+
+Some  conditions are  required to  ensure the  convergence. One  of them  can be
+called the \emph{ping-pong} condition which specifies that:
+\begin{equation}
+x_i(t)-\sum _{k\in V(i)} s_{ik}(t) \geq x_j^i(t)+s_{ij}(t)
+\end{equation}
+for any  processor $i$ and any  $j \in V(i)$ such  that $x_i(t)>x_j^i(t)$.  This
+condition aims  at avoiding a processor  to send a  part of its load  and being
+less loaded after that.
+
+Nevertheless,  we  think that  this  condition may  lead  to  deadlocks in  some
+cases. For example, if we consider  only three processors and that processor $1$
+is linked to processor $2$ which is  also linked to processor $3$ (i.e. a simple
+chain which 3 processors). Now consider we have the following values at time $t$:
+\begin{eqnarray*}
+x_1(t)=10   \\
+x_2(t)=100   \\
+x_3(t)=99.99\\
+ x_3^2(t)=99.99\\
+\end{eqnarray*}
+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
+(\ref{eq:ping-pong})  because  after the  sending  it  will  be less  loaded  that
+$x_3^2(t)$.  So we consider that the \emph{ping-pong} condition is probably to
+strong. Currently, we did not try to make another convergence proof without this
+condition or with a weaker condition.
+%
+\FIXME{Develop: We have the feeling that such a weaker condition
+  exists, because (it's not a proof, but) we have never seen any
+  scenario that is not leading to convergence, even with LB-strategies
+  that are not fulfilling these two conditions.}
+
+\section{Best effort strategy}
+\label{Best-effort}
+
+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.
+
+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
+  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:
+  \begin{itemize}
+  \item the processor's own load, and
+  \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:
+  \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:
+  \begin{equation*}
+    \begin{cases}
+      S_i(t) \subset V(i) \\
+      x^i_j(t) < x_i(t) & \forall j \in S_i(t) \\
+      x^i_j(t) < \bar{x} & \forall j \in S_i(t) \\
+      x^i_j(t) \leq x^i_k(t) & \forall j \in S_i(t), \forall k \in V(i) \setminus S_i(t) \\
+      \bar{x} \leq x_i(t)
+    \end{cases}
+  \end{equation*}
+
+\item Once this selection is completed, processor $i$ sends to each of
+  the selected neighbor $j\in S_i(t)$ an amount of load $s_{ij}(t) =
+  \bar{x} - x^i_j(t)$.
+
+  From the above equations, and notably from the definition of
+  $\bar{x}$, it can easily be verified that:
+  \begin{equation*}
+    \begin{cases}
+      x_i(t) - \sum_{j\in S_i(t)} s_{ij}(t) = \bar{x} \\
+      x^i_j(t) + s_{ij}(t) = \bar{x} & \forall j \in S_i(t)
+    \end{cases}
+  \end{equation*}
+\end{enumerate}
+
+\FIXME{describe parameter $k$}
+
+\section{Other strategies}
+\label{Other}
+
+\FIXME{RÃ©Ã©crire en angliche.}
+
+% \FIXME{faut-il dÃ©crire les stratÃ©gies makhoul et simple ?}
+
+% \paragraph{simple} Tentative de respecter simplement les conditions de Bertsekas.
+% Parmi les voisins moins chargÃ©s que soi, on sÃ©lectionne :
+% \begin{itemize}
+% \item un des moins chargÃ©s (vmin) ;
+% \item un des plus chargÃ©s (vmax),
+% \end{itemize}
+% puis on Ã©quilibre avec vmin en s'assurant que notre charge reste
+% toujours supÃ©rieure Ã  celle de vmin et Ã  celle de vmax.
+
+% On envoie donc (avec "self" pour soi-mÃªme) :
+% \[
+%     \min\left(\frac{load(self) - load(vmin)}{2}, load(self) - load(vmax)\right)
+% \]
+
+\paragraph{makhoul} Ordonne les voisins du moins chargÃ© au plus chargÃ©
+puis calcule les diffÃ©rences de charge entre soi-mÃªme et chacun des
+voisins.
+
+Ensuite, pour chaque voisin, dans l'ordre, et tant qu'on reste plus
+chargÃ© que le voisin en question, on lui envoie 1/(N+1) de la
+diffÃ©rence calculÃ©e au dÃ©part, avec N le nombre de voisins.
+
+C'est l'algorithme~2 dans~\cite{bahi+giersch+makhoul.2008.scalable}.
+
+\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 transferred.
+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 transferred.
+
+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.
+
+\FIXME{Est ce qu'on donne l'algo avec virtual load?}
+
+\FIXME{describe integer mode}
+
+\section{Simulations}
+\label{Simulations}
+
+In order to test and validate our approaches, we wrote a simulator
+using the SimGrid
+framework~\cite{casanova+legrand+quinson.2008.simgrid}.  This
+simulator, which consists of about 2,700 lines of C++, allows to run
+the different load-balancing strategies under various parameters, such
+as the initial distribution of load, the interconnection topology, the
+characteristics of the running platform, etc.  Then several metrics
+are issued that permit to compare the strategies.
 
+The simulation model is detailed in the next section (\ref{Sim
+  model}), and the experimental contexts are described in
+section~\ref{Contexts}.  Then the results of the simulations are
+presented in section~\ref{Results}.
 
+\subsection{Simulation model}
+\label{Sim model}
 
-qsdqsd
+In the simulation model the processors exchange messages which are of
+two kinds.  First, there are \emph{control messages} which only carry
+information that is exchanged between the processors, such as the
+current load, or the virtual load transfers if this option is
+selected.  These messages are rather small, and their size is
+constant.  Then, there are \emph{data messages} that carry the real
+load transferred between the processors.  The size of a data message
+is a function of the amount of load that it carries, and it can be
+pretty large.  In order to receive the messages, each processor has
+two receiving channels, one for each kind of messages.  Finally, when
+a message is sent or received, this is done by using the non-blocking
+primitives of SimGrid\footnote{That are \texttt{MSG\_task\_isend()},
+  and \texttt{MSG\_task\_irecv()}.}.
 
+During the simulation, each processor concurrently runs three threads:
+a \emph{receiving thread}, a \emph{computing thread}, and a
+\emph{load-balancing thread}, which we will briefly describe now.
 
+\paragraph{Receiving thread} The receiving thread is in charge of
+waiting for messages to come, either on the control channel, or on the
+data channel.  Its behavior is sketched by Algorithm~\ref{algo.recv}.
+When a message is received, it is pushed in a buffer of
+received message, to be later consumed by one of the other threads.
+There are two such buffers, one for the control messages, and one for
+the data messages.  The buffers are implemented with a lock-free FIFO
+\cite{sutter.2008.writing} to avoid contention between the threads.
 
+\begin{algorithm}
+  \caption{Receiving thread}
+  \label{algo.recv}
+  \KwData{
+    \begin{algodata}
+      \VAR{ctrl\_chan}, \VAR{data\_chan}
+      & communication channels (control and data) \\
+      \VAR{ctrl\_fifo}, \VAR{data\_fifo}
+      & buffers of received messages (control and data) \\
+    \end{algodata}}
+  \While{true}{%
+    wait for a message to be available on either \VAR{ctrl\_chan},
+    or \VAR{data\_chan}\;
+    \If{a message is available on \VAR{ctrl\_chan}}{%
+      get the message from \VAR{ctrl\_chan}, and push it into \VAR{ctrl\_fifo}\;
+    }
+    \If{a message is available on \VAR{data\_chan}}{%
+      get the message from \VAR{data\_chan}, and push it into \VAR{data\_fifo}\;
+    }
+  }
+\end{algorithm}
+
+\paragraph{Computing thread} The computing thread is in charge of the
+real load management.  As exposed in Algorithm~\ref{algo.comp}, it
+iteratively runs the following operations:
+\begin{itemize}
+\item if some load was received from the neighbors, get it;
+\item if there is some load to send to the neighbors, send it;
+\item run some computation, whose duration is function of the current
+  load of the processor.
+\end{itemize}
+Practically, after the computation, the computing thread waits for a
+small amount of time if the iterations are looping too fast (for
+example, when the current load is near zero).
+
+\begin{algorithm}
+  \caption{Computing thread}
+  \label{algo.comp}
+  \KwData{
+    \begin{algodata}
+      \VAR{data\_fifo} & buffer of received data messages \\
+      \VAR{real\_load} & current load \\
+    \end{algodata}}
+  \While{true}{%
+    \If{\VAR{data\_fifo} is empty and $\VAR{real\_load} = 0$}{%
+      wait until a message is pushed into \VAR{data\_fifo}\;
+    }
+    \While{\VAR{data\_fifo} is not empty}{%
+      pop a message from \VAR{data\_fifo}\;
+      get the load embedded in the message, and add it to \VAR{real\_load}\;
+    }
+    \ForEach{neighbor $n$}{%
+      \If{there is some amount of load $a$ to send to $n$}{%
+        send $a$ units of load to $n$, and subtract it from \VAR{real\_load}\;
+      }
+    }
+    \If{$\VAR{real\_load} > 0.0$}{
+      simulate some computation, whose duration is function of \VAR{real\_load}\;
+      ensure that the main loop does not iterate too fast\;
+    }
+  }
+\end{algorithm}
+
+\paragraph{Load-balancing thread} The load-balancing thread is in
+charge of running the load-balancing algorithm, and exchange the
+control messages.  As shown in Algorithm~\ref{algo.lb}, it iteratively
+runs the following operations:
+\begin{itemize}
+\item get the control messages that were received from the neighbors;
+\item run the load-balancing algorithm;
+\item send control messages to the neighbors, to inform them of the
+  processor's current load, and possibly of virtual load transfers;
+\item wait a minimum (configurable) amount of time, to avoid to
+  iterate too fast.
+\end{itemize}
+
+\begin{algorithm}
+  \caption{Load-balancing}
+  \label{algo.lb}
+  \While{true}{%
+    \While{\VAR{ctrl\_fifo} is not empty}{%
+      pop a message from \VAR{ctrl\_fifo}\;
+      identify the sender of the message,
+      and update the current knowledge of its load\;
+    }
+    run the load-balancing algorithm to make the decision about load transfers\;
+    \ForEach{neighbor $n$}{%
+      send a control messages to $n$\;
+    }
+    ensure that the main loop does not iterate too fast\;
+  }
+\end{algorithm}
+
+\paragraph{}
+For the sake of simplicity, a few details were voluntary omitted from
+these descriptions.  For an exhaustive presentation, we refer to the
+actual source code that was used for the experiments%
+\footnote{As mentioned before, our simulator relies on the SimGrid
+  framework~\cite{casanova+legrand+quinson.2008.simgrid}.  For the
+  experiments, we used a pre-release of SimGrid 3.7 (Git commit
+  67d62fca5bdee96f590c942b50021cdde5ce0c07, available from
+  \url{https://gforge.inria.fr/scm/?group_id=12})}, and which is
+available at
+\url{http://info.iut-bm.univ-fcomte.fr/staff/giersch/software/loba.tar.gz}.
+
+\FIXME{ajouter des dÃ©tails sur la gestion de la charge virtuelle ?}
+
+\subsection{Experimental contexts}
+\label{Contexts}
+
+In order to assess the performances of our algorithms, we ran our
+simulator with various parameters, and extracted several metrics, that
+we will describe in this section.
+
+\paragraph{Load balancing strategies}
+
+Several load balancing strategies were compared.  We ran the experiments with
+the \emph{Best effort}, and with the \emph{Makhoul} strategies.  \emph{Best
+  effort} was tested with parameter $k = 1$, $k = 2$, and $k = 4$.  Secondly,
+each strategy was run in its two variants: with, and without the management of
+\emph{virtual load}.  Finally, we tested each configuration with \emph{real},
+and with \emph{integer} load.
+
+To summarize the different load balancing strategies, we have:
+\begin{description}
+\item[\textbf{strategies:}] \emph{Makhoul}, or \emph{Best effort} with $k\in
+  \{1,2,4\}$
+\item[\textbf{variants:}] with, or without virtual load
+\item[\textbf{domain:}] real load, or integer load
+\end{description}
+%
+This gives us as many as $4\times 2\times 2 = 16$ different strategies.
+
+
+\paragraph{Configurations}
+
+In order to show the behavior of the different strategies in different
+settings, we simulated the executions on two sorts of platforms.  These two
+sorts of platforms differ by their underlaid network topology.  On the one hand,
+we have homogeneous platforms, modeled as a cluster.  On the other hand, we have
+heterogeneous platforms, modeled as the interconnection of a number of clusters.
+The heterogeneous platform descriptions were created by taking a subset of the
+Grid'5000 infrastructure\footnote{Grid'5000 is a French large scale experimental
+  Grid (see \url{https://www.grid5000.fr/}).}, as described in the platform file
+\texttt{g5k.xml} distributed with SimGrid.  Note that the heterogeneity of the
+platform only comes from the network topology.  The processor speeds, and
+network bandwidths were normalized since our algorithms currently are not aware
+of such heterogeneity.  We arbitrarily chose to fix the processor speed to
+1~GFlop/s, and the network bandwidth to 125~MB/s, with a latency of 50~$\mu$s,
+except for the links between geographically distant sites, where the network
+bandwidth was fixed to 2.25~GB/s, with a latency of 500~$\mu$s.
+
+Then we derived each sort of platform with four different number of computing
+nodes: 16, 64, 256, and 1024 nodes.
+
+The distributed processes of the application were then logically organized along
+three possible topologies: a line, a torus or an hypercube.  We ran tests where
+the total load was initially on an only node (at one end for the line topology),
+and other tests where the load was initially randomly distributed across all
+the participating nodes.
+
+For each of the preceding configuration, we finally had to choose the
+computation and communication costs of a load unit.  We chose them, such as to
+have three different computation over communication cost ratios, and hence model
+three different kinds of applications:
+\begin{itemize}
+\item mainly communicating, with a computation/communication cost ratio of $1/10$;
+\item mainly computing, with a computation/communication cost ratio of $10/1$ ;
+\item balanced, with a computation/communication cost ratio of $1/1$.
+\end{itemize}
+
+To summarize the various configurations, we have:
+\begin{description}
+\item[\textbf{platforms:}] homogeneous (cluster), or heterogeneous (subset of
+  Grid'5000)
+\item[\textbf{platform sizes:}] platforms with 16, 64, 256, or 1024 nodes
+\item[\textbf{process topologies:}] line, torus, or hypercube
+\item[\textbf{initial load distribution:}] initially on a only node, or
+  initially randomly distributed over all nodes
+\item[\textbf{computation/communication ratio:}] $10/1$, $1/1$, or $1/10$
+\end{description}
+%
+This gives us as many as $2\times 4\times 3\times 2\times 3 = 144$ different
+configurations.
+%
+Combined with the various load balancing strategies, we had $16\times 144 =
+2304$ distinct settings to evaluate.  In fact, as it will be shown later, we
+didn't run all the strategies, nor all the configurations for the bigger
+platforms with 1024 nodes, since to simulations would have run for a too long
+time.
+
+Anyway, all these the experiments represent more than 240 hours of computing
+time.
+
+\paragraph{Metrics}
+
+\begin{description}
+\item[\textbf{average idle time}]
+\item[\textbf{average convergence date}]
+\item[\textbf{maximum convergence date}]
+\item[\textbf{data transfer amount}] relative to the total data amount
+\end{description}
+
+\subsection{Validation of our approaches}
+\label{Results}
+
+
+On veut montrer quoi ? :
+
+1) best plus rapide que les autres (simple, makhoul)
+2) avantage virtual load
+
+Est ce qu'on peut trouver des contre exemple?
+Topologies variÃ©es
+
+
+Simulation avec temps dÃ©finies assez long et on mesure la qualitÃ© avec : volume de calcul effectuÃ©, volume de donnÃ©es Ã©changÃ©es
+Mais aussi simulation avec temps court qui montre que seul best converge
+
+
+ExpÃ©s avec ratio calcul/comm rapide et lent
+
+Quelques expÃ©s avec charge initiale alÃ©atoire plutot que sur le premier proc
+
+Cadre processeurs homogÃ¨nes
+
+Topologies statiques
+
+On ne tient pas compte de la vitesse des liens donc on la considÃ¨re homogÃ¨ne
+
+Prendre un rÃ©seau hÃ©tÃ©rogÃ¨ne et rendre processeur homogÃ¨ne
+
+Taille : 10 100 trÃ¨s gros
+
+\section{Conclusion and perspectives}
+
+\begin{acknowledgements}
+  Computations have been performed on the supercomputer facilities of
+  the MÃ©socentre de calcul de Franche-ComtÃ©.
+\end{acknowledgements}
+
+\bibliographystyle{spmpsci}
+\bibliography{biblio}
 
 \end{document}
+
+%%% Local Variables:
+%%% mode: latex
+%%% TeX-master: t
+%%% fill-column: 80
+%%% ispell-local-dictionary: "american"
+%%% End:
+
+% LocalWords:  RaphaÃ«l Couturier Arnaud Giersch Abderrahmane Sider Franche ij
+% LocalWords:  Bertsekas Tsitsiklis SimGrid DASUD ComtÃ© BÃ©jaÃ¯a asynchronism ji
+% LocalWords:  ik isend irecv CortÃ©s et al chan ctrl fifo Makhoul
