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

diff --git a/supercomp11/supercomp11.tex b/supercomp11/supercomp11.tex
index 2f2dd31..b321468 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}}
 
@@ -85,7 +88,7 @@ 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
 the same authors in \cite{cedo+cortes+ripoll+al.2007.convergence}.
-\FIXME{Rajouter des choses ici.}
+\FIXME{Rajouter des choses ici.  Lesquelles ?}
 
 Although  the Bertsekas  and Tsitsiklis'  algorithm describes  the  condition to
 ensure the convergence,  there is no indication or  strategy to really implement
@@ -186,11 +189,14 @@ $3$.   If  it  sends  load  to  processor $1$  it  will  not  satisfy  condition
 $x_3^2(t)$.  So we consider that the \emph{ping-pong} condition is probably to
 strong. Currently, we did not try to make another convergence proof without this
 condition or with a weaker condition.
-%
-\FIXME{Develop: We have the feeling that such a weaker condition
-  exists, because (it's not a proof, but) we have never seen any
-  scenario that is not leading to convergence, even with LB-strategies
-  that are not fulfilling these two conditions.}
+
+Nevertheless, we conjecture that such a weaker condition exists.  In fact, we
+have never seen any scenario that is not leading to convergence, even with
+load-balancing strategies that are not exactly fulfilling these two conditions.
+
+It may be the subject of future work to express weaker conditions, and to prove
+that they are sufficient to ensure the convergence of the load-balancing
+algorithm.
 
 \section{Best effort strategy}
 \label{Best-effort}
@@ -260,45 +266,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.}
-
-% \FIXME{faut-il dÃ©crire les stratÃ©gies makhoul et simple ?}
-
-% \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)
-% \]
+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.
 
-\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.
+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.
 
-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}
@@ -482,7 +478,8 @@ actual source code that was used for the experiments%
 available at
 \url{http://info.iut-bm.univ-fcomte.fr/staff/giersch/software/loba.tar.gz}.
 
-\FIXME{ajouter des dÃ©tails sur la gestion de la charge virtuelle ?}
+\FIXME{ajouter des dÃ©tails sur la gestion de la charge virtuelle ?
+par ex, donner l'idÃ©e gÃ©nÃ©rale de l'implÃ©mentation.  l'idÃ©e gÃ©nÃ©rale est dÃ©ja dÃ©crite en section~\ref{Virtual load}}
 
 \subsection{Experimental contexts}
 \label{Contexts}
@@ -520,7 +517,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}
 
@@ -636,7 +634,32 @@ With these constraints in mind, we defined the following metrics:
 \label{Results}
 
 
+On constate quoi (vÃ©rifier avec les chiffres)?
+\begin{itemize}
+\item cluster ou grid, entier ou rÃ©el, ne font pas de grosses diffÃ©rences
+
+\item bookkeeping? amÃ©liore souvent les choses, parfois au prix d'un retard au dÃ©marrage
+
+\item makhoul? se fait battre sur les grosses plateformes
+
+\item taille de plateforme?
+
+\item ratio comp/comm?
+
+\item option $k$? peut-Ãªtre intÃ©ressant sur des plateformes fortement interconnectÃ©es (hypercube)
+
+\item volume de comm? souvent, besteffort/plain en fait plus. pourquoi?
+
+\item rÃ©partition initiale de la charge ?
+
+\item integer mode sur topo. line n'a jamais fini en plain? vÃ©rifier si ce n'est
+  pas Ã  cause de l'effet d'escalier que bk est capable de gommer.
+
+\end{itemize}
+
+\begin{itshape}
 On veut montrer quoi ? :
+\FIXME{remove that part}
 
 1) best plus rapide que les autres (simple, makhoul)
 2) avantage virtual load
@@ -648,7 +671,6 @@ Topologies variÃ©es
 Simulation avec temps dÃ©finies assez long et on mesure la qualitÃ© avec : volume de calcul effectuÃ©, volume de donnÃ©es Ã©changÃ©es
 Mais aussi simulation avec temps court qui montre que seul best converge
 
-
 ExpÃ©s avec ratio calcul/comm rapide et lent
 
 Quelques expÃ©s avec charge initiale alÃ©atoire plutot que sur le premier proc
@@ -662,14 +684,18 @@ On ne tient pas compte de la vitesse des liens donc on la considÃ¨re homogÃ¨ne
 Prendre un rÃ©seau hÃ©tÃ©rogÃ¨ne et rendre processeur homogÃ¨ne
 
 Taille : 10 100 trÃ¨s gros
+\end{itshape}
 
 \section{Conclusion and perspectives}
 
+\FIXME{conclude!}
+
 \begin{acknowledgements}
   Computations have been performed on the supercomputer facilities of
   the MÃ©socentre de calcul de Franche-ComtÃ©.
 \end{acknowledgements}
 
+\FIXME{find and add more references}
 \bibliographystyle{spmpsci}
 \bibliography{biblio}
 
@@ -684,4 +710,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
