From cb56b165bc864d9858b71195e2fb3ea9cb899683 Mon Sep 17 00:00:00 2001 From: couchot Date: Wed, 16 Jul 2014 11:57:05 +0200 Subject: [PATCH] mixage fin --- main.pdf | Bin 1771692 -> 1771692 bytes mixage.tex | 73 ++++++++++++++++++++++++++++------------------------- 2 files changed, 38 insertions(+), 35 deletions(-) diff --git a/main.pdf b/main.pdf index 13f4b5095e7ed9c42905438a19c80cb12bf0d677..ae264f885ae4104ebf456da6ccd2aa8f1c36f063 100644 GIT binary patch delta 164 zcmZ28F=x%hoQ4+07N!>F7M2#)7Pc1l7LFFq7OocV7M>Q~7QPn#7J(MQ7NHj57LgXw z7O@ub7Ks+gEmFZhI1J4U4Nc5UO{PcxkdlV;w%7fT3S@P5axpM< fHnTK#GIcREaC9@UFf%ZF7M2#)7Pc1l7LFFq7OocV7M>Q~7QPn#7J(MQ7NHj57LgXw z7O@ub7Ks+gEmFZhI1G#o&5X=V45ml_kdlV;w%7fT3S@P*Ff?&AHga+?HZU-7cCj=! fb1^h=HgI-zGB-CfwlH(HQ?MbVWV_HmsaaeAzH%+S diff --git a/mixage.tex b/mixage.tex index a03edc5..a499409 100644 --- 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) -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,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. -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$ -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$, @@ -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 -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} @@ -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 -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} @@ -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} - \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} @@ -133,12 +133,12 @@ connus~\cite{Bah00} de conditions suffisantes établissant la convergencedu syst \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é à -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. @@ -158,14 +158,14 @@ f_5(x^{t}) \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} -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 @@ -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. -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 -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. @@ -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} -\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; @@ -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 -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 @@ -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: - 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 - induquent la stabilisation du composant. + indiquent la stabilisation du composant. \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} - \caption{Iterations mixes avec + \caption{Itérations mixes avec \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} - \caption{Iterations asynchrones} + \caption{Itérations asynchrones} \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 @@ -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 - mode paralèle. + mode parallèle. \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} - 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 - 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} @@ -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 -- 2.39.5