X-Git-Url: https://bilbo.iut-bm.univ-fcomte.fr/and/gitweb/loba-papers.git/blobdiff_plain/99c4629e78a3a929c5ba423fc7d6f11cb495e6f1..2ec8c4d1d0aeeb64643e48c72697e8521e7495aa:/supercomp11/supercomp11.tex?ds=inline

diff --git a/supercomp11/supercomp11.tex b/supercomp11/supercomp11.tex
index 2f2dd31..3ba8d85 100644
--- a/supercomp11/supercomp11.tex
+++ b/supercomp11/supercomp11.tex
@@ -14,8 +14,11 @@
   \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}}
 
@@ -260,45 +263,35 @@ 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
+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
 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$)}
+\FIXME[check that it's still named $k$ in Sec.~\ref{Results}]{}
 
 \section{Other strategies}
 \label{Other}
 
-\FIXME{RÃ©Ã©crire en anglais.}
+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.
 
-% \FIXME{faut-il dÃ©crire les stratÃ©gies makhoul et simple ?}
+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.
 
-% \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)
-% \]
-
-\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.
-
-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.
-
-C'est l'algorithme~2 dans~\cite{bahi+giersch+makhoul.2008.scalable}.
 
 \section{Virtual load}
 \label{Virtual load}
@@ -520,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
-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}
 
@@ -684,4 +678,5 @@ Taille : 10 100 trÃ¨s gros
 
 % LocalWords:  RaphaÃ«l Couturier Arnaud Giersch Abderrahmane Sider Franche ij
 % LocalWords:  Bertsekas Tsitsiklis SimGrid DASUD ComtÃ© BÃ©jaÃ¯a asynchronism ji
-% LocalWords:  ik isend irecv CortÃ©s et al chan ctrl fifo Makhoul GFlop xml
+% LocalWords:  ik isend irecv CortÃ©s et al chan ctrl fifo Makhoul GFlop xml pre
+% LocalWords:  FEMTO Makhoul's fca bdee cdde Contassot Vivier underlaid
