Graphs: rename makhoul -> Bertsekas and Tsitsiklis.

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

diff --git a/loba-besteffort/loba-besteffort.tex b/loba-besteffort/loba-besteffort.tex
index ed478e4b2422f6f1c57c555f70610c330335fb1e..55e877c52f0e96dd4b0069d47659a9c497e2e4f6 100644 (file)
--- a/loba-besteffort/loba-besteffort.tex
+++ b/loba-besteffort/loba-besteffort.tex
@@ -66,7 +66,7 @@
   propose a new strategy called \besteffort{} which aims to balance the load
   of a node to all its less loaded neighbors while ensuring that all involved nodes by the load balancing phase have the same amount of load. Moreover, since 
   asynchronous iterative algorithms are less sensitive to communications delays 
   propose a new strategy called \besteffort{} which aims to balance the load
   of a node to all its less loaded neighbors while ensuring that all involved nodes by the load balancing phase have the same amount of load. Moreover, since 
   asynchronous iterative algorithms are less sensitive to communications delays 

-  and their variations, both load transfer and load information messages are dissociated. 
+  and their variations \cite{bcvc07:bc}, both load transfer and load information messages are dissociated. 

   To speedup the convergence time of the load balancing process, we propose {\it a clairvoyant virtual load} heuristic which allows 
   %asynchronous iterative algorithms, in which an asynchronous load balancing
   %algorithm is implemented, can dissociate, most of the time, messages concerning
   To speedup the convergence time of the load balancing process, we propose {\it a clairvoyant virtual load} heuristic which allows 
   %asynchronous iterative algorithms, in which an asynchronous load balancing
   %algorithm is implemented, can dissociate, most of the time, messages concerning


@@ -168,7 +168,7 @@ The main contributions and novelties of our work are summarized in the following
 \item Unlike earlier works, we use a new concept of virtual loads transfers which allows nodes to predict the future loads they will receive in the subsequent iterations. 
 This leads to a noticeable speedup of the global convergence time of the load balancing process.  
 
 \item Unlike earlier works, we use a new concept of virtual loads transfers which allows nodes to predict the future loads they will receive in the subsequent iterations. 
 This leads to a noticeable speedup of the global convergence time of the load balancing process.  
 

-\item We use SimGrid simulator which is known to be able to characterize and modelize realistic models of computation and communication in different types of platforms. We show that taking into account both loads transfers' costs and network contention is essential and has a real impact on the quality of the load balancing performances. 
+\item We use SimGrid simulator which is known to be able to characterize and model realistic models of computation and communication in different types of platforms. We show that taking into account both loads transfers' costs and network contention is essential and has a real impact on the quality of the load balancing performances. 

 
 %\item We improve the straightforward network's diameter bound of the global equilibrium threshold in the network. % not sure, it depends on the remaining time before the paper submission ...
 \end{itemize}
 
 %\item We improve the straightforward network's diameter bound of the global equilibrium threshold in the network. % not sure, it depends on the remaining time before the paper submission ...
 \end{itemize}


@@ -423,7 +423,7 @@ This is particularly true with strongly connected applications.
 In order to reduce this effect, we add the ability to level the amount of load to send.
 The idea, here, is to make as few steps as possible toward the equilibrium, such that a
 potentially unsuitable decision pointed above has a lower impact on the local equilibrium.
 In order to reduce this effect, we add the ability to level the amount of load to send.
 The idea, here, is to make as few steps as possible toward the equilibrium, such that a
 potentially unsuitable decision pointed above has a lower impact on the local equilibrium.

-Roughtly speaking, once $s_{ij}$ is estimated as previously explained, it is simply weighted by
+Roughly speaking, once $s_{ij}$ is estimated as previously explained, it is simply weighted by

 a given prescribed threshold parameter which we call 
 %.  This parameter is called 
 $k$ in
 a given prescribed threshold parameter which we call 
 %.  This parameter is called 
 $k$ in


@@ -494,15 +494,12 @@ received yet.
 
 %With integer load, this algorithm has been adapted by rounding the load value. In fact, we consider that the total amount of load is big enough and that it can be split with integer numbers.
 
 
 %With integer load, this algorithm has been adapted by rounding the load value. In fact, we consider that the total amount of load is big enough and that it can be split with integer numbers.
 

-\medskip 
-{\bf ****** je suis arrivé ici ******** la conclusion est déjà écrite ******}
-{\bf ****** ça serait, peut être, mieux de déplacer la section de "Threads manangement" ici dans cette section  et ll'appler éventuellement "Computation (ou Load) and message passing threads management" ******}
-\medskip
+

 
 
 %\FIXME{describe integer mode}
 
 
 
 %\FIXME{describe integer mode}
 

-\section{Simulations}
+\section{Implementation with SimGrid and simulations}

 \label{sec.simulations}
 
 In order to test and validate our approaches, we wrote a simulator
 \label{sec.simulations}
 
 In order to test and validate our approaches, we wrote a simulator


@@ -678,38 +675,41 @@ To summarize the different load balancing strategies, we have:
 \item[\textbf{strategies:}] \makhoul{}, or \besteffort{} with $k\in
   \{1,2,4\}$
 \item[\textbf{variants:}] with, or without virtual load
 \item[\textbf{strategies:}] \makhoul{}, or \besteffort{} with $k\in
   \{1,2,4\}$
 \item[\textbf{variants:}] with, or without virtual load

-\item[\textbf{domain:}] real load, or integer load
+%\item[\textbf{domain:}] real load, or integer load

 \end{description}
 %
 \end{description}
 %

-This gives us as many as $4\times 2\times 2 = 16$ different strategies.
+%This gives us as many as $4\times 2\times 2 = 16$ different strategies.

 
 \subsubsection{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
 
 \subsubsection{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).
+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 is obviously not realistic.  In a
-real application we would have chosen a decentralized convergence detection
-algorithm, like the one described in \cite{ccl09:ij}.
+%Note that this convergence detection was implemented in a centralized manner.
+%This is easy to do within the simulator, but it is obviously not realistic.  In a
+%real application we would have chosen a decentralized convergence detection
+%algorithm, like the one described in \cite{ccl09:ij}.

 
 

-\subsubsection{Platforms}
+\subsubsection{Platform}

 
 

-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 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.
+%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 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 are 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
+%The clusters are 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.
+
+In order to make our experiments, an 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
 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


@@ -740,31 +740,30 @@ three different kinds of applications:
 \item balanced, with a computation/communication cost ratio of $1/1$.
 \end{itemize}
 
 \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), 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 cost 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,  $16\times 144 =
-2,304$ distinct settings have been evaluated.  In fact, as it will be shown later, only configations with a maximum number of 1,024 nodes are considered in order to limit the time of experiments.
+% To summarize the various configurations, we have:
+% \begin{description}
+% \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 cost 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,  $16\times 144 =
+% 2,304$ distinct settings have been evaluated.  In fact, as it will be shown later, only configurations with a maximum number of 1,024 nodes are considered in order to limit the time of experiments.

 
 
 \subsubsection{Metrics}
 \label{sec.metrics}
 
 
 
 \subsubsection{Metrics}
 \label{sec.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
+In order to evaluate and compare the different load balancing strategies we define several metrics.  Our goal, when choosing these metrics, is to have

 something tending to a constant value, i.e. to have a measure which is not
 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
+changing anymore once the convergence state is reached.  Moreover, we want to

 have some normalized value, in order to be able to compare them across different
 settings.
 
 have some normalized value, in order to be able to compare them across different
 settings.
 


@@ -772,30 +771,31 @@ With these constraints in mind, we define the following metrics:
 %
 \begin{description}
 \item[\textbf{average idle time:}] that is the total time spent, when the nodes
 %
 \begin{description}
 \item[\textbf{average idle time:}] that is the total time spent, when the nodes

-  do not 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 is the average of the dates when
-  all nodes reached the convergence state.  The dates are measured as a number
+  do not 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 time:}] that is the average of the times when
+  all nodes reached the convergence state.  Times are measured as a number

   of (simulated) seconds since the beginning of the simulation.
 
   of (simulated) seconds since the beginning of the simulation.
 

-\item[\textbf{maximum convergence date:}] that is the date when the last node
+\item[\textbf{maximum convergence time:}] that is the time when the last node

   reached the convergence state.
   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.

 
 

-  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 is 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.

 
 

-\item[\textbf{data transfer amount:}] that is 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.
+%   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}
 
 
 \end{description}
 


@@ -806,22 +806,22 @@ With these constraints in mind, we define the following metrics:
 In this section, the results for the different simulations are presented,
 and our observations are explained.
 
 In this section, the results for the different simulations are presented,
 and our observations are explained.
 

-\subsubsection{Cluster versus grid platforms}
+% \subsubsection{Cluster versus grid platforms}

 
 

-As mentioned earlier, different algorithms have been simulated on two kinds of
-physical platforms: clusters and grids.  A first observation,
-is that the graphs we draw from the data have a similar aspect for the two kinds
-of platforms.  The only noticeable difference is that the algorithms need a bit
-more time to achieve the convergence on the grid platforms, than on clusters.
-Nevertheless their relative performances remain generally similar.
+% As mentioned earlier, different algorithms have been simulated on two kinds of
+% physical platforms: clusters and grids.  A first observation,
+% is that the graphs we draw from the data have a similar aspect for the two kinds
+% of platforms.  The only noticeable difference is that the algorithms need a bit
+% more time to achieve the convergence on the grid platforms, than on clusters.
+% Nevertheless their relative performances remain generally similar.

 
 

-This suggests that the relative performances of the different strategies are not
-influenced by the characteristics of the physical platform.  The differences in
-the convergence times can be explained by the fact that on the grid platforms,
-distant sites are interconnected by links of smaller bandwidth.
+% This suggests that the relative performances of the different strategies are not
+% influenced by the characteristics of the physical platform.  The differences in
+% the convergence times can be explained by the fact that on the grid platforms,
+% distant sites are interconnected by links of smaller bandwidth.

 
 

-Therefore, in the following, we only discuss the results for the grid
-platforms.
+% Therefore, in the following, we only discuss the results for the grid
+% platforms.

 
 \subsubsection{Main results}
 
 
 \subsubsection{Main results}
 


@@ -833,7 +833,8 @@ platforms.
   \includegraphics[width=.5\linewidth]{data/graphs/R1-1:10-grid-torus}
   \includegraphics[width=.5\linewidth]{data/graphs/R1-10:1-grid-hcube}%
   \includegraphics[width=.5\linewidth]{data/graphs/R1-1:10-grid-hcube}
   \includegraphics[width=.5\linewidth]{data/graphs/R1-1:10-grid-torus}
   \includegraphics[width=.5\linewidth]{data/graphs/R1-10:1-grid-hcube}%
   \includegraphics[width=.5\linewidth]{data/graphs/R1-1:10-grid-hcube}

-  \caption{Real mode, initially on an only mode, comp/comm cost ratio = $10/1$ (left), or $1/10$ (right).}
+  \caption{Real mode, initially on an only mode, comp/comm cost ratio = $10/1$ (left), or $1/10$ (right). For each bar, from bottom to top, the first part represents the average idle
+time, the second part represents the average convergence time, and then the third part represents the maximum convergence time.}

   \label{fig.results1}
 \end{figure*}
 
   \label{fig.results1}
 \end{figure*}
 


@@ -866,13 +867,14 @@ an hypercube.
 
 Finally, on the graphs, the vertical bars show the measured times for each of
 the algorithms.  These measured times are, from bottom to top, the average idle
 
 Finally, on the graphs, the vertical bars show the measured times for each of
 the algorithms.  These measured times are, from bottom to top, the average idle

-time, the average convergence date, and the maximum convergence date (see
+time, the average convergence time, and the maximum convergence time (see

 Section~\ref{sec.metrics}).  The measurements are repeated for the different
 Section~\ref{sec.metrics}).  The measurements are repeated for the different

-platform sizes.  Some bars are missing, specially for large platforms.  This is
+platform sizes.  Some bars are missing, especially for large platforms.  This is

 either because the algorithm did not reach the convergence state in the
 either because the algorithm did not reach the convergence state in the

-allocated time, or because we simply decided not to run it.
+allocated time.
+

 
 

-\FIXME{annoncer le plan de la suite}
+%\FIXME{annoncer le plan de la suite}

 
 \subsubsection{The \besteffort{} and  \makhoul{} strategies without virtual load}
 
 
 \subsubsection{The \besteffort{} and  \makhoul{} strategies without virtual load}
 


@@ -906,6 +908,9 @@ all the  neighbors.  In opposition,  the \besteffort{} strategy  distributes the
 load fairly so this strategy is better for low connected strategy.
 
 
 load fairly so this strategy is better for low connected strategy.
 
 

+
+
+

 \subsubsection{Virtual load}
 
 The influence of virtual load is most of the time really significant compared to
 \subsubsection{Virtual load}
 
 The influence of virtual load is most of the time really significant compared to


@@ -919,6 +924,9 @@ virtual load has been balanced  between all the processors. So consequently they
 cannot  compute  at  the  beginning.  This is  especially  noticeable  when  the
 communication are slow (on the left part of Figure ~\ref{fig.results1}.
 
 cannot  compute  at  the  beginning.  This is  especially  noticeable  when  the
 communication are slow (on the left part of Figure ~\ref{fig.results1}.
 

+On Figure \ref{fig.resultsN} when the load to balance is initially randomly distributed over all nodes, we can see that the effect of virtual load is not significant for the line. For the torus with the mainly communicating case (on the left of the figure), the effect of the virtual load is very significant. For the hypercube, in any case, the effect of the virtual load is visible. It is more visible when communications have a more important role (i.e. with the mainly communicating case).
+
+

 %Dans ce cas  légère amélioration de la cvg. max.  Temps  moyen de cvg. amélioré,
 %mais plus de temps passé en idle, surtout quand les comms coutent cher.
 
 %Dans ce cas  légère amélioration de la cvg. max.  Temps  moyen de cvg. amélioré,
 %mais plus de temps passé en idle, surtout quand les comms coutent cher.
 


@@ -942,20 +950,21 @@ communication are slow (on the left part of Figure ~\ref{fig.results1}.
 
 As  explained  previously when  the  communication  are  slow the  \besteffort{}
 strategy is efficient. This is due to the fact that it tries to balance the load
 
 As  explained  previously when  the  communication  are  slow the  \besteffort{}
 strategy is efficient. This is due to the fact that it tries to balance the load

-fairly and consequently  a significant amount of the  load is transfered between
+fairly and consequently  a significant amount of the  load is transferred between

 processors.  In this situation, it is possible to reduce the convergence time by
 using  the leveler  parameter  (parameter  $k$).  The  advantage  of using  this
 solution is particularly efficient when the initial load is randomly distributed
 on  the nodes with  torus and  hypercube topologies  and slow  communication. When
 virtual load  mechanism is used,  the effect of  this parameter is  also visible
 processors.  In this situation, it is possible to reduce the convergence time by
 using  the leveler  parameter  (parameter  $k$).  The  advantage  of using  this
 solution is particularly efficient when the initial load is randomly distributed
 on  the nodes with  torus and  hypercube topologies  and slow  communication. When
 virtual load  mechanism is used,  the effect of  this parameter is  also visible

-with the same condition.
+with the same condition. However, sometimes this parameter may have a negative effect on the convergence time.
+

 
 
 
 \subsubsection{With integer load}
 
 We also performed  some experiments with integer load instead  of load with real
 
 
 
 \subsubsection{With integer load}
 
 We also performed  some experiments with integer load instead  of load with real

-value.  In  this case, the  results have globally  the same behavior.   The most
+value.  In  this case, the  results have globally  the same behavior, that is why we decided not to show similar figures.   The most

 interesting  result, from  our point  of view,  is that  the virtual  mode allows
 processors in a line topology to converge to the uniform load balancing. Without
 the virtual  load, most  of the time,  processors converge  to what we  call the
 interesting  result, from  our point  of view,  is that  the virtual  mode allows
 processors in a line topology to converge to the uniform load balancing. Without
 the virtual  load, most  of the time,  processors converge  to what we  call the


@@ -969,12 +978,11 @@ obtain 10 9 8 7 6 6 7 8 9 10 instead of 8 8 8 8 8 8 8 8 8 8).
 %Dans les autres cas, résultats similaires au cas réel: redire que vload est
 %intéressant.
 
 %Dans les autres cas, résultats similaires au cas réel: redire que vload est
 %intéressant.
 

-\FIXME{ajouter une courbe avec l'équilibrage en entier}
+%\FIXME{ajouter une courbe avec l'équilibrage en entier}

 
 

-\FIXME{virer la metrique volume de comms}
+%\FIXME{virer la metrique volume de comms}

 
 

-\FIXME{ajouter une courbe ou on voit l'évolution de la charge en fonction du
-  temps : avec et sans vload}
+%\FIXME{ajouter une courbe ou on voit l'évolution de la charge en fonction du  temps : avec et sans vload}

 
 % \begin{itemize}
 % \item cluster ou grid, entier ou réel, ne font pas de grosses différences
 
 % \begin{itemize}
 % \item cluster ou grid, entier ou réel, ne font pas de grosses différences


@@ -1027,12 +1035,12 @@ Based on SimGrid simulator, we have demonstrated that, when we deal with realist
 
 \section*{Acknowledgments}
 
 
 \section*{Acknowledgments}
 

-Computations have been performed on the supercomputer facilities of the
-Mésocentre de calcul de Franche-Comté.
-
+This  paper  is   partially  funded  by  the  Labex   ACTION  program  (contract
+ANR-11-LABX-01-01).  We also thank the supercomputer facilities of the Mésocentre de calcul de Franche-Comté.
+ 

 \bibliographystyle{elsarticle-num}
 \bibliography{biblio}
 \bibliographystyle{elsarticle-num}
 \bibliography{biblio}

-\FIXME{find and add more references}
+%\FIXME{find and add more references}

 
 \end{document}
 
 
 \end{document}