-\documentclass[smallextended]{svjour3}
+\documentclass[preprint]{elsarticle}
+
\usepackage[utf8]{inputenc}
\usepackage[T1]{fontenc}
-\usepackage{mathptmx}
+
+%\usepackage{newtxtext}
+%\usepackage[cmintegrals]{newtxmath}
+\usepackage{mathptmx,helvet,courier}
+
\usepackage{amsmath}
-\usepackage{courier}
\usepackage{graphicx}
\usepackage{url}
\usepackage[ruled,lined]{algorithm2e}
-\newcommand{\abs}[1]{\lvert#1\rvert} % \abs{x} -> |x|
-
-\newenvironment{algodata}{%
- \begin{tabular}[t]{@{}l@{:~}l@{}}}{%
- \end{tabular}}
-
+%%% Remove this before submission
\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{\abs}[1]{\lvert#1\rvert} % \abs{x} -> |x|
+
+\newenvironment{algodata}{%
+ \begin{tabular}[t]{@{}l@{:~}l@{}}}{%
+ \end{tabular}}
+
\newcommand{\VAR}[1]{\textit{#1}}
-\begin{document}
+\newcommand{\besteffort}{\emph{best effort}}
+\newcommand{\makhoul}{\emph{Makhoul}}
-\title{Best effort strategy and virtual load
- for asynchronous iterative load balancing}
+\begin{document}
-\author{Raphaël Couturier \and
- Arnaud Giersch
-}
+\begin{frontmatter}
-\institute{R. Couturier \and A. Giersch \at
- FEMTO-ST, University of Franche-Comté, Belfort, France \\
- % Tel.: +123-45-678910\\
- % Fax: +123-45-678910\\
- \email{%
- raphael.couturier@femto-st.fr,
- arnaud.giersch@femto-st.fr}
-}
+\journal{Parallel Computing}
-\maketitle
+\title{Best effort strategy and virtual load for\\
+ asynchronous iterative load balancing}
+\author{Raphaël Couturier}
+\ead{raphael.couturier@femto-st.fr}
-\begin{abstract}
+\author{Arnaud Giersch\corref{cor}}
+\ead{arnaud.giersch@femto-st.fr}
-Most of the time, asynchronous load balancing algorithms have extensively been
-studied in a theoretical point of view. The Bertsekas and Tsitsiklis'
-algorithm~\cite[section~7.4]{bertsekas+tsitsiklis.1997.parallel}
-is certainly the most well known algorithm for which the convergence proof is
-given. From a practical point of view, when a node wants to balance a part of
-its load to some of its neighbors, the strategy is not described. In this
-paper, we propose a strategy called \emph{best effort} which tries to balance
-the load of a node to all its less loaded neighbors while ensuring that all the
-nodes concerned by the load balancing phase have the same amount of load.
-Moreover, asynchronous iterative algorithms in which an asynchronous load
-balancing algorithm is implemented most of the time can dissociate messages
-concerning load transfers and message concerning load information. In order to
-increase the converge of a load balancing algorithm, we propose a simple
-heuristic called \emph{virtual load} which allows a node that receives a load
-information message to integrate the load that it will receive later in its
-load (virtually) and consequently sends a (real) part of its load to some of its
-neighbors. In order to validate our approaches, we have defined a simulator
-based on SimGrid which allowed us to conduct many experiments.
+\address{%
+ Institut FEMTO-ST (UMR 6174),
+ Université de Franche-Comté (UFC),
+ Centre National de la Recherche Scientifique (CNRS),
+ École Nationale Supérieure de Mécanique et des Microtechniques (ENSMM),
+ Université de Technologie de Belfort Montbéliard (UTBM)\\
+ 19 avenue du Maréchal Juin, BP 527, 90016 Belfort cedex, France}
+\cortext[cor]{Corresponding author.}
+\begin{abstract}
+ Most of the time, asynchronous load balancing algorithms have extensively been
+ studied in a theoretical point of view. The Bertsekas and Tsitsiklis'
+ algorithm~\cite[section~7.4]{bertsekas+tsitsiklis.1997.parallel} is certainly
+ the most well known algorithm for which the convergence proof is given. From a
+ practical point of view, when a node wants to balance a part of its load to
+ some of its neighbors, the strategy is not described. In this paper, we
+ propose a strategy called \besteffort{} which tries to balance the load
+ of a node to all its less loaded neighbors while ensuring that all the nodes
+ concerned by the load balancing phase have the same amount of load. Moreover,
+ asynchronous iterative algorithms in which an asynchronous load balancing
+ algorithm is implemented most of the time can dissociate messages concerning
+ load transfers and message concerning load information. In order to increase
+ the converge of a load balancing algorithm, we propose a simple heuristic
+ called \emph{virtual load} which allows a node that receives a load
+ information message to integrate the load that it will receive later in its
+ load (virtually) and consequently sends a (real) part of its load to some of
+ its neighbors. In order to validate our approaches, we have defined a
+ simulator based on SimGrid which allowed us to conduct many experiments.
\end{abstract}
+% \begin{keywords}
+% %% keywords here, in the form: keyword \sep keyword
+% \end{keywords}
+
+\end{frontmatter}
+
\section{Introduction}
Load balancing algorithms are extensively used in parallel and distributed
applications in order to reduce the execution times. They can be applied in
different scientific fields from high performance computation to micro sensor
-networks. They are iterative by nature. In literature many kinds of load
+networks. They are iterative by nature.\FIXME{really?}
+In literature many kinds of load
balancing algorithms have been studied. They can be classified according
different criteria: centralized or decentralized, in static or dynamic
environment, with homogeneous or heterogeneous load, using synchronous or
ensure the convergence, there is no indication or strategy to really implement
the load distribution. In other word, a node can send a part of its load to one
or many of its neighbors while all the convergence conditions are
-followed. Consequently, we propose a new strategy called \emph{best effort}
+followed. Consequently, we propose a new strategy called \besteffort{}
that tries to balance the load of a node to all its less loaded neighbors while
ensuring that all the nodes concerned by the load balancing phase have the same
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. Former ones allows a node to inform its
+from data migration messages. Former ones allow 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
+quite often. For example, if a computing iteration takes a significant times
(ranging from seconds to minutes), it is possible to send a new load information
-message at each neighbor at each iteration. Latter messages contains data that
+message to each neighbor at each iteration. Latter messages contain data that
migrates from one node to another one. Depending on the application, it may have
sense or not that nodes try to balance a part of their load at each computing
iteration. But the time to transfer a load message from a node to another one is
is larger. Consequently, it can send a part of it real load to some of its
neighbors if required. We call this trick the \emph{virtual load} mechanism.
-
-
-So, in this work, we propose a new strategy for improving the distribution of
-the load and a simple but efficient trick that also improves the load
-balancing. Moreover, we have conducted many simulations with SimGrid in order to
-validate our improvements are really efficient. Our simulations consider that in
-order to send a message, a latency delays the sending and according to the
-network performance and the message size, the time of the reception of the
+So, in this work, we propose a new strategy to improve the distribution of the
+load and a simple but efficient trick that also improves the load
+balancing. Moreover, we have conducted many simulations with SimGrid in order to
+validate that our improvements are really efficient. Our simulations consider
+that in order to send a message, a latency delays the sending and according to
+the 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. 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.
+In the following of this paper, Section~\ref{sec.bt-algo} describes the
+Bertsekas and Tsitsiklis' asynchronous load balancing algorithm. Moreover, we
+present a possible problem in the convergence conditions.
+Section~\ref{sec.besteffort} 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{sec.other}. In
+Section~\ref{sec.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{sec.simulations}. Finally we give a
+conclusion and some perspectives to this work.
\section{Bertsekas and Tsitsiklis' asynchronous load balancing algorithm}
-\label{BT algo}
+\label{sec.bt-algo}
In order prove the convergence of asynchronous iterative load balancing
Bertsekas and Tsitsiklis proposed a model
in~\cite{bertsekas+tsitsiklis.1997.parallel}. Here we recall some notations.
Consider that $N={1,...,n}$ processors are connected through a network.
-Communication links are represented by a connected undirected graph $G=(N,V)$
-where $V$ is the set of links connecting different processors. In this work, we
+Communication links are represented by a connected undirected graph $G=(N,A)$
+where $A$ is the set of links connecting different processors. In this work, we
consider that processors are homogeneous for sake of simplicity. It is quite
easy to tackle the heterogeneous case~\cite{ElsMonPre02}. Load of processor $i$
at time $t$ is represented by $x_i(t)\geq 0$. Let $V(i)$ be the set of
the amount of load of processor $i$ at time $t+1$ is given by:
\begin{equation}
x_i(t+1)=x_i(t)-\sum_{j\in V(i)} s_{ij}(t) + \sum_{j\in V(i)} r_{ji}(t)
-\label{eq:ping-pong}
+\label{eq.ping-pong}
\end{equation}
cases. For example, if we consider only three processors and that processor $1$
is linked to processor $2$ which is also linked to processor $3$ (i.e. a simple
chain which 3 processors). Now consider we have the following values at time $t$:
-\begin{eqnarray*}
-x_1(t)=10 \\
-x_2(t)=100 \\
-x_3(t)=99.99\\
- x_3^2(t)=99.99\\
-\end{eqnarray*}
-In this case, processor $2$ can either sends load to processor $1$ or processor
-$3$. If it sends load to processor $1$ it will not satisfy condition
-(\ref{eq:ping-pong}) because after the sending it will be less loaded that
+\begin{align*}
+ x_1(t) &= 10 \\
+ x_2(t) &= 100 \\
+ x_3(t) &= 99.99 \\
+ x_3^2(t) &= 99.99 \\
+\end{align*}
+In this case, processor $2$ can either sends load to processor $1$ or processor
+$3$. If it sends load to processor $1$ it will not satisfy condition
+\eqref{eq.ping-pong} because after the sending it will be less loaded that
$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.
algorithm.
\section{Best effort strategy}
-\label{Best-effort}
+\label{sec.besteffort}
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,
+\besteffort{}. 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,
+The general idea behind the \besteffort{} 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.
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}]{}
+Section~\ref{sec.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{sec.results}]{}
\section{Other strategies}
-\label{Other}
+\label{sec.other}
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
+of the new \besteffort{}, 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.
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
+$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.
\section{Virtual load}
-\label{Virtual load}
+\label{sec.virtual-load}
-In this section, we present the concept of \texttt{virtual load}. In order to
+In this section, we present the concept of \emph{virtual load}. In order to
use this concept, load balancing messages must be sent using two different kinds
of messages: load information messages and load balancing messages. More
-precisely, a node wanting to send a part of its load to one of its neighbors,
-can first send a load information message containing the load it will send and
+precisely, a node wanting to send a part of its load to one of its neighbors
+can first send a load information message containing the load it will send, and
then it can send the load balancing message containing data to be transferred.
Load information message are really short, consequently they will be received
very quickly. In opposition, load balancing messages are often bigger and thus
require more time to be transferred.
-The concept of \texttt{virtual load} allows a node that received a load
+The concept of \emph{virtual load} allows a node that received a load
information message to integrate the load that it will receive later in its load
(virtually) and consequently send a (real) part of its load to some of its
neighbors. In fact, a node that receives a load information message knows that
balancing message.
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.
+information of the load they will receive, so they can take it into account.
\FIXME{Est ce qu'on donne l'algo avec virtual load?}
\FIXME{describe integer mode}
\section{Simulations}
-\label{Simulations}
+\label{sec.simulations}
In order to test and validate our approaches, we wrote a simulator
using the SimGrid
-framework~\cite{casanova+legrand+quinson.2008.simgrid}. This
+framework~\cite{simgrid.web,casanova+giersch+legrand+al.2014.simgrid}. This
simulator, which consists of about 2,700 lines of C++, allows to run
the different load-balancing strategies under various parameters, such
as the initial distribution of load, the interconnection topology, the
characteristics of the running platform, etc. Then several metrics
are issued that permit to compare the strategies.
-The simulation model is detailed in the next section (\ref{Sim
- model}), and the experimental contexts are described in
-section~\ref{Contexts}. Then the results of the simulations are
-presented in section~\ref{Results}.
+The simulation model is detailed in the next section (\ref{sec.model}), and the
+experimental contexts are described in section~\ref{sec.exp-context}. Then the
+results of the simulations are presented in section~\ref{sec.results}.
\subsection{Simulation model}
-\label{Sim model}
+\label{sec.model}
In the simulation model the processors exchange messages which are of
two kinds. First, there are \emph{control messages} which only carry
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
+ framework~\cite{casanova+giersch+legrand+al.2014.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
\end{algorithm}
\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}}
+ 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{sec.virtual-load}}
\subsection{Experimental contexts}
-\label{Contexts}
+\label{sec.exp-context}
In order to assess the performances of our algorithms, we ran our
simulator with various parameters, and extracted several metrics, that
\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
+the \besteffort{}, and with the \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},
To summarize the different load balancing strategies, we have:
\begin{description}
-\item[\textbf{strategies:}] \emph{Makhoul}, or \emph{Best effort} with $k\in
+\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
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
+Then we derived each kind of platform with four different numbers of computing
nodes: 16, 64, 256, and 1024 nodes.
\subsubsection{Configurations}
time.
\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
\subsection{Experimental results}
-\label{Results}
+\label{sec.results}
In this section, the results for the different simulations will be presented,
-and we'll try to explain our observations.
+and we will try to explain our observations.
\subsubsection{Cluster vs grid platforms}
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.
+distant sites are interconnected by links of smaller bandwidth.
Therefore, in the following, we'll only discuss the results for the grid
platforms.
when the load to balance is initially randomly distributed over all nodes.
On both figures, the computation/communication cost ratio is $10/1$ on the left
-column, and $1/10$ on the right column. With a computatio/communication cost
+column, and $1/10$ on the right column. With a computation/communication cost
ratio of $1/1$ the results are just between these two extrema, and definitely
don't give additional information, so we chose not to show them here.
are given for the process topology being, from top to bottom, a line, a torus or
an hypercube.
-\FIXME{explain how to read the graphs}
+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
+Section~\ref{sec.metrics}). The measurements are repeated for the different
+platform sizes. Some bars are missing, specially 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.
-each bar -> times for an algorithm
-recall the different times
-no bar -> not run or did not converge in allocated time
+\FIXME{annoncer le plan de la suite}
-repeated for the different platform sizes.
+\subsubsection{The \besteffort{} and \makhoul{} strategies without virtual load}
-\FIXME{donner les premières conclusions, annoncer le plan de la suite}
+Before looking at the different variations, we will first show that the plain
+\besteffort{} strategy is valuable, and may be as good as the \makhoul{}
+strategy. On Figures~\ref{fig.results1} and~\ref{fig.resultsN},
+these strategies are respectively labeled ``b'' and ``a''.
-\subsubsection{With the virtual load extension}
+We can see that the relative performance of these strategies is mainly
+influenced by the application topology. It is for the line topology that the
+difference is the more important. In this case, the \besteffort{} strategy is
+nearly faster than the \makhoul{} strategy. This can be explained by the
+fact that the \besteffort{} strategy tries to distribute the load fairly between
+all the nodes and with the line topology, it is easy to load balance the load
+fairly.
-\subsubsection{The $k$ parameter}
+On the contrary, for the hypercube topology, the \besteffort{} strategy performs
+worse than the \makhoul{} strategy. In this case, the \makhoul{} strategy which
+tries to give more load to few neighbors reaches the equilibrium faster.
-\subsubsection{With an initial random repartition, and larger platforms}
+For the torus topology, for which the number of links is between the line and
+the hypercube, the \makhoul{} strategy is slightly better but the difference is
+more nuanced when the initial load is only on one node. The only case where the
+\makhoul{} strategy is really faster than the \besteffort{} strategy is with the
+random initial distribution when the communication are slow.
-\subsubsection{With integer load}
+Globally the number of interconnection is very important. The more
+the interconnection links are, the faster the \makhoul{} strategy is because
+it distributes quickly significant amount of load, even if this is unfair, between
+all the neighbors. In opposition, the \besteffort{} strategy distributes the
+load fairly so this strategy is better for low connected strategy.
-\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
+\subsubsection{Virtual load}
-\item makhoul? se fait battre sur les grosses plateformes
+The influence of virtual load is most of the time really significant compared to
+the same configuration without it. Sometimes it has no effect but {\bf A
+ VERIFIER} it has never a negative effect on the load balancing we tested.
-\item taille de plateforme?
+On Figure~\ref{fig.results1}, when the load is initially on one node, it can be
+noticed that the average idle times are generally longer with the virtual load
+than without it. This can be explained by the fact that, with virtual load,
+processors will exchange all the load they need to exchange as soon as the
+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}.
-\item ratio comp/comm?
+%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.
-\item option $k$? peut-être intéressant sur des plateformes fortement interconnectées (hypercube)
+%\subsubsection{The \besteffort{} strategy with an initial random load
+% distribution, and larger platforms}
-\item volume de comm? souvent, besteffort/plain en fait plus. pourquoi?
+%In
+%Mêmes conclusions pour line et hcube.
+%Sur tore, BE se fait exploser quand les comms coutent cher.
-\item répartition initiale de la charge ?
+%\FIXME{virer les 1024 ?}
-\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.
+%\subsubsection{With the virtual load extension with an initial random load
+% distribution}
-\end{itemize}
+%Soit c'est équivalent, soit on gagne -> surtout quand les comms coutent cher et
+%qu'il y a beaucoup de voisins.
+
+\subsubsection{The $k$ parameter}
+\label{results-k}
+
+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
+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 topology and slow communication. When
+virtual load mechanism is used, the effect of this parameter is also visible
+with the same condition.
+
+
+
+\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
+intereting 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
+``stairway effect'', that is to say that there is only a difference of one in
+the load of each processor and its neighbors (for example with 10 processors, we
+obtain 10 9 8 7 6 6 7 8 9 10 instead of 8 8 8 8 8 8 8 8 8 8).
+
+%Cas normal, ligne -> converge pas (effet d'escalier).
+%Avec vload, ça converge.
+
+%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{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}
+
+% \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}}
% On veut montrer quoi ? :
% 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}
+\section*{Acknowledgments}
-\FIXME{find and add more references}
-\bibliographystyle{spmpsci}
+Computations have been performed on the supercomputer facilities of the
+Mésocentre de calcul de Franche-Comté.
+
+\bibliographystyle{elsarticle-num}
\bibliography{biblio}
+\FIXME{find and add more references}
\end{document}
%%% 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 Makhoul GFlop xml pre
-% LocalWords: FEMTO Makhoul's fca bdee cdde Contassot Vivier underlaid
+% LocalWords: Raphaël Couturier Arnaud Giersch Franche ij Bertsekas Tsitsiklis
+% LocalWords: SimGrid DASUD Comté asynchronism ji ik isend irecv Cortés et al
+% LocalWords: chan ctrl fifo Makhoul GFlop xml pre FEMTO Makhoul's fca bdee
+% LocalWords: cdde Contassot Vivier underlaid du de Maréchal Juin cedex calcul
+% LocalWords: biblio Institut UMR Université UFC Centre Scientifique CNRS des
+% LocalWords: École Nationale Supérieure Mécanique Microtechniques ENSMM UTBM
+% LocalWords: Technologie Bahi
