X-Git-Url: https://bilbo.iut-bm.univ-fcomte.fr/and/gitweb/hdrcouchot.git/blobdiff_plain/f4dd79b2c3181cb26ec94555b62ed77dcb0a4200..refs/heads/master:/mixage.tex diff --git a/mixage.tex b/mixage.tex index de858cd..356523d 100644 --- a/mixage.tex +++ b/mixage.tex @@ -1,18 +1,26 @@ -\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} 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). -On dit que la stratégie est -\emph{pseudo-periodique} si tous les éléments sont activés infiniment -souvent. +et les quatre derniers éléments (15 est 01111). % , 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épent 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$ -dont chaque élément $D_{ij}^{t}$ represente la date (inférieure ou égale à $t$) +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,15 +71,15 @@ 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} \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} @@ -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'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. +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 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,67 +117,358 @@ connus~\cite{Bah00} de conditions suffisantes établissant la convergencedu syst 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èlles 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 representées à l'aide d'entiers -plutôt que nombres binaires. Le graphe des itérations parallèles est donné +Dans ce qui suit, les configurations sont représentées à l'aide d'entiers +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é à -la~\Fig{fig:mix:xplchaoFig}. Les libélé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}: +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 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. - - - - - - - For instance, consider the matrix $D^t$ to be equal to $(t)$ except -in $D^t_{12}$ where it is equal to $t-1$ if $t$ is odd. Then if $t$ is even, -$x^{t+1}$ is $f(x^{t})$; if $t$ is odd we have +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 $$ x^{t+1} = \left( f_1(x_1^{t},x_2^{t-1},x_3^{t},x_4^{t},x_5^{t}), f_2(x^{t}), \ldots, f_5(x^{t}) \right). $$ -\noindent Starting from $x^0=00011$, the system reaches $x^1 = 01011$ and enters -in a cycle between these two configurations. We are then confronted to -divergent asynchronous iterations whereas the synchronous ones converge. In the -next section, a particular execution mode is described which enables -asynchronism in iterations while guaranteeing the convergence. +\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égie, les itérations +asynchrones divergent alors que les synchrones convergent. +Les sections suivantes de ce chapitre montrent comment résoudre ce problème. + +\subsection{Itérations mixtes} +Introduit dans~\cite{abcvs05} +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. +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)$. +\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 classes, \textit{i.e.}, +$\mathcal{K}=\{1,\ldots,n\}/\eqNode$. On peut définir les itérations mixtes. + +\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é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 +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 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: + \begin{equation*} +% \forall t\, .\, D_{p_0q_0}^{t} = D_{p_1q_1}^{t} + \bigwedge_{p_k \in \class{p}, q_k \in \class{q} } + D_{p_{k}q_{k}}^{t} = d_{pq}^t + \end{equation*} +\end{Def} + +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$. + Si les itérations synchrones convergent vers $x^*$ pour cette stratégie, + alors les itérations mixtes à délai uniforme convergent aussi vers $x^*$ + pour cette stratégie. +\end{theorem} + +La preuve de ce théorème est donnée en section~\ref{anx:mix}. + + + + +\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, mixtes et asynchrones. +Pour simplifier le discours, on considère que les itérations +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. + +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, 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 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 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 + $\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$. +\end{description} + +% The updating strategy and the delays are respectively related to the computation +% and the communication times. In fact, the notion of strategy in dynamical +% systems models the power heterogeneity between the components of the system. And +% the notion of delays models the heterogeneity in the communication links between +% the components. + +\subsection{Le mode synchrone} +\label{sec:evalsync} + +Dans le cas synchrone, la convergence la plus rapide est obtenue lorsque +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 +\begin{equation} + \label{eq:tsisc} + T(\textit{Sync})=I\times(\max_i\textit{cp}_i+\max_{i,j}(B_{ji}\times(\beta_{ij}+\textit{cs}_i\times\tau_{ij}))) +\end{equation} + + +\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 progressive est illustrée à la \Fig{fig:evalsync} qui + 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. + + +\begin{figure} + \centering + \begin{minipage}{1\linewidth} + \includegraphics[scale=0.4]{eval_sync} + \caption{Itérations synchrones} + \label{fig:evalsync} + \end{minipage} + + \begin{minipage}{1\textwidth} + \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]{eval_async} + \caption{Itérations asynchrones} + \label{fig:evalasync} + \end{minipage} +\end{figure} + + + + 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 + \end{equation} +\end{xpl} + +% It is possible to speed up the global execution time while keeping the same +% iteration scheme by relaxing the synchronization constraints only on the +% communications. In that case, called SIAC (Synchronous Iterations - +% Asynchronous Communications), a component sends its state value to every +% component which needs it as soon as that value has been updated. On the +% receiver side, an iteration begins only when all the state values corresponding +% to the previous iteration have been received from the other components whose +% the receiver depends on. + +% In that context, the synchronous iterations scheme is preserved as every +% iteration on any component is computed using the dependency values from the +% previous iteration on the other components. So, the global behavior is +% preserved while the communication cost is decreased. Moreover, the +% synchronization is no more global but restricted to each connected component in +% the connection graph of the system. Their respective speeds of evolution depend +% on their \emph{source classes} (the classes without any external dependency). +% Also, between the starts of two consecutive iterations, a component may receive +% from its dependencies some data values which correspond either to the previous +% iteration or to the current one (from components which have already finished +% their current iteration). This implies a small buffering of the received data +% (two elements per dependency) and an explicit distinction of the received data +% according to their original iteration. + +% Finally, as well as in the following subsections, it is not possible to provide +% an exact evaluation of the global execution time in that case, but we can +% provide lower and upper bounds. The worst case of that version coincides with +% the fully synchronous scheme previously described. And in the best case, all +% the communications are overlapped by the computations on the slowest component, +% implying the suppression of the communication term in~(\ref{eq:tsisc}). + +% We have then the following boundaries: +% \begin{equation} +% \label{eq:tsiac} +% I\times(\max_i\textit{cp}_i)\le T(\textit{SIAC}) \le T(Sync) +% \end{equation} +% \begin{xpl} +% Figure~\ref{fig:evalsiac} illustrates the potential speed up obtained with the +% SIAC variant in the same context of our running example. +% \begin{figure}%[h] +% \centering +% % \includegraphics[width=\textwidth]{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 mixte} +\label{sec:evalmixed} + + +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 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}) +\end{equation} +\noindent qui apparaît lorsque tous les délais de communication sont consommés +par des durées de calcul. + +Concernant le majorant, celui-ci correspond au cas où +les durées de communications entre les classes +désynchronisées ne sont pas consommées par des calculs ou lorsque +chaque classe nécessite la stabilisation de tous ses +ascendants pour converger. On a dans ce cas: + + +\begin{equation} + \label{eq:mixteup} + T(\textit{Mixed})\le\sum_{k \in \mathcal{K}}\left(I_k\times(\max_{l\in + k}\textit{cp}_{l})+\max_{l\in k,e\in k', k\preceq k'}B_{el}\times(\beta_{le}+\textit{cs}_{l}\tau_{le})\right) +\end{equation} + +\begin{xpl} + 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 synchrone. +\end{xpl} + +\subsection{Le mode unaire asynchrone} +\label{sec:evalasync} +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} + T(\textit{Async})\ge\max_{i=1}^{n}I_i\times \textit{cp}_{i} +\end{equation} +où $I_i$ est le nombre d'itérations suffisant pour que le n{\oe}ud $i$ converge +et qui est atteint si tous les n{\oe}uds sont indépendants les uns des autres. +Cette borne est arbitrairement faible et n'est pas atteinte dès qu'une +dépendance existe. +La borne supérieure quant à elle est donnée par: +\begin{equation} + \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 calculs +ne recouvrent nullement les communications. + +\begin{xpl} + 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 + deux autres modes. +\end{xpl} + + + + + + + + + + + + + + +% 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 +%%% TeX-master: "main" +%%% ispell-dictionary: "french" +%%% mode: flyspell +%%% End: