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 }
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
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$,
19 % The synchronous iterations modes are defined for any $i \in
20 % \{1,\ldots,n\}$ and any time $t=0,1,2,...$ by:
22 % \begin{equation}\label{eq:sync}
25 % f_i(x^t) \textrm{ if } \textit{bin}(s^t)[i] = 1\\
26 % x^{t}_i \textrm{ otherwise }
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,
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.
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:
61 \begin{equation}\label{eq:async}
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 }
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}
79 t \geq t_0 \Rightarrow x^{t}=x^{t_0}).
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}.
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.
99 \begin{minipage}[b]{0.55\linewidth}
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
110 \caption{Fonction $f$ de l'exemple jouet.}
113 \begin{minipage}[b]{.40\linewidth}
115 \includegraphics[scale=0.55]{images/xplgraphmix.eps}
117 \caption{Graphe d'interaction associé à $f$.}
118 \label{fig:mix:xplgraph}
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}
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}
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.
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.
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
162 f_1(x_1^{t},x_2^{t-1},x_3^{t},x_4^{t},x_5^{t}), f_2(x^{t}), \ldots,
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.
