merge main

[hdrcouchot.git] / mixage.tex

diff --git a/mixage.tex b/mixage.tex
index a03edc51851b30f617f9871ed34b50ef11619523..a71a36d25735bb68daecf2a65e16e2dbe0a5d1fb 100644 (file)
--- a/mixage.tex
+++ b/mixage.tex
@@ -1,15 +1,26 @@
-\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 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 
+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}
 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) 
 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}
 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.
 On dit que la stratégie est
 \emph{pseudo-periodique}  si tous les éléments sont activés infiniment 
 souvent.


@@ -43,18 +54,19 @@ 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.
 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 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.
 
 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$  
 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$, 
 défini par $\delta_{ij}^t  = t  - D_{ij}^{t}$ est borné par une constante $\delta_0$ pour tous les $i$, $j$.
 à 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$, 
 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 asynchrone} 
+est défini pour chaque  $i

 \in \{1,\ldots,n\}$ et chaque  $t=0,1,2,...$ par:
 
 \vspace{-.5em}
 \in \{1,\ldots,n\}$ et chaque  $t=0,1,2,...$ par:
 
 \vspace{-.5em}


@@ -62,7 +74,7 @@ Le \emph{mode des itérations asynchrones} 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})
   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.
       x^{t}_i  \textrm{ sinon }
     \end{array} 
   \right.


@@ -70,7 +82,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 
 
 \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}      
   \Nats}$, si la fonction atteint un point fixe.
 Cela revient à vérifier la propriété suivante:
 \begin{equation}\label{eq:conv}      


@@ -87,18 +99,20 @@ $(D^{(t)})^{t  \in \Nats}$, alors les itérations de  $f$ sont
 \emph{universellement convergentes}.
 
 
 \emph{universellement convergentes}.
 
 

-\section{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 
 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.
+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{figure}[ht]

-\begin{minipage}[b]{0.55\linewidth}
-  \centering
-  $ f(x)= \left \{
+  \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}  \\
     \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}  \\


@@ -106,48 +120,47 @@ connus~\cite{Bah00} de conditions suffisantes établissant la convergencedu syst
       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}
       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]{images/xplgraphmix.eps}
+  \right.
+  $$
+  
+  \includegraphics[scale=0.55]{xplgraphmix}

   \end{center}
   \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}
 \end{figure}
 
 
 \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}
-\end{minipage}
-\hfill
-\begin{minipage}{0.39\linewidth}
-  \includegraphics[scale=0.55]{images/chao_iterate_excerpt.eps}
-  \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{figure}

+\end{xpl}

 
 

-Dans ce qui suit, les  configurations  sont representées à l'aide d'entiers 
-plutôt que nombres binaires. Le graphe des itérations parallèles est donné 
+
+Dans ce qui suit, les  configurations  sont représentées à l'aide d'entiers 
+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.
 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 
-activés. Les itérations chaotiques ne convergent pas pour la stratégie 
+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 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.   
 
 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 
 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  
 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  


@@ -158,19 +171,19 @@ f_5(x^{t})
 \right).
 $$
 \noindent sinon. 
 \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 
 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.
 
 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}  
 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 
 synchrone. 
 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. 
 
 \begin{Def}[Relation de Synchronisation]\label{def:eqrel}
   Soit une fonction $f$ et  $\Gamma(f)$ son  graphe d'interaction. 


@@ -192,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}
 
 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
 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


@@ -210,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*}
      \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.
 \end{Def}
 
 On a alors le théorème suivant.


@@ -234,28 +241,30 @@ 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.
 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 
-convergent en in $I$ étapes dans le mode synchrone et que le graphe 
-d'intéraction ne contient qu'une seule composante connexe.
+Pour simplifier le discours, on considère que les itérations 
+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.
 
 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 
 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.
 
 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:
 \begin{description}
 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 bits
+  nécessaires 

   pour représenter  l'état courant du composant $i$ et est notée $\textit{cs}_i$;
   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;
   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$.
   $\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$.


@@ -271,7 +280,7 @@ Les notations utilisées sont les suivantes:
 \label{sec:evalsync}
 
 Dans le cas synchrone, la convergence la plus rapide est obtenue lorsque
 \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 
 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,42 +292,42 @@ graphe d'interaction, le temps global de convergence est
 
 \begin{xpl}
   Intuitivement la convergence se propage selon les dépendances internes au système:
 
 \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
-  représente des exécutions parallèles dans le cas d'une initialisation avec la 
+  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 synchrones dans le cas d'une initialisation avec la 

   valeur (00100).
   Dans cette figure et les suivantes, les blocs doublement hachurés
   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}
   \centering
   \begin{minipage}{1\linewidth}
 
 
 \begin{figure}
   \centering
   \begin{minipage}{1\linewidth}

-    \includegraphics[scale=0.4]{images/eval_sync.eps}
-    \caption{Itérations parallèles}
+    \includegraphics[scale=0.4]{eval_sync}
+    \caption{Itérations synchrones}

     \label{fig:evalsync}
   \end{minipage}
   
   \begin{minipage}{1\textwidth}
     \label{fig:evalsync}
   \end{minipage}
   
   \begin{minipage}{1\textwidth}

-    \includegraphics[scale=0.4]{images/eval_mixte.pdf}
-    \caption{Iterations mixes avec
+    \includegraphics[scale=0.4]{eval_mixte}
+    \caption{Itérations mixes avec

       \class{1} $=\{1,2\}$, \class{3} $=\{3\}$,
       \class{4} $=\{4,5\}$.}
     \label{fig:evalmixte}
   \end{minipage}
   
   \begin{minipage}{1\textwidth}
       \class{1} $=\{1,2\}$, \class{3} $=\{3\}$,
       \class{4} $=\{4,5\}$.}
     \label{fig:evalmixte}
   \end{minipage}
   
   \begin{minipage}{1\textwidth}

-    \includegraphics[scale=0.4]{images/eval_async.pdf}
-    \caption{Iterations asynchrones}
+    \includegraphics[scale=0.4]{eval_async}
+    \caption{Itérations asynchrones}

     \label{fig:evalasync}
   \end{minipage}
 \end{figure}
 
   
    
     \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
   \begin{equation}
     \label{eq:I}
     I=I_{\class{1}}+I_{\class{3}}+I_{\class{4}}=2+1+2=5


@@ -366,7 +375,7 @@ graphe d'interaction, le temps global de convergence est
 %   \begin{figure}%[h]
 %     \centering
 %     % \includegraphics[width=\textwidth]{eval_siac.eps}
 %   \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}
 %     \caption{Execution  of  the \textit{SIAC}  iterations  starting  from state  4
 %       (00100).}
 %     \label{fig:evalsiac}


@@ -376,38 +385,14 @@ graphe d'interaction, le temps global de convergence est
 \subsection{le mode mixe}
 \label{sec:evalmixed}
 
 \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.
 
 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 
 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é. 
 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})
 \begin{equation}
   \label{eq:mixtelow}
   T(\textit{Mixed})\ge \sum_{k\in \mathcal{K}} I_k(\max_{l\in k}\textit{cp}_{l})


@@ -432,10 +417,10 @@ 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 
   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 synchrone.

 \end{xpl}
 
 \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.
 \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.


@@ -453,13 +438,14 @@ 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}
   \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}
 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 généralisé 
+  asynchrone.

   Certaines communications issues de l'élément $4$ n'ont pas été représentées
   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}
   On constate que le temps global de convergence est plus petit que celui des
   deux autres modes.
 \end{xpl}


@@ -472,23 +458,20 @@ ne recouvrent nullement les communications.
 
 
 
 
 
 

+ 

 
 
 
 
 
 
 
 
 
 

-
-
-
-\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
 %%% TeX-master: "main"
 
 %%% Local Variables: 
 %%% mode: latex
 %%% TeX-master: "main"

-%%% ispell-dictionary: "american"
+%%% ispell-dictionary: "french"

 %%% mode: flyspell
 %%% End: 
 %%% mode: flyspell
 %%% End: