mixage fin

[hdrcouchot.git] / mixage.tex

diff --git a/mixage.tex b/mixage.tex
index a03edc51851b30f617f9871ed34b50ef11619523..a499409656f0ddabdc97a69d5fdc6bd53b3a5aca 100644 (file)
--- 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) 
 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,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.
 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$  
 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$, 
 à 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 
 
 \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}      


@@ -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 
 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}
 
 \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}
 \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}
 \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}
 
 \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é à 
 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.   
 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. 
 \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}  
 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 
 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.
 \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 
 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.
 
 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}
 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;
   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
 \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,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:
 
 \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
   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}
 
 
 \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}
   
   \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}
       \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}
   
   \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}
 
   
    
     \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


@@ -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 
   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}
 \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}
 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
   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,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
 
 %%% Local Variables: 
 %%% mode: latex