-\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).
+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.
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 ou 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.
+Formalisons le mode les 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
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égies, 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 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.
+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 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é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 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*}
+\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}.
+
+
+
+
+\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.
+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 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 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 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]{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 mixe}
+\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 suffisants pour que la classe
+$\class{k} \in \mathcal{K}$ se stabilise
+sachant 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 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 synchrone.
+\end{xpl}
+
+\subsection{Le mode généralisé 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 calculs
+ne recouvrent nullement les communications.
+
+\begin{xpl}
+ La \Fig{fig:evalasync} présente un exemple d'exécution du mode généralisé
+ 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:
