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}
}
\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;
}
\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;
}
\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}
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
%
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
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
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
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
\end{description}
-\subsection{Validation of our approaches}
+\subsection{Experimental results}
\label{Results}
+In this section, the results for the different simulations will be presented,
+and we'll try to explain our observations.
+
+\subsubsection{Cluster vs grid platforms}
+
+As mentioned earlier, we simulated the different algorithms on two kinds of
+physical platforms: clusters and grids. A first observation that we can make,
+is that the graphs we draw from the data have a similar aspect for the two kinds
+of platforms. The only noticeable difference is that the algorithms need a bit
+more time to achieve the convergence on the grid platforms, than on clusters.
+Nevertheless their relative performances remain generally identical.
+
+This suggests that the relative performances of the different strategies are not
+influenced by the characteristics of the physical platform. The differences in
+the convergence times can be explained by the fact that on the grid platforms,
+distant sites are interconnected by links of smaller bandwith.
+
+Therefore, in the following, we'll only discuss the results for the grid
+platforms. The different results are presented on the
+figures~\ref{fig.results1} and~\ref{fig.resultsN}.
+
+\FIXME{explain how to read the graphs}
+ratio 1:1 not given here
+
+\begin{figure*}[p]
+ \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*}
+
+\begin{figure*}[p]
+ \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{Main results}
+
+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}
+
+\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
\end{itemize}
-\begin{itshape}
-On veut montrer quoi ? :
-\FIXME{remove that part}
+% On veut montrer quoi ? :
-1) best plus rapide que les autres (simple, makhoul)
-2) avantage virtual load
+% 1) best plus rapide que les autres (simple, makhoul)
+% 2) avantage virtual load
-Est ce qu'on peut trouver des contre exemple?
-Topologies variées
+% Est ce qu'on peut trouver des contre exemple?
+% Topologies variées
-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
+% 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
-Expés avec ratio calcul/comm rapide et lent
+% Expés avec ratio calcul/comm rapide et lent
-Quelques expés avec charge initiale aléatoire plutot que sur le premier proc
+% Quelques expés avec charge initiale aléatoire plutot que sur le premier proc
-Cadre processeurs homogènes
+% Cadre processeurs homogènes
-Topologies statiques
+% Topologies statiques
-On ne tient pas compte de la vitesse des liens donc on la considère homogène
+% On ne tient pas compte de la vitesse des liens donc on la considère homogène
-Prendre un réseau hétérogène et rendre processeur homogène
+% Prendre un réseau hétérogène et rendre processeur homogène
-Taille : 10 100 très gros
+% Taille : 10 100 très gros
\end{itshape}
\section{Conclusion and perspectives}
