\newcommand{\VAR}[1]{\textit{#1}}
+\newcommand{\besteffort}{\emph{best effort}}
+\newcommand{\makhoul}{\emph{Makhoul}}
+
\begin{document}
\begin{frontmatter}
\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\\
-}
+ 19 avenue du Maréchal Juin, BP 527, 90016 Belfort cedex, France}
\cortext[cor]{Corresponding author.}
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
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,
\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.
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.
\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},
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
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.
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.
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{The \besteffort{} strategy}
+
+Looking at the graph on figure~\ref{fig.results1}, we can see that the
+\besteffort{} strategy is not too bad, compared to the \makhoul{} strategy.
+
+\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}
+\FIXME{valider l'extension virtual load -> c'est 'achement bien}
+
\subsubsection{The $k$ parameter}
-\subsubsection{With an initial random repartition, and larger platforms}
+\FIXME{proposer le -k -> ça peut aider dans certains cas}
+
+\subsubsection{With an initial random distribution, and larger platforms}
+
+\FIXME{dire quoi ici ?}
\subsubsection{With integer load}
+\FIXME{conclure avec la version entière -> on n'a pas l'effet d'escalier !}
+
\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)?
+\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}
+\end{itemize}}
% On veut montrer quoi ? :
% 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é.
%%% 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
