\usepackage{amsmath}
\usepackage{courier}
\usepackage{graphicx}
+\usepackage{url}
\usepackage[ruled,lined]{algorithm2e}
\newcommand{\abs}[1]{\lvert#1\rvert} % \abs{x} -> |x|
\begin{tabular}[t]{@{}l@{:~}l@{}}}{%
\end{tabular}}
+\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}}
\begin{document}
for asynchronous iterative load balancing}
\author{Raphaël Couturier \and
- Arnaud Giersch \and
- Abderrahmane Sider
+ Arnaud Giersch
}
\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}
- \and
- A. Sider \at
- University of Béjaïa, Béjaïa, Algeria \\
- \email{ar.sider@univ-bejaia.dz}
+ raphael.couturier@femto-st.fr,
+ arnaud.giersch@femto-st.fr}
}
\maketitle
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}.
-{\bf 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
amount of load. Moreover, when real asynchronous applications are considered,
using asynchronous load balancing algorithms can reduce the execution
times. Most of the times, it is simpler to distinguish load information messages
-from data migration messages. Formers ones allows a node to inform its
+from data migration messages. Former ones allows a node to inform its
neighbors of its current load. These messages are very small, they can be sent
quite often. For example, if an computing iteration takes a significant times
(ranging from seconds to minutes), it is possible to send a new load information
network performance and the message size, the time of the reception of the
message also varies.
-In the following of this paper, Section~\ref{BT algo} describes the Bertsekas
-and Tsitsiklis' asynchronous load balancing algorithm. Moreover, we present a
-possible problem in the convergence conditions. Section~\ref{Best-effort}
-presents the best effort strategy which provides an efficient way to reduce the
-execution times. In Section~\ref{Virtual load}, the virtual load mechanism is
-proposed. Simulations allowed to show that both our approaches are valid using a
-quite realistic model detailed in Section~\ref{Simulations}. Finally we give a
-conclusion and some perspectives to this work.
-
+In the following of this paper, Section~\ref{BT algo} describes the Bertsekas
+and Tsitsiklis' asynchronous load balancing algorithm. Moreover, we present a
+possible problem in the convergence conditions. Section~\ref{Best-effort}
+presents the best effort strategy which provides an efficient way to reduce the
+execution times. This strategy will be compared with other ones, presented in
+Section~\ref{Other}. In Section~\ref{Virtual load}, the virtual load mechanism
+is proposed. Simulations allowed to show that both our approaches are valid
+using a quite realistic model detailed in Section~\ref{Simulations}. Finally we
+give a conclusion and some perspectives to this work.
strong. Currently, we did not try to make another convergence proof without this
condition or with a weaker condition.
+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.
\end{equation*}
\end{enumerate}
-\section{Other strategies}
-\label{Other}
+\subsection{Leveling the amount to send}
-\textbf{Question} faut-il décrire les stratégies makhoul et simple ?
+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.
-\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.
+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.
+
+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}]{}
-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}
Doing this, we can expect a faster convergence since nodes have a faster
information of the load they will receive, so they can take in into account.
-\textbf{Question} Est ce qu'on donne l'algo avec virtual load?
+\FIXME{Est ce qu'on donne l'algo avec virtual load?}
+
+\FIXME{describe integer mode}
\section{Simulations}
\label{Simulations}
a \emph{receiving thread}, a \emph{computing thread}, and a
\emph{load-balancing thread}, which we will briefly describe now.
-\paragraph{Receiving thread} The receiving thread is in charge of
-waiting for messages to come, either on the control channel, or on the
-data channel. Its behavior is sketched by Algorithm~\ref{algo.recv}.
-When a message is received, it is pushed in a buffer of
-received message, to be later consumed by one of the other threads.
-There are two such buffers, one for the control messages, and one for
-the data messages. The buffers are implemented with a lock-free FIFO
+For the sake of simplicity, a few details were voluntary omitted from
+these descriptions. For an exhaustive presentation, we refer to the
+actual source code that was used for the experiments%
+\footnote{As mentioned before, our simulator relies on the SimGrid
+ framework~\cite{casanova+legrand+quinson.2008.simgrid}. For the
+ experiments, we used a pre-release of SimGrid 3.7 (Git commit
+ 67d62fca5bdee96f590c942b50021cdde5ce0c07, available from
+ \url{https://gforge.inria.fr/scm/?group_id=12})}, and which is
+available at
+\url{http://info.iut-bm.univ-fcomte.fr/staff/giersch/software/loba.tar.gz}.
+
+\subsubsection{Receiving thread}
+
+The receiving thread is in charge of waiting for messages to come, either on the
+control channel, or on the data channel. Its behavior is sketched by
+Algorithm~\ref{algo.recv}. When a message is received, it is pushed in a buffer
+of received message, to be later consumed by one of the other threads. There
+are two such buffers, one for the control messages, and one for the data
+messages. The buffers are implemented with a lock-free FIFO
\cite{sutter.2008.writing} to avoid contention between the threads.
\begin{algorithm}
}
\end{algorithm}
-\paragraph{Computing thread} The computing thread is in charge of the
-real load management. As exposed in Algorithm~\ref{algo.comp}, it
-iteratively runs the following operations:
+\subsubsection{Computing thread}
+
+The computing thread is in charge of the real load management. As exposed in
+Algorithm~\ref{algo.comp}, it iteratively runs the following operations:
\begin{itemize}
\item if some load was received from the neighbors, get it;
\item if there is some load to send to the neighbors, send it;
}
\end{algorithm}
-\paragraph{Load-balancing thread} The load-balancing thread is in
-charge of running the load-balancing algorithm, and exchange the
-control messages. It iteratively runs the following operations:
+\subsubsection{Load-balancing thread}
+
+The load-balancing thread is in charge of running the load-balancing algorithm,
+and exchange the control messages. As shown in Algorithm~\ref{algo.lb}, it
+iteratively runs the following operations:
\begin{itemize}
\item get the control messages that were received from the neighbors;
\item run the load-balancing algorithm;
}
\end{algorithm}
-\paragraph{}
-For the sake of simplicity, a few details were voluntary omitted from
-these descriptions. For an exhaustive presentation, we refer to the
-actual code that was used for the experiments, and which is
-available at \textbf{FIXME URL}.
-
-\textbf{FIXME: ajouter des détails sur la gestion de la charge virtuelle ?}
+\paragraph{}\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}
-\textbf{FIXME once the experimentation is done!}
+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.
+
+\subsubsection{Load balancing 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[platforms] homogeneous (cluster) ; heterogeneous (subset of Grid5000)
-\item[topologies]
-\item[algorithms]
-\item[etc.]
+\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.
+
+\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).
+
+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}.
+
+\subsubsection{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.
+
+\subsubsection{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), 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.
+
+\subsubsection{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:}] 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}
+
+\subsection{Experimental results}
\label{Results}
+In this section, the results for the different simulations will be presented,
+and we'll try to explain our observations.
+
+\subsubsection{Cluster vs grid platforms}
+
+As mentioned earlier, we simulated the different algorithms on two kinds of
+physical platforms: clusters and grids. A first observation that we can make,
+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 identical.
+
+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 bandwith.
+
+Therefore, in the following, we'll only discuss the results for the grid
+platforms. The different results are presented on the
+figures~\ref{fig.results1} and~\ref{fig.resultsN}.
+
+\FIXME{explain how to read the graphs}
+ratio 1:1 not given here
+
+\begin{figure*}[p]
+ \centering
+ \includegraphics[width=.5\linewidth]{data/graphs/R1-1:10-grid-line}%
+ \includegraphics[width=.5\linewidth]{data/graphs/R1-10:1-grid-line}
+ \includegraphics[width=.5\linewidth]{data/graphs/R1-1:10-grid-torus}%
+ \includegraphics[width=.5\linewidth]{data/graphs/R1-10:1-grid-torus}
+ \includegraphics[width=.5\linewidth]{data/graphs/R1-1:10-grid-hcube}%
+ \includegraphics[width=.5\linewidth]{data/graphs/R1-10:1-grid-hcube}
+ \caption{Real mode, initially on an only mode, comp/comm ratio = 1/10 (left), or 10/1 (right).}
+ \label{fig.results1}
+\end{figure*}
+
+\begin{figure*}[p]
+ \centering
+ \includegraphics[width=.5\linewidth]{data/graphs/RN-1:10-grid-line}%
+ \includegraphics[width=.5\linewidth]{data/graphs/RN-10:1-grid-line}
+ \includegraphics[width=.5\linewidth]{data/graphs/RN-1:10-grid-torus}%
+ \includegraphics[width=.5\linewidth]{data/graphs/RN-10:1-grid-torus}
+ \includegraphics[width=.5\linewidth]{data/graphs/RN-1:10-grid-hcube}%
+ \includegraphics[width=.5\linewidth]{data/graphs/RN-10:1-grid-hcube}
+ \caption{Real mode, random initial distribution, comp/comm ratio = 1/10 (left), or 10/1 (right).}
+ \label{fig.resultsN}
+\end{figure*}
+
+\subsubsection{Main results}
+
+On fig.~\ref{fig.results1}, \dots
+
+\subsubsection{With the virtual load extension}
+
+\subsubsection{The $k$ parameter}
+
+\subsubsection{With an initial random repartition, and larger platforms}
+
+\subsubsection{With integer load}
+
+\FIXME{what about the amount of data?}
+
+\begin{itshape}
+\FIXME{remove that part}
+Dans cet ordre:
+...
+- comparer be/makhoul -> be tient la route
+ -> en réel uniquement
+- valider l'extension virtual load -> c'est 'achement bien
+- proposer le -k -> ça peut aider dans certains cas
+- conclure avec la version entière -> on n'a pas l'effet d'escalier !
+Q: comment inclure les types/tailles de platesformes ?
+Q: comment faire des moyennes ?
+Q: comment introduire les distrib 1/N ?
+...
+
+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?
-On veut montrer quoi ? :
+\item option $k$? peut-être intéressant sur des plateformes fortement interconnectées (hypercube)
-1) best plus rapide que les autres (simple, makhoul)
-2) avantage virtual load
+\item volume de comm? souvent, besteffort/plain en fait plus. pourquoi?
-Est ce qu'on peut trouver des contre exemple?
-Topologies variées
+\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.
-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
+\end{itemize}
+
+% On veut montrer quoi ? :
+
+% 1) best plus rapide que les autres (simple, makhoul)
+% 2) avantage virtual load
+% Est ce qu'on peut trouver des contre exemple?
+% Topologies variées
-Expés avec ratio calcul/comm rapide et lent
-Quelques expés avec charge initiale aléatoire plutot que sur le premier proc
+% 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
-Cadre processeurs homogènes
+% Expés avec ratio calcul/comm rapide et lent
-Topologies statiques
+% Quelques expés avec charge initiale aléatoire plutot que sur le premier proc
-On ne tient pas compte de la vitesse des liens donc on la considère homogène
+% Cadre processeurs homogènes
-Prendre un réseau hétérogène et rendre processeur homogène
+% Topologies statiques
-Taille : 10 100 très gros
+% 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}
%%% Local Variables:
%%% mode: latex
%%% TeX-master: t
+%%% fill-column: 80
%%% ispell-local-dictionary: "american"
%%% End:
% 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 pre
+% LocalWords: FEMTO Makhoul's fca bdee cdde Contassot Vivier underlaid
