X-Git-Url: https://bilbo.iut-bm.univ-fcomte.fr/and/gitweb/loba-papers.git/blobdiff_plain/6a2c40b9574f7d9550ccfff4a3def72d19c59f7c..db33461e614769b3c7c7a8239ebf75a014ec3041:/loba-besteffort/loba-besteffort.tex diff --git a/loba-besteffort/loba-besteffort.tex b/loba-besteffort/loba-besteffort.tex index fd62857..d774cce 100644 --- a/loba-besteffort/loba-besteffort.tex +++ b/loba-besteffort/loba-besteffort.tex @@ -1,72 +1,82 @@ -\documentclass[smallextended]{svjour3} +\documentclass[preprint]{elsarticle} + \usepackage[utf8]{inputenc} \usepackage[T1]{fontenc} -\usepackage{mathptmx} + +%\usepackage{newtxtext} +%\usepackage[cmintegrals]{newtxmath} +\usepackage{mathptmx,helvet,courier} + \usepackage{amsmath} -\usepackage{courier} \usepackage{graphicx} \usepackage{url} \usepackage[ruled,lined]{algorithm2e} -\newcommand{\abs}[1]{\lvert#1\rvert} % \abs{x} -> |x| - -\newenvironment{algodata}{% - \begin{tabular}[t]{@{}l@{:~}l@{}}}{% - \end{tabular}} - +%%% Remove this before submission \newcommand{\FIXMEmargin}[1]{% \marginpar{\textbf{[FIXME]} {\footnotesize #1}}} \newcommand{\FIXME}[2][]{% \ifx #2\relax\relax \FIXMEmargin{#1}% \else \textbf{$\triangleright$\FIXMEmargin{#1}~#2}\fi} +\newcommand{\abs}[1]{\lvert#1\rvert} % \abs{x} -> |x| + +\newenvironment{algodata}{% + \begin{tabular}[t]{@{}l@{:~}l@{}}}{% + \end{tabular}} + \newcommand{\VAR}[1]{\textit{#1}} \begin{document} -\title{Best effort strategy and virtual load - for asynchronous iterative load balancing} +\begin{frontmatter} -\author{Raphaël Couturier \and - Arnaud Giersch -} +\journal{Parallel Computing} -\institute{R. Couturier \and A. Giersch \at - FEMTO-ST, University of Franche-Comté, Belfort, France \\ - % Tel.: +123-45-678910\\ - % Fax: +123-45-678910\\ - \email{% - raphael.couturier@femto-st.fr, - arnaud.giersch@femto-st.fr} -} +\title{Best effort strategy and virtual load for\\ + asynchronous iterative load balancing} -\maketitle +\author{Raphaël Couturier} +\ead{raphael.couturier@femto-st.fr} +\author{Arnaud Giersch\corref{cor}} +\ead{arnaud.giersch@femto-st.fr} -\begin{abstract} - -Most of the time, asynchronous load balancing algorithms have extensively been -studied in a theoretical point of view. The Bertsekas and Tsitsiklis' -algorithm~\cite[section~7.4]{bertsekas+tsitsiklis.1997.parallel} -is certainly the most well known algorithm for which the convergence proof is -given. From a practical point of view, when a node wants to balance a part of -its load to some of its neighbors, the strategy is not described. In this -paper, we propose a strategy called \emph{best effort} which tries to balance -the load of a node to all its less loaded neighbors while ensuring that all the -nodes concerned by the load balancing phase have the same amount of load. -Moreover, asynchronous iterative algorithms in which an asynchronous load -balancing algorithm is implemented most of the time can dissociate messages -concerning load transfers and message concerning load information. In order to -increase the converge of a load balancing algorithm, we propose a simple -heuristic called \emph{virtual load} which allows a node that receives a load -information message to integrate the load that it will receive later in its -load (virtually) and consequently sends a (real) part of its load to some of its -neighbors. In order to validate our approaches, we have defined a simulator -based on SimGrid which allowed us to conduct many experiments. +\address{FEMTO-ST, University of Franche-Comté\\ + 19 avenue de Maréchal Juin, BP 527, 90016 Belfort cedex , France\\ + % Tel.: +123-45-678910\\ + % Fax: +123-45-678910\\ +} +\cortext[cor]{Corresponding author.} +\begin{abstract} + Most of the time, asynchronous load balancing algorithms have extensively been + studied in a theoretical point of view. The Bertsekas and Tsitsiklis' + algorithm~\cite[section~7.4]{bertsekas+tsitsiklis.1997.parallel} is certainly + the most well known algorithm for which the convergence proof is given. From a + practical point of view, when a node wants to balance a part of its load to + some of its neighbors, the strategy is not described. In this paper, we + propose a strategy called \emph{best effort} which tries to balance the load + of a node to all its less loaded neighbors while ensuring that all the nodes + concerned by the load balancing phase have the same amount of load. Moreover, + asynchronous iterative algorithms in which an asynchronous load balancing + algorithm is implemented most of the time can dissociate messages concerning + load transfers and message concerning load information. In order to increase + the converge of a load balancing algorithm, we propose a simple heuristic + called \emph{virtual load} which allows a node that receives a load + information message to integrate the load that it will receive later in its + load (virtually) and consequently sends a (real) part of its load to some of + its neighbors. In order to validate our approaches, we have defined a + simulator based on SimGrid which allowed us to conduct many experiments. \end{abstract} +% \begin{keywords} +% %% keywords here, in the form: keyword \sep keyword +% \end{keywords} + +\end{frontmatter} + \section{Introduction} Load balancing algorithms are extensively used in parallel and distributed @@ -124,20 +134,21 @@ 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. 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. +In the following of this paper, Section~\ref{sec.bt-algo} describes the +Bertsekas and Tsitsiklis' asynchronous load balancing algorithm. Moreover, we +present a possible problem in the convergence conditions. +Section~\ref{sec.besteffort} 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{sec.other}. In +Section~\ref{sec.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{sec.simulations}. Finally we give a +conclusion and some perspectives to this work. \section{Bertsekas and Tsitsiklis' asynchronous load balancing algorithm} -\label{BT algo} +\label{sec.bt-algo} In order prove the convergence of asynchronous iterative load balancing Bertsekas and Tsitsiklis proposed a model @@ -160,7 +171,7 @@ amount of load received by processor $j$ from processor $i$ at time $t$. Then the amount of load of processor $i$ at time $t+1$ is given by: \begin{equation} x_i(t+1)=x_i(t)-\sum_{j\in V(i)} s_{ij}(t) + \sum_{j\in V(i)} r_{ji}(t) -\label{eq:ping-pong} +\label{eq.ping-pong} \end{equation} @@ -183,9 +194,9 @@ x_2(t)=100 \\ x_3(t)=99.99\\ x_3^2(t)=99.99\\ \end{eqnarray*} -In this case, processor $2$ can either sends load to processor $1$ or processor -$3$. If it sends load to processor $1$ it will not satisfy condition -(\ref{eq:ping-pong}) because after the sending it will be less loaded that +In this case, processor $2$ can either sends load to processor $1$ or processor +$3$. If it sends load to processor $1$ it will not satisfy condition +(\ref{eq.ping-pong}) because after the sending it will be less loaded that $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. @@ -199,7 +210,7 @@ that they are sufficient to ensure the convergence of the load-balancing algorithm. \section{Best effort strategy} -\label{Best-effort} +\label{sec.besteffort} In this section we describe a new load-balancing strategy that we call \emph{best effort}. First, we explain the general idea behind this strategy, @@ -271,12 +282,12 @@ potentially wrong decision has a lower impact. Concretely, once $s_{ij}$ has been evaluated as before, it is simply divided by some configurable factor. That's what we named the ``parameter $k$'' in -Section~\ref{Results}. The amount of data to send is then $s_{ij}(t) = (\bar{x} -- x^i_j(t))/k$. -\FIXME[check that it's still named $k$ in Sec.~\ref{Results}]{} +Section~\ref{sec.results}. The amount of data to send is then $s_{ij}(t) = +(\bar{x} - x^i_j(t))/k$. +\FIXME[check that it's still named $k$ in Sec.~\ref{sec.results}]{} \section{Other strategies} -\label{Other} +\label{sec.other} Another load balancing strategy, working under the same conditions, was previously developed by Bahi, Giersch, and Makhoul in @@ -297,9 +308,9 @@ neighbor. \section{Virtual load} -\label{Virtual load} +\label{sec.virtual-load} -In this section, we present the concept of \texttt{virtual load}. In order to +In this section, we present the concept of \emph{virtual load}. In order to use this concept, load balancing messages must be sent using two different kinds of messages: load information messages and load balancing messages. More precisely, a node wanting to send a part of its load to one of its neighbors, @@ -309,7 +320,7 @@ Load information message are really short, consequently they will be received very quickly. In opposition, load balancing messages are often bigger and thus require more time to be transferred. -The concept of \texttt{virtual load} allows a node that received a load +The concept of \emph{virtual load} allows a node that received a load information message to integrate the load that it will receive later in its load (virtually) and consequently send a (real) part of its load to some of its neighbors. In fact, a node that receives a load information message knows that @@ -327,7 +338,7 @@ information of the load they will receive, so they can take in into account. \FIXME{describe integer mode} \section{Simulations} -\label{Simulations} +\label{sec.simulations} In order to test and validate our approaches, we wrote a simulator using the SimGrid @@ -338,13 +349,12 @@ as the initial distribution of load, the interconnection topology, the characteristics of the running platform, etc. Then several metrics are issued that permit to compare the strategies. -The simulation model is detailed in the next section (\ref{Sim - model}), and the experimental contexts are described in -section~\ref{Contexts}. Then the results of the simulations are -presented in section~\ref{Results}. +The simulation model is detailed in the next section (\ref{sec.model}), and the +experimental contexts are described in section~\ref{sec.exp-context}. Then the +results of the simulations are presented in section~\ref{sec.results}. \subsection{Simulation model} -\label{Sim model} +\label{sec.model} In the simulation model the processors exchange messages which are of two kinds. First, there are \emph{control messages} which only carry @@ -481,10 +491,11 @@ iteratively runs the following operations: \end{algorithm} \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}} + 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{sec.virtual-load}} \subsection{Experimental contexts} -\label{Contexts} +\label{sec.exp-context} In order to assess the performances of our algorithms, we ran our simulator with various parameters, and extracted several metrics, that @@ -633,7 +644,7 @@ With these constraints in mind, we defined the following metrics: \subsection{Experimental results} -\label{Results} +\label{sec.results} In this section, the results for the different simulations will be presented, and we'll try to explain our observations. @@ -785,14 +796,14 @@ On constate quoi (vérifier avec les chiffres)? \FIXME{conclude!} -\begin{acknowledgements} - Computations have been performed on the supercomputer facilities of - the Mésocentre de calcul de Franche-Comté. -\end{acknowledgements} +\section*{Acknowledgements} -\FIXME{find and add more references} -\bibliographystyle{spmpsci} +Computations have been performed on the supercomputer facilities of the +Mésocentre de calcul de Franche-Comté. + +\bibliographystyle{elsarticle-num} \bibliography{biblio} +\FIXME{find and add more references} \end{document}