From: Arnaud Giersch Date: Tue, 5 Dec 2017 16:56:12 +0000 (+0100) Subject: [sharelatex-git-integration Best effort strategy and virtual load for asynchronous... X-Git-Url: https://bilbo.iut-bm.univ-fcomte.fr/and/gitweb/loba-papers.git/commitdiff_plain/fa2cdc28662b5efc4913918718eaf7a8beaa0919 [sharelatex-git-integration Best effort strategy and virtual load for asynchronous iterative load balancing 2017/12/05 17:56:12] --- diff --git a/loba-besteffort/biblio.bib b/loba-besteffort/biblio.bib index 48537bc..69dd14f 100644 --- a/loba-besteffort/biblio.bib +++ b/loba-besteffort/biblio.bib @@ -321,3 +321,14 @@ pages = {279--301}, year = {1989} } + + + +@book{bcvc07:bc, +author = {Bahi, J. M. and Contassot-Vivier, S. and Couturier, R.}, +title = {Parallel Iterative Algorithms: from sequential to grid computing}, +publisher = {Chapman \& Hall/CRC}, +series = {Numerical Analysis \& Scientific Computating}, +year = 2007, +note = {}, +} \ No newline at end of file diff --git a/loba-besteffort/loba-besteffort.tex b/loba-besteffort/loba-besteffort.tex index ed478e4..55e877c 100644 --- 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 - 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 @@ -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 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} @@ -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. -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 @@ -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. -\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} -\section{Simulations} +\section{Implementation with SimGrid and simulations} \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{domain:}] real load, or integer 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. +%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 -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 @@ -740,31 +740,30 @@ three different kinds of applications: \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} -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 -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. @@ -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 - 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. -\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. + %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} @@ -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. -\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} @@ -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} - \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*} @@ -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 -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 -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 -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} @@ -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. + + + \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}. +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. @@ -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 -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 -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 -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 @@ -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. -\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 @@ -1027,12 +1035,12 @@ Based on SimGrid simulator, we have demonstrated that, when we deal with realist \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} -\FIXME{find and add more references} +%\FIXME{find and add more references} \end{document}