X-Git-Url: https://bilbo.iut-bm.univ-fcomte.fr/and/gitweb/loba-papers.git/blobdiff_plain/a2a8d07a9e743174f5c7121b387e73dfa8d5eaaa..019bcd66f0712c7954b6e9e15ec7abe92063795b:/loba-besteffort/loba-besteffort.tex

diff --git a/loba-besteffort/loba-besteffort.tex b/loba-besteffort/loba-besteffort.tex
index d97c653..9f26237 100644
--- a/loba-besteffort/loba-besteffort.tex
+++ b/loba-besteffort/loba-besteffort.tex
@@ -27,6 +27,9 @@
 
 \newcommand{\VAR}[1]{\textit{#1}}
 
+\newcommand{\besteffort}{\emph{best effort}}
+\newcommand{\makhoul}{\emph{Makhoul}}
+
 \begin{document}
 
 \begin{frontmatter}
@@ -37,13 +40,16 @@
   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}}
-\ead{arnaud.giersch@femto-st.fr}
+\ead{arnaud.giersch@univ-fcomte.fr}
+
+\author{Mourad Hakem}
+\ead{mourad.hakem@univ-fcomte.fr}
 
-\address{FEMTO-ST, University of Franche-ComtÃ©\\
- 19 avenue du MarÃ©chal Juin, BP 527, 90016 Belfort cedex, France}
+\address{%
+  FEMTO-ST Institute, Univ Bourgogne Franche-ComtÃ©, Belfort, France}
 
 \cortext[cor]{Corresponding author.}
 
@@ -54,17 +60,16 @@
   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
+  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
-  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}
 
@@ -79,18 +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
-networks.   They are  iterative by  nature.  In  literature many  kinds  of load
+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
-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
-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
-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
@@ -101,18 +107,17 @@ 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}
+followed. Consequently,  we propose a  new strategy called  \besteffort{}
 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
+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 
+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
-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
+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,
@@ -121,19 +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.
 
-
-
-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
+{\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
+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.
+\end{itemize}
 
 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
@@ -151,8 +158,8 @@ 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
+Communication links  are represented by  a connected undirected  graph $G=(N,A)$
+where $A$ 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
@@ -161,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.
 
-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
@@ -185,15 +192,17 @@ 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*}
+\begin{align*}
+  x_1(t)   &= 10    \\
+  x_2(t)   &= 100   \\
+  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
-(\ref{eq.ping-pong}) because after the sending it will be less loaded that
+\eqref{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.
@@ -206,16 +215,23 @@ 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.
 
+
+\section{Related works}
+\label{sec.related.works}
+{\bf A FAIRE}
+
+
+
 \section{Best effort strategy}
 \label{sec.besteffort}
 
 In this section we describe a new load-balancing strategy that we call
-\emph{best effort}.  First, we explain the general idea behind this strategy,
+\besteffort{}.  First, we explain the general idea behind this strategy,
 and then we describe some variants of this basic strategy.
 
 \subsection{Basic strategy}
 
-The general idea behind the \emph{best effort} strategy is that each processor,
+The general idea behind the \besteffort{} 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.
@@ -226,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 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}
-  \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}
-  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*}
-  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) \\
@@ -277,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.
 
-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}]{}
@@ -289,7 +304,7 @@ Section~\ref{sec.results}.  The amount of data to send is then $s_{ij}(t) =
 Another load balancing strategy, working under the same conditions, was
 previously developed by Bahi, Giersch, and Makhoul in
 \cite{bahi+giersch+makhoul.2008.scalable}.  In order to assess the performances
-of the new \emph{best effort}, we naturally chose to compare it to this anterior
+of the new \besteffort{}, we naturally chose to compare it to this anterior
 work.  More precisely, we will use the algorithm~2 from
 \cite{bahi+giersch+makhoul.2008.scalable} and, in the following, we will
 reference it under the name of Makhoul's.
@@ -299,7 +314,7 @@ a load balancing decision, it starts by sorting its neighbors by increasing
 order of their load.  Then, it computes the difference between its own load, and
 the load of each of its neighbors.  Finally, taking the neighbors following the
 order defined before, the amount of load to send $s_{ij}$ is computed as
-$1/(N+1)$ of the load difference, with $N$ being the number of neighbors.  This
+$1/(n+1)$ of the load difference, with $n$ being the number of neighbors.  This
 process continues as long as the node is more loaded than the considered
 neighbor.
 
@@ -310,8 +325,8 @@ neighbor.
 In this section,  we present the concept of \emph{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
+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
@@ -319,19 +334,21 @@ 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
-(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
-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.
 
 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.
+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?}
 
+With integer load, we adapt this algorithm by .... {\bf RAPH a faire}
+
 \FIXME{describe integer mode}
 
 \section{Simulations}
@@ -339,7 +356,7 @@ information of the load they will receive, so they can take in into account.
 
 In order to test and validate our approaches, we wrote a simulator
 using the SimGrid
-framework~\cite{casanova+legrand+quinson.2008.simgrid}.  This
+framework~\cite{simgrid.web,casanova+giersch+legrand+al.2014.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
@@ -375,7 +392,7 @@ 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
+  framework~\cite{casanova+giersch+legrand+al.2014.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
@@ -501,7 +518,7 @@ we will describe in this section.
 \subsubsection{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
+the \besteffort{}, and with the \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},
@@ -509,7 +526,7 @@ 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
+\item[\textbf{strategies:}] \makhoul{}, or \besteffort{} with $k\in
   \{1,2,4\}$
 \item[\textbf{variants:}] with, or without virtual load
 \item[\textbf{domain:}] real load, or integer load
@@ -553,7 +570,7 @@ algorithms currently do not handle heterogeneous computing resources, the
 processor speeds were normalized, and we arbitrarily chose to fix them to
 1~GFlop/s.
 
-Then we derived each sort of platform with four different number of computing
+Then we derived each kind of platform with four different numbers of computing
 nodes: 16, 64, 256, and 1024 nodes.
 
 \subsubsection{Configurations}
@@ -645,7 +662,7 @@ With these constraints in mind, we defined the following metrics:
 \label{sec.results}
 
 In this section, the results for the different simulations will be presented,
-and we'll try to explain our observations.
+and we will try to explain our observations.
 
 \subsubsection{Cluster vs grid platforms}
 
@@ -714,40 +731,123 @@ platform sizes.  Some bars are missing, specially for large platforms.  This is
 either because the algorithm did not reach the convergence state in the
 allocated time, or because we simply decided not to run it.
 
-\FIXME{donner les premiÃ¨res conclusions, annoncer le plan de la suite}
-\FIXME{comparer be/makhoul -> be tient la route (parler du cas rÃ©el uniquement)}
+\FIXME{annoncer le plan de la suite}
 
-\subsubsection{With the virtual load extension}
+\subsubsection{The \besteffort{} and  \makhoul{} strategies without virtual load}
 
-\FIXME{valider l'extension virtual load -> c'est 'achement bien}
+Before looking  at the different variations,  we will first show  that the plain
+\besteffort{}  strategy  is valuable,  and  may be  as  good  as the  \makhoul{}
+strategy.  On  Figures~\ref{fig.results1} and~\ref{fig.resultsN},
+these strategies are respectively labeled ``b'' and ``a''.
 
-\subsubsection{The $k$ parameter}
+We  can  see  that  the  relative  performance of  these  strategies  is  mainly
+influenced by  the application topology.  It  is for the line  topology that the
+difference is the  more important.  In this case,  the \besteffort{} strategy is
+nearly faster than the \makhoul{} strategy.  This can  be explained by the
+fact that the \besteffort{} strategy tries to distribute the load fairly between
+all the nodes  and with the line topology,  it is easy to load  balance the load
+fairly.
 
-\FIXME{proposer le -k -> Ã§a peut aider dans certains cas}
+On the contrary, for the hypercube topology, the \besteffort{} strategy performs
+worse than the \makhoul{} strategy. In this case, the \makhoul{} strategy which
+tries to give more load to few neighbors reaches the equilibrium faster.
 
-\subsubsection{With an initial random distribution, and larger platforms}
+For the torus  topology, for which the  number of links is between  the line and
+the hypercube, the \makhoul{} strategy  is slightly better but the difference is
+more nuanced when the initial load is  only on one node. The only case where the
+\makhoul{} strategy is really faster than the \besteffort{} strategy is with the
+random initial distribution when the communication are slow.
 
-\FIXME{dire quoi ici ?}
+Globally   the  number  of   interconnection  is   very  important.    The  more
+the interconnection links are, the  faster the \makhoul{} strategy is because
+it distributes quickly significant amount of load, even if this is unfair, between
+all the  neighbors.  In opposition,  the \besteffort{} strategy  distributes the
+load fairly so this strategy is better for low connected strategy.
 
-\subsubsection{With integer load}
 
-\FIXME{conclure avec la version entiÃ¨re -> on n'a pas l'effet d'escalier !}
+\subsubsection{Virtual load}
 
-\FIXME{what about the amount of data?}
+The influence of virtual load is most of the time really significant compared to
+the  same configuration  without  it. Sometimes  it  has no  effect  but {\bf  A
+  VERIFIER} it has never a negative effect on the load balancing we tested.
 
-\FIXME{On constate quoi (vÃ©rifier avec les chiffres)?
-\begin{itemize}
-\item cluster ou grid, entier ou rÃ©el, ne font pas de grosses diffÃ©rences
-\item bookkeeping? amÃ©liore souvent les choses, parfois au prix d'un retard au dÃ©marrage
-\item makhoul? se fait battre sur les grosses plateformes
-\item taille de plateforme?
-\item ratio comp/comm?
-\item option $k$? peut-Ãªtre intÃ©ressant sur des plateformes fortement interconnectÃ©es (hypercube)
-\item volume de comm? souvent, besteffort/plain en fait plus. pourquoi?
-\item rÃ©partition initiale de la charge ?
-\item integer mode sur topo. line n'a jamais fini en plain? vÃ©rifier si ce n'est
-  pas Ã  cause de l'effet d'escalier que bk est capable de gommer.
-\end{itemize}}
+On Figure~\ref{fig.results1}, when the load is  initially on one node, it can be
+noticed that the  average idle times are generally longer  with the virtual load
+than without  it. This  can be explained  by the  fact that, with  virtual load,
+processors  will exchange all  the load  they need  to exchange  as soon  as the
+virtual load has been balanced  between all the processors. So consequently they
+cannot  compute  at  the  beginning.  This is  especially  noticeable  when  the
+communication are slow (on the left part of Figure ~\ref{fig.results1}.
+
+%Dans ce cas  lÃ©gÃ¨re amÃ©lioration de la cvg. max.  Temps  moyen de cvg. amÃ©liorÃ©,
+%mais plus de temps passÃ© en idle, surtout quand les comms coutent cher.
+
+%\subsubsection{The \besteffort{} strategy with an initial random load
+%  distribution, and larger platforms}
+
+%In 
+%MÃªmes conclusions pour line et hcube.
+%Sur tore, BE se fait exploser quand les comms coutent cher.
+
+%\FIXME{virer les 1024 ?}
+
+%\subsubsection{With the virtual load extension with an initial random load
+%  distribution}
+
+%Soit c'est Ã©quivalent, soit on gagne -> surtout quand les comms coutent cher et
+%qu'il y a beaucoup de voisins.
+
+\subsubsection{The $k$ parameter}
+\label{results-k}
+
+As  explained  previously when  the  communication  are  slow the  \besteffort{}
+strategy is efficient. This is due to the fact that it tries to balance the load
+fairly and consequently  a significant amount of the  load is transfered between
+processors.  In this situation, it is possible to reduce the convergence time by
+using  the leveler  parameter  (parameter  $k$).  The  advantage  of using  this
+solution is particularly efficient when the initial load is randomly distributed
+on  the nodes with  torus and  hypercube topology  and slow  communication. When
+virtual load  mechanism is used,  the effect of  this parameter is  also visible
+with the same condition.
+
+
+
+\subsubsection{With integer load}
+
+We also performed  some experiments with integer load instead  of load with real
+value.  In  this case, the  results have globally  the same behavior.   The most
+intereting  result, from  our point  of view,  is that  the virtual  mode allows
+processors in a line topology to converge to the uniform load balancing. Without
+the virtual  load, most  of the time,  processors converge  to what we  call the
+``stairway effect'', that  is to say that  there is only a difference  of one in
+the load of each processor and its neighbors (for example with 10 processors, we
+obtain 10 9 8 7 6 6 7 8 9 10 instead of 8 8 8 8 8 8 8 8 8 8).
+
+%Cas normal, ligne -> converge pas (effet d'escalier).
+%Avec vload, Ã§a converge.
+
+%Dans les autres cas, rÃ©sultats similaires au cas rÃ©el: redire que vload est
+%intÃ©ressant.
+
+\FIXME{ajouter une courbe avec l'Ã©quilibrage en entier}
+
+\FIXME{virer la metrique volume de comms}
+
+\FIXME{ajouter une courbe ou on voit l'Ã©volution de la charge en fonction du
+  temps : avec et sans vload}
+
+% \begin{itemize}
+% \item cluster ou grid, entier ou rÃ©el, ne font pas de grosses diffÃ©rences
+% \item bookkeeping? amÃ©liore souvent les choses, parfois au prix d'un retard au dÃ©marrage
+% \item makhoul? se fait battre sur les grosses plateformes
+% \item taille de plateforme?
+% \item ratio comp/comm?
+% \item option $k$? peut-Ãªtre intÃ©ressant sur des plateformes fortement interconnectÃ©es (hypercube)
+% \item volume de comm? souvent, besteffort/plain en fait plus. pourquoi?
+% \item rÃ©partition initiale de la charge ?
+% \item integer mode sur topo. line n'a jamais fini en plain? vÃ©rifier si ce n'est
+%   pas Ã  cause de l'effet d'escalier que bk est capable de gommer.
+% \end{itemize}}
 
 % On veut montrer quoi ? :
 
@@ -801,4 +901,6 @@ MÃ©socentre de calcul de Franche-ComtÃ©.
 % LocalWords:  SimGrid DASUD ComtÃ© asynchronism ji ik isend irecv CortÃ©s et al
 % LocalWords:  chan ctrl fifo Makhoul GFlop xml pre FEMTO Makhoul's fca bdee
 % LocalWords:  cdde Contassot Vivier underlaid du de MarÃ©chal Juin cedex calcul
-% LocalWords:  biblio
+% LocalWords:  biblio Institut UMR UniversitÃ© UFC Centre Scientifique CNRS des
+% LocalWords:  Ãcole Nationale SupÃ©rieure MÃ©canique Microtechniques ENSMM UTBM
+% LocalWords:  Technologie Bahi
