mixage.tex

   1 \JFC{Refaire le châpeau}
   2 \section{Généralisation au cadre asynchrone}
   3 Dans ce chapitre une stratégie $s=(s^{t})^{t \in \Nats}$ est une séquence
   4 \emph{des éléments} qui sont mis à jour au temps $t$. Pratiquement,
   5 on représente ceci comme un nombre décimal dont la représentation en
   6 binaire donne la liste des éléments modifiés. Par exemple, pour un système
   7 à 5 éléments la stratégie définie par
   8 \begin{equation}\label{eq:pseudo}
   9 s^{t}=24 \textrm{ si  $t$ est pair et  } s^{t}=15 \textrm{ sinon }
  10 \end{equation}
  11 \noindent active successivement les deux premiers éléments (24 est 11000)
  12 et les quatre derniers éléments (15  est  01111).
  13 On dit que la stratégie est
  14 \emph{pseudo-periodique}  si tous les éléments sont activés infiniment
  15 souvent.
  16 % , it is sufficient to establish  that the set $\{t \mid t \in \mathbb{N}
  17 % \land \textit{bin}(s^t)[i]  = 1\}$  is infinite for  any $i$,  $1 \le i  \le n$,
  18 % where
  19 % The  synchronous iterations  modes are  defined for  any $i  \in
  20 % \{1,\ldots,n\}$ and any time $t=0,1,2,...$ by:
  21 % \vspace{-.5em}
  22 % \begin{equation}\label{eq:sync}
  23 %   x^{t+1}_i= \left\{
  24 % \begin{array}{l}
  25 % f_i(x^t) \textrm{ if } \textit{bin}(s^t)[i] = 1\\
  26 % x^{t}_i \textrm{ otherwise }
  27 % \end{array}
  28 % \right.
  29 % \end{equation}
  30 % \vspace{-.5em}
  31 % Notice that  parallel iterations only  constrain $s^t$ to be  equal to $2^n-1$
  32 % for any $t$ whereas chaotic iterations do not constrain $s$.
  33 % for  convenient reasons  [[JFC  : a  affiner]],  the set  of components  $\{1,
  34 % \ldots,  n\}$   may  be  partitioned   into  $\alpha$  blocks   $b_1,  \ldots,
  35 % b_{\alpha}$.
  36 % %Elements of $b_i$ are ordered w.r.t. the component number.
  37 % For $1\le i \le \alpha$, let $B_i$ be the product-space of block $i$.
  38 % Formaly, $B_i = \Pi_{j \in b_{i} } E_j$.
  39 % To  ease   the  reading,  lowercase   variable  and  upercase   one  represent
  40 % respectively an element of some $E_i$ and a matrix of elements in some $E_i$.
  41 % The components  may  be updated  (in  a random  order)  according to  a
  42 % strategy $s$, as in the synchronous mode.
  43 Dans le mode asynchrone, a chaque itération $t$, chaque composant peut
  44 mettre à jour son état en
  45 fonction des dernières valeurs qu'il connaît des autre composants.
  46 Obtenir où non les valeurs les plus à jours dépend du temps de calcul et
  47 du temps d'acheminement de celles-ci. On parle de latence, de délai.
  48
  49 Formalisons le mode les itérations asynchrones.
  50 Soit $x^0 =(x_1^0, \ldots, x_n^0)$ une configuration initiale.
  51 Soit $(D^{t})^{t \in  \Nats}$ la suite de matrice de taille $n  \times n$
  52 dont chaque élément $D_{ij}^{t}$ représente la date (inférieure ou égale à $t$)
  53 à laquelle la valeur $x_j$ produite par le composant $j$ devient
  54 disponible au composant $i$.
  55 On considère que le délai entre l'émission par $j$ et la réception par $i$,
  56 défini par $\delta_{ij}^t  = t  - D_{ij}^{t}$ est borné par une constante $\delta_0$ pour tous les $i$, $j$.
  57 Le \emph{mode des itérations asynchrones} est défini pour chaque  $i
  58 \in \{1,\ldots,n\}$ et chaque  $t=0,1,2,...$ par:
  59
  60 \vspace{-.5em}
  61 \begin{equation}\label{eq:async}
  62   x^{t+1}_i= \left\{
  63     \begin{array}{l}
  64       f_i( x_1^{D_{i1}^t},\ldots, x_{n}^{D_{i{n}}^t})
  65       \textrm{ if } \textit{bin}(s^t)[i] = 1\\
  66       x^{t}_i  \textrm{ sinon }
  67     \end{array}
  68   \right.
  69 \end{equation}
  70
  71 \noindent où $\textit{bin}$ convertit un entier en un nombre binaire.
  72 Les itérations de $f$ sont \emph{convergentes} modulo une configuration
  73 initiale  $x^0$,  une  stratégie $s$ et une matrice de dates  $(D^{t})^{t  \in
  74   \Nats}$, si la fonction atteint un point fixe.
  75 Cela revient à vérifier la propriété suivante:
  76 \begin{equation}\label{eq:conv}
  77 \exists t_0 \,.\,
  78 (\forall t  \,.\,
  79 t \geq t_0  \Rightarrow  x^{t}=x^{t_0}).
  80 \end{equation}
  81 Sinon les itérations sont dites \emph{divergentes}.
  82 De plus, si $ (x^{(t)})^{t \in \mathbb{N}}$ défini  selon l'équation
  83 \Equ{eq:async} satisfait \Equ{eq:conv}  pour tous les  $x^{(0)}
  84 \in  E$,  pour toutes les stratégies pseudo périodiques
  85 $s$  et pour toutes les matrices de dates,
  86 $(D^{(t)})^{t  \in \Nats}$, alors les itérations de  $f$ sont
  87 \emph{universellement convergentes}.
  88
  89
  90 \section{Exemple jouet}
  91 On considère cinq éléments prenant à valeurs dans $\Bool$.
  92 Une configuration dans $\Bool^5$ est représentée par un entier entre
  93 0 et 31. La~\Fig{fig:mix:map} donne la fonction définissant la dynamique du
  94 système. La~\Fig{fig:mix:xplgraph} donne le graphe d'interaction associé à cette fonction.
  95 On note que le graphe d'interaction contient cinq cycles. Les résultats
  96 connus~\cite{Bah00} de conditions suffisantes établissant la convergence du système pour les itérations synchrones et asynchrones sont basés sur l'absence de cycles. Ils ne peuvent donc pas être appliqués ici.
  97
  98 \begin{figure}[ht]
  99 \begin{minipage}[b]{0.55\linewidth}
 100   \centering
 101   $ f(x)= \left \{
 102     \begin{array}{lll}
 103       f_1(x_1,x_2,x_3,x_4,x_5) & = & x_1.\overline{x_2} + \overline{x_1}.x_2 \\
 104       f_2(x_1,x_2,x_3,x_4,x_5) & = & \overline{x_1 + x_2}  \\
 105       f_3(x_1,x_2,x_3,x_4,x_5) & = & x_3.\overline{x_1} \\
 106       f_4(x_1,x_2,x_3,x_4,x_5) & = & x_5  \\
 107       f_5(x_1,x_2,x_3,x_4,x_5) & = & \overline{x_3} + x_4
 108     \end{array}
 109   \right.  $
 110 \caption{Fonction $f$ de l'exemple jouet.}
 111 \label{fig:mix:map}
 112 \end{minipage}\hfill
 113 \begin{minipage}[b]{.40\linewidth}
 114   \begin{center}
 115     \includegraphics[scale=0.55]{images/xplgraphmix.eps}
 116   \end{center}
 117   \caption{Graphe d'interaction associé à $f$.}
 118   \label{fig:mix:xplgraph}
 119 \end{minipage}
 120 \end{figure}
 121
 122
 123 \begin{figure}
 124 \begin{minipage}{0.56\linewidth}
 125   \includegraphics[scale=0.55]{images/para_iterate_dec.eps}
 126   \caption{Itérations parallèles de $f$.}\label{fig:mix:xplparaFig}
 127 \end{minipage}
 128 \hfill
 129 \begin{minipage}{0.39\linewidth}
 130   \includegraphics[scale=0.55]{images/chao_iterate_excerpt.eps}
 131   \caption{Extrait d'itérations chaotiques.}
 132   \label{fig:mix:xplchaoFig}
 133 \end{minipage}
 134 \end{figure}
 135
 136 Dans ce qui suit, les  configurations  sont représentées à l'aide d'entiers
 137 plutôt que nombres binaires. Le graphe des itérations parallèles est donné
 138 en~\Fig{fig:mix:xplparaFig}. Depuis n'importe quelle configuration, on constate
 139 qu'il converge vers le point fixe correspondant à l'entier 19.
 140 Un extrait du graphe des itérations chaotiques est donné à
 141 la~\Fig{fig:mix:xplchaoFig}. Les libellés des arcs correspondent aux éléments
 142 activés. Les itérations chaotiques ne convergent pas pour la stratégie
 143 pseudo périodique donnée à l'équation~\Equ{eq:pseudo}:
 144 le système peut infiniment boucler entre 11 et 3, entre 15 et 7.
 145
 146 Comme les itérations chaotiques ne convergent pas pour certaines stratégies,
 147 les itérations asynchrones basées sur les même stratégies peuvent ne pas
 148 converger aussi. Cependant, même si l'on considère que tous les composants
 149 sont activés à chaque itération, c'est à dire si $s^t$ est
 150 constamment égal à $2^n-1$, le délais peut introduire de la divergence.
 151 On considère par exemple la matrice $D^t$ dont chaque élément vaut  $t$
 152 sauf $D^t_{12}$  qui vaut $t-1$ si $t$  est impair.
 153 On a ainsi $x^{t+1}= f(x^{t})$ si $t$ est pair et
 154 $$
 155 x^{t+1}  = \left(
 156 f_1(x_1^{t},x_2^{t-1},x_3^{t},x_4^{t},x_5^{t}), f_2(x^{t}), \ldots,
 157 f_5(x^{t})
 158 \right).
 159 $$
 160 \noindent sinon.
 161 En démarrant de $x^0=00011$, le système atteint $x^1 = 01011$ et boucle entre
 162 ces deux configurations. Pour une même stratégies, les itérations
 163 asynchrones divergent alors que les synchrones convergent.
 164 Les sections suivantes de ce chapitre montrent comment résoudre ce problème.
 165
 166 \section{Itérations Mixes}
 167 Introduit dans~\cite{abcvs05}
 168 le mode d'\emph{itérations mixes} combine synchronisme et asynchronisme.
 169 Intuitivement, les n{\oe}uds qui pourraient introduire des cycles dans
 170 les itérations asynchrones sont regroupés.
 171 Les noeuds à l'intérieur de chaque groupe seront itérés de manière
 172 synchrone.
 173 L'asynchronisme est conservé entre les groupes.
 174
 175 \begin{Def}[Relation de Synchronisation]\label{def:eqrel}
 176   Soit une fonction $f$ et  $\Gamma(f)$ son  graphe d'interaction.
 177   La  \emph{relation de synchronisation} $\eqNode$ est
 178   définie sur l'ensemble des n{\oe}uds par:
 179   $i \eqNode j$ si $i$ et $j$  appartiennent à la même composante fortement
 180   connexe (CFC) dans $\Gamma(F)$.
 181 \end{Def}
 182
 183 On peut facilement démontrer que la relation de synchronisation est une
 184 relation d'équivalence sur l'ensemble des éléments.
 185 On introduit quelques notations: par la suite \class{i} représente la classe
 186 d'équivalence de $i$ et $\mathcal{K}$ représente l'ensemble de toutes
 187 les classe, \textit{i.e.},
 188 $\mathcal{K}=\{1,\ldots,n\}/\eqNode$. On peut définir les itérations mixes.
 189
 190 \begin{Def}[Itérations mixes]
 191 Les itérations mixes d'un système discret suit l'équation \Equ{eq:async} où
 192 de plus   $bin(s^t)[i]=bin(s^t)[j]$ et $D_{ij}^t=D_{ji}^t=t$ si $i \eqNode j$.
 193 \end{Def}
 194
 195 Dans ce contexte, il n'y a plus de délais entre deux noeuds de la même CFC
 196 et leurs mises à jour sont synchronisées.
 197 Cependant, pour $p_0$ et $p_1$ dans la même  classe \class{p},
 198 et $q$ dans une autre classe \class{q}, ce  mode opératoire autorise
 199 des délais différents entre $p_0$ et $q$  et entre  $p_1$ et $q$.
 200 Ainsi $p_1$ et $p_2$ sont distinguables même s'ils appartiennent à la même
 201 classe.
 202 Pour gommer cette distinction, on définit le mode suivant:
 203 \begin{Def}[Itérations mixes avec delais uniformes]
 204   Le mode mixe a des \emph{délais uniformes}si pour chaque
 205   $t=0,1,\ldots$ et pour chaque paire de  classes  $(\class{p}, \class{q})$,
 206   il existe une constante $d^t_{pq}$  telle que la propriété suivante est
 207   établie:
 208   \begin{equation*}
 209 %    \forall t\, .\,      D_{p_0q_0}^{t}  =     D_{p_1q_1}^{t}
 210      \bigwedge_{p_k \in  \class{p}, q_k \in \class{q} }
 211      D_{p_{k}q_{k}}^{t}  =   d_{pq}^t
 212   \end{equation*}
 213   % Je me demande si cette formalisation n'a pas un souci par rapport à une
 214   % formalisation avec un seul q ?! (car deux éléments supposent qu'ils sont distincts)
 215   % car si on a deux éléments dans chaque classe, on peut alors avoir deux
 216   % groupes de délais : supposons (a,b) dans p et (c,d) dans q
 217   % a,c et b,d sont égaux et a,d et b,c sont égaux mais rien n'implique que a,c et
 218   % a,d soient égaux !!!
 219 \end{Def}
 220
 221 On a alors le théorème suivant.
 222
 223
 224 \begin{theorem}\label{th:cvg}
 225   Soit une fonction $f$ possédant un unique point fixe $x^*$ et une stratégie
 226   pseudo périodique $s$.
 227   Si les itérations synchrones convergent vers $x^*$ pour cette stratégie,
 228   alors les itérations mixes à délai uniforme convergent aussi vers $x^*$
 229   pour cette stratégie.
 230 \end{theorem}
 231
 232 La preuve de ce théorème est donnée en section~\ref{anx:mix}.
 233
 234
 235
 236
 237 \section{Durées de convergence}
 238 Cette section donne des bornes supérieures et inférieures des durées
 239 globales de convergence pour les modes synchrones, mixes et asynchrones.
 240 Pour simplifier le discours, on considère que les itérations
 241 convergent en in $I$ étapes dans le mode synchrone et que le graphe
 242 d'interaction ne contient qu'une seule composante connexe.
 243 Les durées de convergence prennent en compte les temps de calcul et les temps
 244 de communication, ce depuis l'initialisation et jusqu'à la stabilisation.
 245
 246 Pour simplifier l'évaluation, nous considérons que le temps de calcul d'une
 247 itération sur un composant ainsi que celui de communication entre deux
 248 composants est constant. Ceci implique en particulier que, dans
 249 le mode asynchrone, les délais  sont bornés. En d'autres mots, il existe
 250 un entier $\delta_0$ tel que $0 \le t-D_{ij}^t \le \delta_0$ est établi
 251 pour tout couple de n{\oe}uds $(i,j)$.
 252 Les notations utilisées sont les suivantes:
 253 \begin{description}
 254 \item [Taille pour coder l'information:] elle représente le nombre de nécessaire de bits
 255   pour représenter  l'état courant du composant $i$ et est notée $\textit{cs}_i$;
 256 \item [Temps de calcul:] le composant $i$ a besoins de  $\textit{cp}_i$ unités de temps
 257   pour faire une mise à jour locale de son état;
 258 \item   [Temps de communication:] On utilise le modèle classique de communication
 259   $\beta+L\tau$  où $L$ est le nombre de bits  transférés.
 260   On définit  $\beta_{ij}$ et  $\tau_{ij}$ comme la latence et la bande passante du lien
 261   entre  $i$ et $j$.
 262 \end{description}
 263
 264 % The updating strategy and the delays are respectively related to the computation
 265 % and  the communication  times.  In fact,  the  notion of  strategy in  dynamical
 266 % systems models the power heterogeneity between the components of the system. And
 267 % the notion of delays models the heterogeneity in the communication links between
 268 % the components.
 269
 270 \subsection{Le mode synchrone}
 271 \label{sec:evalsync}
 272
 273 Dans le cas synchrone, la convergence la plus rapide est obtenue lorsque
 274 le point fixe $x^*$ est accessible en un seul pas depuis toute configuration.
 275 Le temps global de convergence est donc minoré par $T_{min}(Sync)=\max_i\textit{cp}_i$
 276 Dans le cas général, si $B$ est la matrice d'adjacence représentant le
 277 graphe d'interaction, le temps global de convergence est
 278 \begin{equation}
 279   \label{eq:tsisc}
 280   T(\textit{Sync})=I\times(\max_i\textit{cp}_i+\max_{i,j}(B_{ji}\times(\beta_{ij}+\textit{cs}_i\times\tau_{ij})))
 281 \end{equation}
 282
 283
 284 \begin{xpl}
 285   Intuitivement la convergence se propage selon les dépendances internes au système:
 286   un n{\oe}uds se stabilise lorsque ceux dont il dépend sont eux aussi stables.
 287   Cette stabilisation progressive est illustrée à la \Fig{fig:evalsync} qui
 288   représente des exécutions parallèles dans le cas d'une initialisation avec la
 289   valeur (00100).
 290   Dans cette figure et les suivantes, les blocs doublement hachurés
 291   indiquent la stabilisation du composant.
 292
 293
 294 \begin{figure}
 295   \centering
 296   \begin{minipage}{1\linewidth}
 297     \includegraphics[scale=0.4]{images/eval_sync.eps}
 298     \caption{Itérations parallèles}
 299     \label{fig:evalsync}
 300   \end{minipage}
 301
 302   \begin{minipage}{1\textwidth}
 303     \includegraphics[scale=0.4]{images/eval_mixte.pdf}
 304     \caption{Itérations mixes avec
 305       \class{1} $=\{1,2\}$, \class{3} $=\{3\}$,
 306       \class{4} $=\{4,5\}$.}
 307     \label{fig:evalmixte}
 308   \end{minipage}
 309
 310   \begin{minipage}{1\textwidth}
 311     \includegraphics[scale=0.4]{images/eval_async.pdf}
 312     \caption{Itérations asynchrones}
 313     \label{fig:evalasync}
 314   \end{minipage}
 315 \end{figure}
 316
 317
 318
 319   On peut constater que la première classe  \class{1} se stabilise en deux itérations,
 320   la seconde classe \class{3} atteint sa valeur finale l'itération suivante
 321   tandis que la dernière classe, \class{4}, converge en deux itérations.
 322   \begin{equation}
 323     \label{eq:I}
 324     I=I_{\class{1}}+I_{\class{3}}+I_{\class{4}}=2+1+2=5
 325   \end{equation}
 326 \end{xpl}
 327
 328 % It is  possible to  speed up the  global execution  time while keeping  the same
 329 % iteration  scheme  by  relaxing  the  synchronization constraints  only  on  the
 330 % communications.    In  that   case,  called   SIAC  (Synchronous   Iterations  -
 331 % Asynchronous  Communications),  a  component  sends  its state  value  to  every
 332 % component  which needs  it  as soon  as that  value  has been  updated.  On  the
 333 % receiver side, an iteration begins  only when all the state values corresponding
 334 % to the  previous iteration  have been received  from the other  components whose
 335 % the receiver depends on.
 336
 337 % In  that  context, the  synchronous  iterations  scheme  is preserved  as  every
 338 % iteration  on any component  is computed  using the  dependency values  from the
 339 % previous  iteration  on  the  other  components.  So,  the  global  behavior  is
 340 % preserved   while  the   communication   cost  is   decreased.   Moreover,   the
 341 % synchronization is no more global  but restricted to each connected component in
 342 % the connection graph of the system.  Their respective speeds of evolution depend
 343 % on their  \emph{source classes} (the  classes without any  external dependency).
 344 % Also, between the starts of  two consecutive iterations, a component may receive
 345 % from its dependencies  some data values which correspond  either to the previous
 346 % iteration or  to the  current one (from  components which have  already finished
 347 % their current iteration).   This implies a small buffering  of the received data
 348 % (two elements per  dependency) and an explicit distinction  of the received data
 349 % according to their original iteration.
 350
 351 % Finally, as well as in the  following subsections, it is not possible to provide
 352 % an  exact evaluation  of the  global execution  time in  that case,  but  we can
 353 % provide lower and  upper bounds.  The worst case of  that version coincides with
 354 % the fully  synchronous scheme previously described.   And in the  best case, all
 355 % the communications are overlapped by  the computations on the slowest component,
 356 % implying the suppression of the communication term in~(\ref{eq:tsisc}).
 357
 358 % We have then the following boundaries:
 359 % \begin{equation}
 360 %   \label{eq:tsiac}
 361 %   I\times(\max_i\textit{cp}_i)\le T(\textit{SIAC}) \le T(Sync)
 362 % \end{equation}
 363 % \begin{xpl}
 364 %   Figure~\ref{fig:evalsiac} illustrates the potential speed up obtained with the
 365 %   SIAC variant in the same context of our running example.
 366 %   \begin{figure}%[h]
 367 %     \centering
 368 %     % \includegraphics[width=\textwidth]{eval_siac.eps}
 369 %     \includegraphics[width=\textwidth]{images/eval_siac.eps}
 370 %     \caption{Execution  of  the \textit{SIAC}  iterations  starting  from state  4
 371 %       (00100).}
 372 %     \label{fig:evalsiac}
 373 %   \end{figure}
 374 % \end{xpl}
 375
 376 \subsection{le mode mixe}
 377 \label{sec:evalmixed}
 378
 379 % As  detailed  in Sect.~\ref{sec:mdn},  the  mixed  case asynchronously  combines
 380 % subsets of synchronized components  (the different classes). The double interest
 381 % of  that  approach is  to  ensure  the convergence  of  the  system while  using
 382 % asynchronism.
 383
 384 % The  part  of  asynchronism often  reduces  the  global  execution time  as  the
 385 % communications  between  subgroups are  implicitly  overlapped by  computations.
 386 % However, the iterative scheme is no more the same as the synchronous one and its
 387 % number of  iterations to reach  the convergence will  be greater or  equal.
 388
 389 % Le nombre d'itérations requises pour obtenir la convergence en mode mixe
 390 % dépend des arangements entre les délais de communication et les durées de
 391 % calcul.
 392
 393 % number directly  depends on the arrangement  of delays during  the execution and
 394 % then on the communication times. But  it also depends on the evolution functions
 395 % which influence  the way each  part of the  system stabilizes itself.
 396 % In fact,  according to its evolution  function, a component may  reach its fixed
 397 % point  state even  with  a part  of its  input  data not  recently updated.   In
 398 % addition, as  mentioned earlier, the  set of components  in any system  does not
 399 % stabilize at the same time and there is often a propagation of the stabilization
 400 % through the system.
 401 % Also, the  previously mentioned phenomenon of  stabilization propagation through
 402 % the system is still present in mixed mode.
 403
 404 On considère $|\mathcal{K}|$  classes de composants synchronisés.
 405 (comme donné  en équation~(\ref{eq:I}).
 406 Soit $I_k$ le nombre d'itérations suffisants pour que la classe
 407 $k  \in \mathcal{K}$ se stabilise
 408 sachant  toutes ses dépendances ont déjà convergé.
 409 Ainsi $I$ vaut $\sum_{k \in \mathcal{K}} I_k$.
 410 La borne inférieur pour la durée de convergence des itérations asynchrones est
 411 \begin{equation}
 412   \label{eq:mixtelow}
 413   T(\textit{Mixed})\ge \sum_{k\in \mathcal{K}} I_k(\max_{l\in k}\textit{cp}_{l})
 414 \end{equation}
 415 \noindent qui apparaît lorsque tous les délais de communication sont consommés
 416 par des durées de calcul.
 417
 418 Concernant le majorant, celui-ci correspond au cas où
 419 les durées de communications entre les classes
 420 désynchronisées ne sont pas consommées par des calculs ou lorsque
 421 chaque classe nécessite la stabilisation de tous ses
 422 ascendants pour converger. On a dans ce cas:
 423
 424
 425 \begin{equation}
 426   \label{eq:mixteup}
 427   T(\textit{Mixed})\le\sum_{k \in \mathcal{K}}\left(I_k\times(\max_{l\in
 428       k}\textit{cp}_{l})+\max_{l\in k,e\in k', k\preceq k'}B_{el}\times(\beta_{le}+\textit{cs}_{l}\tau_{le})\right)
 429 \end{equation}
 430
 431 \begin{xpl}
 432   Une exécution du mode mixe est donnée à la~\Fig{fig:evalmixte}.
 433   On peut constater que le temps d'exécution peut être
 434   plus petit que pour le
 435   mode parallèle.
 436 \end{xpl}
 437
 438 \subsection{Le mode asynchrone}
 439 \label{sec:evalasync}
 440 En terme de durée de convergence, ce mode peut être vu comme un
 441 cas particulier du mode mixe où toutes les classes sont des singletons.
 442 La borne minimale peut donc s'exprimer comme:
 443 \begin{equation}
 444   \label{eq:asynclow}
 445   T(\textit{Async})\ge\max_{i=1}^{n}I_i\times \textit{cp}_{i}
 446 \end{equation}
 447 où $I_i$ est le nombre d'itérations suffisant pour que le n{\oe}ud $i$ converge
 448 et qui est atteint si tous les n{\oe}uds sont indépendants les uns des autres.
 449 Cette borne est arbitrairement faible et n'est pas atteinte dès qu'une
 450 dépendance existe.
 451 La borne supérieure quant à elle est donnée par:
 452 \begin{equation}
 453   \label{eq:asyncup}
 454   T(\textit{Async})\le\sum_{i=1}^{n}\left(I_i\times \textit{cp}_{i}+\max_{1\le k \le n}B_{ki}(\beta_{ik}+\textit{cs}_{i}\tau_{ik})\right)
 455 \end{equation}
 456 et apparaît lorsque chaque élément dépend des autres et que les calcules
 457 ne recouvrent nullement les communications.
 458
 459 \begin{xpl}
 460   La \Fig{fig:evalasync} présente un exemple d'exécution du mode asynchrone.
 461   Certaines communications issues de l'élément $4$ n'ont pas été représentées
 462   pour des raisons de clarté.
 463   On constate que le temps global de convergence est plus petit que celui des
 464   deux autres modes.
 465 \end{xpl}
 466
 467
 468
 469
 470
 471
 472
 473
 474
 475 \section{Conclusion}
 476 Introduire de l'asynchronisme peut permettre de réduire le temps
 477 d'exécution global, mais peut aussi introduire de la divergence.
 478 Dans ce chapitre, nous avons exposé comment construire un mode combinant les
 479 avantage du synchronisme en terme de convergence avec les avantages
 480 de l'asynchronisme en terme de vitesse de convergence.
 481
 482
 483
 484
 485
 486
 487 % The  part  of  asynchronism often  reduces  the  global  execution time  as  the
 488 % communications  between  subgroups are  implicitly  overlapped by  computations.
 489 % However, the iterative scheme is no more the same as the synchronous one and its
 490 % number of  iterations to reach  the convergence will  be greater or  equal.
 491
 492 %%% Local Variables:
 493 %%% mode: latex
 494 %%% TeX-master: "main"
 495 %%% ispell-dictionary: "american"
 496 %%% mode: flyspell
 497 %%% End: