X-Git-Url: https://bilbo.iut-bm.univ-fcomte.fr/and/gitweb/loba-papers.git/blobdiff_plain/9ab6d3b1551a28b58f5df7ea6346f08eafb814e9..3c2f33b63a5a1a5dd563955b54c361efaa0d2690:/supercomp11/supercomp11.tex?ds=sidebyside diff --git a/supercomp11/supercomp11.tex b/supercomp11/supercomp11.tex index b321468..a7bc09a 100644 --- a/supercomp11/supercomp11.tex +++ b/supercomp11/supercomp11.tex @@ -364,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. -\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} @@ -395,9 +407,10 @@ the data messages. The buffers are implemented with a lock-free FIFO } \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; @@ -436,10 +449,11 @@ example, when the current load is near zero). } \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; @@ -466,19 +480,7 @@ runs the following operations: } \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} @@ -488,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. -\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 @@ -507,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. -\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 @@ -520,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}. -\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 @@ -546,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. -\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 @@ -589,7 +591,7 @@ 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 @@ -630,9 +632,67 @@ With these constraints in mind, we defined the following metrics: \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. + +\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} @@ -657,33 +717,31 @@ On constate quoi (vérifier avec les chiffres)? \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}