X-Git-Url: https://bilbo.iut-bm.univ-fcomte.fr/and/gitweb/loba-papers.git/blobdiff_plain/1630e7fa688ea1692b8a13f554924252b4047321..019bcd66f0712c7954b6e9e15ec7abe92063795b:/loba-besteffort/loba-besteffort.tex diff --git a/loba-besteffort/loba-besteffort.tex b/loba-besteffort/loba-besteffort.tex index 9007b17..9f26237 100644 --- a/loba-besteffort/loba-besteffort.tex +++ b/loba-besteffort/loba-besteffort.tex @@ -40,13 +40,16 @@ asynchronous iterative load balancing} \author{Raphaël Couturier} -\ead{raphael.couturier@femto-st.fr} +\ead{raphael.couturier@univ-fcomte.fr} \author{Arnaud Giersch\corref{cor}} -\ead{arnaud.giersch@femto-st.fr} +\ead{arnaud.giersch@univ-fcomte.fr} -\address{FEMTO-ST, University of Franche-Comté\\ - 19 avenue du Maréchal Juin, BP 527, 90016 Belfort cedex, France} +\author{Mourad Hakem} +\ead{mourad.hakem@univ-fcomte.fr} + +\address{% + FEMTO-ST Institute, Univ Bourgogne Franche-Comté, Belfort, France} \cortext[cor]{Corresponding author.} @@ -60,14 +63,13 @@ propose a strategy called \besteffort{} 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 + asynchronous iterative algorithms, in which an asynchronous load balancing + algorithm is implemented, can dissociate, most of the time, 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 + called \emph{virtual load}. This heuristic allows a node that receives a load + information message to integrate this information, even if the load has not been received yet. Consequently the node sends a (real) part of its load to some of + its neighbors taking into account the virtual load it will receive soon. In order to validate our approaches, we have defined a simulator based on SimGrid which allowed us to conduct many experiments. \end{abstract} @@ -82,18 +84,19 @@ Load balancing algorithms are extensively used in parallel and distributed applications in order to reduce the execution times. They can be applied in different scientific fields from high performance computation to micro sensor -networks. They are iterative by nature. In literature many kinds of load +networks. In a distributed context (i.e. without centralization), they are iterative by nature. +In literature many kinds of load balancing algorithms have been studied. They can be classified according different criteria: centralized or decentralized, in static or dynamic environment, with homogeneous or heterogeneous load, using synchronous or asynchronous iterations, with a static topology or a dynamic one which evolves during time. In this work, we focus on asynchronous load balancing algorithms -where computer nodes are considered homogeneous and with homogeneous load with +where computing nodes are considered homogeneous and with homogeneous load with no external load. In this context, Bertsekas and Tsitsiklis have proposed an -algorithm which is definitively a reference for many works. In their work, they +algorithm which is definitively a reference for many works. In their work, they proved that under classical hypotheses of asynchronous iterative algorithms and a special constraint avoiding \emph{ping-pong} effect, an asynchronous -iterative algorithm converge to the uniform load distribution. This work has +iterative algorithm converges to the uniform load distribution. This work has 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 @@ -110,12 +113,11 @@ 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. 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 +from data migration messages. Former ones allow a node to inform its +neighbors of its current load. These messages are very small, they can be sent +often and very quickly. For example, if a computing iteration takes a significant times (ranging from seconds to minutes), it is possible to send a new load information -message at each neighbor at each iteration. Latter messages contains data that -migrates from one node to another one. Depending on the application, it may have +message to each neighbor at each iteration. Then the load is sent, but the reception may take time when the amount of load is huge and when communication links are slow. Depending on the application, it may have sense or not that nodes try to balance a part of their load at each computing iteration. But the time to transfer a load message from a node to another one is often much more longer that to time to transfer a load information message. So, @@ -124,19 +126,21 @@ it can take this information into account and it can consider that its new load is larger. Consequently, it can send a part of it real load to some of its neighbors if required. We call this trick the \emph{virtual load} mechanism. - - -So, in this work, we propose a new strategy for improving the distribution of -the load and a simple but efficient trick that also improves the load -balancing. Moreover, we have conducted many simulations with SimGrid in order to -validate our improvements are really efficient. Our simulations consider that in -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 +{\bf The contributions of this paper are the following:} +\begin{itemize} +\item We propose a new strategy to improve the distribution of the +load and a simple but efficient trick that also improves the load +balancing. +\item we have conducted many simulations with SimGrid in order to +validate that our improvements are really efficient. Our simulations consider +that in 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. +\end{itemize} 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. +present a possible problem in the convergence conditions. In Section~\ref{sec.related.works}, related works are presented. 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 @@ -154,8 +158,8 @@ In order prove the convergence of asynchronous iterative load balancing Bertsekas and Tsitsiklis proposed a model in~\cite{bertsekas+tsitsiklis.1997.parallel}. Here we recall some notations. Consider that $N={1,...,n}$ processors are connected through a network. -Communication links are represented by a connected undirected graph $G=(N,V)$ -where $V$ is the set of links connecting different processors. In this work, we +Communication links are represented by a connected undirected graph $G=(N,A)$ +where $A$ is the set of links connecting different processors. In this work, we consider that processors are homogeneous for sake of simplicity. It is quite easy to tackle the heterogeneous case~\cite{ElsMonPre02}. Load of processor $i$ at time $t$ is represented by $x_i(t)\geq 0$. Let $V(i)$ be the set of @@ -164,7 +168,7 @@ each of its neighbors $j \in V(i)$ represented by $x_j^i(t)$. According to asynchronism and communication delays, this estimate may be outdated. We also consider that the load is described by a continuous variable. -When a processor send a part of its load to one or some of its neighbors, the +When a processor sends a part of its load to one or some of its neighbors, the transfer takes time to be completed. Let $s_{ij}(t)$ be the amount of load that processor $i$ has transferred to processor $j$ at time $t$ and let $r_{ij}(t)$ be the amount of load received by processor $j$ from processor $i$ at time $t$. Then @@ -188,15 +192,17 @@ Nevertheless, we think that this condition may lead to deadlocks in some cases. For example, if we consider only three processors and that processor $1$ is linked to processor $2$ which is also linked to processor $3$ (i.e. a simple chain which 3 processors). Now consider we have the following values at time $t$: -\begin{eqnarray*} -x_1(t)=10 \\ -x_2(t)=100 \\ -x_3(t)=99.99\\ - x_3^2(t)=99.99\\ -\end{eqnarray*} +\begin{align*} + x_1(t) &= 10 \\ + x_2(t) &= 100 \\ + x_3(t) &= 99.99 \\ + x_3^2(t) &= 99.99 \\ +\end{align*} +{\bf RAPH, pourquoi il y a $x_3^2$?. Sinon il faudra reformuler la suite, c'est mal dit} + 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 +\eqref{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. @@ -209,6 +215,13 @@ 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{Related works} +\label{sec.related.works} +{\bf A FAIRE} + + + \section{Best effort strategy} \label{sec.besteffort} @@ -229,21 +242,20 @@ he proceeds as following. \item First, the neighbors are sorted in non-decreasing order of their known loads $x^i_j(t)$. -\item Then, this sorted list is traversed in order to find its largest - prefix such as the load of each selected neighbor is lesser than: +\item Then, this sorted list is used to find its largest + prefix such as the load of each selected neighbor is smaller than: \begin{itemize} - \item the processor's own load, and + \item the load of processor $i$, and \item the mean of the loads of the selected neighbors and of the processor's load. \end{itemize} - Let's call $S_i(t)$ the set of the selected neighbors, and - $\bar{x}(t)$ the mean of the loads of the selected neighbors and of - the processor load: + Let $S_i(t)$ be the set of the selected neighbors, and + $\bar{x}(t)$ be the mean of the loads of the selected neighbors plus the load of processor $i$: \begin{equation*} \bar{x}(t) = \frac{1}{\abs{S_i(t)} + 1} \left( x_i(t) + \sum_{j\in S_i(t)} x^i_j(t) \right) \end{equation*} - The following properties hold: + The following properties hold: {\bf RAPH : la suite tombe du ciel :-)} \begin{equation*} \begin{cases} S_i(t) \subset V(i) \\ @@ -280,8 +292,8 @@ In order to reduce this effect, we add the ability to level the amount to send. The idea, here, is to make smaller steps toward the equilibrium, such that a 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 +Roughtly speaking, once $s_{ij}$ has been evaluated as previously explained, it is simply divided by +a given factor. This parameter is called $k$ in 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}]{} @@ -302,7 +314,7 @@ a load balancing decision, it starts by sorting its neighbors by increasing order of their load. Then, it computes the difference between its own load, and the load of each of its neighbors. Finally, taking the neighbors following the order defined before, the amount of load to send $s_{ij}$ is computed as -$1/(N+1)$ of the load difference, with $N$ being the number of neighbors. This +$1/(n+1)$ of the load difference, with $n$ being the number of neighbors. This process continues as long as the node is more loaded than the considered neighbor. @@ -313,8 +325,8 @@ neighbor. 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, -can first send a load information message containing the load it will send and +precisely, a node wanting to send a part of its load to one of its neighbors +can first send a load information message containing the load it will send, and then it can send the load balancing message containing data to be transferred. Load information message are really short, consequently they will be received very quickly. In opposition, load balancing messages are often bigger and thus @@ -322,19 +334,21 @@ require more time to be transferred. 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 +(virtually). Consequently the considered node can send a (real) part of its load to some of its neighbors. In fact, a node that receives a load information message knows that later it will receive the corresponding load balancing message containing the -corresponding data. So if this node detects it is too loaded compared to some +corresponding data. So, if this node detects it is too loaded compared to some of its neighbors and if it has enough load (real load), then it can send more load to some of its neighbors without waiting the reception of the load balancing message. Doing this, we can expect a faster convergence since nodes have a faster -information of the load they will receive, so they can take in into account. +information of the load they will receive, so they can take it into account. \FIXME{Est ce qu'on donne l'algo avec virtual load?} +With integer load, we adapt this algorithm by .... {\bf RAPH a faire} + \FIXME{describe integer mode} \section{Simulations} @@ -342,7 +356,7 @@ information of the load they will receive, so they can take in into account. In order to test and validate our approaches, we wrote a simulator using the SimGrid -framework~\cite{casanova+legrand+quinson.2008.simgrid}. This +framework~\cite{simgrid.web,casanova+giersch+legrand+al.2014.simgrid}. This simulator, which consists of about 2,700 lines of C++, allows to run the different load-balancing strategies under various parameters, such as the initial distribution of load, the interconnection topology, the @@ -378,7 +392,7 @@ 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 + framework~\cite{casanova+giersch+legrand+al.2014.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 @@ -556,7 +570,7 @@ algorithms currently do not handle heterogeneous computing resources, the processor speeds were normalized, and we arbitrarily chose to fix them to 1~GFlop/s. -Then we derived each sort of platform with four different number of computing +Then we derived each kind of platform with four different numbers of computing nodes: 16, 64, 256, and 1024 nodes. \subsubsection{Configurations} @@ -648,7 +662,7 @@ With these constraints in mind, we defined the following metrics: \label{sec.results} In this section, the results for the different simulations will be presented, -and we'll try to explain our observations. +and we will try to explain our observations. \subsubsection{Cluster vs grid platforms} @@ -719,56 +733,103 @@ allocated time, or because we simply decided not to run it. \FIXME{annoncer le plan de la suite} -\subsubsection{The \besteffort{} strategy with the load initially on only one - node} +\subsubsection{The \besteffort{} and \makhoul{} strategies without virtual load} + +Before looking at the different variations, we will first show that the plain +\besteffort{} strategy is valuable, and may be as good as the \makhoul{} +strategy. On Figures~\ref{fig.results1} and~\ref{fig.resultsN}, +these strategies are respectively labeled ``b'' and ``a''. + +We can see that the relative performance of these strategies is mainly +influenced by the application topology. It is for the line topology that the +difference is the more important. In this case, the \besteffort{} strategy is +nearly faster than the \makhoul{} strategy. This can be explained by the +fact that the \besteffort{} strategy tries to distribute the load fairly between +all the nodes and with the line topology, it is easy to load balance the load +fairly. + +On the contrary, for the hypercube topology, the \besteffort{} strategy performs +worse than the \makhoul{} strategy. In this case, the \makhoul{} strategy which +tries to give more load to few neighbors reaches the equilibrium faster. + +For the torus topology, for which the number of links is between the line and +the hypercube, the \makhoul{} strategy is slightly better but the difference is +more nuanced when the initial load is only on one node. The only case where the +\makhoul{} strategy is really faster than the \besteffort{} strategy is with the +random initial distribution when the communication are slow. -Before looking at the different variations, we'll first show that the plain -\besteffort{} strategy is valuable, and may be as good as the \makhoul{} -strategy. On the graphs from the figure~\ref{fig.results1}, these strategies -are respectively labeled ``b'' and ``a''. +Globally the number of interconnection is very important. The more +the interconnection links are, the faster the \makhoul{} strategy is because +it distributes quickly significant amount of load, even if this is unfair, between +all the neighbors. In opposition, the \besteffort{} strategy distributes the +load fairly so this strategy is better for low connected strategy. -twice faster on lines -almost equivalent on torus -worse on hcubes --> interconnection +\subsubsection{Virtual load} -plus c'est connecté, moins bon est BE car à vouloir trop bien équilibrer -localement, le processeurs se perturbent mutuellement. Du coup, makhoul qui -équilibre moins bien localement est moins perturbé par ces interférences. +The influence of virtual load is most of the time really significant compared to +the same configuration without it. Sometimes it has no effect but {\bf A + VERIFIER} it has never a negative effect on the load balancing we tested. -\subsubsection{With the virtual load extension with the load initially on only - one node} +On Figure~\ref{fig.results1}, when the load is initially on one node, it can be +noticed that the average idle times are generally longer with the virtual load +than without it. This can be explained by the fact that, with virtual load, +processors will exchange all the load they need to exchange as soon as the +virtual load has been balanced between all the processors. So consequently they +cannot compute at the beginning. This is especially noticeable when the +communication are slow (on the left part of Figure ~\ref{fig.results1}. -Dans ce cas légère amélioration de la cvg. max. Temps moyen de cvg. amélioré, -mais plus de temps passé en idle, surtout quand les comms coutent cher. +%Dans ce cas légère amélioration de la cvg. max. Temps moyen de cvg. amélioré, +%mais plus de temps passé en idle, surtout quand les comms coutent cher. -\subsubsection{The \besteffort{} strategy with an initial random load - distribution, and larger platforms} +%\subsubsection{The \besteffort{} strategy with an initial random load +% distribution, and larger platforms} -Mêmes conclusions pour line et hcube. -Sur tore, BE se fait exploser quand les comms coutent cher. +%In +%Mêmes conclusions pour line et hcube. +%Sur tore, BE se fait exploser quand les comms coutent cher. -\FIXME{virer les 1024 ?} +%\FIXME{virer les 1024 ?} -\subsubsection{With the virtual load extension with an initial random load - distribution} +%\subsubsection{With the virtual load extension with an initial random load +% distribution} -Soit c'est équivalent, soit on gagne -> surtout quand les comms coutent cher et -qu'il y a beaucoup de voisins. +%Soit c'est équivalent, soit on gagne -> surtout quand les comms coutent cher et +%qu'il y a beaucoup de voisins. \subsubsection{The $k$ parameter} +\label{results-k} + +As explained previously when the communication are slow the \besteffort{} +strategy is efficient. This is due to the fact that it tries to balance the load +fairly and consequently a significant amount of the load is transfered between +processors. In this situation, it is possible to reduce the convergence time by +using the leveler parameter (parameter $k$). The advantage of using this +solution is particularly efficient when the initial load is randomly distributed +on the nodes with torus and hypercube topology and slow communication. When +virtual load mechanism is used, the effect of this parameter is also visible +with the same condition. + + + +\subsubsection{With integer load} -Dans le cas où les comms coutent cher et ou BE se fait avoir, on peut ameliorer -les perfs avec le param k. +We also performed some experiments with integer load instead of load with real +value. In this case, the results have globally the same behavior. The most +intereting result, from our point of view, is that the virtual mode allows +processors in a line topology to converge to the uniform load balancing. Without +the virtual load, most of the time, processors converge to what we call the +``stairway effect'', that is to say that there is only a difference of one in +the load of each processor and its neighbors (for example with 10 processors, we +obtain 10 9 8 7 6 6 7 8 9 10 instead of 8 8 8 8 8 8 8 8 8 8). -\subsubsection{With integer load, 1 ou N} +%Cas normal, ligne -> converge pas (effet d'escalier). +%Avec vload, ça converge. -Cas normal, ligne -> converge pas (effet d'escalier). -Avec vload, ça converge. +%Dans les autres cas, résultats similaires au cas réel: redire que vload est +%intéressant. -Dans les autres cas, résultats similaires au cas réel: redire que vload est -intéressant. +\FIXME{ajouter une courbe avec l'équilibrage en entier} \FIXME{virer la metrique volume de comms} @@ -840,4 +901,6 @@ Mésocentre de calcul de Franche-Comté. % LocalWords: SimGrid DASUD Comté asynchronism ji ik isend irecv Cortés et al % LocalWords: chan ctrl fifo Makhoul GFlop xml pre FEMTO Makhoul's fca bdee % LocalWords: cdde Contassot Vivier underlaid du de Maréchal Juin cedex calcul -% LocalWords: biblio +% LocalWords: biblio Institut UMR Université UFC Centre Scientifique CNRS des +% LocalWords: École Nationale Supérieure Mécanique Microtechniques ENSMM UTBM +% LocalWords: Technologie Bahi