Describe Makhoul's algorithm in English.

[loba-papers.git] / supercomp11 / supercomp11.tex

diff --git a/supercomp11/supercomp11.tex b/supercomp11/supercomp11.tex
index db3e809cbe07a1b5c33c692f719ba867f1dd5f09..741aa267d9a0e7ab788f9932f3824d469cd36169 100644 (file)
--- a/supercomp11/supercomp11.tex
+++ b/supercomp11/supercomp11.tex
@@ -14,8 +14,11 @@
   \begin{tabular}[t]{@{}l@{:~}l@{}}}{%
   \end{tabular}}
 
   \begin{tabular}[t]{@{}l@{:~}l@{}}}{%
   \end{tabular}}
 

-\newcommand{\FIXME}[1]{%
-  \textbf{$\triangleright$\marginpar{\textbf{[FIXME]}}~#1}}
+\newcommand{\FIXMEmargin}[1]{%
+  \marginpar{\textbf{[FIXME]} {\footnotesize #1}}}
+\newcommand{\FIXME}[2][]{%
+  \ifx #2\relax\relax \FIXMEmargin{#1}%
+  \else \textbf{$\triangleright$\FIXMEmargin{#1}~#2}\fi}

 
 \newcommand{\VAR}[1]{\textit{#1}}
 
 
 \newcommand{\VAR}[1]{\textit{#1}}
 


@@ -195,11 +198,16 @@ condition or with a weaker condition.
 \section{Best effort strategy}
 \label{Best-effort}
 
 \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.
 
 More precisely, when a processor $i$ is in its load-balancing phase,
 he proceeds as following.


@@ -246,38 +254,44 @@ he proceeds as following.
   \end{equation*}
 \end{enumerate}
 
   \end{equation*}
 \end{enumerate}
 

-\FIXME{describe parameter $k$}
+\subsection{Leveling the amount to send}

 
 

-\section{Other strategies}
-\label{Other}
+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.

 
 

-\FIXME{Réécrire en anglais.}
+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 that a
+potentially wrong decision has a lower impact.

 
 

-% \FIXME{faut-il décrire les stratégies makhoul et simple ?}
+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}]{}

 
 

-% \paragraph{simple} Tentative de respecter simplement les conditions de Bertsekas.
-% Parmi les voisins moins chargés que soi, on sélectionne :
-% \begin{itemize}
-% \item un des moins chargés (vmin) ;
-% \item un des plus chargés (vmax),
-% \end{itemize}
-% puis on équilibre avec vmin en s'assurant que notre charge reste
-% toujours supérieure à celle de vmin et à celle de vmax.
-
-% On envoie donc (avec "self" pour soi-même) :
-% \[
-%     \min\left(\frac{load(self) - load(vmin)}{2}, load(self) - load(vmax)\right)
-% \]
+\section{Other strategies}
+\label{Other}

 
 

-\paragraph{makhoul} Ordonne les voisins du moins chargé au plus chargé
-puis calcule les différences de charge entre soi-même et chacun des
-voisins.
+Another load balancing strategy, working under the same conditions, was
+previously developed by Bahi, Giersch, and Makhoul in
+\cite{bahi+giersch+makhoul.2008.scalable}.  In order to assess the performances
+of the new \emph{best effort}, we naturally chose to compare it to this anterior
+work.  More precisely, we will use the algorithm~2 from
+\cite{bahi+giersch+makhoul.2008.scalable} and, in the following, we will
+reference it under the name of Makhoul's.

 
 

-Ensuite, pour chaque voisin, dans l'ordre, et tant qu'on reste plus
-chargé que le voisin en question, on lui envoie 1/(N+1) de la
-différence calculée au départ, avec N le nombre de voisins.
+Here is an outline of the Makhoul's algorithm.  When a given node needs to take
+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
+process continues as long as the node is more loaded than the considered
+neighbor.

 
 

-C'est l'algorithme~2 dans~\cite{bahi+giersch+makhoul.2008.scalable}.

 
 \section{Virtual load}
 \label{Virtual load}
 
 \section{Virtual load}
 \label{Virtual load}


@@ -499,7 +513,8 @@ number of computing iterations (2000 in our case).
 Note that this convergence detection was implemented in a centralized manner.
 This is easy to do within the simulator, but it's obviously not realistic.  In a
 real application we would have chosen a decentralized convergence detection
 Note that this convergence detection was implemented in a centralized manner.
 This is easy to do within the simulator, but it's obviously not realistic.  In a
 real application we would have chosen a decentralized convergence detection

-algorithm, like the one described in \cite{10.1109/TPDS.2005.2}.
+algorithm, like the one described by Bahi, Contassot-Vivier, Couturier, and
+Vernier in \cite{10.1109/TPDS.2005.2}.

 
 \paragraph{Platforms}
 
 
 \paragraph{Platforms}