X-Git-Url: https://bilbo.iut-bm.univ-fcomte.fr/and/gitweb/hdrcouchot.git/blobdiff_plain/98c34e4d34d6f63836eefca981f5d1ce73a865e2..2b04820abccb0772b10b2c53542ecddc6a6f600c:/mixage.tex?ds=sidebyside

diff --git a/mixage.tex b/mixage.tex
index a499409..d5f1981 100644
--- a/mixage.tex
+++ b/mixage.tex
@@ -1,8 +1,19 @@
-\JFC{Refaire le chÃ¢peau}
-\section{GÃ©nÃ©ralisation au cadre asynchrone}
-Dans ce chapitre une stratÃ©gie $s=(s^{t})^{t \in \Nats}$ est une sÃ©quence
-\emph{des Ã©lÃ©ments} qui sont mis Ã  jour au temps $t$. Pratiquement, 
-on reprÃ©sente ceci comme un nombre dÃ©cimal dont la reprÃ©sentation en 
+
+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.
+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 
+ne sont pas Ã  jour.
+Cette section vise l'Ã©tude de ce mode.
+
+
+%\subsection{GÃ©nÃ©ralisation au cadre asynchrone}
+Pratiquement, chaque stratÃ©gie du mode gÃ©nÃ©ralisÃ© peut Ãªtre 
+mÃ©morisÃ©e  comme un nombre dÃ©cimal dont la reprÃ©sentation en 
 binaire donne la liste des Ã©lÃ©ments modifiÃ©s. Par exemple, pour un systÃ¨me 
 Ã  5 Ã©lÃ©ments la stratÃ©gie dÃ©finie par 
 \begin{equation}\label{eq:pseudo}
@@ -46,7 +57,7 @@ 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 
 du temps d'acheminement de celles-ci. On parle de latence, de dÃ©lai.
 
-Formalisons le mode les itÃ©rations asynchrones.
+Formalisons le mode les itÃ©rations asynchrone.
 Soit $x^0 =(x_1^0, \ldots, x_n^0)$ une configuration initiale.
 Soit $(D^{t})^{t \in  \Nats}$ la suite de matrice de taille $n  \times n$  
 dont chaque Ã©lÃ©ment $D_{ij}^{t}$ reprÃ©sente la date (infÃ©rieure ou Ã©gale Ã  $t$) 
@@ -54,7 +65,8 @@ 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 asynchrones} est dÃ©fini pour chaque  $i
+Le \emph{mode des itÃ©rations gÃ©nÃ©ralisÃ©es sans attente} 
+est dÃ©fini pour chaque  $i
 \in \{1,\ldots,n\}$ et chaque  $t=0,1,2,...$ par:
 
 \vspace{-.5em}
@@ -87,13 +99,15 @@ $(D^{(t)})^{t  \in \Nats}$, alors les itÃ©rations de  $f$ sont
 \emph{universellement convergentes}.
 
 
-\section{Exemple jouet}
+\subsection{Exemple jouet}
 On considÃ¨re cinq Ã©lÃ©ments prenant Ã  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.
 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 synchrones et asynchrones sont basÃ©s sur l'absence de cycles. Ils ne peuvent donc pas Ãªtre appliquÃ©s ici.
+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}
@@ -112,7 +126,7 @@ connus~\cite{Bah00} de conditions suffisantes Ã©tablissant la convergence du sys
 \end{minipage}\hfill
 \begin{minipage}[b]{.40\linewidth}
   \begin{center}
-    \includegraphics[scale=0.55]{images/xplgraphmix.eps}
+    \includegraphics[scale=0.55]{xplgraphmix}
   \end{center}
   \caption{Graphe d'interaction associÃ© Ã  $f$.}
   \label{fig:mix:xplgraph}
@@ -122,12 +136,12 @@ connus~\cite{Bah00} de conditions suffisantes Ã©tablissant la convergence du sys
 
 \begin{figure}
 \begin{minipage}{0.56\linewidth}
-  \includegraphics[scale=0.55]{images/para_iterate_dec.eps}
+  \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]{images/chao_iterate_excerpt.eps}
+  \includegraphics[scale=0.55]{chao_iterate_excerpt}
   \caption{Extrait d'itÃ©rations chaotiques.}
   \label{fig:mix:xplchaoFig}
 \end{minipage}
@@ -160,17 +174,17 @@ $$
 \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 
-asynchrones divergent alors que les synchrones convergent.
+asynhrones divergent alors que les synchrones convergent.
 Les sections suivantes de ce chapitre montrent comment rÃ©soudre ce problÃ¨me.
 
-\section{ItÃ©rations Mixes}
+\subsection{ItÃ©rations Mixes}
 Introduit dans~\cite{abcvs05}  
 le mode d'\emph{itÃ©rations mixes} combine synchronisme et asynchronisme.
 Intuitivement, les n{\oe}uds qui pourraient introduire des cycles dans 
 les itÃ©rations asynchrones sont regroupÃ©s. 
 Les noeuds Ã  l'intÃ©rieur de chaque groupe seront itÃ©rÃ©s de maniÃ¨re 
 synchrone. 
-L'asynchronisme est conservÃ© entre les groupes.
+Les itÃ©rations asynchrones sont conservÃ©es entre les groupes.
 
 \begin{Def}[Relation de Synchronisation]\label{def:eqrel}
   Soit une fonction $f$ et  $\Gamma(f)$ son  graphe d'interaction. 
@@ -234,7 +248,7 @@ La preuve de ce thÃ©orÃ¨me est donnÃ©e en section~\ref{anx:mix}.
 
 
 
-\section{DurÃ©es de convergence} 
+\subsection{DurÃ©es de convergence} 
 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 
@@ -246,7 +260,7 @@ de communication, ce depuis l'initialisation et jusqu'Ã  la stabilisation.
 Pour simplifier l'Ã©valuation, nous considÃ©rons que le temps de calcul d'une 
 itÃ©ration sur un composant ainsi que celui de communication entre deux 
 composants est constant. Ceci implique en particulier que, dans 
-le mode asynchrone, les dÃ©lais  sont bornÃ©s. En d'autres mots, il existe 
+le mode asynchrone, ces derniers  sont bornÃ©s. En d'autres mots, il existe 
 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:
@@ -294,13 +308,13 @@ graphe d'interaction, le temps global de convergence est
 \begin{figure}
   \centering
   \begin{minipage}{1\linewidth}
-    \includegraphics[scale=0.4]{images/eval_sync.eps}
+    \includegraphics[scale=0.4]{eval_sync}
     \caption{ItÃ©rations parallÃ¨les}
     \label{fig:evalsync}
   \end{minipage}
   
   \begin{minipage}{1\textwidth}
-    \includegraphics[scale=0.4]{images/eval_mixte.pdf}
+    \includegraphics[scale=0.4]{eval_mixte}
     \caption{ItÃ©rations mixes avec
       \class{1} $=\{1,2\}$, \class{3} $=\{3\}$,
       \class{4} $=\{4,5\}$.}
@@ -308,7 +322,7 @@ graphe d'interaction, le temps global de convergence est
   \end{minipage}
   
   \begin{minipage}{1\textwidth}
-    \includegraphics[scale=0.4]{images/eval_async.pdf}
+    \includegraphics[scale=0.4]{eval_async}
     \caption{ItÃ©rations asynchrones}
     \label{fig:evalasync}
   \end{minipage}
@@ -366,7 +380,7 @@ graphe d'interaction, le temps global de convergence est
 %   \begin{figure}%[h]
 %     \centering
 %     % \includegraphics[width=\textwidth]{eval_siac.eps}
-%     \includegraphics[width=\textwidth]{images/eval_siac.eps}
+%     \includegraphics[width=\textwidth]{eval_siac.eps}
 %     \caption{Execution  of  the \textit{SIAC}  iterations  starting  from state  4
 %       (00100).}
 %     \label{fig:evalsiac}
@@ -435,7 +449,7 @@ ascendants pour converger. On a dans ce cas:
   mode parallÃ¨le.
 \end{xpl}
 
-\subsection{Le mode asynchrone}
+\subsection{Le mode gÃ©nÃ©ralisÃ© asynchrone}
 \label{sec:evalasync}
 En terme de durÃ©e de convergence, ce mode peut Ãªtre vu comme un 
 cas particulier du mode mixe oÃ¹ toutes les classes sont des singletons.
@@ -472,12 +486,6 @@ ne recouvrent nullement les communications.
 
 
 
-\section{Conclusion}
-Introduire de l'asynchronisme peut permettre de rÃ©duire le temps 
-d'exÃ©cution global, mais peut aussi introduire de la divergence. 
-Dans ce chapitre, nous avons exposÃ© comment construire un mode combinant les
-avantage du synchronisme en terme de convergence avec les avantages 
-de l'asynchronisme en terme de vitesse de convergence.
  
 
 
