From: Arnaud Giersch <arnaud.giersch@iut-bm.univ-fcomte.fr>
Date: Mon, 11 Feb 2013 17:17:19 +0000 (+0100)
Subject: Describe parameter k.
X-Git-Url: https://bilbo.iut-bm.univ-fcomte.fr/and/gitweb/loba-papers.git/commitdiff_plain/99c4629e78a3a929c5ba423fc7d6f11cb495e6f1

Describe parameter k.
---

diff --git a/supercomp11/supercomp11.tex b/supercomp11/supercomp11.tex
index db3e809..2f2dd31 100644
--- a/supercomp11/supercomp11.tex
+++ b/supercomp11/supercomp11.tex
@@ -195,11 +195,16 @@ condition or with a weaker condition.
 \section{Best effort strategy}
 \label{Best-effort}
 
-In this section we  describe  a new load-balancing strategy that we call
-\emph{best effort}.  The general idea behind this strategy is that each
-processor, that detects it has more load than some of its neighbors, 
-sends some load to the most of its less loaded neighbors, doing its
-best to reach the equilibrium between those neighbors and himself.
+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,
+and then we describe some variants of this basic strategy.
+
+\subsection{Basic strategy}
+
+The general idea behind the \emph{best effort} strategy is that each processor,
+that detects it has more load than some of its neighbors, sends some load to the
+most of its less loaded neighbors, doing its best to reach the equilibrium
+between those neighbors and himself.
 
 More precisely, when a processor $i$ is in its load-balancing phase,
 he proceeds as following.
@@ -246,7 +251,23 @@ he proceeds as following.
   \end{equation*}
 \end{enumerate}
 
-\FIXME{describe parameter $k$}
+\subsection{Leveling the amount to send}
+
+With the aforementioned basic strategy, each node does its best to reach the
+equilibrium with its neighbors.  Since each node may be taking the same kind of
+decision at the same moment, there is the risk that a node receives load from
+several of its neighbors, and then is temporary going off the equilibrium state.
+This is particularly true with strongly connected applications.
+
+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 as 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
+Section~\ref{Results}.  The amount of data to send is then $s_{ij}(t) = (\bar{x}
+- x^i_j(t))/k$.
+\FIXME{check the name ($k$)}
 
 \section{Other strategies}
 \label{Other}