X-Git-Url: https://bilbo.iut-bm.univ-fcomte.fr/and/gitweb/loba-papers.git/blobdiff_plain/a17baac0d900ec0555cc2002c02c3af3fd38ade7..499377296c4679d5c97e63f9b61675727749a6c8:/supercomp11/supercomp11.tex?ds=sidebyside

diff --git a/supercomp11/supercomp11.tex b/supercomp11/supercomp11.tex
index f41425c..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,20 +189,28 @@ $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}
 
-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,38 +257,44 @@ he proceeds as following.
   \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 angliche.}
+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}
@@ -461,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}
@@ -497,8 +515,10 @@ an amount of load at less than 1\% of the load average, during an arbitrary
 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}.
+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 by Bahi, Contassot-Vivier, Couturier, and
+Vernier in \cite{10.1109/TPDS.2005.2}.
 
 \paragraph{Platforms}
 
@@ -507,16 +527,21 @@ settings, we simulated the executions on two sorts of platforms.  These two
 sorts of platforms differ by their underlaid network topology.  On the one hand,
 we have homogeneous platforms, modeled as a cluster.  On the other hand, we have
 heterogeneous platforms, modeled as the interconnection of a number of clusters.
+
+The clusters were modeled by a fixed number of computing nodes interconnected
+through a backbone link.  Each computing node has a computing power of
+1~GFlop/s, and is connected to the backbone by a network link whose bandwidth is
+of 125~MB/s, with a latency of 50~$\mu$s.  The backbone has a network bandwidth
+of 2.25~GB/s, with a latency of 500~$\mu$s.
+
 The heterogeneous platform descriptions were created by taking a subset of the
 Grid'5000 infrastructure\footnote{Grid'5000 is a French large scale experimental
   Grid (see \url{https://www.grid5000.fr/}).}, as described in the platform file
 \texttt{g5k.xml} distributed with SimGrid.  Note that the heterogeneity of the
-platform only comes from the network topology.  The processor speeds, and
-network bandwidths were normalized since our algorithms currently are not aware
-of such heterogeneity.  We arbitrarily chose to fix the processor speed to
-1~GFlop/s, and the network bandwidth to 125~MB/s, with a latency of 50~$\mu$s,
-except for the links between geographically distant sites, where the network
-bandwidth was fixed to 2.25~GB/s, with a latency of 500~$\mu$s.
+platform here only comes from the network topology.  Indeed, since our
+algorithms currently do not handle heterogeneous computing resources, the
+processor speeds were normalized, and we arbitrarily chose to fix them to
+1~GFlop/s.
 
 Then we derived each sort of platform with four different number of computing
 nodes: 16, 64, 256, and 1024 nodes.
@@ -582,7 +607,7 @@ With these constraints in mind, we defined the following metrics:
   that can be compared between simulations of different sizes.
 
   This metric is expected to give an idea of the ability of the strategy to
-  diffuse the load quickly, lesser is better.
+  diffuse the load quickly.  A smaller value is better.
 
 \item[\textbf{average convergence date:}] that's the average of the dates when
   all nodes reached the convergence state.  The dates are measured as a number
@@ -592,15 +617,15 @@ With these constraints in mind, we defined the following metrics:
   reached the convergence state.
 
   These two dates give an idea of the time needed by the strategy to reach the
-  equilibrium state, lesser is doubtlessly better.
+  equilibrium state.  A smaller value is better.
 
-\item[\textbf{data transfer amount:}] that's the sum of the amount of data of
-  all transfers during the simulation.  This sum is then normalized by dividing
-  it by the total amount of data present in the system.
+\item[\textbf{data transfer amount:}] that's the sum of the amount of all data
+  transfers during the simulation.  This sum is then normalized by dividing it
+  by the total amount of data present in the system.
 
   This metric is expected to give an idea of the efficiency of the strategy in
   terms of data movements, i.e. its ability to reach the equilibrium with fewer
-  transfers.
+  transfers.  Again, a smaller value is better.
 
 \end{description}
 
@@ -609,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
@@ -621,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
@@ -635,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}
 
@@ -657,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
+% 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
