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:
