X-Git-Url: https://bilbo.iut-bm.univ-fcomte.fr/and/gitweb/hdrcouchot.git/blobdiff_plain/98c34e4d34d6f63836eefca981f5d1ce73a865e2..2b04820abccb0772b10b2c53542ecddc6a6f600c:/mixage.tex?ds=sidebyside diff --git a/mixage.tex b/mixage.tex index a499409..d5f1981 100644 --- 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} @@ -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. -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$) @@ -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$. -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} @@ -87,13 +99,15 @@ $(D^{(t)})^{t \in \Nats}$, alors les itérations de $f$ sont \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 -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} @@ -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} - \includegraphics[scale=0.55]{images/xplgraphmix.eps} + \includegraphics[scale=0.55]{xplgraphmix} \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} - \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} - \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} @@ -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 -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. -\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. -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. @@ -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 @@ -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 -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: @@ -294,13 +308,13 @@ graphe d'interaction, le temps global de convergence est \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} - \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\}$.} @@ -308,7 +322,7 @@ graphe d'interaction, le temps global de convergence est \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} @@ -366,7 +380,7 @@ graphe d'interaction, le temps global de convergence est % \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} @@ -435,7 +449,7 @@ ascendants pour converger. On a dans ce cas: 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. @@ -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.