X-Git-Url: https://bilbo.iut-bm.univ-fcomte.fr/and/gitweb/loba-papers.git/blobdiff_plain/6a2c40b9574f7d9550ccfff4a3def72d19c59f7c..5432212c4bb6f191fc44cb3d0e4b1e66aa3dd9e8:/loba-besteffort/loba-besteffort.tex

diff --git a/loba-besteffort/loba-besteffort.tex b/loba-besteffort/loba-besteffort.tex
index fd62857..44a6853 100644
--- a/loba-besteffort/loba-besteffort.tex
+++ b/loba-besteffort/loba-besteffort.tex
@@ -1,72 +1,82 @@
-\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
@@ -124,20 +134,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
@@ -160,7 +171,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}
 
 
@@ -183,9 +194,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.
@@ -199,7 +210,7 @@ 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,
@@ -271,12 +282,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
-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
@@ -297,9 +308,9 @@ neighbor.
 
 
 \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,
@@ -309,7 +320,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.
 
-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
@@ -327,7 +338,7 @@ 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
@@ -338,13 +349,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.
 
-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
@@ -481,10 +491,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
@@ -592,6 +603,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
@@ -633,7 +645,7 @@ 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.
@@ -697,13 +709,13 @@ 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}
-
-each bar -> times for an algorithm
-recall the different times
-no bar -> not run or did not converge in allocated time
-
-repeated for the different platform sizes.
+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{donner les premiÃ¨res conclusions, annoncer le plan de la suite}
 
@@ -785,14 +797,14 @@ On constate quoi (vÃ©rifier avec les chiffres)?
 
 \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}
 
