supercomp11/supercomp11.tex

   1 \documentclass[smallextended]{svjour3}
   2 \usepackage[utf8]{inputenc}
   3 \usepackage[T1]{fontenc}
   4 \usepackage{mathptmx}
   5 \usepackage{amsmath}
   6 \usepackage{courier}
   7 \usepackage{graphicx}
   8
   9 \newcommand{\abs}[1]{\lvert#1\rvert} % \abs{x} -> |x|
  10
  11 \begin{document}
  12
  13 \title{Best effort strategy and virtual load
  14   for asynchronous iterative load balancing}
  15
  16 \author{Raphaël Couturier \and
  17         Arnaud Giersch \and
  18         Abderrahmane Sider
  19 }
  20
  21 \institute{R. Couturier \and A. Giersch \at
  22               LIFC, University of Franche-Comté, Belfort, France \\
  23               % Tel.: +123-45-678910\\
  24               % Fax: +123-45-678910\\
  25               \email{%
  26                 raphael.couturier@univ-fcomte.fr,
  27                 arnaud.giersch@univ-fcomte.fr}
  28            \and
  29            A. Sider \at
  30               University of Béjaïa, Béjaïa, Algeria \\
  31               \email{ar.sider@univ-bejaia.dz}
  32 }
  33
  34 \maketitle
  35
  36
  37 \begin{abstract}
  38
  39 Most of the  time, asynchronous load balancing algorithms  have extensively been
  40 studied in a theoretical point  of view. The Bertsekas and Tsitsiklis'
  41 algorithm~\cite[section~7.4]{bertsekas+tsitsiklis.1997.parallel}
  42 is certainly  the most well known  algorithm for which the  convergence proof is
  43 given. From a  practical point of view, when  a node wants to balance  a part of
  44 its  load to some  of its  neighbors, the  strategy is  not described.   In this
  45 paper, we propose a strategy  called \emph{best effort} which tries to balance
  46 the load of a node to all  its less loaded neighbors while ensuring that all the
  47 nodes  concerned by  the load  balancing  phase have  the same  amount of  load.
  48 Moreover,  asynchronous  iterative  algorithms  in which  an  asynchronous  load
  49 balancing  algorithm is  implemented most  of the  time can  dissociate messages
  50 concerning load transfers and message  concerning load information.  In order to
  51 increase  the  converge of  a  load balancing  algorithm,  we  propose a  simple
  52 heuristic called \emph{virtual load} which allows a node that receives an load
  53 information message  to integrate the  load that it  will receive later  in its
  54 load (virtually) and consequently sends a (real) part of its load to some of its
  55 neighbors.  In order to  validate our  approaches, we  have defined  a simulator
  56 based on SimGrid which allowed us to conduct many experiments.
  57
  58
  59 \end{abstract}
  60
  61 \section{Introduction}
  62
  63 Load  balancing algorithms  are  extensively used  in  parallel and  distributed
  64 applications in  order to  reduce the  execution times. They  can be  applied in
  65 different scientific  fields from high  performance computation to  micro sensor
  66 networks.   They are  iterative by  nature.  In  literature many  kinds  of load
  67 balancing  algorithms  have been  studied.   They  can  be classified  according
  68 different  criteria:   centralized  or  decentralized,  in   static  or  dynamic
  69 environment,  with  homogeneous  or  heterogeneous load,  using  synchronous  or
  70 asynchronous iterations, with  a static topology or a  dynamic one which evolves
  71 during time.  In  this work, we focus on  asynchronous load balancing algorithms
  72 where computer nodes  are considered homogeneous and with  homogeneous load with
  73 no external  load. In  this context, Bertsekas  and Tsitsiklis have  proposed an
  74 algorithm which is definitively a reference  for many works. In their work, they
  75 proved that under classical  hypotheses of asynchronous iterative algorithms and
  76 a  special  constraint   avoiding  \emph{ping-pong}  effect,  an  asynchronous
  77 iterative algorithm  converge to  the uniform load  distribution. This  work has
  78 been extended by many authors. For example, Cortés et al., with
  79 DASUD~\cite{cortes+ripoll+cedo+al.2002.asynchronous}, propose a
  80 version working with integer load.  This work was later generalized by
  81 the same authors in \cite{cedo+cortes+ripoll+al.2007.convergence}.
  82 {\bf Rajouter des choses ici}.
  83
  84 Although  the Bertsekas  and Tsitsiklis'  algorithm describes  the  condition to
  85 ensure the convergence,  there is no indication or  strategy to really implement
  86 the load distribution. In other word, a node  can send a part of its load to one
  87 or   many  of   its  neighbors   while  all   the  convergence   conditions  are
  88 followed. Consequently,  we propose a  new strategy called  \emph{best effort}
  89 that tries to balance the load of  a node to all its less loaded neighbors while
  90 ensuring that all the nodes concerned  by the load balancing phase have the same
  91 amount of  load.  Moreover, when real asynchronous  applications are considered,
  92 using  asynchronous   load  balancing   algorithms  can  reduce   the  execution
  93 times. Most of the times, it is simpler to distinguish load information messages
  94 from  data  migration  messages.  Formers  ones  allows  a  node to  inform  its
  95 neighbors of its  current load. These messages are very small,  they can be sent
  96 quite often.  For example, if an  computing iteration takes  a significant times
  97 (ranging from seconds to minutes), it is possible to send a new load information
  98 message at each  neighbor at each iteration. Latter  messages contains data that
  99 migrates from one node to another one. Depending on the application, it may have
 100 sense or not  that nodes try to balance  a part of their load  at each computing
 101 iteration. But the time to transfer a load message from a node to another one is
 102 often much more longer that to  time to transfer a load information message. So,
 103 when a node receives the information  that later it will receive a data message,
 104 it can take this information into account  and it can consider that its new load
 105 is larger.   Consequently, it can  send a part  of it real  load to some  of its
 106 neighbors if required. We call this trick the \emph{virtual load} mechanism.
 107
 108
 109
 110 So, in  this work, we propose a  new strategy for improving  the distribution of
 111 the  load  and  a  simple  but  efficient trick  that  also  improves  the  load
 112 balancing. Moreover, we have conducted  many simulations with SimGrid in order to
 113 validate our improvements are really efficient. Our simulations consider that in
 114 order  to send a  message, a  latency delays  the sending  and according  to the
 115 network  performance and  the message  size, the  time of  the reception  of the
 116 message also varies.
 117
 118 In the  following of this  paper, Section~\ref{BT algo} describes  the Bertsekas
 119 and Tsitsiklis'  asynchronous load balancing  algorithm. Moreover, we  present a
 120 possible  problem  in  the  convergence  conditions.   Section~\ref{Best-effort}
 121 presents the best effort strategy which  provides an efficient way to reduce the
 122 execution  times. In Section~\ref{Virtual  load}, the  virtual load  mechanism is
 123 proposed. Simulations allowed to show that both our approaches are valid using a
 124 quite realistic  model detailed in  Section~\ref{Simulations}. Finally we  give a
 125 conclusion and some perspectives to this work.
 126
 127
 128
 129
 130 \section{Bertsekas  and Tsitsiklis' asynchronous load balancing algorithm}
 131 \label{BT algo}
 132
 133 In  order  prove  the  convergence  of  asynchronous  iterative  load  balancing
 134 Bertsekas         and        Tsitsiklis         proposed         a        model
 135 in~\cite{bertsekas+tsitsiklis.1997.parallel}.   Here we  recall  some notations.
 136 Consider  that  $N={1,...,n}$  processors   are  connected  through  a  network.
 137 Communication links  are represented by  a connected undirected  graph $G=(N,V)$
 138 where $V$ is the set of links connecting different processors. In this work, we
 139 consider that  processors are  homogeneous for sake  of simplicity. It  is quite
 140 easy to tackle the  heterogeneous case~\cite{ElsMonPre02}. Load of processor $i$
 141 at  time $t$  is  represented  by $x_i(t)\geq  0$.   Let $V(i)$  be  the set  of
 142 neighbors of processor  $i$.  Each processor $i$ has an estimate  of the load of
 143 each  of its  neighbors $j  \in V(i)$  represented by  $x_j^i(t)$.  According to
 144 asynchronism and communication  delays, this estimate may be  outdated.  We also
 145 consider that the load is described by a continuous variable.
 146
 147 When a processor  send a part of its  load to one or some of  its neighbors, the
 148 transfer takes time to be completed.  Let $s_{ij}(t)$ be the amount of load that
 149 processor $i$ has transferred to processor $j$ at time $t$ and let $r_{ij}(t)$ be the
 150 amount of  load received by processor $j$  from processor $i$ at  time $t$. Then
 151 the amount of load of processor $i$ at time $t+1$ is given by:
 152 \begin{equation}
 153 x_i(t+1)=x_i(t)-\sum_{j\in V(i)} s_{ij}(t) + \sum_{j\in V(i)} r_{ji}(t)
 154 \label{eq:ping-pong}
 155 \end{equation}
 156
 157
 158 Some  conditions are  required to  ensure the  convergence. One  of them  can be
 159 called the \emph{ping-pong} condition which specifies that:
 160 \begin{equation}
 161 x_i(t)-\sum _{k\in V(i)} s_{ik}(t) \geq x_j^i(t)+s_{ij}(t)
 162 \end{equation}
 163 for any  processor $i$ and any  $j \in V(i)$ such  that $x_i(t)>x_j^i(t)$.  This
 164 condition aims  at avoiding a processor  to send a  part of its load  and being
 165 less loaded after that.
 166
 167 Nevertheless,  we  think that  this  condition may  lead  to  deadlocks in  some
 168 cases. For example, if we consider  only three processors and that processor $1$
 169 is linked to processor $2$ which is  also linked to processor $3$ (i.e. a simple
 170 chain which 3 processors). Now consider we have the following values at time $t$:
 171 \begin{eqnarray*}
 172 x_1(t)=10   \\
 173 x_2(t)=100   \\
 174 x_3(t)=99.99\\
 175  x_3^2(t)=99.99\\
 176 \end{eqnarray*}
 177 In this case, processor $2$ can  either sends load to processor $1$ or processor
 178 $3$.   If  it  sends  load  to  processor $1$  it  will  not  satisfy  condition
 179 (\ref{eq:ping-pong})  because  after the  sending  it  will  be less  loaded  that
 180 $x_3^2(t)$.  So we consider that the \emph{ping-pong} condition is probably to
 181 strong. Currently, we did not try to make another convergence proof without this
 182 condition or with a weaker condition.
 183
 184
 185 \section{Best effort strategy}
 186 \label{Best-effort}
 187
 188 We will describe here a new load-balancing strategy that we called
 189 \emph{best effort}.  The general idea behind this strategy is, for a
 190 processor, to send some load to the most of its neighbors, doing its
 191 best to reach the equilibrium between those neighbors and himself.
 192
 193 More precisely, when a processors $i$ is in its load-balancing phase,
 194 he proceeds as following.
 195 \begin{enumerate}
 196 \item First, the neighbors are sorted in non-decreasing order of their
 197   known loads $x^i_j(t)$.
 198
 199 \item Then, this sorted list is traversed in order to find its largest
 200   prefix such as the load of each selected neighbor is lesser than:
 201   \begin{itemize}
 202   \item the processor's own load, and
 203   \item the mean of the loads of the selected neighbors and of the
 204     processor's load.
 205   \end{itemize}
 206   Let's call $S_i(t)$ the set of the selected neighbors, and
 207   $\bar{x}(t)$ the mean of the loads of the selected neighbors and of
 208   the processor load:
 209   \begin{equation*}
 210     \bar{x}(t) = \frac{1}{\abs{S_i(t)} + 1}
 211       \left( x_i(t) + \sum_{j\in S_i(t)} x^i_j(t) \right)
 212   \end{equation*}
 213   The following properties hold:
 214   \begin{equation*}
 215     \begin{cases}
 216       S_i(t) \subset V(i) \\
 217       x^i_j(t) < x_i(t) & \forall j \in S_i(t) \\
 218       x^i_j(t) < \bar{x} & \forall j \in S_i(t) \\
 219       x^i_j(t) \leq x^i_k(t) & \forall j \in S_i(t), \forall k \in V(i) \setminus S_i(t) \\
 220       \bar{x} \leq x_i(t)
 221     \end{cases}
 222   \end{equation*}
 223
 224 \item Once this selection is completed, processor $i$ sends to each of
 225   the selected neighbor $j\in S_i(t)$ an amount of load $s_{ij}(t) =
 226   \bar{x} - x^i_j(t)$.
 227
 228   From the above equations, and notably from the definition of
 229   $\bar{x}$, it can easily be verified that:
 230   \begin{equation*}
 231     \begin{cases}
 232       x_i(t) - \sum_{j\in S_i(t)} s_{ij}(t) = \bar{x} \\
 233       x^i_j(t) + s_{ij}(t) = \bar{x} & \forall j \in S_i(t)
 234     \end{cases}
 235   \end{equation*}
 236 \end{enumerate}
 237
 238 \section{Other strategies}
 239 \label{Other}
 240
 241 \textbf{Question} faut-il décrire les stratégies makhoul et simple ?
 242
 243 \paragraph{simple} Tentative de respecter simplement les conditions de Bertsekas.
 244 Parmi les voisins moins chargés que soi, on sélectionne :
 245 \begin{itemize}
 246 \item un des moins chargés (vmin) ;
 247 \item un des plus chargés (vmax),
 248 \end{itemize}
 249 puis on équilibre avec vmin en s'assurant que notre charge reste
 250 toujours supérieure à celle de vmin et à celle de vmax.
 251
 252 On envoie donc (avec "self" pour soi-même) :
 253 \[
 254     \min\left(\frac{load(self) - load(vmin)}{2}, load(self) - load(vmax)\right)
 255 \]
 256
 257 \paragraph{makhoul} Ordonne les voisins du moins chargé au plus chargé
 258 puis calcule les différences de charge entre soi-même et chacun des
 259 voisins.
 260
 261 Ensuite, pour chaque voisin, dans l'ordre, et tant qu'on reste plus
 262 chargé que le voisin en question, on lui envoie 1/(N+1) de la
 263 différence calculée au départ, avec N le nombre de voisins.
 264
 265 C'est l'algorithme~2 dans~\cite{bahi+giersch+makhoul.2008.scalable}.
 266
 267 \section{Virtual load}
 268 \label{Virtual load}
 269
 270 \section{Simulations}
 271 \label{Simulations}
 272
 273 In order to test and validate our approaches, we wrote a simulator
 274 using the SimGrid
 275 framework~\cite{casanova+legrand+quinson.2008.simgrid}.  This
 276 simulator, which consists of about 2,700 lines of C++, allows to run
 277 the different load-balancing strategies under various parameters, such
 278 as the initial distribution of load, the interconnection topology, the
 279 characteristics of the running platform, etc.  Then several metrics
 280 are issued that permit to compare the strategies.
 281
 282 The simulation model is detailed in the next section (\ref{Sim
 283   model}), then the results of the simulations are presented in
 284 section~\ref{Results}.
 285
 286 \subsection{Simulation model}
 287 \label{Sim model}
 288
 289 In the simulation model the processors exchange messages which are of
 290 two kinds.  First, there are \emph{control messages} which only carry
 291 information that is exchanged between the processors, such as the
 292 current load, or the virtual load transfers if this option is
 293 selected.  These messages are rather small, and their size is
 294 constant.  Then, there are \emph{data messages} that carry the real
 295 load transferred between the processors.  The size of a data message
 296 is a function of the amount of load that it carries, and it can be
 297 pretty large.  In order to receive the messages, each processor has
 298 two receiving channels, one for each kind of messages.  Finally, when
 299 a message is sent or received, this is done by using the non-blocking
 300 primitives of SimGrid\footnote{That are \texttt{MSG\_task\_isend()},
 301   and \texttt{MSG\_task\_irecv()}.}.
 302
 303 During the simulation, each processor concurrently runs three threads:
 304 a \emph{receiving thread}, a \emph{computing thread}, and a
 305 \emph{load-balancing thread}, which we will briefly describe now.
 306
 307 \paragraph{Receiving thread} The receiving thread is in charge of
 308 waiting for messages to come, either on the control channel, or on the
 309 data channel.  When a message is received, it is pushed in a buffer of
 310 received message, to be later consumed by one of the other threads.
 311 There are two such buffers, one for the control messages, and one for
 312 the data messages.  The buffers are implemented with a lock-free FIFO
 313 \cite{sutter.2008.writing} to avoid contention between the threads.
 314
 315 \paragraph{Computing thread} The computing thread is in charge of the
 316 real load management.  It iteratively runs the following operations:
 317 \begin{itemize}
 318 \item if some load was received from the neighbors, get it;
 319 \item if there is some load to send to the neighbors, send it;
 320 \item run some computation, whose duration is function of the current
 321   load of the processor.
 322 \end{itemize}
 323 Practically, after the computation, the computing thread waits for a
 324 small amount of time if the iterations are looping too fast (for
 325 example, when the current load is zero).
 326
 327 \paragraph{Load-balancing thread} The load-balancing thread is in
 328 charge of running the load-balancing algorithm, and exchange the
 329 control messages.  It iteratively runs the following operations:
 330 \begin{itemize}
 331 \item get the control messages that were received from the neighbors;
 332 \item run the load-balancing algorithm;
 333 \item send control messages to the neighbors, to inform them of the
 334   processor's current load, and possibly of virtual load transfers;
 335 \item wait a minimum (configurable) amount of time, to avoid to
 336   iterate too fast.
 337 \end{itemize}
 338
 339 \subsection{Validation of our approaches}
 340 \label{Results}
 341
 342
 343 On veut montrer quoi ? :
 344
 345 1) best plus rapide que les autres (simple, makhoul)
 346 2) avantage virtual load
 347
 348 Est ce qu'on peut trouver des contre exemple?
 349 Topologies variées
 350
 351
 352 Simulation avec temps définies assez long et on mesure la qualité avec : volume de calcul effectué, volume de données échangées
 353 Mais aussi simulation avec temps court qui montre que seul best converge
 354
 355
 356 Expés avec ratio calcul/comm rapide et lent
 357
 358 Quelques expés avec charge initiale aléatoire plutot que sur le premier proc
 359
 360 Cadre processeurs homogènes
 361
 362 Topologies statiques
 363
 364 On ne tient pas compte de la vitesse des liens donc on la considère homogène
 365
 366 Prendre un réseau hétérogène et rendre processeur homogène
 367
 368 Taille : 10 100 très gros
 369
 370 \section{Conclusion and perspectives}
 371
 372
 373 \bibliographystyle{spmpsci}
 374 \bibliography{biblio}
 375
 376 \end{document}
 377
 378 %%% Local Variables:
 379 %%% mode: latex
 380 %%% TeX-master: t
 381 %%% ispell-local-dictionary: "american"
 382 %%% End:
 383
 384 % LocalWords:  Raphaël Couturier Arnaud Giersch Abderrahmane Sider Franche ij
 385 % LocalWords:  Bertsekas Tsitsiklis SimGrid DASUD Comté Béjaïa asynchronism ji
 386 % LocalWords:  ik isend irecv