X-Git-Url: https://bilbo.iut-bm.univ-fcomte.fr/and/gitweb/loba-papers.git/blobdiff_plain/6f6ebdac1613681f5093eb2303424044b5f60f12..a2921953b585b36d55e5d8819a99f4da8f842a13:/supercomp11/supercomp11.tex?ds=inline

diff --git a/supercomp11/supercomp11.tex b/supercomp11/supercomp11.tex
index 3a1ec31..741aa26 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}}
 
@@ -29,12 +32,12 @@
 }
 
 \institute{R. Couturier \and A. Giersch \at
-              LIFC, University of Franche-Comté, Belfort, France \\
+              FEMTO-ST, University of Franche-Comté, Belfort, France \\
               % Tel.: +123-45-678910\\
               % Fax: +123-45-678910\\
               \email{%
-                raphael.couturier@univ-fcomte.fr,
-                arnaud.giersch@univ-fcomte.fr}
+                raphael.couturier@femto-st.fr,
+                arnaud.giersch@femto-st.fr}
 }
 
 \maketitle
@@ -195,11 +198,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,38 +254,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}
@@ -468,38 +482,150 @@ available at
 
 In order to assess the performances of our algorithms, we ran our
 simulator with various parameters, and extracted several metrics, that
-we will describe in this section.  Overall, the experiments represent
-more than 240 hours of computing time.
+we will describe in this section.
 
 \paragraph{Load balancing strategies}
 
-We ran the experiments with the \emph{Best effort}, and with the \emph{Makhoul}
-strategies.  \emph{Best effort} was tested with parameter $k = 1$, $k = 2$, and
-$k = 4$.  Secondly, each strategy was run in its two variants: with, and without
-the management of \emph{virtual load}.  Finally, we tested each configuration
-with \emph{real}, and with \emph{integer} load.
-This gives us as many as 32 different strategies.
+Several load balancing strategies were compared.  We ran the experiments with
+the \emph{Best effort}, and with the \emph{Makhoul} strategies.  \emph{Best
+  effort} was tested with parameter $k = 1$, $k = 2$, and $k = 4$.  Secondly,
+each strategy was run in its two variants: with, and without the management of
+\emph{virtual load}.  Finally, we tested each configuration with \emph{real},
+and with \emph{integer} load.
+
+To summarize the different load balancing strategies, we have:
+\begin{description}
+\item[\textbf{strategies:}] \emph{Makhoul}, or \emph{Best effort} with $k\in
+  \{1,2,4\}$
+\item[\textbf{variants:}] with, or without virtual load
+\item[\textbf{domain:}] real load, or integer load
+\end{description}
+%
+This gives us as many as $4\times 2\times 2 = 16$ different strategies.
+
+\paragraph{End of the simulation}
+
+The simulations were run until the load was nearly balanced among the
+participating nodes.  More precisely the simulation stops when each node holds
+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 by Bahi, Contassot-Vivier, Couturier, and
+Vernier in \cite{10.1109/TPDS.2005.2}.
+
+\paragraph{Platforms}
+
+In order to show the behavior of the different strategies in different
+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 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.
 
 \paragraph{Configurations}
+
+The distributed processes of the application were then logically organized along
+three possible topologies: a line, a torus or an hypercube.  We ran tests where
+the total load was initially on an only node (at one end for the line topology),
+and other tests where the load was initially randomly distributed across all the
+participating nodes.  The total amount of load was fixed to a number of load
+units equal to 1000 times the number of node.  The average load is then of 1000
+load units.
+
+For each of the preceding configuration, we finally had to choose the
+computation and communication costs of a load unit.  We chose them, such as to
+have three different computation over communication cost ratios, and hence model
+three different kinds of applications:
+\begin{itemize}
+\item mainly communicating, with a computation/communication cost ratio of $1/10$;
+\item mainly computing, with a computation/communication cost ratio of $10/1$ ;
+\item balanced, with a computation/communication cost ratio of $1/1$.
+\end{itemize}
+
+To summarize the various configurations, we have:
 \begin{description}
-\item[\textbf{platforms}] homogeneous (cluster); heterogeneous (subset
-  of Grid5000)
-\item[\textbf{platform size}] platforms with 16, 64, 256, and 1024 nodes
-\item[\textbf{topologies}] line; torus; hypercube
-\item[\textbf{initial load distribution}] initially on a only node;
-  initially on all nodes
-\item[\textbf{comp/comm ratio}] $10/1$, $1/1$, $1/10$
+\item[\textbf{platforms:}] homogeneous (cluster), or heterogeneous (subset of
+  Grid'5000)
+\item[\textbf{platform sizes:}] platforms with 16, 64, 256, or 1024 nodes
+\item[\textbf{process topologies:}] line, torus, or hypercube
+\item[\textbf{initial load distribution:}] initially on a only node, or
+  initially randomly distributed over all nodes
+\item[\textbf{computation/communication ratio:}] $10/1$, $1/1$, or $1/10$
 \end{description}
+%
+This gives us as many as $2\times 4\times 3\times 2\times 3 = 144$ different
+configurations.
+%
+Combined with the various load balancing strategies, we had $16\times 144 =
+2304$ distinct settings to evaluate.  In fact, as it will be shown later, we
+didn't run all the strategies, nor all the configurations for the bigger
+platforms with 1024 nodes, since to simulations would have run for a too long
+time.
+
+Anyway, all these the experiments represent more than 240 hours of computing
+time.
 
 \paragraph{Metrics}
 
+In order to evaluate and compare the different load balancing strategies we had
+to define several metrics.  Our goal, when choosing these metrics, was to have
+something tending to a constant value, i.e. to have a measure which is not
+changing anymore once the convergence state is reached.  Moreover, we wanted to
+have some normalized value, in order to be able to compare them across different
+settings.
+
+With these constraints in mind, we defined the following metrics:
+%
 \begin{description}
-\item[\textbf{average idle time}]
-\item[\textbf{average convergence date}]
-\item[\textbf{maximum convergence date}]
-\item[\textbf{data transfer amount}] relative to the total data amount
+\item[\textbf{average idle time:}] that's the total time spent, when the nodes
+  don't hold any share of load, and thus have nothing to compute.  This total
+  time is divided by the number of participating nodes, such as to have a number
+  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.  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
+  of (simulated) seconds since the beginning of the simulation.
+
+\item[\textbf{maximum convergence date:}] that's the date when the last node
+  reached the convergence state.
+
+  These two dates give an idea of the time needed by the strategy to reach the
+  equilibrium state.  A smaller value is better.
+
+\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.  Again, a smaller value is better.
+
 \end{description}
 
+
 \subsection{Validation of our approaches}
 \label{Results}
 
@@ -552,4 +678,4 @@ 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
+% LocalWords:  ik isend irecv Cortés et al chan ctrl fifo Makhoul GFlop xml