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 élements (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épent 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}$ represente 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égi $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'intéraction associé à cette fonction.
  95 On note que le graphe d'intéraction contient cinq cycles. Les résultats
  96 connus~\cite{Bah00} de conditions suffisantes établissant la convergencedu 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èlles 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 representé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 libélé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
 152
 153
 154
 155
 156
 157   For instance, consider the matrix $D^t$ to be equal to $(t)$ except
 158 in $D^t_{12}$  where it is equal  to $t-1$ if $t$  is odd. Then if  $t$ is even,
 159 $x^{t+1}$ is $f(x^{t})$; if $t$ is odd we have
 160 $$
 161 x^{t+1}  = \left(
 162 f_1(x_1^{t},x_2^{t-1},x_3^{t},x_4^{t},x_5^{t}), f_2(x^{t}), \ldots,
 163 f_5(x^{t})
 164 \right).
 165 $$
 166 \noindent Starting from $x^0=00011$, the system reaches $x^1 = 01011$ and enters
 167 in  a  cycle  between these  two  configurations.   We  are then  confronted  to
 168 divergent asynchronous iterations whereas the synchronous ones converge.  In the
 169 next  section,   a  particular  execution   mode  is  described   which  enables
 170 asynchronism in iterations while guaranteeing the convergence.
 171
 172