From: couchot Date: Wed, 2 Jul 2014 14:31:14 +0000 (+0200) Subject: après mixage.... X-Git-Url: https://bilbo.iut-bm.univ-fcomte.fr/and/gitweb/hdrcouchot.git/commitdiff_plain/6e2993d89d55fe5f9e1380a06c4d9da27d6c7703?ds=inline après mixage.... --- diff --git a/main.pdf b/main.pdf index d41d713..13f4b50 100644 Binary files a/main.pdf and b/main.pdf differ diff --git a/main.tex b/main.tex index 5e94a3c..e12726a 100644 --- a/main.tex +++ b/main.tex @@ -121,12 +121,13 @@ \newcommand{\deriv}{\mathrm{d}} \newcommand{\class}[1]{\ensuremath{\langle #1\rangle}} \newcommand{\dom}[0]{\ensuremath{\textit{dom}}} - + \newcommand{\eqNode}[0]{\ensuremath{{\mathcal{R}}}} \newtheorem{theorem}{Théorème} \newtheorem{lemma}{Lemme} \newtheorem*{xpl}{Exemple} -\newtheorem{Proof}{Preuve} +\newtheorem*{Proof}{Preuve} +\newtheorem{Def}{Définition} \begin{document} \input{glossaire.tex} @@ -184,13 +185,18 @@ Blabla blabla. \chapter{Preuves sur les SDD} -\section{Preuve du théorème~\ref{th:Adrien}}\label{anx:sccg} +\section{Théorème~\ref{th:Adrien}}\label{anx:sccg} \input{annexesccg} -\section{Preuve de continuité de $G_f$ dans $(\mathcal{X},d)$}\label{anx:cont} +\section{Continuité de $G_f$ dans $(\mathcal{X},d)$}\label{anx:cont} \input{annexecontinuite.tex} -\section{Preuve de Correction et de complétude de l'approche de vérification de convergence à l'aide de SPIN}\label{anx:promela} + +\section{Convergence du mode mixe}\label{anx:mix} +\input{annexePreuveMixage} + + +\section{Correction et complétude de la vérification de convergence par SPIN}\label{anx:promela} \input{annexePromelaProof} \backmatter diff --git a/mixage.tex b/mixage.tex index de858cd..a03edc5 100644 --- a/mixage.tex +++ b/mixage.tex @@ -148,25 +148,347 @@ 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émarant 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. +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 symplifier 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. +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 represente 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 accesible 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 progresive 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. + + +\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{Iterations 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{Iterations 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. + \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 paralè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'execution du mode asynchrone. + Certaines communications issues de l'élément $4$ n'ont pas été représentées + pour des raisons de clareté. + On constate que le temps global de convergence est plus petit que celui des + deux autres modes. +\end{xpl} + + + + + + + + + + + + + + + + +\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. +%%% Local Variables: +%%% mode: latex +%%% TeX-master: "main" +%%% ispell-dictionary: "american" +%%% mode: flyspell +%%% End: