X-Git-Url: https://bilbo.iut-bm.univ-fcomte.fr/and/gitweb/loba-papers.git/blobdiff_plain/58583054e42c6065604b04ac3781a45efb869549..380e5cf3507605371bba52eb9a64a9e9c6bcdf24:/loba-besteffort/loba-besteffort.tex

diff --git a/loba-besteffort/loba-besteffort.tex b/loba-besteffort/loba-besteffort.tex
index 23fe6ea..e966c40 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}
@@ -42,8 +45,13 @@
 \author{Arnaud Giersch\corref{cor}}
 \ead{arnaud.giersch@femto-st.fr}
 
-\address{FEMTO-ST, University of Franche-Comté\\
- 19 avenue du Maréchal Juin, BP 527, 90016 Belfort cedex, France}
+\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}
 
 \cortext[cor]{Corresponding author.}
 
@@ -54,7 +62,7 @@
   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
@@ -101,7 +109,7 @@ 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,
@@ -210,12 +218,12 @@ algorithm.
 \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.
@@ -289,7 +297,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.
@@ -501,7 +509,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 +517,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
@@ -645,7 +653,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}
 
@@ -716,45 +724,88 @@ allocated time, or because we simply decided not to run it.
 
 \FIXME{annoncer le plan de la suite}
 
-\subsubsection{The \emph{best effort} strategy}
+\subsubsection{The \besteffort{} strategy with the load initially on only one
+  node}
+
+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  the graphs  from the figure~\ref{fig.results1},  these strategies
+(with virtual load feature) are respectively labeled ``b'' and ``a''.
+
+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 twice as  fast as the \makhoul{} strategy.  This can  be explained by the
+fact that the \besteffort{} strategy tries to distribute the load faitly between
+all the nodes  and with the line topology,  it is easy to load  balance the load
+fairly.
+
+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 equilibrum faster.
+
+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.
+
+Globally   the  number  of   interconnection  is   very  important.    The  more
+interconnection links there 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.
 
-Looking at the graph on figure~\ref{fig.results1}, we can see that the
-\emph{best effort} strategy is not too bad.
 
-\FIXME{donner les premières conclusions}
-\FIXME{comparer be/makhoul -> be tient la route (parler du cas réel uniquement)}
+\subsubsection{With the virtual load extension with the load initially on only
+  one node}
 
-\subsubsection{With the virtual load extension}
+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.
 
-\FIXME{valider l'extension virtual load -> c'est 'achement bien}
+\subsubsection{The \besteffort{} strategy with an initial random load
+  distribution, and larger platforms}
+
+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}
 
-\FIXME{proposer le -k -> ça peut aider dans certains cas}
+Dans le cas où les comms coutent cher et ou BE se fait avoir, on peut ameliorer
+les perfs avec le param k.
 
-\subsubsection{With an initial random distribution, and larger platforms}
+\subsubsection{With integer load, 1 ou N}
 
-\FIXME{dire quoi ici ?}
+Cas normal, ligne -> converge pas (effet d'escalier).
+Avec vload, ça converge.
 
-\subsubsection{With integer load}
+Dans les autres cas, résultats similaires au cas réel: redire que vload est
+intéressant.
 
-\FIXME{conclure avec la version entière -> on n'a pas l'effet d'escalier !}
+\FIXME{virer la metrique volume de comms}
 
-\FIXME{what about the amount of data?}
+\FIXME{ajouter une courbe ou on voit l'évolution de la charge en fonction du
+  temps : avec et sans vload}
 
-\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}}
+% \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 ? :
 
@@ -808,4 +859,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