From 6f6ebdac1613681f5093eb2303424044b5f60f12 Mon Sep 17 00:00:00 2001 From: Arnaud Giersch Date: Wed, 28 Nov 2012 18:45:17 +0100 Subject: [PATCH] wip --- supercomp11/biblio.bib | 3 +- supercomp11/supercomp11.tex | 60 ++++++++++++++++++++++++------------- 2 files changed, 42 insertions(+), 21 deletions(-) diff --git a/supercomp11/biblio.bib b/supercomp11/biblio.bib index 1e8c121..036695f 100644 --- a/supercomp11/biblio.bib +++ b/supercomp11/biblio.bib @@ -30,7 +30,8 @@ booktitle = {10th IEEE International Conference on Computer Modeling and Simulation}, year = 2008, - month = mar + month = mar, + url = {http://simgrid.gforge.inria.fr/} } @Article{cedo+cortes+ripoll+al.2007.convergence, diff --git a/supercomp11/supercomp11.tex b/supercomp11/supercomp11.tex index 5db76a9..3a1ec31 100644 --- a/supercomp11/supercomp11.tex +++ b/supercomp11/supercomp11.tex @@ -5,6 +5,7 @@ \usepackage{amsmath} \usepackage{courier} \usepackage{graphicx} +\usepackage{url} \usepackage[ruled,lined]{algorithm2e} \newcommand{\abs}[1]{\lvert#1\rvert} % \abs{x} -> |x| @@ -96,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 @@ -120,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. -\FIXME{What about Section~\ref{Other}?} +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. @@ -420,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 -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; @@ -450,14 +452,34 @@ 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 -actual code that was used for the experiments, and which is -available at \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}. \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. 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 @@ -469,13 +491,6 @@ available at \FIXME{URL}. \item[\textbf{comp/comm ratio}] $10/1$, $1/1$, $1/10$ \end{description} -\paragraph{Algorithms} -\begin{description} -\item[\textbf{strategies}] makhoul; besteffort with $k\in \{1,2,4\}$ -\item[\textbf{variants}] with, and without virtual load (bookkeeping) -\item[\textbf{domain}] real load, and integer load -\end{description} - \paragraph{Metrics} \begin{description} @@ -518,6 +533,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} @@ -527,6 +546,7 @@ Taille : 10 100 très gros %%% Local Variables: %%% mode: latex %%% TeX-master: t +%%% fill-column: 80 %%% ispell-local-dictionary: "american" %%% End: -- 2.39.5