Rename: "hcube" -> "hypercube".

[loba-papers.git] / loba-besteffort / loba-besteffort.tex

diff --git a/loba-besteffort/loba-besteffort.tex b/loba-besteffort/loba-besteffort.tex
index 44a685303399648776bd202c11353dfe24f05d03..2d0f414fd365ec501a0ea2249e627a4454fde86f 100644 (file)
--- a/loba-besteffort/loba-besteffort.tex
+++ b/loba-besteffort/loba-besteffort.tex
@@ -27,6 +27,9 @@
 
 \newcommand{\VAR}[1]{\textit{#1}}
 
 
 \newcommand{\VAR}[1]{\textit{#1}}
 

+\newcommand{\besteffort}{\emph{best effort}}
+\newcommand{\makhoul}{\emph{Makhoul}}
+

 \begin{document}
 
 \begin{frontmatter}
 \begin{document}
 
 \begin{frontmatter}


@@ -42,11 +45,13 @@
 \author{Arnaud Giersch\corref{cor}}
 \ead{arnaud.giersch@femto-st.fr}
 
 \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.}
 
 
 \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
   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
   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
 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,
 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,


@@ -213,12 +218,12 @@ algorithm.
 \label{sec.besteffort}
 
 In this section we describe a new load-balancing strategy that we call
 \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}
 
 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.
 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.


@@ -292,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
 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.
 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.


@@ -504,7 +509,7 @@ we will describe in this section.
 \subsubsection{Load balancing strategies}
 
 Several load balancing strategies were compared.  We ran the experiments with
 \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},
   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},


@@ -512,7 +517,7 @@ and with \emph{integer} load.
 
 To summarize the different load balancing strategies, we have:
 \begin{description}
 
 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
   \{1,2,4\}$
 \item[\textbf{variants:}] with, or without virtual load
 \item[\textbf{domain:}] real load, or integer load


@@ -662,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,
 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.
 
 Therefore, in the following, we'll only discuss the results for the grid
 platforms.


@@ -701,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
 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.
 
 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.
 


@@ -717,54 +722,76 @@ 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.
 
 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{annoncer le plan de la suite}

 
 

-\subsubsection{With the virtual load extension}
+\subsubsection{The \besteffort{} strategy with the load initially on only one
+  node}

 
 

-\subsubsection{The $k$ parameter}
+Before looking at the different variations, we'll 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
+are respectively labeled ``b'' and ``a''.

 
 

-\subsubsection{With an initial random repartition,  and larger platforms}
+twice faster on lines
+almost equivalent on torus
+worse on hcubes

 
 

-\subsubsection{With integer load}
+-> interconnection

 
 

-\FIXME{what about the amount of data?}
+plus c'est connecté, moins bon est BE car à vouloir trop bien équilibrer
+localement, le processeurs se perturbent mutuellement.  Du coup, makhoul qui
+équilibre moins bien localement est moins perturbé par ces interférences.

 
 

-\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 ?
-...
+\subsubsection{With the virtual load extension with the load initially on only
+  one node}

 
 

-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
+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 bookkeeping? améliore souvent les choses, parfois au prix d'un retard au démarrage
+\subsubsection{The \besteffort{} strategy with an initial random load
+  distribution, and larger platforms}

 
 

-\item makhoul? se fait battre sur les grosses plateformes
+Mêmes conclusions pour line et hcube.
+Sur tore, BE se fait exploser quand les comms coutent cher.

 
 

-\item taille de plateforme?
+\FIXME{virer les 1024 ?}

 
 

-\item ratio comp/comm?
+\subsubsection{With the virtual load extension with an initial random load
+  distribution}

 
 

-\item option $k$? peut-être intéressant sur des plateformes fortement interconnectées (hypercube)
+Soit c'est équivalent, soit on gagne -> surtout quand les comms coutent cher et
+qu'il y a beaucoup de voisins.

 
 

-\item volume de comm? souvent, besteffort/plain en fait plus. pourquoi?
+\subsubsection{The $k$ parameter}

 
 

-\item répartition initiale de la charge ?
+Dans le cas où les comms coutent cher et ou BE se fait avoir, on peut ameliorer
+les perfs avec le param k.

 
 

-\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 integer load, 1 ou N}

 
 

-\end{itemize}
+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{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 ? :
 
 
 % On veut montrer quoi ? :
 


@@ -791,13 +818,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
 % 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{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é.
 
 Computations have been performed on the supercomputer facilities of the
 Mésocentre de calcul de Franche-Comté.


@@ -815,7 +841,8 @@ Mésocentre de calcul de Franche-Comté.
 %%% ispell-local-dictionary: "american"
 %%% End:
 
 %%% 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