X-Git-Url: https://bilbo.iut-bm.univ-fcomte.fr/and/gitweb/loba-papers.git/blobdiff_plain/e8a50f36912db421cea4c11f504ea9d253a9430f..59636878becb2087601db617b593fd3f35181655:/loba-besteffort/loba-besteffort.tex

diff --git a/loba-besteffort/loba-besteffort.tex b/loba-besteffort/loba-besteffort.tex
index b53ffec..3ccb2b0 100644
--- a/loba-besteffort/loba-besteffort.tex
+++ b/loba-besteffort/loba-besteffort.tex
@@ -3,9 +3,9 @@
 \usepackage[utf8]{inputenc}
 \usepackage[T1]{fontenc}
 
-\usepackage{newtxtext}
-\usepackage[cmintegrals]{newtxmath}
-%\usepackage{mathptmx,helvet,courier}
+%\usepackage{newtxtext}
+%\usepackage[cmintegrals]{newtxmath}
+\usepackage{mathptmx,helvet,courier}
 
 \usepackage{amsmath}
 \usepackage{graphicx}
@@ -27,6 +27,9 @@
 
 \newcommand{\VAR}[1]{\textit{#1}}
 
+\newcommand{\besteffort}{\emph{best effort}}
+\newcommand{\makhoul}{\emph{Makhoul}}
+
 \begin{document}
 
 \begin{frontmatter}
@@ -42,11 +45,13 @@
 \author{Arnaud Giersch\corref{cor}}
 \ead{arnaud.giersch@femto-st.fr}
 
-\address{FEMTO-ST, University of Franche-ComtÃ©\\
- 19 avenue de MarÃ©chal Juin, BP 527, 90016 Belfort cedex , France\\
-  % Tel.: +123-45-678910\\
-  % Fax: +123-45-678910\\
-}
+\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.}
 
@@ -57,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
@@ -104,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,
@@ -134,20 +139,21 @@ 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.
+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.
+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
+Section~\ref{sec.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{sec.simulations}.  Finally we give a
+conclusion and some perspectives to this work.
 
 
 
 \section{Bertsekas  and Tsitsiklis' asynchronous load balancing algorithm}
-\label{BT algo}
+\label{sec.bt-algo}
 
 In  order  prove  the  convergence  of  asynchronous  iterative  load  balancing
 Bertsekas         and        Tsitsiklis         proposed         a        model
@@ -170,7 +176,7 @@ 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}
+\label{eq.ping-pong}
 \end{equation}
 
 
@@ -193,9 +199,9 @@ 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
+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.
@@ -209,15 +215,15 @@ that they are sufficient to ensure the convergence of the load-balancing
 algorithm.
 
 \section{Best effort strategy}
-\label{Best-effort}
+\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.
@@ -281,17 +287,17 @@ 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
-Section~\ref{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{Results}]{}
+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}]{}
 
 \section{Other strategies}
-\label{Other}
+\label{sec.other}
 
 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.
@@ -307,7 +313,7 @@ neighbor.
 
 
 \section{Virtual load}
-\label{Virtual load}
+\label{sec.virtual-load}
 
 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
@@ -337,24 +343,23 @@ information of the load they will receive, so they can take in into account.
 \FIXME{describe integer mode}
 
 \section{Simulations}
-\label{Simulations}
+\label{sec.simulations}
 
 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+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}.
+The simulation model is detailed in the next section (\ref{sec.model}), and the
+experimental contexts are described in section~\ref{sec.exp-context}.  Then the
+results of the simulations are presented in section~\ref{sec.results}.
 
 \subsection{Simulation model}
-\label{Sim model}
+\label{sec.model}
 
 In the simulation model the processors exchange messages which are of
 two kinds.  First, there are \emph{control messages} which only carry
@@ -491,10 +496,11 @@ iteratively runs the following operations:
 \end{algorithm}
 
 \paragraph{}\FIXME{ajouter des dÃ©tails sur la gestion de la charge virtuelle ?
-par ex, donner l'idÃ©e gÃ©nÃ©rale de l'implÃ©mentation.  l'idÃ©e gÃ©nÃ©rale est dÃ©ja dÃ©crite en section~\ref{Virtual load}}
+  par ex, donner l'idÃ©e gÃ©nÃ©rale de l'implÃ©mentation.  l'idÃ©e gÃ©nÃ©rale est dÃ©ja
+  dÃ©crite en section~\ref{sec.virtual-load}}
 
 \subsection{Experimental contexts}
-\label{Contexts}
+\label{sec.exp-context}
 
 In order to assess the performances of our algorithms, we ran our
 simulator with various parameters, and extracted several metrics, that
@@ -503,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},
@@ -511,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
@@ -602,6 +608,7 @@ Anyway, all these the experiments represent more than 240 hours of computing
 time.
 
 \subsubsection{Metrics}
+\label{sec.metrics}
 
 In order to evaluate and compare the different load balancing strategies we had
 to define several metrics.  Our goal, when choosing these metrics, was to have
@@ -643,10 +650,10 @@ With these constraints in mind, we defined the following metrics:
 
 
 \subsection{Experimental results}
-\label{Results}
+\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}
 
@@ -660,7 +667,7 @@ Nevertheless their relative performances remain generally identical.
 This suggests that the relative performances of the different strategies are not
 influenced by the characteristics of the physical platform.  The differences in
 the convergence times can be explained by the fact that on the grid platforms,
-distant sites are interconnected by links of smaller bandwith.
+distant sites are interconnected by links of smaller bandwidth.
 
 Therefore, in the following, we'll only discuss the results for the grid
 platforms.
@@ -699,7 +706,7 @@ initially on an only node, while the results on figure~\ref{fig.resultsN} are
 when the load to balance is initially randomly distributed over all nodes.
 
 On both figures, the computation/communication cost ratio is $10/1$ on the left
-column, and $1/10$ on the right column.  With a computatio/communication cost
+column, and $1/10$ on the right column.  With a computation/communication cost
 ratio of $1/1$ the results are just between these two extrema, and definitely
 don't give additional information, so we chose not to show them here.
 
@@ -707,62 +714,131 @@ On each of the figures~\ref{fig.results1} and~\ref{fig.resultsN}, the results
 are given for the process topology being, from top to bottom, a line, a torus or
 an hypercube.
 
-\FIXME{explain how to read the graphs}
+Finally, on the graphs, the vertical bars show the measured times for each of
+the algorithms.  These measured times are, from bottom to top, the average idle
+time, the average convergence date, and the maximum convergence date (see
+Section~\ref{sec.metrics}).  The measurements are repeated for the different
+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.
 
-each bar -> times for an algorithm
-recall the different times
-no bar -> not run or did not converge in allocated time
+\FIXME{annoncer le plan de la suite}
 
-repeated for the different platform sizes.
+\subsubsection{The \besteffort{} and  \makhoul{} strategies without virtual load}
 
-\FIXME{donner les premiÃ¨res conclusions, annoncer le plan de la suite}
+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{With the virtual load extension}
+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.
 
-\subsubsection{The $k$ parameter}
+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 repartition,  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.
 
-\subsubsection{With integer load}
+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.
 
-\FIXME{what about the amount of data?}
-
-\begin{itshape}
-\FIXME{remove that part}
-Dans cet ordre:
-...
-- comparer be/makhoul -> be tient la route
-        -> en rÃ©el uniquement
-- valider l'extension virtual load -> c'est 'achement bien
-- proposer le -k -> Ã§a peut aider dans certains cas
-- conclure avec la version entiÃ¨re -> on n'a pas l'effet d'escalier !
-Q: comment inclure les types/tailles de platesformes ?
-Q: comment faire des moyennes ?
-Q: comment introduire les distrib 1/N ?
-...
-
-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
+\subsubsection{Virtual load}
 
-\item makhoul? se fait battre sur les grosses plateformes
+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.
 
-\item taille de plateforme?
+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}.
 
-\item ratio comp/comm?
+%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.
 
-\item option $k$? peut-Ãªtre intÃ©ressant sur des plateformes fortement interconnectÃ©es (hypercube)
+%\subsubsection{The \besteffort{} strategy with an initial random load
+%  distribution, and larger platforms}
 
-\item volume de comm? souvent, besteffort/plain en fait plus. pourquoi?
+%In 
+%MÃªmes conclusions pour line et hcube.
+%Sur tore, BE se fait exploser quand les comms coutent cher.
 
-\item rÃ©partition initiale de la charge ?
+%\FIXME{virer les 1024 ?}
 
-\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.
+%\subsubsection{With the virtual load extension with an initial random load
+%  distribution}
 
-\end{itemize}
+%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 ? :
 
@@ -789,13 +865,12 @@ On constate quoi (vÃ©rifier avec les chiffres)?
 % Prendre un rÃ©seau hÃ©tÃ©rogÃ¨ne et rendre processeur homogÃ¨ne
 
 % Taille : 10 100 trÃ¨s gros
-\end{itshape}
 
 \section{Conclusion and perspectives}
 
 \FIXME{conclude!}
 
-\section*{Acknowledgements}
+\section*{Acknowledgments}
 
 Computations have been performed on the supercomputer facilities of the
 MÃ©socentre de calcul de Franche-ComtÃ©.
@@ -813,7 +888,10 @@ MÃ©socentre de calcul de Franche-ComtÃ©.
 %%% 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 GFlop xml pre
-% LocalWords:  FEMTO Makhoul's fca bdee cdde Contassot Vivier underlaid
+% LocalWords:  RaphaÃ«l Couturier Arnaud Giersch Franche ij Bertsekas Tsitsiklis
+% 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 Institut UMR UniversitÃ© UFC Centre Scientifique CNRS des
+% LocalWords:  Ãcole Nationale SupÃ©rieure MÃ©canique Microtechniques ENSMM UTBM
+% LocalWords:  Technologie Bahi
