\end{equation}
\noindent active successivement les deux premiers éléments (24 est 11000)
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.
% , 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 ou non les valeurs les plus à jours dépend 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 asynchrone.
+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}$ représente la date (inférieure ou égale à $t$)
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élai peut introduire de la divergence.
On considère par exemple la matrice $D^t$ dont chaque élément vaut $t$
$$
\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
-asynhrones divergent alors que les synchrones convergent.
+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 Mixes}
+\subsection{Itérations mixtes}
Introduit dans~\cite{abcvs05}
-le mode d'\emph{itérations mixes} combine synchronisme et asynchronisme.
+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
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)$.
+ 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.
+les classes, \textit{i.e.},
+$\mathcal{K}=\{1,\ldots,n\}/\eqNode$. On peut définir les itérations mixtes.
-\begin{Def}[Itérations mixes]
-Les itérations mixes d'un système discret suit l'équation \Equ{eq:async} où
+\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}
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
+\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:
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^*$
+ alors les itérations mixtes à délai uniforme convergent aussi vers $x^*$
pour cette stratégie.
\end{theorem}
\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.
+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.
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
+\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.
\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.
+ 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).
\begin{minipage}{1\textwidth}
\includegraphics[scale=0.4]{eval_mixte}
- \caption{Itérations mixes avec
+ \caption{Itérations mixtes avec
\class{1} $=\{1,2\}$, \class{3} $=\{3\}$,
\class{4} $=\{4,5\}$.}
\label{fig:evalmixte}
% \end{figure}
% \end{xpl}
-\subsection{le mode mixe}
+\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 suffisants pour que la classe
+Soit $I_k$ le nombre d'itérations suffisant pour que la classe
$\class{k} \in \mathcal{K}$ se stabilise
-sachant toutes ses dépendances ont déjà convergé.
+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}
\end{equation}
\begin{xpl}
- Une exécution du mode mixe est donnée à la~\Fig{fig:evalmixte}.
+ 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 généralisé asynchrone}
+\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 mixe où toutes les classes sont des singletons.
+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}
ne recouvrent nullement les communications.
\begin{xpl}
- La \Fig{fig:evalasync} présente un exemple d'exécution du mode généralisé
+ 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é.
