X-Git-Url: https://bilbo.iut-bm.univ-fcomte.fr/and/gitweb/loba-papers.git/blobdiff_plain/f3f57de44c8e94b6bab37e9f0eb1daf631e2aeca..ccdcd0ac01b39dae92f6c456577fafdb046a36bd:/loba-besteffort/loba-besteffort.tex?ds=sidebyside diff --git a/loba-besteffort/loba-besteffort.tex b/loba-besteffort/loba-besteffort.tex index 00cb3c5..c387ad6 100644 --- a/loba-besteffort/loba-besteffort.tex +++ b/loba-besteffort/loba-besteffort.tex @@ -87,7 +87,8 @@ 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. They are iterative by nature.\FIXME{really?} +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 @@ -115,11 +116,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 +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 -quite often. For example, if an computing iteration takes a significant times +quite often. 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 +message to each neighbor at each iteration. Latter messages contain data that migrates from one node to another one. 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 @@ -129,14 +130,12 @@ 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 +So, in this work, we propose a new strategy to improve 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 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. In the following of this paper, Section~\ref{sec.bt-algo} describes the @@ -159,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 @@ -193,15 +192,15 @@ 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*} 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. @@ -307,7 +306,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. @@ -318,8 +317,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 @@ -336,7 +335,7 @@ 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?} @@ -347,7 +346,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 @@ -383,7 +382,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 @@ -561,7 +560,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} @@ -803,13 +802,24 @@ with the same condition. -\subsubsection{With integer load, 1 ou N} +\subsubsection{With integer load} + +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). + +%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}