X-Git-Url: https://bilbo.iut-bm.univ-fcomte.fr/and/gitweb/hdrcouchot.git/blobdiff_plain/2b04820abccb0772b10b2c53542ecddc6a6f600c..e9f2cb916f164b15bce8fe96e4f5432d3df9b7b2:/mixage.tex

diff --git a/mixage.tex b/mixage.tex
index d5f1981..e4a283c 100644
--- a/mixage.tex
+++ b/mixage.tex
@@ -3,7 +3,7 @@ Pour Ãªtre exÃ©cutÃ©,
 le mode des itÃ©rations gÃ©nÃ©ralisÃ©es nÃ©cessite que chaque Ã©lÃ©ment 
 connaisse la valeur de chaque autre Ã©lÃ©ment dont il dÃ©pend.
 Pratiquement, cela se rÃ©alise en diffusant les valeurs des Ã©lÃ©ments de 
-proche en proche Ã  tous les composants.
+proche en proche Ã  tous les composants avant chaque itÃ©ration.
 Dans le mode gÃ©nÃ©ralisÃ© 
 \emph{asynchrone}, le composant n'attend pas: il met Ã  jour sa 
 valeur avec les derniÃ¨res valeurs dont il dispose, mÃªme si celles-ci 
@@ -54,7 +54,7 @@ souvent.
 Dans le mode asynchrone, a chaque itÃ©ration $t$, chaque composant peut
 mettre Ã  jour son Ã©tat en 
 fonction des derniÃ¨res valeurs qu'il connaÃ®t des autre composants.
-Obtenir oÃ¹ non les valeurs les plus Ã  jours dÃ©pend du temps de calcul et 
+Obtenir ou non les valeurs les plus Ã  jours dÃ©pend du temps de calcul et 
 du temps d'acheminement de celles-ci. On parle de latence, de dÃ©lai.
 
 Formalisons le mode les itÃ©rations asynchrone.
@@ -65,7 +65,7 @@ dont chaque Ã©lÃ©ment $D_{ij}^{t}$ reprÃ©sente la date (infÃ©rieure ou Ã©gale Ã 
 disponible au composant $i$. 
 On considÃ¨re que le dÃ©lai entre l'Ã©mission par $j$ et la rÃ©ception par $i$, 
 dÃ©fini par $\delta_{ij}^t  = t  - D_{ij}^{t}$ est bornÃ© par une constante $\delta_0$ pour tous les $i$, $j$.
-Le \emph{mode des itÃ©rations gÃ©nÃ©ralisÃ©es sans attente} 
+Le \emph{mode des itÃ©rations gÃ©nÃ©ralisÃ©es asynchrone} 
 est dÃ©fini pour chaque  $i
 \in \{1,\ldots,n\}$ et chaque  $t=0,1,2,...$ par:
 
@@ -74,7 +74,7 @@ est dÃ©fini pour chaque  $i
   x^{t+1}_i= \left\{
     \begin{array}{l}
       f_i( x_1^{D_{i1}^t},\ldots, x_{n}^{D_{i{n}}^t})
-      \textrm{ if } \textit{bin}(s^t)[i] = 1\\ 
+      \textrm{ si } \textit{bin}(s^t)[i] = 1\\ 
       x^{t}_i  \textrm{ sinon }
     \end{array} 
   \right.
@@ -99,20 +99,20 @@ $(D^{(t)})^{t  \in \Nats}$, alors les itÃ©rations de  $f$ sont
 \emph{universellement convergentes}.
 
 
-\subsection{Exemple jouet}
-On considÃ¨re cinq Ã©lÃ©ments prenant Ã  valeurs dans $\Bool$. 
+\begin{xpl}
+On considÃ¨re cinq Ã©lÃ©ments Ã  valeurs dans $\Bool$. 
 Une configuration dans $\Bool^5$ est reprÃ©sentÃ©e par un entier entre 
-0 et 31. La~\Fig{fig:mix:map} donne la fonction dÃ©finissant la dynamique du 
-systÃ¨me. La~\Fig{fig:mix:xplgraph} donne le graphe d'interaction associÃ© Ã  cette fonction.
+0 et 31. 
+La~\Fig{fig:mix:map} donne la fonction dÃ©finissant la dynamique du 
+systÃ¨me et son graphe d'interaction.
 On note que le graphe d'interaction contient cinq cycles. Les rÃ©sultats 
 connus~\cite{Bah00} de conditions suffisantes Ã©tablissant la convergence
 du systÃ¨me pour les itÃ©rations gÃ©nÃ©ralisÃ©es sont
 basÃ©s sur l'absence de cycles. Ils ne peuvent donc pas Ãªtre appliquÃ©s ici.
 
-\begin{figure}[ht]
-\begin{minipage}[b]{0.55\linewidth}
-  \centering
-  $ f(x)= \left \{
+\begin{figure}%[ht]
+  \begin{center}
+    $$ f(x)= \left \{
     \begin{array}{lll}
       f_1(x_1,x_2,x_3,x_4,x_5) & = & x_1.\overline{x_2} + \overline{x_1}.x_2 \\
       f_2(x_1,x_2,x_3,x_4,x_5) & = & \overline{x_1 + x_2}  \\
@@ -120,48 +120,47 @@ basÃ©s sur l'absence de cycles. Ils ne peuvent donc pas Ãªtre appliquÃ©s ici.
       f_4(x_1,x_2,x_3,x_4,x_5) & = & x_5  \\
       f_5(x_1,x_2,x_3,x_4,x_5) & = & \overline{x_3} + x_4
     \end{array}
-  \right.  $
-\caption{Fonction $f$ de l'exemple jouet.}
-\label{fig:mix:map}
-\end{minipage}\hfill
-\begin{minipage}[b]{.40\linewidth}
-  \begin{center}
-    \includegraphics[scale=0.55]{xplgraphmix}
+  \right.
+  $$
+  
+  \includegraphics[scale=0.55]{xplgraphmix}
   \end{center}
-  \caption{Graphe d'interaction associÃ© Ã  $f$.}
-  \label{fig:mix:xplgraph}
-\end{minipage}
+  \caption{DÃ©finition de $f:\Bool^5 \rightarrow \Bool^5$ et son graphe d'interaction}
+  \label{fig:mix:map}
 \end{figure}
 
 
 \begin{figure}
-\begin{minipage}{0.56\linewidth}
-  \includegraphics[scale=0.55]{para_iterate_dec}
-  \caption{ItÃ©rations parallÃ¨les de $f$.}\label{fig:mix:xplparaFig}
-\end{minipage}
-\hfill
-\begin{minipage}{0.39\linewidth}
-  \includegraphics[scale=0.55]{chao_iterate_excerpt}
-  \caption{Extrait d'itÃ©rations chaotiques.}
-  \label{fig:mix:xplchaoFig}
-\end{minipage}
+  \begin{center}
+    \subfigure[ItÃ©rations synchrones de $f$.]{
+        \includegraphics[scale=0.50]{para_iterate_dec}
+        \label{fig:mix:xplparaFig}
+    }
+    \subfigure[Extrait des itÃ©rations unaires.]{
+        \includegraphics[scale=0.49]{chao_iterate_excerpt}
+        \label{fig:mix:xplchaoFig}
+    }
+    \end{center}
+ \caption{Graphes des itÃ©rations de $f$ dÃ©finie Ã  la figure~\ref{fig:mix:map}}
 \end{figure}
+\end{xpl}
+
 
 Dans ce qui suit, les  configurations  sont reprÃ©sentÃ©es Ã  l'aide d'entiers 
-plutÃ´t que nombres binaires. Le graphe des itÃ©rations parallÃ¨les est donnÃ© 
+plutÃ´t que nombres binaires. Le graphe des itÃ©rations synchrones est donnÃ© 
 en~\Fig{fig:mix:xplparaFig}. Depuis n'importe quelle configuration, on constate 
 qu'il converge vers le point fixe correspondant Ã  l'entier 19.
-Un extrait du graphe des itÃ©rations chaotiques est donnÃ© Ã  
+Un extrait du graphe des itÃ©rations unaires est donnÃ© Ã  
 la~\Fig{fig:mix:xplchaoFig}. Les libellÃ©s des arcs correspondent aux Ã©lÃ©ments 
-activÃ©s. Les itÃ©rations chaotiques ne convergent pas pour la stratÃ©gie 
+activÃ©s. Les itÃ©rations unaires ne convergent pas pour la stratÃ©gie 
 pseudo pÃ©riodique donnÃ©e Ã  l'Ã©quation~\Equ{eq:pseudo}:
 le systÃ¨me peut infiniment boucler entre 11 et 3, entre 15 et 7.   
 
-Comme les itÃ©rations chaotiques ne convergent pas pour certaines stratÃ©gies,
+Comme les itÃ©rations unaires ne convergent pas pour certaines stratÃ©gies,
 les itÃ©rations asynchrones basÃ©es sur les mÃªme stratÃ©gies peuvent ne pas 
 converger aussi. Cependant, mÃªme si l'on considÃ¨re que tous les composants 
 sont activÃ©s Ã  chaque itÃ©ration, c'est Ã  dire si $s^t$ est 
-constamment Ã©gal Ã  $2^n-1$, le dÃ©lais peut introduire de la divergence.
+constamment Ã©gal Ã  $2^n-1$, le dÃ©lai peut introduire de la divergence.
 On considÃ¨re par exemple la matrice $D^t$ dont chaque Ã©lÃ©ment vaut  $t$
 sauf $D^t_{12}$  qui vaut $t-1$ si $t$  est impair. 
 On a ainsi $x^{t+1}= f(x^{t})$ si $t$ est pair et  
@@ -174,7 +173,7 @@ $$
 \noindent sinon. 
 En dÃ©marrant de $x^0=00011$, le systÃ¨me atteint $x^1 = 01011$ et boucle entre 
 ces deux configurations. Pour une mÃªme stratÃ©gies, les itÃ©rations 
-asynhrones divergent alors que les synchrones convergent.
+asynchrones divergent alors que les synchrones convergent.
 Les sections suivantes de ce chapitre montrent comment rÃ©soudre ce problÃ¨me.
 
 \subsection{ItÃ©rations Mixes}
@@ -206,7 +205,7 @@ Les itÃ©rations mixes d'un systÃ¨me discret suit l'Ã©quation \Equ{eq:async} oÃ¹
 de plus   $bin(s^t)[i]=bin(s^t)[j]$ et $D_{ij}^t=D_{ji}^t=t$ si $i \eqNode j$.
 \end{Def}
 
-Dans ce contexte, il n'y a plus de dÃ©lais entre deux noeuds de la mÃªme CFC
+Dans ce contexte, il n'y a plus de dÃ©lai entre deux noeuds de la mÃªme CFC
 et leurs mises Ã  jour sont synchronisÃ©es.
 Cependant, pour $p_0$ et $p_1$ dans la mÃªme  classe \class{p}, 
 et $q$ dans une autre classe \class{q}, ce  mode opÃ©ratoire autorise
@@ -224,12 +223,6 @@ Pour gommer cette distinction, on dÃ©finit le mode suivant:
      \bigwedge_{p_k \in  \class{p}, q_k \in \class{q} } 
      D_{p_{k}q_{k}}^{t}  =   d_{pq}^t    
   \end{equation*}
-  % Je me demande si cette formalisation n'a pas un souci par rapport Ã  une
-  % formalisation avec un seul q ?! (car deux Ã©lÃ©ments supposent qu'ils sont distincts)
-  % car si on a deux Ã©lÃ©ments dans chaque classe, on peut alors avoir deux
-  % groupes de dÃ©lais : supposons (a,b) dans p et (c,d) dans q
-  % a,c et b,d sont Ã©gaux et a,d et b,c sont Ã©gaux mais rien n'implique que a,c et
-  % a,d soient Ã©gaux !!!
 \end{Def}
 
 On a alors le thÃ©orÃ¨me suivant.
@@ -252,7 +245,7 @@ La preuve de ce thÃ©orÃ¨me est donnÃ©e en section~\ref{anx:mix}.
 Cette section donne des bornes supÃ©rieures et infÃ©rieures des durÃ©es 
 globales de convergence pour les modes synchrones, mixes et asynchrones.
 Pour simplifier le discours, on considÃ¨re que les itÃ©rations 
-convergent en in $I$ Ã©tapes dans le mode synchrone et que le graphe 
+convergent en $I$ Ã©tapes dans le mode synchrone et que le graphe 
 d'interaction ne contient qu'une seule composante connexe.
 Les durÃ©es de convergence prennent en compte les temps de calcul et les temps 
 de communication, ce depuis l'initialisation et jusqu'Ã  la stabilisation.
@@ -265,11 +258,13 @@ un entier $\delta_0$ tel que $0 \le t-D_{ij}^t \le \delta_0$ est Ã©tabli
 pour tout couple de n{\oe}uds $(i,j)$. 
 Les notations utilisÃ©es sont les suivantes:
 \begin{description}
-\item [Taille pour coder l'information:] elle reprÃ©sente le nombre de nÃ©cessaire de bits 
+\item [Taille pour coder l'information] elle reprÃ©sente le nombre 
+  de bits
+  nÃ©cessaires 
   pour reprÃ©senter  l'Ã©tat courant du composant $i$ et est notÃ©e $\textit{cs}_i$;
-\item [Temps de calcul:] le composant $i$ a besoins de  $\textit{cp}_i$ unitÃ©s de temps 
+\item [Temps de calcul] le composant $i$ a besoins de  $\textit{cp}_i$ unitÃ©s de temps 
   pour faire une mise Ã  jour locale de son Ã©tat;
-\item   [Temps de communication:] On utilise le modÃ¨le classique de communication 
+\item   [Temps de communication] on utilise le modÃ¨le classique de communication 
   $\beta+L\tau$  oÃ¹ $L$ est le nombre de bits  transfÃ©rÃ©s. 
   On dÃ©finit  $\beta_{ij}$ et  $\tau_{ij}$ comme la latence et la bande passante du lien 
   entre  $i$ et $j$.
@@ -299,7 +294,7 @@ graphe d'interaction, le temps global de convergence est
   Intuitivement la convergence se propage selon les dÃ©pendances internes au systÃ¨me:
   un n{\oe}uds se stabilise lorsque ceux dont il dÃ©pend sont eux aussi stables.
   Cette stabilisation progressive est illustrÃ©e Ã  la \Fig{fig:evalsync} qui
-  reprÃ©sente des exÃ©cutions parallÃ¨les dans le cas d'une initialisation avec la 
+  reprÃ©sente des exÃ©cutions synchrones dans le cas d'une initialisation avec la 
   valeur (00100).
   Dans cette figure et les suivantes, les blocs doublement hachurÃ©s
   indiquent la stabilisation du composant.
@@ -309,7 +304,7 @@ graphe d'interaction, le temps global de convergence est
   \centering
   \begin{minipage}{1\linewidth}
     \includegraphics[scale=0.4]{eval_sync}
-    \caption{ItÃ©rations parallÃ¨les}
+    \caption{ItÃ©rations synchrones}
     \label{fig:evalsync}
   \end{minipage}
   
@@ -390,38 +385,14 @@ graphe d'interaction, le temps global de convergence est
 \subsection{le mode mixe}
 \label{sec:evalmixed}
 
-% As  detailed  in Sect.~\ref{sec:mdn},  the  mixed  case asynchronously  combines
-% subsets of synchronized components  (the different classes). The double interest
-% of  that  approach is  to  ensure  the convergence  of  the  system while  using
-% asynchronism.
-
-% The  part  of  asynchronism often  reduces  the  global  execution time  as  the
-% communications  between  subgroups are  implicitly  overlapped by  computations.
-% However, the iterative scheme is no more the same as the synchronous one and its
-% number of  iterations to reach  the convergence will  be greater or  equal.
-
-% Le nombre d'itÃ©rations requises pour obtenir la convergence en mode mixe 
-% dÃ©pend des arangements entre les dÃ©lais de communication et les durÃ©es de 
-% calcul. 
-
-% number directly  depends on the arrangement  of delays during  the execution and
-% then on the communication times. But  it also depends on the evolution functions
-% which influence  the way each  part of the  system stabilizes itself.  
-% In fact,  according to its evolution  function, a component may  reach its fixed
-% point  state even  with  a part  of its  input  data not  recently updated.   In
-% addition, as  mentioned earlier, the  set of components  in any system  does not
-% stabilize at the same time and there is often a propagation of the stabilization
-% through the system.
-% Also, the  previously mentioned phenomenon of  stabilization propagation through
-% the system is still present in mixed mode.
 
 On considÃ¨re $|\mathcal{K}|$  classes de composants synchronisÃ©s.
-(comme donnÃ©  en Ã©quation~(\ref{eq:I}).
+(comme donnÃ©  en Ã©quation~(\ref{eq:I})).
 Soit $I_k$ le nombre d'itÃ©rations suffisants pour que la classe 
-$k  \in \mathcal{K}$ se stabilise 
+$\class{k}  \in \mathcal{K}$ se stabilise 
 sachant  toutes ses dÃ©pendances ont dÃ©jÃ  convergÃ©. 
-Ainsi $I$ vaut $\sum_{k \in \mathcal{K}} I_k$.
-La borne infÃ©rieur pour la durÃ©e de convergence des itÃ©rations asynchrones est 
+Ainsi $I$ vaut $\sum_{\class{k} \in \mathcal{K}} I_k$.
+La borne infÃ©rieure pour la durÃ©e de convergence des itÃ©rations asynchrones est 
 \begin{equation}
   \label{eq:mixtelow}
   T(\textit{Mixed})\ge \sum_{k\in \mathcal{K}} I_k(\max_{l\in k}\textit{cp}_{l})
@@ -446,7 +417,7 @@ ascendants pour converger. On a dans ce cas:
   Une exÃ©cution du mode mixe est donnÃ©e Ã  la~\Fig{fig:evalmixte}.
   On peut constater que le temps d'exÃ©cution peut Ãªtre  
   plus petit que pour le 
-  mode parallÃ¨le.
+  mode synchrone.
 \end{xpl}
 
 \subsection{Le mode gÃ©nÃ©ralisÃ© asynchrone}
@@ -467,11 +438,12 @@ La borne supÃ©rieure quant Ã  elle est donnÃ©e par:
   \label{eq:asyncup}
   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)
 \end{equation}
-et apparaÃ®t lorsque chaque Ã©lÃ©ment dÃ©pend des autres et que les calcules 
+et apparaÃ®t lorsque chaque Ã©lÃ©ment dÃ©pend des autres et que les calculs 
 ne recouvrent nullement les communications.
 
 \begin{xpl}
-  La \Fig{fig:evalasync} prÃ©sente un exemple d'exÃ©cution du mode asynchrone.
+  La \Fig{fig:evalasync} prÃ©sente un exemple d'exÃ©cution du mode gÃ©nÃ©ralisÃ© 
+  asynchrone.
   Certaines communications issues de l'Ã©lÃ©ment $4$ n'ont pas Ã©tÃ© reprÃ©sentÃ©es
   pour des raisons de clartÃ©.
   On constate que le temps global de convergence est plus petit que celui des
@@ -500,6 +472,6 @@ ne recouvrent nullement les communications.
 %%% Local Variables: 
 %%% mode: latex
 %%% TeX-master: "main"
-%%% ispell-dictionary: "american"
+%%% ispell-dictionary: "french"
 %%% mode: flyspell
 %%% End: 
