-\documentclass[smallextended]{svjour3}
+\documentclass[preprint]{elsarticle}
+
\usepackage[utf8]{inputenc}
\usepackage[T1]{fontenc}
-\usepackage{mathptmx}
+
+%\usepackage{newtxtext}
+%\usepackage[cmintegrals]{newtxmath}
+\usepackage{mathptmx,helvet,courier}
+
\usepackage{amsmath}
-\usepackage{courier}
\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{\abs}[1]{\lvert#1\rvert} % \abs{x} -> |x|
+
+\newenvironment{algodata}{%
+ \begin{tabular}[t]{@{}l@{:~}l@{}}}{%
+ \end{tabular}}
+
\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 de Maréchal Juin, BP 527, 90016 Belfort cedex , France\\
+ % Tel.: +123-45-678910\\
+ % Fax: +123-45-678910\\
+}
+\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}
+% \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
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
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}
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.
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,
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
\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,
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
\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
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
\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
\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.
\FIXME{conclude!}
-\begin{acknowledgements}
- Computations have been performed on the supercomputer facilities of
- the Mésocentre de calcul de Franche-Comté.
-\end{acknowledgements}
+\section*{Acknowledgements}
-\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}
+\FIXME{find and add more references}
\end{document}
