ajout du dossier talk

[hdrcouchot.git] / mixage.tex

diff --git a/mixage.tex b/mixage.tex
index 4ee1171951de32a11e3f7674db2114cb10c5faa3..973305ac8693132f017b2acfb3073d477d0359b9 100644 (file)
--- a/mixage.tex
+++ b/mixage.tex
@@ -48,20 +48,20 @@ et les quatre derniers éléments (15  est  01111).
 % respectively an element of some $E_i$ and a matrix of elements in some $E_i$.
 % The components  may  be updated  (in  a random  order)  according to  a
 % strategy $s$, as in the synchronous mode. 
 % respectively an element of some $E_i$ and a matrix of elements in some $E_i$.
 % The components  may  be updated  (in  a random  order)  according to  a
 % strategy $s$, as in the synchronous mode. 

-Dans le mode asynchrone, a chaque itération $t$, chaque composant peut
+Dans le mode asynchrone, à chaque itération $t$, chaque composant peut

 mettre à jour son état en 
 mettre à jour son état en 

-fonction des dernières valeurs qu'il connaît des autre composants.
+fonction des dernières valeurs qu'il connaît des autres composants.

 Obtenir ou non les valeurs les plus à jour dépend du temps de calcul et 
 du temps d'acheminement de celles-ci. On parle de latence, de délai.
 
 Obtenir ou non les valeurs les plus à jour 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.
+Formalisons le mode des itérations asynchrone.

 Soit $x^0 =(x_1^0, \ldots, x_n^0)$ une configuration initiale.
 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 $(D^{t})^{t \in  \Nats}$ la suite de matrices de taille $n  \times n$  

 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$, 
 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$.
+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 asynchrone} 
 est défini pour chaque  $i
 \in \{1,\ldots,n\}$ et chaque  $t=0,1,2,...$ par:
 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:


@@ -90,7 +90,7 @@ t \geq t_0  \Rightarrow  x^{t}=x^{t_0}).
 Sinon les itérations sont dites \emph{divergentes}.
 De plus, si $ (x^{(t)})^{t \in \mathbb{N}}$ défini  selon l'équation 
 \Equ{eq:async} satisfait \Equ{eq:conv}  pour tous les  $x^{(0)}
 Sinon les itérations sont dites \emph{divergentes}.
 De plus, si $ (x^{(t)})^{t \in \mathbb{N}}$ défini  selon l'équation 
 \Equ{eq:async} satisfait \Equ{eq:conv}  pour tous les  $x^{(0)}

-\in  E$,  pour toutes les stratégies pseudo périodiques 
+\in  E$,  pour toutes les stratégies pseudo-périodiques 

 $s$  et pour toutes les matrices de dates,
 $(D^{(t)})^{t  \in \Nats}$, alors les itérations de  $f$ sont 
 \emph{universellement convergentes}.
 $s$  et pour toutes les matrices de dates,
 $(D^{(t)})^{t  \in \Nats}$, alors les itérations de  $f$ sont 
 \emph{universellement convergentes}.


@@ -150,12 +150,12 @@ qu'il converge vers le point fixe correspondant à l'entier 19.
 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 
 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}:
+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 unaires ne convergent pas pour certaines stratégies,
 les itérations asynchrones basées sur les même stratégies peuvent ne pas 
 le système peut infiniment boucler entre 11 et 3, entre 15 et 7.   
 
 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 
+converger non plus. 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élai peut introduire de la divergence.
 On considère par exemple la matrice $D^t$ dont chaque élément vaut  $t$
 sont activés à chaque itération, c'est à dire si $s^t$ est 
 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$


@@ -169,13 +169,13 @@ f_5(x^{t})
 $$
 \noindent sinon. 
 En démarrant de $x^0=00011$, le système atteint $x^1 = 01011$ et boucle entre 
 $$
 \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 
+ces deux configurations. Pour une même stratégie, les itérations 

 asynchrones divergent alors que les synchrones convergent.
 Les sections suivantes de ce chapitre montrent comment résoudre ce problème.
 
 asynchrones divergent alors que les synchrones convergent.
 Les sections suivantes de ce chapitre montrent comment résoudre ce problème.
 

-\subsection{Itérations Mixes}
+\subsection{Itérations mixtes}

 Introduit dans~\cite{abcvs05}  
 Introduit dans~\cite{abcvs05}  

-le mode d'\emph{itérations mixes} combine synchronisme et asynchronisme.
+le mode d'\emph{itérations mixtes} 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 
 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 


@@ -194,11 +194,11 @@ 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 
 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.
+les classes, \textit{i.e.},
+$\mathcal{K}=\{1,\ldots,n\}/\eqNode$. On peut définir les itérations mixtes.

 
 

-\begin{Def}[Itérations mixes]
-Les itérations mixes d'un système discret suit l'équation \Equ{eq:async} où
+\begin{Def}[Itérations mixtes]
+Les itérations mixtes d'un système discret suivent 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}
 


@@ -210,8 +210,8 @@ 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:
 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 
+\begin{Def}[Itérations mixtes avec delais uniformes]
+  Le mode mixte 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:
   $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:


@@ -227,9 +227,9 @@ 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 
 
 \begin{theorem}\label{th:cvg}
   Soit une fonction $f$ possédant un unique point fixe $x^*$ et une stratégie 

-  pseudo périodique $s$.
+  pseudo-périodique $s$.

   Si les itérations synchrones convergent vers $x^*$ pour cette stratégie, 
   Si les itérations synchrones convergent vers $x^*$ pour cette stratégie, 

-  alors les itérations mixes à délai uniforme convergent aussi vers $x^*$
+  alors les itérations mixtes à délai uniforme convergent aussi vers $x^*$

   pour cette stratégie.
 \end{theorem}
 
   pour cette stratégie.
 \end{theorem}
 


@@ -240,7 +240,7 @@ 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 
 
 \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.
+globales de convergence pour les modes synchrones, mixtes 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.
 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.


@@ -259,7 +259,7 @@ Les notations utilisées sont les suivantes:
   de bits
   nécessaires 
   pour représenter  l'état courant du composant $i$ et est notée $\textit{cs}_i$;
   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 besoin 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. 
   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. 


@@ -289,7 +289,7 @@ 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}uds se stabilise lorsque ceux dont il dépend sont eux aussi stables.
+  un n{\oe}ud 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).
   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).


@@ -307,7 +307,7 @@ graphe d'interaction, le temps global de convergence est
   
   \begin{minipage}{1\textwidth}
     \includegraphics[scale=0.4]{eval_mixte}
   
   \begin{minipage}{1\textwidth}
     \includegraphics[scale=0.4]{eval_mixte}

-    \caption{Itérations mixes avec
+    \caption{Itérations mixtes avec

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


@@ -379,15 +379,15 @@ graphe d'interaction, le temps global de convergence est
 %   \end{figure}
 % \end{xpl}
 
 %   \end{figure}
 % \end{xpl}
 

-\subsection{le mode mixe}
+\subsection{le mode mixte}

 \label{sec:evalmixed}
 
 
 On considère $|\mathcal{K}|$  classes de composants synchronisés.
 (comme donné  en équation~(\ref{eq:I})).
 \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 
+Soit $I_k$ le nombre d'itérations suffisant pour que la classe 

 $\class{k}  \in \mathcal{K}$ se stabilise 
 $\class{k}  \in \mathcal{K}$ se stabilise 

-sachant  toutes ses dépendances ont déjà convergé. 
+sachant que 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}
 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}


@@ -411,7 +411,7 @@ ascendants pour converger. On a dans ce cas:
 \end{equation}
 
 \begin{xpl}
 \end{equation}
 
 \begin{xpl}

-  Une exécution du mode mixe est donnée à la~\Fig{fig:evalmixte}.
+  Une exécution du mode mixte 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.
   On peut constater que le temps d'exécution peut être  
   plus petit que pour le 
   mode synchrone.


@@ -419,8 +419,8 @@ ascendants pour converger. On a dans ce cas:
 
 \subsection{Le mode unaire asynchrone}
 \label{sec:evalasync}
 
 \subsection{Le mode unaire 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.
+En termes de durée de convergence, ce mode peut être vu comme un 
+cas particulier du mode mixte où toutes les classes sont des singletons.

 La borne minimale peut donc s'exprimer comme:
 \begin{equation}
   \label{eq:asynclow}
 La borne minimale peut donc s'exprimer comme:
 \begin{equation}
   \label{eq:asynclow}