X-Git-Url: https://bilbo.iut-bm.univ-fcomte.fr/and/gitweb/loba-papers.git/blobdiff_plain/bcf6cef9fa1df52f632849a68fc08e41f6163bb1..3a7899b35652f292727ce064ddf00c71717863be:/supercomp11/supercomp11.tex?ds=sidebyside

diff --git a/supercomp11/supercomp11.tex b/supercomp11/supercomp11.tex
index 81ee704..01ca4f7 100644
--- a/supercomp11/supercomp11.tex
+++ b/supercomp11/supercomp11.tex
@@ -5,30 +5,36 @@
 \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}}
+
+\newcommand{\FIXME}[1]{%
+  \textbf{$\triangleright$\marginpar{\textbf{[FIXME]}}~#1}}
+
+\newcommand{\VAR}[1]{\textit{#1}}
+
 \begin{document}
 
 \title{Best effort strategy and virtual load
   for asynchronous iterative load balancing}
 
 \author{RaphaÃ«l Couturier \and
-        Arnaud Giersch \and
-        Abderrahmane Sider
+        Arnaud Giersch
 }
 
 \institute{R. Couturier \and A. Giersch \at
-              LIFC, University of Franche-ComtÃ©, Belfort, France \\
+              FEMTO-ST, University of Franche-ComtÃ©, Belfort, France \\
               % Tel.: +123-45-678910\\
               % Fax: +123-45-678910\\
               \email{%
-                raphael.couturier@univ-fcomte.fr,
-                arnaud.giersch@univ-fcomte.fr}
-           \and
-           A. Sider \at
-              University of BÃ©jaÃ¯a, BÃ©jaÃ¯a, Algeria \\
-              \email{ar.sider@univ-bejaia.dz}
+                raphael.couturier@femto-st.fr,
+                arnaud.giersch@femto-st.fr}
 }
 
 \maketitle
@@ -49,7 +55,7 @@ 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 an load
+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
@@ -79,7 +85,7 @@ been extended by many authors. For example, CortÃ©s et al., with
 DASUD~\cite{cortes+ripoll+cedo+al.2002.asynchronous}, propose a
 version working with integer load.  This work was later generalized by
 the same authors in \cite{cedo+cortes+ripoll+al.2007.convergence}.
-{\bf Rajouter des choses ici}.
+\FIXME{Rajouter des choses ici.}
 
 Although  the Bertsekas  and Tsitsiklis'  algorithm describes  the  condition to
 ensure the convergence,  there is no indication or  strategy to really implement
@@ -91,7 +97,7 @@ ensuring that all the nodes concerned  by the load balancing phase have the same
 amount of  load.  Moreover, when real asynchronous  applications are considered,
 using  asynchronous   load  balancing   algorithms  can  reduce   the  execution
 times. Most of the times, it is simpler to distinguish load information messages
-from  data  migration  messages.  Formers  ones  allows  a  node to  inform  its
+from  data  migration  messages.  Former  ones  allows  a  node to  inform  its
 neighbors of its  current load. These messages are very small,  they can be sent
 quite often.  For example, if an  computing iteration takes  a significant times
 (ranging from seconds to minutes), it is possible to send a new load information
@@ -115,15 +121,15 @@ 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. 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{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.
 
 
 
@@ -180,7 +186,11 @@ $3$.   If  it  sends  load  to  processor $1$  it  will  not  satisfy  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.
-
+%
+\FIXME{Develop: We have the feeling that such a weaker condition
+  exists, because (it's not a proof, but) we have never seen any
+  scenario that is not leading to convergence, even with LB-strategies
+  that are not fulfilling these two conditions.}
 
 \section{Best effort strategy}
 \label{Best-effort}
@@ -236,24 +246,28 @@ he proceeds as following.
   \end{equation*}
 \end{enumerate}
 
+\FIXME{describe parameter $k$}
+
 \section{Other strategies}
 \label{Other}
 
-\textbf{Question} faut-il dÃ©crire les stratÃ©gies makhoul et simple ?
+\FIXME{RÃ©Ã©crire en angliche.}
 
-\paragraph{simple} Tentative de respecter simplement les conditions de Bertsekas.
-Parmi les voisins moins chargÃ©s que soi, on sÃ©lectionne :
-\begin{itemize}
-\item un des moins chargÃ©s (vmin) ;
-\item un des plus chargÃ©s (vmax),
-\end{itemize}
-puis on Ã©quilibre avec vmin en s'assurant que notre charge reste
-toujours supÃ©rieure Ã  celle de vmin et Ã  celle de vmax.
+% \FIXME{faut-il dÃ©crire les stratÃ©gies makhoul et simple ?}
 
-On envoie donc (avec "self" pour soi-mÃªme) :
-\[
-    \min\left(\frac{load(self) - load(vmin)}{2}, load(self) - load(vmax)\right)
-\]
+% \paragraph{simple} Tentative de respecter simplement les conditions de Bertsekas.
+% Parmi les voisins moins chargÃ©s que soi, on sÃ©lectionne :
+% \begin{itemize}
+% \item un des moins chargÃ©s (vmin) ;
+% \item un des plus chargÃ©s (vmax),
+% \end{itemize}
+% puis on Ã©quilibre avec vmin en s'assurant que notre charge reste
+% toujours supÃ©rieure Ã  celle de vmin et Ã  celle de vmax.
+
+% On envoie donc (avec "self" pour soi-mÃªme) :
+% \[
+%     \min\left(\frac{load(self) - load(vmin)}{2}, load(self) - load(vmax)\right)
+% \]
 
 \paragraph{makhoul} Ordonne les voisins du moins chargÃ© au plus chargÃ©
 puis calcule les diffÃ©rences de charge entre soi-mÃªme et chacun des
@@ -268,6 +282,33 @@ C'est l'algorithme~2 dans~\cite{bahi+giersch+makhoul.2008.scalable}.
 \section{Virtual load}
 \label{Virtual load}
 
+In this section,  we present the concept of \texttt{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,
+can first send  a load information message containing the load  it will send and
+then it can send the load  balancing message containing data  to be transferred.
+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
+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
+later it  will receive the  corresponding load balancing message  containing the
+corresponding data.  So  if this node detects it is too  loaded compared to some
+of its neighbors  and if it has enough  load (real load), then it  can send more
+load  to  some of  its  neighbors  without waiting  the  reception  of the  load
+balancing message.
+
+Doing  this, we  can  expect a  faster  convergence since  nodes  have a  faster
+information of the load they will receive, so they can take in into account.
+
+\FIXME{Est ce qu'on donne l'algo avec virtual load?}
+
+\FIXME{describe integer mode}
+
 \section{Simulations}
 \label{Simulations}
 
@@ -281,8 +322,9 @@ 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}), then the results of the simulations are presented in
-section~\ref{Results}.
+  model}), and the experimental contexts are described in
+section~\ref{Contexts}.  Then the results of the simulations are
+presented in section~\ref{Results}.
 
 \subsection{Simulation model}
 \label{Sim model}
@@ -307,14 +349,38 @@ a \emph{receiving thread}, a \emph{computing thread}, and a
 
 \paragraph{Receiving thread} The receiving thread is in charge of
 waiting for messages to come, either on the control channel, or on the
-data channel.  When a message is received, it is pushed in a buffer of
+data channel.  Its behavior is sketched by Algorithm~\ref{algo.recv}.
+When a message is received, it is pushed in a buffer of
 received message, to be later consumed by one of the other threads.
 There are two such buffers, one for the control messages, and one for
 the data messages.  The buffers are implemented with a lock-free FIFO
 \cite{sutter.2008.writing} to avoid contention between the threads.
 
+\begin{algorithm}
+  \caption{Receiving thread}
+  \label{algo.recv}
+  \KwData{
+    \begin{algodata}
+      \VAR{ctrl\_chan}, \VAR{data\_chan}
+      & communication channels (control and data) \\
+      \VAR{ctrl\_fifo}, \VAR{data\_fifo}
+      & buffers of received messages (control and data) \\
+    \end{algodata}}
+  \While{true}{%
+    wait for a message to be available on either \VAR{ctrl\_chan},
+    or \VAR{data\_chan}\;
+    \If{a message is available on \VAR{ctrl\_chan}}{%
+      get the message from \VAR{ctrl\_chan}, and push it into \VAR{ctrl\_fifo}\;
+    }
+    \If{a message is available on \VAR{data\_chan}}{%
+      get the message from \VAR{data\_chan}, and push it into \VAR{data\_fifo}\;
+    }
+  }
+\end{algorithm}
+
 \paragraph{Computing thread} The computing thread is in charge of the
-real load management.  It iteratively runs the following operations:
+real load management.  As exposed in Algorithm~\ref{algo.comp}, it
+iteratively runs the following operations:
 \begin{itemize}
 \item if some load was received from the neighbors, get it;
 \item if there is some load to send to the neighbors, send it;
@@ -323,11 +389,40 @@ real load management.  It iteratively runs the following operations:
 \end{itemize}
 Practically, after the computation, the computing thread waits for a
 small amount of time if the iterations are looping too fast (for
-example, when the current load is zero).
+example, when the current load is near zero).
+
+\begin{algorithm}
+  \caption{Computing thread}
+  \label{algo.comp}
+  \KwData{
+    \begin{algodata}
+      \VAR{data\_fifo} & buffer of received data messages \\
+      \VAR{real\_load} & current load \\
+    \end{algodata}}
+  \While{true}{%
+    \If{\VAR{data\_fifo} is empty and $\VAR{real\_load} = 0$}{%
+      wait until a message is pushed into \VAR{data\_fifo}\;
+    }
+    \While{\VAR{data\_fifo} is not empty}{%
+      pop a message from \VAR{data\_fifo}\;
+      get the load embedded in the message, and add it to \VAR{real\_load}\;
+    }
+    \ForEach{neighbor $n$}{%
+      \If{there is some amount of load $a$ to send to $n$}{%
+        send $a$ units of load to $n$, and subtract it from \VAR{real\_load}\;
+      }
+    }
+    \If{$\VAR{real\_load} > 0.0$}{
+      simulate some computation, whose duration is function of \VAR{real\_load}\;
+      ensure that the main loop does not iterate too fast\;
+    }
+  }
+\end{algorithm}
 
 \paragraph{Load-balancing thread} The load-balancing thread is in
 charge of running the load-balancing algorithm, and exchange the
-control messages.  It iteratively runs the following operations:
+control messages.  As shown in Algorithm~\ref{algo.lb}, it iteratively
+runs the following operations:
 \begin{itemize}
 \item get the control messages that were received from the neighbors;
 \item run the load-balancing algorithm;
@@ -337,6 +432,133 @@ control messages.  It iteratively runs the following operations:
   iterate too fast.
 \end{itemize}
 
+\begin{algorithm}
+  \caption{Load-balancing}
+  \label{algo.lb}
+  \While{true}{%
+    \While{\VAR{ctrl\_fifo} is not empty}{%
+      pop a message from \VAR{ctrl\_fifo}\;
+      identify the sender of the message,
+      and update the current knowledge of its load\;
+    }
+    run the load-balancing algorithm to make the decision about load transfers\;
+    \ForEach{neighbor $n$}{%
+      send a control messages to $n$\;
+    }
+    ensure that the main loop does not iterate too fast\;
+  }
+\end{algorithm}
+
+\paragraph{}
+For the sake of simplicity, a few details were voluntary omitted from
+these descriptions.  For an exhaustive presentation, we refer to the
+actual source code that was used for the experiments%
+\footnote{As mentioned before, our simulator relies on the SimGrid
+  framework~\cite{casanova+legrand+quinson.2008.simgrid}.  For the
+  experiments, we used a pre-release of SimGrid 3.7 (Git commit
+  67d62fca5bdee96f590c942b50021cdde5ce0c07, available from
+  \url{https://gforge.inria.fr/scm/?group_id=12})}, and which is
+available at
+\url{http://info.iut-bm.univ-fcomte.fr/staff/giersch/software/loba.tar.gz}.
+
+\FIXME{ajouter des dÃ©tails sur la gestion de la charge virtuelle ?}
+
+\subsection{Experimental contexts}
+\label{Contexts}
+
+In order to assess the performances of our algorithms, we ran our
+simulator with various parameters, and extracted several metrics, that
+we will describe in this section.
+
+\paragraph{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
+  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},
+and with \emph{integer} load.
+
+To summarize the different load balancing strategies, we have:
+\begin{description}
+\item[\textbf{strategies:}] \emph{Makhoul}, or \emph{Best effort} with $k\in
+  \{1,2,4\}$
+\item[\textbf{variants:}] with, or without virtual load
+\item[\textbf{domain:}] real load, or integer load
+\end{description}
+%
+This gives us as many as $4\times 2\times 2 = 16$ different strategies.
+
+
+\paragraph{Configurations}
+
+In order to show the behavior of the different strategies in different
+settings, we simulated the executions on two sorts of platforms.  These two
+sorts of platforms differ by their underlaid network topology.  On the one hand,
+we have homogeneous platforms, modeled as a cluster.  On the other hand, we have
+heterogeneous platforms, modeled as the interconnection of a number of clusters.
+The heterogeneous platform descriptions were created by taking a subset of the
+Grid'5000 infrastructure\footnote{Grid'5000 is a French large scale experimental
+  Grid (see \url{https://www.grid5000.fr/}).}, as described in the platform file
+\texttt{g5k.xml} distributed with SimGrid.  Note that the heterogeneity of the
+platform only comes from the network topology.  The processor speeds, and
+network bandwidths were normalized since our algorithms currently are not aware
+of such heterogeneity.  We arbitrarily chose to fix the processor speed to
+1~GFlop/s, and the network bandwidth to 125~MB/s, with a latency of 50~$\mu$s,
+except for the links between geographically distant sites, where the network
+bandwidth was fixed to 2.25~GB/s, with a latency of 500~$\mu$s.
+
+Then we derived each sort of platform with four different number of computing
+nodes: 16, 64, 256, and 1024 nodes.
+
+The distributed processes of the application were then logically organized along
+three possible topologies: a line, a torus or an hypercube.  We ran tests where
+the total load was initially on an only node (at one end for the line topology),
+and other tests where the load was initially randomly distributed across all
+the participating nodes.
+
+For each of the preceding configuration, we finally had to choose the
+computation and communication costs of a load unit.  We chose them, such as to
+have three different computation over communication cost ratios, and hence model
+three different kinds of applications:
+\begin{itemize}
+\item mainly communicating, with a computation/communication cost ratio of $1/10$;
+\item mainly computing, with a computation/communication cost ratio of $10/1$ ;
+\item balanced, with a computation/communication cost ratio of $1/1$.
+\end{itemize}
+
+To summarize the various configurations, we have:
+\begin{description}
+\item[\textbf{platforms:}] homogeneous (cluster), or heterogeneous (subset of
+  Grid'5000)
+\item[\textbf{platform sizes:}] platforms with 16, 64, 256, or 1024 nodes
+\item[\textbf{process topologies:}] line, torus, or hypercube
+\item[\textbf{initial load distribution:}] initially on a only node, or
+  initially randomly distributed over all nodes
+\item[\textbf{computation/communication ratio:}] $10/1$, $1/1$, or $1/10$
+\end{description}
+%
+This gives us as many as $2\times 4\times 3\times 2\times 3 = 144$ different
+configurations.
+%
+Combined with the various load balancing strategies, we had $16\times 144 =
+2304$ distinct settings to evaluate.  In fact, as it will be shown later, we
+didn't run all the strategies, nor all the configurations for the bigger
+platforms with 1024 nodes, since to simulations would have run for a too long
+time.
+
+Anyway, all these the experiments represent more than 240 hours of computing
+time.
+
+\paragraph{Metrics}
+
+\begin{description}
+\item[\textbf{average idle time}]
+\item[\textbf{average convergence date}]
+\item[\textbf{maximum convergence date}]
+\item[\textbf{data transfer amount}] relative to the total data amount
+\end{description}
+
 \subsection{Validation of our approaches}
 \label{Results}
 
@@ -370,6 +592,10 @@ Taille : 10 100 trÃ¨s gros
 
 \section{Conclusion and perspectives}
 
+\begin{acknowledgements}
+  Computations have been performed on the supercomputer facilities of
+  the MÃ©socentre de calcul de Franche-ComtÃ©.
+\end{acknowledgements}
 
 \bibliographystyle{spmpsci}
 \bibliography{biblio}
@@ -379,9 +605,10 @@ Taille : 10 100 trÃ¨s gros
 %%% Local Variables:
 %%% mode: latex
 %%% TeX-master: t
+%%% fill-column: 80
 %%% 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
+% LocalWords:  ik isend irecv CortÃ©s et al chan ctrl fifo Makhoul
