fsfd

[hdrcouchot.git] / mixage.tex

diff --git a/mixage.tex b/mixage.tex
index a499409656f0ddabdc97a69d5fdc6bd53b3a5aca..d5f1981d43478f293e5ea98fdf53ca9b1e274a02 100644 (file)
--- a/mixage.tex
+++ b/mixage.tex
@@ -1,8 +1,19 @@
-\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.
+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}
 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}


@@ -46,7 +57,7 @@ fonction des dernières valeurs qu'il connaît des autre composants.
 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.
 
 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.
+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}$ représente la date (inférieure ou égale à $t$) 
 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}$ représente la date (inférieure ou égale à $t$) 


@@ -54,7 +65,8 @@ dont chaque élément $D_{ij}^{t}$ représente la date (inférieure ou égale à
 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$.
 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 sans attente} 
+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}


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

-\section{Exemple jouet}
+\subsection{Exemple jouet}

 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'interaction associé à cette fonction.
 On note que le graphe d'interaction contient cinq cycles. Les résultats 
 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'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.
+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}
 
 \begin{figure}[ht]
 \begin{minipage}[b]{0.55\linewidth}


@@ -112,7 +126,7 @@ connus~\cite{Bah00} de conditions suffisantes établissant la convergence du sys
 \end{minipage}\hfill
 \begin{minipage}[b]{.40\linewidth}
   \begin{center}
 \end{minipage}\hfill
 \begin{minipage}[b]{.40\linewidth}
   \begin{center}

-    \includegraphics[scale=0.55]{images/xplgraphmix.eps}
+    \includegraphics[scale=0.55]{xplgraphmix}

   \end{center}
   \caption{Graphe d'interaction associé à $f$.}
   \label{fig:mix:xplgraph}
   \end{center}
   \caption{Graphe d'interaction associé à $f$.}
   \label{fig:mix:xplgraph}


@@ -122,12 +136,12 @@ connus~\cite{Bah00} de conditions suffisantes établissant la convergence du sys
 
 \begin{figure}
 \begin{minipage}{0.56\linewidth}
 
 \begin{figure}
 \begin{minipage}{0.56\linewidth}

-  \includegraphics[scale=0.55]{images/para_iterate_dec.eps}
+  \includegraphics[scale=0.55]{para_iterate_dec}

   \caption{Itérations parallèles de $f$.}\label{fig:mix:xplparaFig}
 \end{minipage}
 \hfill
 \begin{minipage}{0.39\linewidth}
   \caption{Itérations parallèles de $f$.}\label{fig:mix:xplparaFig}
 \end{minipage}
 \hfill
 \begin{minipage}{0.39\linewidth}

-  \includegraphics[scale=0.55]{images/chao_iterate_excerpt.eps}
+  \includegraphics[scale=0.55]{chao_iterate_excerpt}

   \caption{Extrait d'itérations chaotiques.}
   \label{fig:mix:xplchaoFig}
 \end{minipage}
   \caption{Extrait d'itérations chaotiques.}
   \label{fig:mix:xplchaoFig}
 \end{minipage}


@@ -160,17 +174,17 @@ $$
 \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 
 \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.
+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}  
 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. 
 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. 

-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. 


@@ -234,7 +248,7 @@ 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.
 Pour simplifier le discours, on considère que les itérations 
 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 


@@ -246,7 +260,7 @@ 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 
 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:
 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:


@@ -294,13 +308,13 @@ graphe d'interaction, le temps global de convergence est
 \begin{figure}
   \centering
   \begin{minipage}{1\linewidth}
 \begin{figure}
   \centering
   \begin{minipage}{1\linewidth}

-    \includegraphics[scale=0.4]{images/eval_sync.eps}
+    \includegraphics[scale=0.4]{eval_sync}

     \caption{Itérations parallèles}
     \label{fig:evalsync}
   \end{minipage}
   
   \begin{minipage}{1\textwidth}
     \caption{Itérations parallèles}
     \label{fig:evalsync}
   \end{minipage}
   
   \begin{minipage}{1\textwidth}

-    \includegraphics[scale=0.4]{images/eval_mixte.pdf}
+    \includegraphics[scale=0.4]{eval_mixte}

     \caption{Itérations mixes avec
       \class{1} $=\{1,2\}$, \class{3} $=\{3\}$,
       \class{4} $=\{4,5\}$.}
     \caption{Itérations mixes avec
       \class{1} $=\{1,2\}$, \class{3} $=\{3\}$,
       \class{4} $=\{4,5\}$.}


@@ -308,7 +322,7 @@ graphe d'interaction, le temps global de convergence est
   \end{minipage}
   
   \begin{minipage}{1\textwidth}
   \end{minipage}
   
   \begin{minipage}{1\textwidth}

-    \includegraphics[scale=0.4]{images/eval_async.pdf}
+    \includegraphics[scale=0.4]{eval_async}

     \caption{Itérations asynchrones}
     \label{fig:evalasync}
   \end{minipage}
     \caption{Itérations asynchrones}
     \label{fig:evalasync}
   \end{minipage}


@@ -366,7 +380,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}


@@ -435,7 +449,7 @@ ascendants pour converger. On a dans ce cas:
   mode parallèle.
 \end{xpl}
 
   mode parallèle.
 \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.


@@ -472,12 +486,6 @@ 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.