X-Git-Url: https://bilbo.iut-bm.univ-fcomte.fr/and/gitweb/hdrcouchot.git/blobdiff_plain/6e2993d89d55fe5f9e1380a06c4d9da27d6c7703..cb56b165bc864d9858b71195e2fb3ea9cb899683:/mixage.tex?ds=inline

diff --git a/mixage.tex b/mixage.tex
index a03edc5..a499409 100644
--- a/mixage.tex
+++ b/mixage.tex
@@ -9,7 +9,7 @@ binaire donne la liste des Ã©lÃ©ments modifiÃ©s. Par exemple, pour un systÃ¨me
 s^{t}=24 \textrm{ si  $t$ est pair et  } s^{t}=15 \textrm{ sinon }
 \end{equation}
 \noindent active successivement les deux premiers Ã©lÃ©ments (24 est 11000) 
-et les quatre derniers Ã©lements (15  est  01111).  
+et les quatre derniers Ã©lÃ©ments (15  est  01111).  
 On dit que la stratÃ©gie est
 \emph{pseudo-periodique}  si tous les Ã©lÃ©ments sont activÃ©s infiniment 
 souvent.
@@ -43,13 +43,13 @@ 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Ã©pent du temps de calcul et 
+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.
 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}$ represente la date (infÃ©rieure ou Ã©gale Ã  $t$) 
+dont chaque Ã©lÃ©ment $D_{ij}^{t}$ reprÃ©sente la date (infÃ©rieure ou Ã©gale Ã  $t$) 
 Ã  laquelle la valeur $x_j$ produite par le composant $j$ devient 
 disponible au composant $i$. 
 On considÃ¨re que le dÃ©lai entre l'Ã©mission par $j$ et la rÃ©ception par $i$, 
@@ -70,7 +70,7 @@ Le \emph{mode des itÃ©rations asynchrones} est dÃ©fini pour chaque  $i
 
 \noindent oÃ¹ $\textit{bin}$ convertit un entier en un nombre binaire.
 Les itÃ©rations de $f$ sont \emph{convergentes} modulo une configuration 
-initiale  $x^0$,  une  stratÃ©gi $s$ et une matrice de dates  $(D^{t})^{t  \in
+initiale  $x^0$,  une  stratÃ©gie $s$ et une matrice de dates  $(D^{t})^{t  \in
   \Nats}$, si la fonction atteint un point fixe.
 Cela revient Ã  vÃ©rifier la propriÃ©tÃ© suivante:
 \begin{equation}\label{eq:conv}      
@@ -91,9 +91,9 @@ $(D^{(t)})^{t  \in \Nats}$, alors les itÃ©rations de  $f$ sont
 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'intÃ©raction associÃ© Ã  cette fonction.
-On note que le graphe d'intÃ©raction contient cinq cycles. Les rÃ©sultats 
-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.
+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.
 
 \begin{figure}[ht]
 \begin{minipage}[b]{0.55\linewidth}
@@ -123,7 +123,7 @@ connus~\cite{Bah00} de conditions suffisantes Ã©tablissant la convergencedu syst
 \begin{figure}
 \begin{minipage}{0.56\linewidth}
   \includegraphics[scale=0.55]{images/para_iterate_dec.eps}
-  \caption{ItÃ©rations parallÃ¨lles de $f$.}\label{fig:mix:xplparaFig}
+  \caption{ItÃ©rations parallÃ¨les de $f$.}\label{fig:mix:xplparaFig}
 \end{minipage}
 \hfill
 \begin{minipage}{0.39\linewidth}
@@ -133,12 +133,12 @@ connus~\cite{Bah00} de conditions suffisantes Ã©tablissant la convergencedu syst
 \end{minipage}
 \end{figure}
 
-Dans ce qui suit, les  configurations  sont representÃ©es Ã  l'aide d'entiers 
+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Ã© 
 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Ã© Ã  
-la~\Fig{fig:mix:xplchaoFig}. Les libÃ©lÃ©s des arcs correspondent aux Ã©lÃ©ments 
+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 
 pseudo pÃ©riodique donnÃ©e Ã  l'Ã©quation~\Equ{eq:pseudo}:
 le systÃ¨me peut infiniment boucler entre 11 et 3, entre 15 et 7.   
@@ -158,14 +158,14 @@ f_5(x^{t})
 \right).
 $$
 \noindent sinon. 
-En dÃ©marant de $x^0=00011$, le systÃ¨me atteint $x^1 = 01011$ et boucle entre 
+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.
 Les sections suivantes de ce chapitre montrent comment rÃ©soudre ce problÃ¨me.
 
 \section{ItÃ©rations Mixes}
 Introduit dans~\cite{abcvs05}  
-le mode d'\emph{itÃ©rations mixes} combine syncrhonisme et asynchronisme.
+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 
@@ -237,9 +237,9 @@ La preuve de ce thÃ©orÃ¨me est donnÃ©e en section~\ref{anx:mix}.
 \section{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 symplifier le discours, on considÃ¨re que les itÃ©rations 
+Pour simplifier le discours, on considÃ¨re que les itÃ©rations 
 convergent en in $I$ Ã©tapes dans le mode synchrone et que le graphe 
-d'intÃ©raction ne contient qu'une seule composante connexe.
+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.
 
@@ -251,7 +251,7 @@ 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 represente le nombre de nÃ©cessaire de bits 
+\item [Taille pour coder l'information:] elle reprÃ©sente le nombre de nÃ©cessaire de bits 
   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 
   pour faire une mise Ã  jour locale de son Ã©tat;
@@ -271,7 +271,7 @@ Les notations utilisÃ©es sont les suivantes:
 \label{sec:evalsync}
 
 Dans le cas synchrone, la convergence la plus rapide est obtenue lorsque
-le point fixe $x^*$ est accesible en un seul pas depuis toute configuration.
+le point fixe $x^*$ est accessible en un seul pas depuis toute configuration.
 Le temps global de convergence est donc minorÃ© par $T_{min}(Sync)=\max_i\textit{cp}_i$
 Dans le cas gÃ©nÃ©ral, si $B$ est la matrice d'adjacence reprÃ©sentant le 
 graphe d'interaction, le temps global de convergence est 
@@ -283,12 +283,12 @@ graphe d'interaction, le temps global de convergence est
 
 \begin{xpl}
   Intuitivement la convergence se propage selon les dÃ©pendances internes au systÃ¨me:
-  un n{\oe}ud se stabilise lorsque ceux dont il dÃ©pend sont eux aussi stables.
-  Cette stabilisation progresive est illustrÃ©e Ã  la \Fig{fig:evalsync} qui
+  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 
   valeur (00100).
   Dans cette figure et les suivantes, les blocs doublement hachurÃ©s
-  induquent la stabilisation du composant.
+  indiquent la stabilisation du composant.
 
 
 \begin{figure}
@@ -301,7 +301,7 @@ graphe d'interaction, le temps global de convergence est
   
   \begin{minipage}{1\textwidth}
     \includegraphics[scale=0.4]{images/eval_mixte.pdf}
-    \caption{Iterations mixes avec
+    \caption{ItÃ©rations mixes avec
       \class{1} $=\{1,2\}$, \class{3} $=\{3\}$,
       \class{4} $=\{4,5\}$.}
     \label{fig:evalmixte}
@@ -309,16 +309,16 @@ graphe d'interaction, le temps global de convergence est
   
   \begin{minipage}{1\textwidth}
     \includegraphics[scale=0.4]{images/eval_async.pdf}
-    \caption{Iterations asynchrones}
+    \caption{ItÃ©rations asynchrones}
     \label{fig:evalasync}
   \end{minipage}
 \end{figure}
 
   
    
-  On peut constater que la premiiÃ¨re classe  \class{1} se stabilise en deux itÃ©rations,
-  la seconde classe \class{3} atteint sa valeur finale l'itÃ©rations suivante 
-  tandis que la derniÃ¨re classe, \class{4}, converge en deux iterations.
+  On peut constater que la premiÃ¨re classe  \class{1} se stabilise en deux itÃ©rations,
+  la seconde classe \class{3} atteint sa valeur finale l'itÃ©ration suivante 
+  tandis que la derniÃ¨re classe, \class{4}, converge en deux itÃ©rations.
   \begin{equation}
     \label{eq:I}
     I=I_{\class{1}}+I_{\class{3}}+I_{\class{4}}=2+1+2=5
@@ -432,7 +432,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 paralÃ¨le.
+  mode parallÃ¨le.
 \end{xpl}
 
 \subsection{Le mode asynchrone}
@@ -457,9 +457,9 @@ et apparaÃ®t lorsque chaque Ã©lÃ©ment dÃ©pend des autres et que les calcules
 ne recouvrent nullement les communications.
 
 \begin{xpl}
-  La \Fig{fig:evalasync} prÃ©sente un exemple d'execution du mode asynchrone.
+  La \Fig{fig:evalasync} prÃ©sente un exemple d'exÃ©cution du mode asynchrone.
   Certaines communications issues de l'Ã©lÃ©ment $4$ n'ont pas Ã©tÃ© reprÃ©sentÃ©es
-  pour des raisons de claretÃ©.
+  pour des raisons de clartÃ©.
   On constate que le temps global de convergence est plus petit que celui des
   deux autres modes.
 \end{xpl}
@@ -472,19 +472,22 @@ 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.
+ 
 
 
 
 
 
-
-
-
-\section{Conclusion}
-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.
+% 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.
 
 %%% Local Variables: 
 %%% mode: latex
