]> AND Private Git Repository - hdrcouchot.git/blob - mixage.tex
Logo AND Algorithmique Numérique Distribuée

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