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
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
when a node receives the information that later it will receive a data message,
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
when a node receives the information that later it will receive a data message,
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
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
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
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
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
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
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
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.
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~\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)$
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)$
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
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
When a processor send 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
When a processor send 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
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}
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)-\sum _{k\in V(i)} s_{ik}(t) \geq x_j^i(t)+s_{ij}(t)
\end{equation}
for any processor $i$ and any $j \in V(i)$ such that $x_i(t)>x_j^i(t)$. This
x_i(t)-\sum _{k\in V(i)} s_{ik}(t) \geq x_j^i(t)+s_{ij}(t)
\end{equation}
for any processor $i$ and any $j \in V(i)$ such that $x_i(t)>x_j^i(t)$. This
less loaded after that.
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
less loaded after that.
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
-% LocalWords: Raphaël Couturier Arnaud Giersch Abderrahmane Sider
-% LocalWords: Bertsekas Tsitsiklis SimGrid DASUD
+% LocalWords: Raphaël Couturier Arnaud Giersch Abderrahmane Sider Franche ij
+% LocalWords: Bertsekas Tsitsiklis SimGrid DASUD Comté Béjaïa asynchronism ji
+% LocalWords: ik
