.

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

diff --git a/loba-besteffort/loba-besteffort.tex b/loba-besteffort/loba-besteffort.tex
index fd628570de2cd1549a1073d77618b2395f066d16..23fe6ea03ed8b66c4081faa739338686910ed930 100644 (file)
--- a/loba-besteffort/loba-besteffort.tex
+++ b/loba-besteffort/loba-besteffort.tex
@@ -1,72 +1,79 @@
-\documentclass[smallextended]{svjour3}
+\documentclass[preprint]{elsarticle}
+

 \usepackage[utf8]{inputenc}
 \usepackage[T1]{fontenc}
 \usepackage[utf8]{inputenc}
 \usepackage[T1]{fontenc}

-\usepackage{mathptmx}
+
+%\usepackage{newtxtext}
+%\usepackage[cmintegrals]{newtxmath}
+\usepackage{mathptmx,helvet,courier}
+

 \usepackage{amsmath}
 \usepackage{amsmath}

-\usepackage{courier}

 \usepackage{graphicx}
 \usepackage{url}
 \usepackage[ruled,lined]{algorithm2e}
 
 \usepackage{graphicx}
 \usepackage{url}
 \usepackage[ruled,lined]{algorithm2e}
 

-\newcommand{\abs}[1]{\lvert#1\rvert} % \abs{x} -> |x|
-
-\newenvironment{algodata}{%
-  \begin{tabular}[t]{@{}l@{:~}l@{}}}{%
-  \end{tabular}}
-
+%%% Remove this before submission

 \newcommand{\FIXMEmargin}[1]{%
   \marginpar{\textbf{[FIXME]} {\footnotesize #1}}}
 \newcommand{\FIXME}[2][]{%
   \ifx #2\relax\relax \FIXMEmargin{#1}%
   \else \textbf{$\triangleright$\FIXMEmargin{#1}~#2}\fi}
 
 \newcommand{\FIXMEmargin}[1]{%
   \marginpar{\textbf{[FIXME]} {\footnotesize #1}}}
 \newcommand{\FIXME}[2][]{%
   \ifx #2\relax\relax \FIXMEmargin{#1}%
   \else \textbf{$\triangleright$\FIXMEmargin{#1}~#2}\fi}
 

+\newcommand{\abs}[1]{\lvert#1\rvert} % \abs{x} -> |x|
+
+\newenvironment{algodata}{%
+  \begin{tabular}[t]{@{}l@{:~}l@{}}}{%
+  \end{tabular}}
+

 \newcommand{\VAR}[1]{\textit{#1}}
 
 \begin{document}
 
 \newcommand{\VAR}[1]{\textit{#1}}
 
 \begin{document}
 

-\title{Best effort strategy and virtual load
-  for asynchronous iterative load balancing}
+\begin{frontmatter}

 
 

-\author{Raphaël Couturier \and
-        Arnaud Giersch
-}
+\journal{Parallel Computing}

 
 

-\institute{R. Couturier \and A. Giersch \at
-              FEMTO-ST, University of Franche-Comté, Belfort, France \\
-              % Tel.: +123-45-678910\\
-              % Fax: +123-45-678910\\
-              \email{%
-                raphael.couturier@femto-st.fr,
-                arnaud.giersch@femto-st.fr}
-}
+\title{Best effort strategy and virtual load for\\
+  asynchronous iterative load balancing}

 
 

-\maketitle
+\author{Raphaël Couturier}
+\ead{raphael.couturier@femto-st.fr}

 
 

+\author{Arnaud Giersch\corref{cor}}
+\ead{arnaud.giersch@femto-st.fr}

 
 

-\begin{abstract}
-
-Most of the  time, asynchronous load balancing algorithms  have extensively been
-studied in a theoretical point  of view. The Bertsekas and Tsitsiklis'
-algorithm~\cite[section~7.4]{bertsekas+tsitsiklis.1997.parallel}
-is certainly  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 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 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 simulator
-based on SimGrid which allowed us to conduct many experiments.
+\address{FEMTO-ST, University of Franche-Comté\\
+ 19 avenue du Maréchal Juin, BP 527, 90016 Belfort cedex, France}

 
 

+\cortext[cor]{Corresponding author.}

 
 

+\begin{abstract}
+  Most of the time, asynchronous load balancing algorithms have extensively been
+  studied in a theoretical point of view. The Bertsekas and Tsitsiklis'
+  algorithm~\cite[section~7.4]{bertsekas+tsitsiklis.1997.parallel} is certainly
+  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
+  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
+  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
+  simulator based on SimGrid which allowed us to conduct many experiments.

 \end{abstract}
 
 \end{abstract}
 

+% \begin{keywords}
+%   %% keywords here, in the form: keyword \sep keyword
+% \end{keywords}
+
+\end{frontmatter}
+

 \section{Introduction}
 
 Load  balancing algorithms  are  extensively used  in  parallel and  distributed
 \section{Introduction}
 
 Load  balancing algorithms  are  extensively used  in  parallel and  distributed


@@ -124,20 +131,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.
 
 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}
 
 
 
 \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
 
 In  order  prove  the  convergence  of  asynchronous  iterative  load  balancing
 Bertsekas         and        Tsitsiklis         proposed         a        model


@@ -160,7 +168,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)
 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}
 
 
 \end{equation}
 
 


@@ -183,9 +191,9 @@ x_2(t)=100   \\
 x_3(t)=99.99\\
  x_3^2(t)=99.99\\
 \end{eqnarray*}
 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.
 $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.


@@ -199,7 +207,7 @@ that they are sufficient to ensure the convergence of the load-balancing
 algorithm.
 
 \section{Best effort strategy}
 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,
 
 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,


@@ -271,12 +279,12 @@ 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
 
 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}
 
 \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
 
 Another load balancing strategy, working under the same conditions, was
 previously developed by Bahi, Giersch, and Makhoul in


@@ -297,9 +305,9 @@ neighbor.
 
 
 \section{Virtual load}
 
 
 \section{Virtual load}

-\label{Virtual load}
+\label{sec.virtual-load}

 
 

-In this section,  we present the concept of \texttt{virtual  load}.  In order to
+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,
 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,


@@ -309,7 +317,7 @@ Load information  message are really  short, consequently they will  be received
 very quickly.  In opposition, load  balancing messages are often bigger and thus
 require more time to be transferred.
 
 very quickly.  In opposition, load  balancing messages are often bigger and thus
 require more time to be transferred.
 

-The  concept  of  \texttt{virtual load}  allows  a  node  that received  a  load
+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
 neighbors. In fact,  a node that receives a load  information message knows that
 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
 neighbors. In fact,  a node that receives a load  information message knows that


@@ -327,7 +335,7 @@ information of the load they will receive, so they can take in into account.
 \FIXME{describe integer mode}
 
 \section{Simulations}
 \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
 
 In order to test and validate our approaches, we wrote a simulator
 using the SimGrid


@@ -338,13 +346,12 @@ 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.
 
 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}
 
 \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
 
 In the simulation model the processors exchange messages which are of
 two kinds.  First, there are \emph{control messages} which only carry


@@ -481,10 +488,11 @@ iteratively runs the following operations:
 \end{algorithm}
 
 \paragraph{}\FIXME{ajouter des détails sur la gestion de la charge virtuelle ?
 \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}
 
 \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
 
 In order to assess the performances of our algorithms, we ran our
 simulator with various parameters, and extracted several metrics, that


@@ -592,6 +600,7 @@ Anyway, all these the experiments represent more than 240 hours of computing
 time.
 
 \subsubsection{Metrics}
 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
 
 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


@@ -633,7 +642,7 @@ With these constraints in mind, we defined the following metrics:
 
 
 \subsection{Experimental results}
 
 
 \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.
 
 In this section, the results for the different simulations will be presented,
 and we'll try to explain our observations.


@@ -650,7 +659,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.


@@ -689,7 +698,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.
 


@@ -697,62 +706,55 @@ 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.
 
 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.
+
+\FIXME{annoncer le plan de la suite}

 
 

-each bar -> times for an algorithm
-recall the different times
-no bar -> not run or did not converge in allocated time
+\subsubsection{The \emph{best effort} strategy}

 
 

-repeated for the different platform sizes.
+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, annoncer le plan de la suite}
+\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}
 
 
 \subsubsection{With the virtual load extension}
 

+\FIXME{valider l'extension virtual load -> c'est 'achement bien}
+

 \subsubsection{The $k$ parameter}
 
 \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}
 
 
 \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?}
 
 \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
 \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 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 makhoul? se fait battre sur les grosses plateformes

-

 \item taille de plateforme?
 \item taille de plateforme?

-

 \item ratio comp/comm?
 \item ratio comp/comm?

-

 \item option $k$? peut-être intéressant sur des plateformes fortement interconnectées (hypercube)
 \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 volume de comm? souvent, besteffort/plain en fait plus. pourquoi?

-

 \item répartition initiale de la charge ?
 \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.
 \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 ? :
 
 
 % On veut montrer quoi ? :
 


@@ -779,20 +781,19 @@ 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!}
 

-\begin{acknowledgements}
-  Computations have been performed on the supercomputer facilities of
-  the Mésocentre de calcul de Franche-Comté.
-\end{acknowledgements}
+\section*{Acknowledgments}

 
 

-\FIXME{find and add more references}
-\bibliographystyle{spmpsci}
+Computations have been performed on the supercomputer facilities of the
+Mésocentre de calcul de Franche-Comté.
+
+\bibliographystyle{elsarticle-num}

 \bibliography{biblio}
 \bibliography{biblio}

+\FIXME{find and add more references}

 
 \end{document}
 
 
 \end{document}
 


@@ -803,7 +804,8 @@ On constate quoi (vérifier avec les chiffres)?
 %%% 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