X-Git-Url: https://bilbo.iut-bm.univ-fcomte.fr/and/gitweb/hdrcouchot.git/blobdiff_plain/cb56b165bc864d9858b71195e2fb3ea9cb899683..refs/heads/master:/mixage.tex diff --git a/mixage.tex b/mixage.tex index a499409..356523d 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 avant chaque itération. +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} @@ -10,9 +21,6 @@ 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 é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. % , it is sufficient to establish that the set $\{t \mid t \in \mathbb{N} % \land \textit{bin}(s^t)[i] = 1\}$ is infinite for any $i$, $1 \le i \le n$, % where @@ -40,21 +48,22 @@ souvent. % 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 -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 +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. -Formalisons le mode les itérations asynchrones. +Formalisons le mode des 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$ +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$, -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 +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: \vspace{-.5em} @@ -62,8 +71,8 @@ Le \emph{mode des itérations asynchrones} est défini pour chaque $i x^{t+1}_i= \left\{ \begin{array}{l} f_i( x_1^{D_{i1}^t},\ldots, x_{n}^{D_{i{n}}^t}) - \textrm{ if } \textit{bin}(s^t)[i] = 1\\ - x^{t}_i \textrm{ sinon } + \textrm{ si } i \in s^t \\ + x^{t}_i \textrm{ sinon.} \end{array} \right. \end{equation} @@ -81,24 +90,26 @@ 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)} -\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}. -\section{Exemple jouet} -On considère cinq éléments prenant à valeurs dans $\Bool$. +\begin{xpl} +On considère cinq éléments à 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. +0 et 31. +La~\Fig{fig:mix:map} donne la fonction définissant la dynamique du +système et son graphe d'interaction. 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} - \centering - $ f(x)= \left \{ +\begin{figure}%[ht] + \begin{center} + $$ f(x)= \left \{ \begin{array}{lll} f_1(x_1,x_2,x_3,x_4,x_5) & = & x_1.\overline{x_2} + \overline{x_1}.x_2 \\ f_2(x_1,x_2,x_3,x_4,x_5) & = & \overline{x_1 + x_2} \\ @@ -106,48 +117,47 @@ connus~\cite{Bah00} de conditions suffisantes établissant la convergence du sys f_4(x_1,x_2,x_3,x_4,x_5) & = & x_5 \\ f_5(x_1,x_2,x_3,x_4,x_5) & = & \overline{x_3} + x_4 \end{array} - \right. $ -\caption{Fonction $f$ de l'exemple jouet.} -\label{fig:mix:map} -\end{minipage}\hfill -\begin{minipage}[b]{.40\linewidth} - \begin{center} - \includegraphics[scale=0.55]{images/xplgraphmix.eps} + \right. + $$ + + \includegraphics[scale=0.55]{xplgraphmix} \end{center} - \caption{Graphe d'interaction associé à $f$.} - \label{fig:mix:xplgraph} -\end{minipage} + \caption{Définition de $f:\Bool^5 \rightarrow \Bool^5$ et son graphe d'interaction} + \label{fig:mix:map} \end{figure} \begin{figure} -\begin{minipage}{0.56\linewidth} - \includegraphics[scale=0.55]{images/para_iterate_dec.eps} - \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} - \caption{Extrait d'itérations chaotiques.} - \label{fig:mix:xplchaoFig} -\end{minipage} + \begin{center} + \subfigure[Itérations synchrones de $f$.]{ + \includegraphics[scale=0.50]{para_iterate_dec} + \label{fig:mix:xplparaFig} + } + \subfigure[Extrait des itérations unaires.]{ + \includegraphics[scale=0.49]{chao_iterate_excerpt} + \label{fig:mix:xplchaoFig} + } + \end{center} + \caption{Graphes des itérations de $f$ définie à la figure~\ref{fig:mix:map}} \end{figure} +\end{xpl} + 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é +plutôt que nombres binaires. Le graphe des itérations synchrones 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é à +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 chaotiques ne convergent pas pour la stratégie -pseudo périodique donnée à l'équation~\Equ{eq:pseudo}: +activés. Les itérations unaires 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. -Comme les itérations chaotiques ne convergent pas pour certaines stratégies, +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élais peut introduire de la divergence. +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$ sauf $D^t_{12}$ qui vaut $t-1$ si $t$ est impair. On a ainsi $x^{t+1}= f(x^{t})$ si $t$ est pair et @@ -159,40 +169,40 @@ f_5(x^{t}) $$ \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. -\section{Itérations Mixes} +\subsection{Itérations mixtes} 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 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. La \emph{relation de synchronisation} $\eqNode$ est définie sur l'ensemble des n{\oe}uds par: $i \eqNode j$ si $i$ et $j$ appartiennent à la même composante fortement - connexe (CFC) dans $\Gamma(F)$. + connexe (CFC) dans $\Gamma(f)$. \end{Def} 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 -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} -Dans ce contexte, il n'y a plus de délais entre deux noeuds de la même CFC +Dans ce contexte, il n'y a plus de délai entre deux noeuds de la même CFC et leurs mises à jour sont synchronisées. Cependant, pour $p_0$ et $p_1$ dans la même classe \class{p}, et $q$ dans une autre classe \class{q}, ce mode opératoire autorise @@ -200,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: -\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: @@ -210,12 +220,6 @@ Pour gommer cette distinction, on définit le mode suivant: \bigwedge_{p_k \in \class{p}, q_k \in \class{q} } D_{p_{k}q_{k}}^{t} = d_{pq}^t \end{equation*} - % Je me demande si cette formalisation n'a pas un souci par rapport à une - % formalisation avec un seul q ?! (car deux éléments supposent qu'ils sont distincts) - % car si on a deux éléments dans chaque classe, on peut alors avoir deux - % groupes de délais : supposons (a,b) dans p et (c,d) dans q - % a,c et b,d sont égaux et a,d et b,c sont égaux mais rien n'implique que a,c et - % a,d soient égaux !!! \end{Def} On a alors le théorème suivant. @@ -223,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 - pseudo périodique $s$. + pseudo-périodique $s$. 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} @@ -234,11 +238,11 @@ 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. +globales de convergence pour les modes synchrones, mixtes et asynchrones. 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 $I$ étapes dans le mode synchrone et que le graphe 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. @@ -246,16 +250,18 @@ 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: \begin{description} -\item [Taille pour coder l'information:] elle représente le nombre de nécessaire de bits +\item [Taille pour coder l'information] elle représente le nombre + 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 +\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. On définit $\beta_{ij}$ et $\tau_{ij}$ comme la latence et la bande passante du lien entre $i$ et $j$. @@ -283,9 +289,9 @@ 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}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 parallèles dans le cas d'une initialisation avec la + représente des exécutions synchrones dans le cas d'une initialisation avec la valeur (00100). Dans cette figure et les suivantes, les blocs doublement hachurés indiquent la stabilisation du composant. @@ -294,21 +300,21 @@ graphe d'interaction, le temps global de convergence est \begin{figure} \centering \begin{minipage}{1\linewidth} - \includegraphics[scale=0.4]{images/eval_sync.eps} - \caption{Itérations parallèles} + \includegraphics[scale=0.4]{eval_sync} + \caption{Itérations synchrones} \label{fig:evalsync} \end{minipage} \begin{minipage}{1\textwidth} - \includegraphics[scale=0.4]{images/eval_mixte.pdf} - \caption{Itérations mixes avec + \includegraphics[scale=0.4]{eval_mixte} + \caption{Itérations mixtes avec \class{1} $=\{1,2\}$, \class{3} $=\{3\}$, \class{4} $=\{4,5\}$.} \label{fig:evalmixte} \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,48 +372,24 @@ 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} % \end{figure} % \end{xpl} -\subsection{le mode mixe} +\subsection{le mode mixte} \label{sec:evalmixed} -% As detailed in Sect.~\ref{sec:mdn}, the mixed case asynchronously combines -% subsets of synchronized components (the different classes). The double interest -% of that approach is to ensure the convergence of the system while using -% asynchronism. - -% 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. - -% Le nombre d'itérations requises pour obtenir la convergence en mode mixe -% dépend des arangements entre les délais de communication et les durées de -% calcul. - -% number directly depends on the arrangement of delays during the execution and -% then on the communication times. But it also depends on the evolution functions -% which influence the way each part of the system stabilizes itself. -% In fact, according to its evolution function, a component may reach its fixed -% point state even with a part of its input data not recently updated. In -% addition, as mentioned earlier, the set of components in any system does not -% stabilize at the same time and there is often a propagation of the stabilization -% through the system. -% Also, the previously mentioned phenomenon of stabilization propagation through -% the system is still present in mixed mode. 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 -$k \in \mathcal{K}$ se stabilise -sachant toutes ses dépendances ont déjà convergé. -Ainsi $I$ vaut $\sum_{k \in \mathcal{K}} I_k$. -La borne inférieur pour la durée de convergence des itérations asynchrones est +(comme donné en équation~(\ref{eq:I})). +Soit $I_k$ le nombre d'itérations suffisant pour que la classe +$\class{k} \in \mathcal{K}$ se stabilise +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} \label{eq:mixtelow} T(\textit{Mixed})\ge \sum_{k\in \mathcal{K}} I_k(\max_{l\in k}\textit{cp}_{l}) @@ -429,16 +411,16 @@ ascendants pour converger. On a dans ce cas: \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 parallèle. + mode synchrone. \end{xpl} -\subsection{Le mode asynchrone} +\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} @@ -453,11 +435,12 @@ La borne supérieure quant à elle est donnée par: \label{eq:asyncup} T(\textit{Async})\le\sum_{i=1}^{n}\left(I_i\times \textit{cp}_{i}+\max_{1\le k \le n}B_{ki}(\beta_{ik}+\textit{cs}_{i}\tau_{ik})\right) \end{equation} -et apparaît lorsque chaque élément dépend des autres et que les calcules +et apparaît lorsque chaque élément dépend des autres et que les calculs ne recouvrent nullement les communications. \begin{xpl} - La \Fig{fig:evalasync} présente un exemple d'exécution du mode asynchrone. + La \Fig{fig:evalasync} présente un exemple d'exécution du mode unaire + asynchrone. Certaines communications issues de l'élément $4$ n'ont pas été représentées pour des raisons de clarté. On constate que le temps global de convergence est plus petit que celui des @@ -472,12 +455,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. @@ -492,6 +469,6 @@ de l'asynchronisme en terme de vitesse de convergence. %%% Local Variables: %%% mode: latex %%% TeX-master: "main" -%%% ispell-dictionary: "american" +%%% ispell-dictionary: "french" %%% mode: flyspell %%% End: