X-Git-Url: https://bilbo.iut-bm.univ-fcomte.fr/and/gitweb/hdrcouchot.git/blobdiff_plain/f4dd79b2c3181cb26ec94555b62ed77dcb0a4200..98c34e4d34d6f63836eefca981f5d1ce73a865e2:/mixage.tex?ds=inline diff --git a/mixage.tex b/mixage.tex index de858cd..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. @@ -148,25 +148,350 @@ 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 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 +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é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 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. + +\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 classe, \textit{i.e.}, +$\mathcal{K}=\{1,\ldots,n\}/\eqNode$. On peut définir les itérations mixes. + +\begin{Def}[Itérations mixes] +Les itérations mixes d'un système discret suit 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 +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 mixes avec delais uniformes] + Le mode mixe 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*} + % 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. + + +\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 mixes à 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}. + + + + +\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 simplifier le discours, on considère que les itérations +convergent en in $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, les délais 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 + 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; +\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}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 + indiquent la stabilisation du composant. + + +\begin{figure} + \centering + \begin{minipage}{1\linewidth} + \includegraphics[scale=0.4]{images/eval_sync.eps} + \caption{Itérations parallèles} + \label{fig:evalsync} + \end{minipage} + + \begin{minipage}{1\textwidth} + \includegraphics[scale=0.4]{images/eval_mixte.pdf} + \caption{Itérations mixes 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} + \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]{images/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} +\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 +\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 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 parallèle. +\end{xpl} + +\subsection{Le mode 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. +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 calcules +ne recouvrent nullement les communications. + +\begin{xpl} + 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 clarté. + On constate que le temps global de convergence est plus petit que celui des + deux autres modes. +\end{xpl} + + + + + + + + + +\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. + + + + + +% 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: "american" +%%% mode: flyspell +%%% End: