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}
+
+\author{Mourad Hakem}
+\ead{mourad.hakem@univ-fcomte.fr}
\address{%
- Institut FEMTO-ST (UMR 6174),
- Université de Franche-Comté (UFC),
- Centre National de la Recherche Scientifique (CNRS),
- École Nationale Supérieure de Mécanique et des Microtechniques (ENSMM),
- Université de Technologie de Belfort Montbéliard (UTBM)\\
- 19 avenue du Maréchal Juin, BP 527, 90016 Belfort cedex, France}
+ FEMTO-ST Institute, Univ Bourgogne Franche-Comté, Belfort, France}
\cortext[cor]{Corresponding author.}
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}
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.\FIXME{really?}
+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
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 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 a computing iteration takes a significant times
+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 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
+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,
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 to improve the distribution 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. Moreover, we have conducted many simulations with SimGrid in order to
+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
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
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
\eqref{eq.ping-pong} because after the sending it will be less loaded that
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}
\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) \\
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}]{}
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.
\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}
In order to test and validate our approaches, we wrote a simulator
using the SimGrid
-framework~\cite{simgrid.web,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
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
