rairo

[hdrcouchot.git] / mixage.tex

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 é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
% The  synchronous iterations  modes are  defined for  any $i  \in
% \{1,\ldots,n\}$ and any time $t=0,1,2,...$ by:
% \vspace{-.5em}
% \begin{equation}\label{eq:sync}
%   x^{t+1}_i= \left\{
% \begin{array}{l}
% f_i(x^t) \textrm{ if } \textit{bin}(s^t)[i] = 1\\ 
% x^{t}_i \textrm{ otherwise }
% \end{array} 
% \right.
% \end{equation}
% \vspace{-.5em}
% Notice that  parallel iterations only  constrain $s^t$ to be  equal to $2^n-1$
% for any $t$ whereas chaotic iterations do not constrain $s$.
% for  convenient reasons  [[JFC  : a  affiner]],  the set  of components  $\{1,
% \ldots,  n\}$   may  be  partitioned   into  $\alpha$  blocks   $b_1,  \ldots,
% b_{\alpha}$.
% %Elements of $b_i$ are ordered w.r.t. the component number.
% For $1\le i \le \alpha$, let $B_i$ be the product-space of block $i$.
% Formaly, $B_i = \Pi_{j \in b_{i} } E_j$.
% To  ease   the  reading,  lowercase   variable  and  upercase   one  represent
% respectively an element of some $E_i$ and a matrix of elements in some $E_i$.
% The components  may  be updated  (in  a random  order)  according to  a
% 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 
du temps d'acheminement de celles-ci. On parle de latence, de délai.

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$) 
à 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 généralisées asynchrone} 
est défini pour chaque  $i
\in \{1,\ldots,n\}$ et chaque  $t=0,1,2,...$ par:

\vspace{-.5em}
\begin{equation}\label{eq:async}
  x^{t+1}_i= \left\{
    \begin{array}{l}
      f_i( x_1^{D_{i1}^t},\ldots, x_{n}^{D_{i{n}}^t})
      \textrm{ si } \textit{bin}(s^t)[i] = 1\\ 
      x^{t}_i  \textrm{ sinon }
    \end{array} 
  \right.
\end{equation}

\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é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}      
\exists t_0 \,.\, 
(\forall t  \,.\,
t \geq t_0  \Rightarrow  x^{t}=x^{t_0}).
\end{equation}
Sinon les itérations sont dites \emph{divergentes}.
De plus, si $ (x^{(t)})^{t \in \mathbb{N}}$ défini  selon l'équation 
\Equ{eq:async} satisfait \Equ{eq:conv}  pour tous les  $x^{(0)}
\in  E$,  pour toutes les stratégies pseudo périodiques 
$s$  et pour toutes les matrices de dates,
$(D^{(t)})^{t  \in \Nats}$, alors les itérations de  $f$ sont 
\emph{universellement convergentes}.


\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 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{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_3(x_1,x_2,x_3,x_4,x_5) & = & x_3.\overline{x_1} \\
      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.
  $$
  
  \includegraphics[scale=0.55]{xplgraphmix}
  \end{center}
  \caption{Définition de $f:\Bool^5 \rightarrow \Bool^5$ et son graphe d'interaction}
  \label{fig:mix:map}
\end{figure}


\begin{figure}
  \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 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 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 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é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 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.
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: