wip.

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

diff --git a/supercomp11/supercomp11.tex b/supercomp11/supercomp11.tex
index 741aa267d9a0e7ab788f9932f3824d469cd36169..a7bc09a5ad9d58c58ad6fc8dec1c0e1df654cc72 100644 (file)
--- a/supercomp11/supercomp11.tex
+++ b/supercomp11/supercomp11.tex
@@ -88,7 +88,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}.

-\FIXME{Rajouter des choses ici.}
+\FIXME{Rajouter des choses ici.  Lesquelles ?}

 
 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


@@ -189,11 +189,14 @@ $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.}
+
+Nevertheless, we conjecture that such a weaker condition exists.  In fact, we
+have never seen any scenario that is not leading to convergence, even with
+load-balancing strategies that are not exactly fulfilling these two conditions.
+
+It may be the subject of future work to express weaker conditions, and to prove
+that they are sufficient to ensure the convergence of the load-balancing
+algorithm.

 
 \section{Best effort strategy}
 \label{Best-effort}
 
 \section{Best effort strategy}
 \label{Best-effort}


@@ -361,13 +364,25 @@ During the simulation, each processor concurrently runs three threads:
 a \emph{receiving thread}, a \emph{computing thread}, and a
 \emph{load-balancing thread}, which we will briefly describe now.
 
 a \emph{receiving thread}, a \emph{computing thread}, and a
 \emph{load-balancing thread}, which we will briefly describe now.
 

-\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.  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
+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}.
+
+\subsubsection{Receiving thread}
+
+The receiving thread is in charge of waiting for messages to come, either on the
+control channel, or on the 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}
 \cite{sutter.2008.writing} to avoid contention between the threads.
 
 \begin{algorithm}


@@ -392,9 +407,10 @@ the data messages.  The buffers are implemented with a lock-free FIFO
   }
 \end{algorithm}
 
   }
 \end{algorithm}
 

-\paragraph{Computing thread} The computing thread is in charge of the
-real load management.  As exposed in Algorithm~\ref{algo.comp}, it
-iteratively runs the following operations:
+\subsubsection{Computing thread}
+
+The computing thread is in charge of the 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;
 \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;


@@ -433,10 +449,11 @@ example, when the current load is near zero).
   }
 \end{algorithm}
 
   }
 \end{algorithm}
 

-\paragraph{Load-balancing thread} The load-balancing thread is in
-charge of running the load-balancing algorithm, and exchange the
-control messages.  As shown in Algorithm~\ref{algo.lb}, it iteratively
-runs the following operations:
+\subsubsection{Load-balancing thread}
+
+The load-balancing thread is in charge of running the load-balancing algorithm,
+and exchange the 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;


@@ -463,19 +480,8 @@ runs the following operations:
   }
 \end{algorithm}
 
   }
 \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 ?}
+\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}}

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


@@ -484,7 +490,7 @@ 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.
 
 simulator with various parameters, and extracted several metrics, that
 we will describe in this section.
 

-\paragraph{Load balancing strategies}
+\subsubsection{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
 
 Several load balancing strategies were compared.  We ran the experiments with
 the \emph{Best effort}, and with the \emph{Makhoul} strategies.  \emph{Best


@@ -503,7 +509,7 @@ To summarize the different load balancing strategies, we have:
 %
 This gives us as many as $4\times 2\times 2 = 16$ different strategies.
 
 %
 This gives us as many as $4\times 2\times 2 = 16$ different strategies.
 

-\paragraph{End of the simulation}
+\subsubsection{End of the simulation}

 
 The simulations were run until the load was nearly balanced among the
 participating nodes.  More precisely the simulation stops when each node holds
 
 The simulations were run until the load was nearly balanced among the
 participating nodes.  More precisely the simulation stops when each node holds


@@ -516,7 +522,7 @@ real application we would have chosen a decentralized convergence detection
 algorithm, like the one described by Bahi, Contassot-Vivier, Couturier, and
 Vernier in \cite{10.1109/TPDS.2005.2}.
 
 algorithm, like the one described by Bahi, Contassot-Vivier, Couturier, and
 Vernier in \cite{10.1109/TPDS.2005.2}.
 

-\paragraph{Platforms}
+\subsubsection{Platforms}

 
 In order to show the behavior of the different strategies in different
 settings, we simulated the executions on two sorts of platforms.  These two
 
 In order to show the behavior of the different strategies in different
 settings, we simulated the executions on two sorts of platforms.  These two


@@ -542,7 +548,7 @@ processor speeds were normalized, and we arbitrarily chose to fix them to
 Then we derived each sort of platform with four different number of computing
 nodes: 16, 64, 256, and 1024 nodes.
 
 Then we derived each sort of platform with four different number of computing
 nodes: 16, 64, 256, and 1024 nodes.
 

-\paragraph{Configurations}
+\subsubsection{Configurations}

 
 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 distributed processes of the application were then logically organized along
 three possible topologies: a line, a torus or an hypercube.  We ran tests where


@@ -585,7 +591,7 @@ time.
 Anyway, all these the experiments represent more than 240 hours of computing
 time.
 
 Anyway, all these the experiments represent more than 240 hours of computing
 time.
 

-\paragraph{Metrics}
+\subsubsection{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


@@ -626,44 +632,128 @@ With these constraints in mind, we defined the following metrics:
 \end{description}
 
 
 \end{description}
 
 

-\subsection{Validation of our approaches}
+\subsection{Experimental results}

 \label{Results}
 
 \label{Results}
 

+In this section, the results for the different simulations will be presented,
+and we'll try to explain our observations.
+
+\FIXME{cluster vs. grid : cluster légèrement plus rapide, mais c'est tout -> chose to give results for grid only.}
+
+\FIXME{explain how to read the graphs}
+
+\subsubsection{Main results}
+
+\begin{figure}
+  \centering
+  \includegraphics[width=.5\linewidth]{data/graphs/R1-1:10-grid-line}%
+  \includegraphics[width=.5\linewidth]{data/graphs/R1-10:1-grid-line}
+  \includegraphics[width=.5\linewidth]{data/graphs/R1-1:10-grid-torus}%
+  \includegraphics[width=.5\linewidth]{data/graphs/R1-10:1-grid-torus}
+  \includegraphics[width=.5\linewidth]{data/graphs/R1-1:10-grid-hcube}%
+  \includegraphics[width=.5\linewidth]{data/graphs/R1-10:1-grid-hcube}
+  \caption{Real mode, initially on an only mode, comp/comm ratio = 1/10 (left), or 10/1 (right).}
+  \label{fig.results1}
+\end{figure}
+
+On fig.~\ref{fig.results1}, \dots
+
+\subsubsection{With the virtual load extension}
+
+\subsubsection{The $k$ parameter}
+
+\subsubsection{With an initial random repartition,  and larger platforms}
+
+\begin{figure}
+  \centering
+  \includegraphics[width=.5\linewidth]{data/graphs/RN-1:10-grid-line}%
+  \includegraphics[width=.5\linewidth]{data/graphs/RN-10:1-grid-line}
+  \includegraphics[width=.5\linewidth]{data/graphs/RN-1:10-grid-torus}%
+  \includegraphics[width=.5\linewidth]{data/graphs/RN-10:1-grid-torus}
+  \includegraphics[width=.5\linewidth]{data/graphs/RN-1:10-grid-hcube}%
+  \includegraphics[width=.5\linewidth]{data/graphs/RN-10:1-grid-hcube}
+  \caption{Real mode, random initial distribution, comp/comm ratio = 1/10 (left), or 10/1 (right).}
+  \label{fig.resultsN}
+\end{figure}
+
+\subsubsection{With integer load}
+
+\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)?
+\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 makhoul? se fait battre sur les grosses plateformes
+
+\item taille de plateforme?
+
+\item ratio comp/comm?
+
+\item option $k$? peut-être intéressant sur des plateformes fortement interconnectées (hypercube)

 
 

-On veut montrer quoi ? :
+\item volume de comm? souvent, besteffort/plain en fait plus. pourquoi?

 
 

-1) best plus rapide que les autres (simple, makhoul)
-2) avantage virtual load
+\item répartition initiale de la charge ?

 
 

-Est ce qu'on peut trouver des contre exemple?
-Topologies variées
+\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}
+
+% On veut montrer quoi ? :
+
+% 1) best plus rapide que les autres (simple, makhoul)
+% 2) avantage virtual load

 
 

-Simulation avec temps définies assez long et on mesure la qualité avec : volume de calcul effectué, volume de données échangées
-Mais aussi simulation avec temps court qui montre que seul best converge
+% Est ce qu'on peut trouver des contre exemple?
+% Topologies variées

 
 
 
 

-Expés avec ratio calcul/comm rapide et lent
+% Simulation avec temps définies assez long et on mesure la qualité avec : volume de calcul effectué, volume de données échangées
+% Mais aussi simulation avec temps court qui montre que seul best converge

 
 

-Quelques expés avec charge initiale aléatoire plutot que sur le premier proc
+% Expés avec ratio calcul/comm rapide et lent

 
 

-Cadre processeurs homogènes
+% Quelques expés avec charge initiale aléatoire plutot que sur le premier proc

 
 

-Topologies statiques
+% Cadre processeurs homogènes

 
 

-On ne tient pas compte de la vitesse des liens donc on la considère homogène
+% Topologies statiques

 
 

-Prendre un réseau hétérogène et rendre processeur homogène
+% On ne tient pas compte de la vitesse des liens donc on la considère 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}
 
 
 \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}
 
 \begin{acknowledgements}
   Computations have been performed on the supercomputer facilities of
   the Mésocentre de calcul de Franche-Comté.
 \end{acknowledgements}
 

+\FIXME{find and add more references}

 \bibliographystyle{spmpsci}
 \bibliography{biblio}
 
 \bibliographystyle{spmpsci}
 \bibliography{biblio}
 


@@ -678,4 +768,5 @@ Taille : 10 100 très gros
 
 % LocalWords:  Raphaël Couturier Arnaud Giersch Abderrahmane Sider Franche ij
 % LocalWords:  Bertsekas Tsitsiklis SimGrid DASUD Comté Béjaïa asynchronism ji
 
 % 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
+% 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