From db33461e614769b3c7c7a8239ebf75a014ec3041 Mon Sep 17 00:00:00 2001 From: Arnaud Giersch Date: Mon, 18 Mar 2013 22:57:02 +0100 Subject: [PATCH] Normalize labels. --- loba-besteffort/loba-besteffort.tex | 59 +++++++++++++++-------------- 1 file changed, 30 insertions(+), 29 deletions(-) diff --git a/loba-besteffort/loba-besteffort.tex b/loba-besteffort/loba-besteffort.tex index 6a76602..d774cce 100644 --- a/loba-besteffort/loba-besteffort.tex +++ b/loba-besteffort/loba-besteffort.tex @@ -134,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 @@ -170,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} @@ -193,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. @@ -209,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, @@ -281,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 @@ -307,7 +308,7 @@ neighbor. \section{Virtual load} -\label{Virtual load} +\label{sec.virtual-load} 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 @@ -337,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 @@ -348,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 @@ -491,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 @@ -643,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. -- 2.39.5