-\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
% strategy $s$, as in the synchronous mode.
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
+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$)
+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
+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}
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\\
+ \textrm{ si } \textit{bin}(s^t)[i] = 1\\
x^{t}_i \textrm{ sinon }
\end{array}
\right.
\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}
\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} \\
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
+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 terme 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:
