-\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.
+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}
Obtenir où 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}$ représente la date (inférieure ou égale à $t$)
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 sans attente}
+est défini pour chaque $i
\in \{1,\ldots,n\}$ et chaque $t=0,1,2,...$ par:
\vspace{-.5em}
\emph{universellement convergentes}.
-\section{Exemple jouet}
+\subsection{Exemple jouet}
On considère cinq éléments prenant à 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'interaction associé à cette fonction.
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 synchrones et asynchrones sont basés sur l'absence de cycles. Ils ne peuvent donc pas être appliqués ici.
+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}
\end{minipage}\hfill
\begin{minipage}[b]{.40\linewidth}
\begin{center}
- \includegraphics[scale=0.55]{images/xplgraphmix.eps}
+ \includegraphics[scale=0.55]{xplgraphmix}
\end{center}
\caption{Graphe d'interaction associé à $f$.}
\label{fig:mix:xplgraph}
\begin{figure}
\begin{minipage}{0.56\linewidth}
- \includegraphics[scale=0.55]{images/para_iterate_dec.eps}
+ \includegraphics[scale=0.55]{para_iterate_dec}
\caption{Itérations parallèles de $f$.}\label{fig:mix:xplparaFig}
\end{minipage}
\hfill
\begin{minipage}{0.39\linewidth}
- \includegraphics[scale=0.55]{images/chao_iterate_excerpt.eps}
+ \includegraphics[scale=0.55]{chao_iterate_excerpt}
\caption{Extrait d'itérations chaotiques.}
\label{fig:mix:xplchaoFig}
\end{minipage}
\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.
+asynhrones divergent alors que les synchrones convergent.
Les sections suivantes de ce chapitre montrent comment résoudre ce problème.
-\section{Itérations Mixes}
+\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.
-L'asynchronisme est conservé entre les groupes.
+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.
-\section{Durées de convergence}
+\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
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
+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{figure}
\centering
\begin{minipage}{1\linewidth}
- \includegraphics[scale=0.4]{images/eval_sync.eps}
+ \includegraphics[scale=0.4]{eval_sync}
\caption{Itérations parallèles}
\label{fig:evalsync}
\end{minipage}
\begin{minipage}{1\textwidth}
- \includegraphics[scale=0.4]{images/eval_mixte.pdf}
+ \includegraphics[scale=0.4]{eval_mixte}
\caption{Itérations mixes avec
\class{1} $=\{1,2\}$, \class{3} $=\{3\}$,
\class{4} $=\{4,5\}$.}
\end{minipage}
\begin{minipage}{1\textwidth}
- \includegraphics[scale=0.4]{images/eval_async.pdf}
+ \includegraphics[scale=0.4]{eval_async}
\caption{Itérations asynchrones}
\label{fig:evalasync}
\end{minipage}
% \begin{figure}%[h]
% \centering
% % \includegraphics[width=\textwidth]{eval_siac.eps}
-% \includegraphics[width=\textwidth]{images/eval_siac.eps}
+% \includegraphics[width=\textwidth]{eval_siac.eps}
% \caption{Execution of the \textit{SIAC} iterations starting from state 4
% (00100).}
% \label{fig:evalsiac}
mode parallèle.
\end{xpl}
-\subsection{Le mode asynchrone}
+\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.
-\section{Conclusion}
-Introduire de l'asynchronisme peut permettre de réduire le temps
-d'exécution global, mais peut aussi introduire de la divergence.
-Dans ce chapitre, nous avons exposé comment construire un mode combinant les
-avantage du synchronisme en terme de convergence avec les avantages
-de l'asynchronisme en terme de vitesse de convergence.
