wip

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

diff --git a/supercomp11/supercomp11.tex b/supercomp11/supercomp11.tex
index 472a724e88be8487149a813a776731b7585b11b1..3a1ec31ce717a0b652e07596b528264e97c93ab2 100644 (file)
--- a/supercomp11/supercomp11.tex
+++ b/supercomp11/supercomp11.tex
@@ -5,6 +5,7 @@
 \usepackage{amsmath}
 \usepackage{courier}
 \usepackage{graphicx}
 \usepackage{amsmath}
 \usepackage{courier}
 \usepackage{graphicx}

+\usepackage{url}

 \usepackage[ruled,lined]{algorithm2e}
 
 \newcommand{\abs}[1]{\lvert#1\rvert} % \abs{x} -> |x|
 \usepackage[ruled,lined]{algorithm2e}
 
 \newcommand{\abs}[1]{\lvert#1\rvert} % \abs{x} -> |x|


@@ -13,6 +14,9 @@
   \begin{tabular}[t]{@{}l@{:~}l@{}}}{%
   \end{tabular}}
 
   \begin{tabular}[t]{@{}l@{:~}l@{}}}{%
   \end{tabular}}
 

+\newcommand{\FIXME}[1]{%
+  \textbf{$\triangleright$\marginpar{\textbf{[FIXME]}}~#1}}
+

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


@@ -21,8 +25,7 @@
   for asynchronous iterative load balancing}
 
 \author{Raphaël Couturier \and
   for asynchronous iterative load balancing}
 
 \author{Raphaël Couturier \and

-        Arnaud Giersch \and
-        Abderrahmane Sider
+        Arnaud Giersch

 }
 
 \institute{R. Couturier \and A. Giersch \at
 }
 
 \institute{R. Couturier \and A. Giersch \at


@@ -32,10 +35,6 @@
               \email{%
                 raphael.couturier@univ-fcomte.fr,
                 arnaud.giersch@univ-fcomte.fr}
               \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}

 }
 
 \maketitle
 }
 
 \maketitle


@@ -86,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}.
 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
 
 Although  the Bertsekas  and Tsitsiklis'  algorithm describes  the  condition to
 ensure the convergence,  there is no indication or  strategy to really implement


@@ -98,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
 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
 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


@@ -122,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.
 
 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.

 
 
 
 
 
 


@@ -187,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.
 $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}
 
 \section{Best effort strategy}
 \label{Best-effort}


@@ -243,24 +246,28 @@ he proceeds as following.
   \end{equation*}
 \end{enumerate}
 
   \end{equation*}
 \end{enumerate}
 

+\FIXME{describe parameter $k$}
+

 \section{Other strategies}
 \label{Other}
 
 \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
 
 \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


@@ -298,7 +305,9 @@ 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.
 
 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.
 

-\textbf{Question} Est ce qu'on donne l'algo avec virtual load?
+\FIXME{Est ce qu'on donne l'algo avec virtual load?}
+
+\FIXME{describe integer mode}

 
 \section{Simulations}
 \label{Simulations}
 
 \section{Simulations}
 \label{Simulations}


@@ -412,7 +421,8 @@ example, when the current load is near zero).
 
 \paragraph{Load-balancing thread} The load-balancing thread is in
 charge of running the load-balancing algorithm, and exchange the
 
 \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;
 \begin{itemize}
 \item get the control messages that were received from the neighbors;
 \item run the load-balancing algorithm;


@@ -442,20 +452,52 @@ control messages.  It iteratively runs the following operations:
 \paragraph{}
 For the sake of simplicity, a few details were voluntary omitted from
 these descriptions.  For an exhaustive presentation, we refer to the
 \paragraph{}
 For the sake of simplicity, a few details were voluntary omitted from
 these descriptions.  For an exhaustive presentation, we refer to the

-actual code that was used for the experiments, and which is
-available at \textbf{FIXME URL}.
+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}.

 
 

-\textbf{FIXME: ajouter des détails sur la gestion de la charge virtuelle ?}
+\FIXME{ajouter des détails sur la gestion de la charge virtuelle ?}

 
 \subsection{Experimental contexts}
 \label{Contexts}
 
 
 \subsection{Experimental contexts}
 \label{Contexts}
 

-\textbf{FIXME once the experimentation is done!}
+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.  Overall, the experiments represent
+more than 240 hours of computing time.
+
+\paragraph{Load balancing strategies}
+
+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.
+This gives us as many as 32 different strategies.
+
+\paragraph{Configurations}
+\begin{description}
+\item[\textbf{platforms}] homogeneous (cluster); heterogeneous (subset
+  of Grid5000)
+\item[\textbf{platform size}] platforms with 16, 64, 256, and 1024 nodes
+\item[\textbf{topologies}] line; torus; hypercube
+\item[\textbf{initial load distribution}] initially on a only node;
+  initially on all nodes
+\item[\textbf{comp/comm ratio}] $10/1$, $1/1$, $1/10$
+\end{description}
+
+\paragraph{Metrics}
+

 \begin{description}
 \begin{description}

-\item[platforms] homogeneous ; heterogeneous generated with the SIMULACRUM tool~\cite{QUINSON:2010:INRIA-00502839:1}
-\item[topologies]
-\item[algorithms]
-\item[etc.]
+\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}
 \end{description}
 
 \subsection{Validation of our approaches}


@@ -491,6 +533,10 @@ Taille : 10 100 très gros
 
 \section{Conclusion and perspectives}
 
 
 \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}
 
 \bibliographystyle{spmpsci}
 \bibliography{biblio}


@@ -500,6 +546,7 @@ Taille : 10 100 très gros
 %%% Local Variables:
 %%% mode: latex
 %%% TeX-master: t
 %%% Local Variables:
 %%% mode: latex
 %%% TeX-master: t

+%%% fill-column: 80

 %%% ispell-local-dictionary: "american"
 %%% End:
 
 %%% ispell-local-dictionary: "american"
 %%% End: