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

diff --git a/mixage.tex b/mixage.tex
index de858cd..e4a283c 100644
--- 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) 
-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,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.
-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.
 
-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}$ 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$.
-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}
@@ -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})
-      \textrm{ if } \textit{bin}(s^t)[i] = 1\\ 
+      \textrm{ si } \textit{bin}(s^t)[i] = 1\\ 
       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 
-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}      
@@ -87,18 +99,20 @@ $(D^{(t)})^{t  \in \Nats}$, alors les itÃ©rations de  $f$ sont
 \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 
-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{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}  \\
@@ -106,67 +120,358 @@ 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}
-  \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}
-  \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]{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{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.
-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.   
 
-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.
-
-
-
-
-
-
-  For instance, consider the matrix $D^t$ to be equal to $(t)$ except
-in $D^t_{12}$  where it is equal  to $t-1$ if $t$  is odd. Then if  $t$ is even,
-$x^{t+1}$ is $f(x^{t})$; if $t$ is odd we have
+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  
 $$
 x^{t+1}  = \left(
 f_1(x_1^{t},x_2^{t-1},x_3^{t},x_4^{t},x_5^{t}), f_2(x^{t}), \ldots, 
 f_5(x^{t})
 \right).
 $$
-\noindent Starting from $x^0=00011$, the system reaches $x^1 = 01011$ and enters
-in  a  cycle  between these  two  configurations.   We  are then  confronted  to
-divergent asynchronous iterations whereas the synchronous ones converge.  In the
-next  section,   a  particular  execution   mode  is  described   which  enables
-asynchronism in iterations while guaranteeing the convergence.
+\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.
+Les sections suivantes de ce chapitre montrent comment rÃ©soudre ce problÃ¨me.
+
+\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. 
+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. 
+  La  \emph{relation de synchronisation} $\eqNode$ est
+  dÃ©finie sur l'ensemble des n{\oe}uds par:
+  $i \eqNode j$ si $i$ et $j$  appartiennent Ã  la mÃªme composante fortement
+  connexe (CFC) dans $\Gamma(F)$.
+\end{Def}
+
+On peut facilement dÃ©montrer que la relation de synchronisation est une 
+relation d'Ã©quivalence sur l'ensemble des Ã©lÃ©ments. 
+On introduit quelques notations: par la suite \class{i} reprÃ©sente la classe 
+d'Ã©quivalence de $i$ et $\mathcal{K}$ reprÃ©sente l'ensemble de toutes 
+les classe, \textit{i.e.},
+$\mathcal{K}=\{1,\ldots,n\}/\eqNode$. On peut dÃ©finir les itÃ©rations mixes.
+
+\begin{Def}[ItÃ©rations mixes]
+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Ã©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
+des dÃ©lais diffÃ©rents entre $p_0$ et $q$  et entre  $p_1$ et $q$.
+Ainsi $p_1$ et $p_2$ sont distinguables mÃªme s'ils appartiennent Ã  la mÃªme 
+classe.
+Pour gommer cette distinction, on dÃ©finit le mode suivant:
+\begin{Def}[ItÃ©rations mixes avec delais uniformes]
+  Le mode mixe a des \emph{dÃ©lais uniformes}si pour chaque 
+  $t=0,1,\ldots$ et pour chaque paire de  classes  $(\class{p}, \class{q})$,
+  il existe une constante $d^t_{pq}$  telle que la propriÃ©tÃ© suivante est 
+  Ã©tablie:
+  \begin{equation*}
+%    \forall t\, .\,      D_{p_0q_0}^{t}  =     D_{p_1q_1}^{t}  
+     \bigwedge_{p_k \in  \class{p}, q_k \in \class{q} } 
+     D_{p_{k}q_{k}}^{t}  =   d_{pq}^t    
+  \end{equation*}
+\end{Def}
+
+On a alors le thÃ©orÃ¨me suivant.
+
+
+\begin{theorem}\label{th:cvg}
+  Soit une fonction $f$ possÃ©dant un unique point fixe $x^*$ et une stratÃ©gie 
+  pseudo pÃ©riodique $s$.
+  Si les itÃ©rations synchrones convergent vers $x^*$ pour cette stratÃ©gie, 
+  alors les itÃ©rations mixes Ã  dÃ©lai uniforme convergent aussi vers $x^*$
+  pour cette stratÃ©gie.
+\end{theorem}
+
+La preuve de ce thÃ©orÃ¨me est donnÃ©e en section~\ref{anx:mix}.
+
+
+
+
+\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 
+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 
+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}
+\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 
+  pour faire une mise Ã  jour locale de son Ã©tat;
+\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$.
+\end{description}
+
+% The updating strategy and the delays are respectively related to the computation
+% and  the communication  times.  In fact,  the  notion of  strategy in  dynamical
+% systems models the power heterogeneity between the components of the system. And
+% the notion of delays models the heterogeneity in the communication links between
+% the components.
+
+\subsection{Le mode synchrone}
+\label{sec:evalsync}
+
+Dans le cas synchrone, la convergence la plus rapide est obtenue lorsque
+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 
+\begin{equation}
+  \label{eq:tsisc}
+  T(\textit{Sync})=I\times(\max_i\textit{cp}_i+\max_{i,j}(B_{ji}\times(\beta_{ij}+\textit{cs}_i\times\tau_{ij})))
+\end{equation}
+
+
+\begin{xpl}
+  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 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.
+
+
+\begin{figure}
+  \centering
+  \begin{minipage}{1\linewidth}
+    \includegraphics[scale=0.4]{eval_sync}
+    \caption{ItÃ©rations synchrones}
+    \label{fig:evalsync}
+  \end{minipage}
+  
+  \begin{minipage}{1\textwidth}
+    \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}
+    \includegraphics[scale=0.4]{eval_async}
+    \caption{ItÃ©rations asynchrones}
+    \label{fig:evalasync}
+  \end{minipage}
+\end{figure}
+
+  
+   
+  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
+  \end{equation}
+\end{xpl}
+
+% It is  possible to  speed up the  global execution  time while keeping  the same
+% iteration  scheme  by  relaxing  the  synchronization constraints  only  on  the
+% communications.    In  that   case,  called   SIAC  (Synchronous   Iterations  -
+% Asynchronous  Communications),  a  component  sends  its state  value  to  every
+% component  which needs  it  as soon  as that  value  has been  updated.  On  the
+% receiver side, an iteration begins  only when all the state values corresponding
+% to the  previous iteration  have been received  from the other  components whose
+% the receiver depends on.
+
+% In  that  context, the  synchronous  iterations  scheme  is preserved  as  every
+% iteration  on any component  is computed  using the  dependency values  from the
+% previous  iteration  on  the  other  components.  So,  the  global  behavior  is
+% preserved   while  the   communication   cost  is   decreased.   Moreover,   the
+% synchronization is no more global  but restricted to each connected component in
+% the connection graph of the system.  Their respective speeds of evolution depend
+% on their  \emph{source classes} (the  classes without any  external dependency).
+% Also, between the starts of  two consecutive iterations, a component may receive
+% from its dependencies  some data values which correspond  either to the previous
+% iteration or  to the  current one (from  components which have  already finished
+% their current iteration).   This implies a small buffering  of the received data
+% (two elements per  dependency) and an explicit distinction  of the received data
+% according to their original iteration.
+
+% Finally, as well as in the  following subsections, it is not possible to provide
+% an  exact evaluation  of the  global execution  time in  that case,  but  we can
+% provide lower and  upper bounds.  The worst case of  that version coincides with
+% the fully  synchronous scheme previously described.   And in the  best case, all
+% the communications are overlapped by  the computations on the slowest component,
+% implying the suppression of the communication term in~(\ref{eq:tsisc}).
+
+% We have then the following boundaries:
+% \begin{equation}
+%   \label{eq:tsiac}
+%   I\times(\max_i\textit{cp}_i)\le T(\textit{SIAC}) \le T(Sync)
+% \end{equation}
+% \begin{xpl}    
+%   Figure~\ref{fig:evalsiac} illustrates the potential speed up obtained with the
+%   SIAC variant in the same context of our running example.
+%   \begin{figure}%[h]
+%     \centering
+%     % \includegraphics[width=\textwidth]{eval_siac.eps}
+%     \includegraphics[width=\textwidth]{eval_siac.eps}
+%     \caption{Execution  of  the \textit{SIAC}  iterations  starting  from state  4
+%       (00100).}
+%     \label{fig:evalsiac}
+%   \end{figure}
+% \end{xpl}
+
+\subsection{le mode mixe}
+\label{sec:evalmixed}
+
+
+On considÃ¨re $|\mathcal{K}|$  classes de composants synchronisÃ©s.
+(comme donnÃ©  en Ã©quation~(\ref{eq:I})).
+Soit $I_k$ le nombre d'itÃ©rations suffisants pour que la classe 
+$\class{k}  \in \mathcal{K}$ se stabilise 
+sachant  toutes ses dÃ©pendances ont dÃ©jÃ  convergÃ©. 
+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})
+\end{equation}
+\noindent qui apparaÃ®t lorsque tous les dÃ©lais de communication sont consommÃ©s 
+par des durÃ©es de calcul.
+
+Concernant le majorant, celui-ci correspond au cas oÃ¹ 
+les durÃ©es de communications entre les classes
+dÃ©synchronisÃ©es ne sont pas consommÃ©es par des calculs ou lorsque 
+chaque classe nÃ©cessite la stabilisation de tous ses 
+ascendants pour converger. On a dans ce cas:
+
+
+\begin{equation}
+  \label{eq:mixteup}
+  T(\textit{Mixed})\le\sum_{k \in \mathcal{K}}\left(I_k\times(\max_{l\in
+      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)
+\end{equation}
+
+\begin{xpl}
+  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 synchrone.
+\end{xpl}
+
+\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.
+La borne minimale peut donc s'exprimer comme:
+\begin{equation}
+  \label{eq:asynclow}
+  T(\textit{Async})\ge\max_{i=1}^{n}I_i\times \textit{cp}_{i}
+\end{equation}
+oÃ¹ $I_i$ est le nombre d'itÃ©rations suffisant pour que le n{\oe}ud $i$ converge
+et qui est atteint si tous les n{\oe}uds sont indÃ©pendants les uns des autres.
+Cette borne est arbitrairement faible et n'est pas atteinte dÃ¨s qu'une 
+dÃ©pendance existe.
+La borne supÃ©rieure quant Ã  elle est donnÃ©e par:
+\begin{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 calculs 
+ne recouvrent nullement les communications.
+
+\begin{xpl}
+  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
+  deux autres modes.
+\end{xpl}
+
+
+
+
+
+
+
+
+
+ 
+
+
+
+
 
+% 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"
+%%% ispell-dictionary: "french"
+%%% mode: flyspell
+%%% End: 
