X-Git-Url: https://bilbo.iut-bm.univ-fcomte.fr/and/gitweb/these_charles_emile.git/blobdiff_plain/0af348b9f9fa2f0bc44be5f4a129e869fbb7e5d4..HEAD:/These_RCE.tex?ds=sidebyside

diff --git a/These_RCE.tex b/These_RCE.tex
index 2e58d63..7455573 100644
--- a/These_RCE.tex
+++ b/These_RCE.tex
@@ -67,6 +67,12 @@
 %\usepackage{subcaption}
 \usepackage{graphicx}
 
+\usepackage{algpseudocode}
+\algnewcommand\algorithmicinput{\textbf{Input:}}
+\algnewcommand\Input{\item[\algorithmicinput]}
+\algnewcommand\algorithmicoutput{\textbf{Output:}}
+\algnewcommand\Output{\item[\algorithmicoutput]}
+
 \usepackage{multirow}
  
 %%--------------------
@@ -77,11 +83,11 @@
 %% The second mandatory parameter is the date of the PhD defense.
 %% The third mandatory parameter is the reference number given by
 %% the University Library after the PhD defense.
-\declarethesis[Sous-titre]{Titre}{17 septembre 2012}{XXX}
+\declarethesis[]{Simulations Ã  trÃ¨s large Ã©chelle d'algorithmes parallÃ¨les numÃ©riques itÃ©ratifs et asynchrones}{XX XXX 2016}{XXX}
  
 %%--------------------
 %% Set the author of the PhD thesis
-\addauthor[email]{PrÃ©nom}{Nom}
+\addauthor[email]{C. E.}{RAMAMONJISOA}
  
 %%--------------------
 %% Add a member of the jury
@@ -215,6 +221,11 @@
 
 \part{PARTIE I: Contexte scientifique et revue de l'Ã©tat de l'art}
 
+Cette premiÃ¨re partie met en exergue d'une part, le contexte scientifique de nos travaux et d'autre part, une revue de l'Ã©tat de l'art dans le domaine de la recherche concernÃ© ainsi que les travaux associÃ©s existant actuellement. \\
+Elle introduit ainsi dans un premier chapitre, la classe des algorithmes itÃ©ratifs parallÃ¨les de systÃ¨mes d'Ã©quations linÃ©aires ou non Ã  large Ã©chelle et les mÃ©thodes de rÃ©solution particuliÃ¨rement, dans un environnement de type grille. DiffÃ©rents algorithmes seront prÃ©sentÃ©s et les Ã©tapes d'approche pour exÃ©cuter l'application, en particulier, le problÃ©matique du partitionnement du problÃ¨me ainsi que les mÃ©canismes des communications synchrone et asynchrone seront rappellÃ©s. Une section de ce chapitre montre les interÃªts et principes de la simulation d'exÃ©cution des algorithmes de calcul sur grille. DiffÃ©rents outils de simulation seront prÃ©sentÃ©s et comparÃ©s en insistant particuliÃ¨rement sur SIMGRID, l'outil choisi pour rÃ©aliser nos travaux. Comme les algorithmes utilisÃ©s sont Ã©crits en MPI (Message Passing Interface), les primitives MPI les plus utilisÃ©s sont passÃ©es en revue. Enfin, le chapitre se ferme sur l'utilisation du module SMPI (Simulation MPI) de SIMGRID qui simule le comportement et l'exÃ©cution rÃ©elle des applications MPI.\\
+Un second chapitre est consacrÃ© Ã  l'Ã©tude de la performance des applications parallÃ¨les et distribuÃ©es, en particulier, la classe d'algorithmes qui nous interesse. Deux volets principaux sont concernÃ©s par cette Ã©tude : l'analyse de la performance et la prÃ©diction de cette mÃªme performance Ã  grande Ã©chelle. L'analyse de la performance de l'application essaie de dÃ©terminer le comportement du code selon les diffÃ©rents environnement d'exÃ©cution, mais aussi de chercher Ã  optimiser le code en identifant les parties du code les plus consommatrices de ressources (CPU, mÃ©moire, communications, ...) tout en Ã©liminant certains bugs du code. Par ailleurs, la prÃ©diction de la performance, comme son nom l'indique, essaie de reporter le comportement du code Ã  grande Ã©chelle Ã  partir de benchmarks effectuÃ©s Ã  moindre echelle. Surtout, les indicateurs de temps de calcul et de communication dans la grille sont capturÃ©s lors d'une telle prÃ©diction. Une telle opÃ©ration peut se faire sur une plateforme difficilement accessible dans la pratique ou mÃªme encore inexistante. Plusieurs outils d'analyse de la performance du code seront prÃ©sentÃ©s ainsi qu' une mÃ©thode pour la prÃ©diction de la performance du code. \\
+Le dernier chapitre de cette premiÃ¨re partie avance nos motivations sur les contributions dans ce domaine choisi, pour la simulation de l'exÃ©cution des algorithmes concernÃ©s sur une grille de calcul afin d'analyser leurs performances mais surtout de pouvoir simuler et prÃ©dire les rÃ©sultats d'exÃ©cution Ã  grande Ã©chelle avec une grille composÃ©e de plus en plus de grappes d'ordinateurs et de plus en plus de processeurs et de coeurs.    
+
 \chapter{Cadre de travail et contexte scientifique}
 
 \section{Classe des algorithmes itÃ©ratifs parallÃ¨les Ã  large Ã©chelle dans une grille de calcul}
@@ -235,7 +246,7 @@ recherchÃ©e X{*} avec une valeur rÃ©siduelle la plus rÃ©duite possible.
   X^{k+1} = \text{f ( } X^k \text{ ), k = 0,1, \dots{} }	
 \end{equation}
 
-oÃ¹ chaque $x_k$ est un vecteur Ã  n dimension et f une fonction de $R^n$ vers
+oÃ¹ chaque $X_k$ est un vecteur Ã  n dimension et f une fonction de $R^n$ vers
 $R^n$.
 
 La solution du problÃ¨me sera donc le vecteur X{*} tel que X{*} = f
@@ -245,14 +256,14 @@ L'exÃ©cution en parallÃ¨le d'un tel algorithme
 consiste au dÃ©coupage (partitionnement) du problÃ¨me en plus petits
 morceaux (ou blocs) et d'assigner chaque bloc Ã  une
 unitÃ© de calcul. Chaque processeur tourne le mÃªme algorithme de faÃ§on
-concourante jusqu'Ã  la dÃ©tection de la convergence
+conccurente jusqu'Ã  la dÃ©tection de la convergence
 locale qui peut Ãªtre obtenue soit par l'atteinte d'un
 nombre maximum fixÃ© d'itÃ©rations soit que la diffÃ©rence
 entre les valeurs du vecteur inconnu entre deux itÃ©rations successives est devenue
 infÃ©rieure Ã  la valeur rÃ©siduelle convenue. Cette condition de convergence
 locale peut Ãªtre Ã©crite comme suit : 
 \begin{equation}
-  (k\leq \MI) \text{ or } (\|X_l^k - X_l^{k+1}\|_{\infty}\leq\epsilon)	
+  (k\leq \MI) \text{ or } (\|X_l^k - X_l^{k+1}\|\leq\epsilon)	
 \end{equation}
 La convergence globale sera dÃ©clarÃ©e lorsque tous les processeurs
 ont atteint leur convergence locale. De faÃ§on gÃ©nÃ©rale, plusieurs
@@ -278,13 +289,16 @@ figure \figref{decoupage} prÃ©sente un exemple de dÃ©coupage en domaines de la
 matrice initiale entre deux clusters constituÃ©s chacun de 18 processeurs, soit un total de 36 processeurs.
 
 \begin{figure}[!ht]
-%\centering
-\begin{minipage}[t]{5.5cm}
+\centering
+\begin{minipage}[t]{6.5cm}
 \centering
 \includegraphics [ width =5.5cm]{"3D data partitionning btw 2 clusters"}
 \caption {DÃ©coupage d'une matrice tridimensionnelle entre deux clusters formÃ©s de 18 processeurs chacun}
 \end{minipage}
-\begin{minipage}[t]{5.5cm}
+\begin{minipage}[t]{1.4cm}
+\centering
+\end{minipage}
+\begin{minipage}[t]{6.5cm}
 \centering
 \includegraphics [ width =5.5cm]{"1D-2D-3D Domain decomposition"}
 \caption {DÃ©composition en domaines 1D, 2D et 3D}
@@ -373,9 +387,26 @@ un Ã©quilibre entre ces deux temps constitue un des objectifs dÃ¨s le
 partitionnement du problÃ¨me. Le temps de communication est impactÃ©
 sur la faÃ§on dont les Ã©changes sont effectuÃ©s. 
 
-\mfigure[h]{width=8cm, height=8cm}{"Synchronous iterations model"} {ModÃ¨le de communication synchrone} {sync}
 
-\mfigure[h]{width=8cm, height=8cm}{"Asynchronous iterations model"} {ModÃ¨le de communication asynchrone} {async}
+\begin{figure}[!ht]
+\centering
+\begin{minipage}[t]{6.5cm}
+\centering
+\includegraphics [ width =5.5cm]{"Synchronous iterations model"}
+\caption {ModÃ¨le de communication synchrone}
+\end{minipage}
+\begin{minipage}[t]{1.4cm}
+\centering
+\end{minipage}
+\begin{minipage}[t]{6.5cm}
+\centering
+\includegraphics [ width =5.5cm]{"Asynchronous iterations model"}
+\caption {ModÃ¨le de communication asynchrone}
+\end{minipage}
+%\caption{Partitionnement du problÃ¨me}
+\end{figure}
+
+
 
 %\begin{figure}[h]
 %\begin{subfigure}{0.5\textwidth}
@@ -445,34 +476,362 @@ si un mÃ©canisme de reprise sur panne est mis en place.
 \section{MÃ©thodes de rÃ©solution parallÃ¨les du problÃ¨me de Poisson et de
 l'algorithme two-stage multisplitting de Krylov}
 
+Afin de valider les rÃ©sultats de simulation d'applications distribuÃ©es parallÃ¨les effectuÃ©e dans le cadre de nos travaux, diffÃ©rents algorithmes, largement utilisÃ©s dans diffÃ©rents domaines scientifiques, Ã©crits en MPI/C ont Ã©tÃ© utilisÃ©s. Ils font partie de la classe des mÃ©thodes de rÃ©solution numÃ©rique itÃ©rative qui, en opposition aux mÃ©thodes directes et par approches successives,calcule par approximation la solution du problÃ¨me posÃ© avec une erreur connue d'avance aprÃ¨s l'initialisation d'une valeur initiale. Les mÃ©thodes itÃ©ratives permettent la rÃ©solution des systÃ¨mes linÃ©aires mais aussi non linÃ©aires. Elles se prÃªtent Ã  une parallÃ¨lisation plus aisÃ©e et supportent mieux le passage Ã  l'echelle [4]. 
+Les sections suivantes vont dÃ©crire les algorithmes considÃ©rÃ©s Ã  savoir la mÃ©thode de rÃ©solution de Jacobi et l'algorithme de Krylov avec deux variantes : le classique GMRES en mode native  d'une part et la variante multi-dÃ©composition(multisplitting) d'autre part.
+
 \subsection{Algorithme de Jacobi}
+L'algorithme de Jacobi est une des plus simples mÃ©thodes de rÃ©solutions d'un systÃ¨me d'Ã©quations linÃ©aires [3,4].
+
+Soit le systÃ¨me d'Ã©quations linÃ©aires suivant : 
+
+\begin{equation}
+\label{eq:2}
+Ax = b   
+\end{equation}
+oÃ¹ : 	
+
+\begin{tabbing}
+\hspace{2cm}\=\kill
+  \> A est une matrice carrÃ©e rÃ©elle creuse inversible de taille n, \\ 
+  \> x le vecteur inconnu de taille n, \\ 
+  \> et b un vecteur constant.\\
+\end{tabbing}
+
+\eqref{eq:2} peut s'Ã©crire : 
+
+\begin{equation*}
+  \left(\begin{array}{ccc}
+      a_{1,1} & \cdots & a_{1,n} \\
+      \vdots & \ddots & \vdots\\
+      a_{n,1} & \cdots & a_{n,n}
+    \end{array} \right)
+  \times
+  \left(\begin{array}{c}
+      x_1 \\
+      \vdots\\
+      x_n
+    \end{array} \right)
+	=
+  \left(\begin{array}{c}
+      b_1 \\
+      \vdots\\
+      b_n
+    \end{array} \right)
+\end{equation*}
+ 
+Notons : \\ 
+D la matrice carrÃ©e de taille n formÃ©e par la diagonale de A. On suppose qu'aucun Ã©lÃ©ment $a_{i,i}$ n'est Ã©gal Ã  0. \\
+L (resp. U) la matrice carrÃ©e de taille n formÃ©e par les Ã©lÃ©ments du bas (resp. haut) de A.\\
+On a donc : 
+
+\begin{equation*}
+D=\left( \begin{array}{ccc}
+a_{1,1} & \cdots & 0 \\
+\vdots & \ddots & \vdots \\
+0 & \cdots & a_{n,n}
+\end{array}\right) 
+\space
+, \hspace{0,1cm}L=\left( \begin{array}{ccc}
+0 & \cdots & 0 \\
+\vdots & \ddots & \vdots \\
+a_{n,1} & \cdots & 0
+\end{array}\right)
+\space
+et \hspace{0,2cm}U=\left( \begin{array}{ccc}
+0 & \cdots & a_{1,n} \\
+\vdots & \ddots & \vdots \\
+0 & \cdots & 0
+\end{array}\right)
+\end{equation*}
+
+Comme A = D + (L + U) et si $D^{-1}$ est l'inverse de la matrice diagonale D, on peut Ã©crire :
+
+\begin{equation*}
+Ax = b  \Leftrightarrow  ( D + L + U )x = b  
+\end{equation*}
+
+\begin{equation*}
+\Leftrightarrow  Dx = -(L+U)x + b
+\end{equation*}
+
+\begin{equation}
+\label{eq:3}
+\Leftrightarrow ( x = D^{-1} \times [-(L+U)] x + D^{-1} b)
+\end{equation}
+Cette derniÃ¨re Ã©galitÃ© est l'equation $du  point  fixe$. L'algorithme itÃ©ratif de Jacobi Figure~\ref{algo:01} (version sÃ©quentielle) et ses variantes dÃ©coule de cette Ã©quation [4]. Si $x^{(k)}$ est la valeur approchÃ©e du vecteur inconnu Ã  l'itÃ©ration $k$, on a d'aprÃ¨s \eqref{eq:3} avec un $x^{0}$ initial donnÃ© : 
+
+\begin{equation}
+x^{(k+1)} = D^{-1} \times [-(L+U)] x^{(k)} + D^{-1} b  
+\end{equation}
+
+\begin{figure}[!t]
+\begin{algorithmic}[1]
+\Input $A_{ij}$ (Matrice d'entrÃ©e), $b_{i}$ (Vecteur du membre droit), $n$ (Taille des vecteurs) et des matrices, $xOld_{i}$ (vecteur solution Ã  l'itÃ©ration prÃ©cÃ©dente)
+\Output $x_{i}$ (Vecteur solution)\medskip
+
+\State Charger $A_{ij}$, $b_{i}$, $n$, 
+\State Assigner la valeur initiale $x^0$ 
+\State \textbf{repeat} 
+\For {$i=0,1,2,\ldots (n-1)$} 
+\State $x_i \leftarrow 0$
+\For {$j=0,1,2,\ldots (n-1) \hspace{0.1cm} et \hspace{0.1cm} j \neq i$}
+\State $x_{i} \leftarrow x_{i} + A_{ij} \times xOld_{j}$
+\EndFor
+\For {$i=0,1,2,\ldots (n-1)$}
+\State $xOld_{i} \leftarrow ( b_{i} - x_{i} ) \quad {/} \quad A_{ii}$
+\EndFor
+\EndFor
+\State \textbf{Until} {( Obtention de la condition de convergence )} 
+
+\Statex
+\end{algorithmic}
+\caption{Algorithme itÃ©ratif de Jacobi}
+\label{algo:01}
+\end{figure}
+
+La condition de convergence est dÃ©terminÃ©e au dÃ©but du traitement. La mÃ©thode permet de passer Ã  large Ã©chelle en distribuant l'exÃ©cutuion de l'algorithme sur un environnement de grille de calcul. 
 
 \subsection{MÃ©thode de rÃ©solution GMRES}
 
-Native
+La mÃ©thode native GMRES ou "Generalized Minimal Residual", dÃ©veloppÃ©e par Saad et Schultz en 1986, est une des mÃ©thodes itÃ©ratives les plus utilisÃ©es pour rÃ©soudre un systÃ¨me d'Ã©quations linÃ©aires ou non [3,4,43,44,45]. Elle est basÃ©e sur la minimisation de la norme euclidienne d'un vecteur rÃ©sidu obtenu Ã  chaque itÃ©ration par une projection sur un espace de Krylov. Plus prÃ©cisement, soit le systÃ¨me d'Ã©quations \eqref{eq:2}. Un sous-espace de Krylov d'ordre {m} est dÃ©fini comme suit : 
 
-Version Â« two-stage Â»
+\begin{equation}
+\label{eq:Krylov}
+K_m = Vect \{ b, Ab, A^2b, ..., A^{m-1}b \}   
+\end{equation}
+
+oÃ¹ : Vect dÃ©signe l'espace gÃ©nÃ©rÃ© par les vecteurs en argument.
+  
+Il est dÃ©montrÃ© [3,..] que le vecteur projetÃ© $x_m$ sur $K_m$ donne une valeur approchÃ©e de la solution exacte du systÃ¨me d'Ã©quations en minimisant le rÃ©sidu $r_m$ tel que : 
+
+\begin{equation}
+\label{eq:residu}
+r_m = Ax_m - b   
+\end{equation}
+On suppose que les vecteurs de l'Ã©quation \eqref{eq:Krylov} sont linÃ©airement indÃ©pendants. Comme le montre cette Ã©quation, la taille des vecteurs de base augmente linÃ©airement avec m qui varie de 0 Ã  $n-1$ (n Ã©tant la taille initiale de la matrice A) entrainant Ã  chaque itÃ©ration un besoin de stockage de plus en plus grand. \\  
+
+Afin de rÃ©duire et optimiser l'algorithme, on peut combiner avec d'autres mÃ©thodes telles que les itÃ©rations de Arnoldi [] utilisant la procÃ©dure d'orthogonalisation de Gram-Shmidt [] pour trouver une base orthonormÃ©e de l'espace $K_m$ notÃ©e $Q_m = [q_1, ..., q_m]$. On peut donc Ã©crire : 
+
+\begin{equation}
+\label{eq:proj}
+\forall x_m \in K_m, x_m = Q_m y 
+\end{equation}
+
+et le rÃ©sidu dont la norme est Ã  minimiser peut s'Ã©crire :  
+\begin{equation}
+\label{eq:residu}
+r_m = A Q_m y - b  
+\end{equation}
+
+D'aprÃ¨s cette procÃ©dure, il existe une matrice de Hessenberg $H_m$ de taille m telle que :    
+\begin{equation}
+\label{eq:hessen}
+H_m = Q^T_m A Q_m  
+\end{equation}
+En introduisant la matrice notÃ©e $\tilde{H}_m$ obtenue par l'ajout d'une ligne supplÃ©mentaire Ã  $H_m$ avec la seule valeur non nulle est celle Ã  la position (m+1,m), on dÃ©montre qu'on a la relation suivante [3,43,44,45] : 
+ 
+\begin{equation}
+\label{eq:hessen1}
+A Q_m = Q_{m+1} \tilde{H}_m   
+\end{equation}
+
+Ainsi, le rÃ©sidu donnÃ© par l'Ã©quation \eqref{eq:residu} peut s'Ã©crire en utilisant \eqref{eq:hessen1} : 
+\begin{equation*}
+\label{eq:residu1}
+(r_m = Q_{m+1} \tilde{H}_m y - b) \\
+\Leftrightarrow  (\|r_m\| = \|Q_{m+1} \tilde{H}_m y - b\|) 
+\end{equation*}
+
+Comme la norme ne change pas aprÃ¨s la multiplication avec la matrice unitaire $Q^{-1}_m$, on a :
+\begin{equation*}
+\label{eq:norme1}
+\|r_m\| = \|Q_{m+1} \tilde{H}_m y - b\| = \|Q^{-1}_m Q_{m+1} \tilde{H}_m y - Q^{-1}_m b\|  
+\end{equation*}
+
+Ou : 
+
+\begin{equation}
+\label{eq:norme2}
+\|r_m\| = \|\tilde{H}_m y - Q^{-1}_m b\|  
+\end{equation}
+
+Or : 
+\begin{equation}
+\label{eq:q_1}
+Q^{-1}_m b = \left( \begin{array}{c}
+q^{-1}_1 b \\
+q^{-1}_2 b \\
+\vdots \\
+q^{-1}_{m+1} b 
+\end{array}\right)   
+\end{equation}
+
+Et comme les colonnes $q_j$ de $Q_m$ forment une base orthonormale de l'espace de Krylov $K_m$, on a : 
+
+\begin{equation*}
+\label{eq:q1}
+q_1 = \frac{b}{\|b\|}  
+\end{equation*}
+et : 
+\begin{equation*}
+\label{eq:q_1j}
+\forall j > 1,  q^{-1}_{j} b = 0 \text { et } q^{-1}_1 b = \|b\|
+\end{equation*}
+Donc, l'Ã©quation \eqref{eq:q_1} peut s'ecrire :
+
+\begin{equation}
+\label{eq:q_f}
+Q^{-1}_m b = \|b\| e_1 \text{ avec } e_1 = (1,0, ..., 0)^T
+\end{equation}
+
+Finalement, la norme du rÃ©sidu Ã  minimiser peut s'Ã©crire Ã  partie de \eqref{eq:norme2} et \eqref{eq:q_f} :  
+
+\begin{equation}
+\label{eq:norme3}
+\|r_m\| = \| \tilde{H}_m y - \text {  } \|b\|  \text {  } e_1 \|  
+\end{equation}
+La mÃ©thode des moindres carrÃ©s peut Ãªtre utilisÃ©e pour effectuer cette minimisation et trouver $y$. On utilise aprÃ¨s la relation \eqref{eq:proj} pour dÃ©terminer la valeur approchÃ©e de la solution Ã  l'itÃ©ration m.
+
+\begin{equation*}
+\label{eq:proj1}
+x_m = Q_m y 
+\end{equation*}
+L'algorithme de GMRES repose sur ces deux derniÃ¨res equations.
+Une autre amÃ©lioration de l'algorithme, surtout en terme de rÃ©duction des vecteurs Ã  maintenir en mÃ©moire mais aussi en termes de temps de calcul pour atteindre la convergence, est le "redÃ©marrage" [43]. Il s'agit de "redÃ©marrer" l'algorithme aprÃ¨s une tranche de k itÃ©rations, k Ã©tant fixÃ© par l'utilisateur au dÃ©part. A chaque redÃ©marrage, la valeur initiale $x_0$ est remplacÃ©e par le dernier $x_m$ trouvÃ© et $r_0$ par le dernier $r_m$.  \\ 
+
+Le pseudo-code de l'algorithme GMRES optimisÃ© avec les itÃ©rations d'Arnoldi avec un redÃ©marrage est donnÃ© Ã  la Figure~\ref{algo:02}.  
+
+\begin{figure}[!t]
+\begin{algorithmic}[1]
+\Input \\
+$A_{ij}$ (Matrice d'entrÃ©e), $b_{i}$ (Vecteur du membre droit), $n$ (Taille des vecteurs) et des matrices, \\
+$m$ (Nombre d'itÃ©rations avant redÃ©marrage), $h_{ij}$ (Matrice de Hessenberg),  \\
+$q_i$(Suite de vecteurs constituant une base orthonormÃ©e de l'espace de Krylov $K_i$),   \\
+$w_i$ (variable intermÃ©diaire)
+\Output $x_{m}$ (Vecteur solution)\medskip
+
+\State Charger $A_{ij}$, $b_{i}$, $n$, 
+\State Assigner la valeur initiale $x^0$ 
+\State $r_0 \leftarrow b - Ax_0$ 
+\State $q_1 \leftarrow \frac{r_0}{\|r_0\|}$ 
+\State \textbf{repeat} 
+\For {$j=0,1,2,\ldots m$} 
+\For {$i=1,2,\ldots j$} 
+\State $h_{i,j} = (A q_j, q_i)$
+\State $x_i \leftarrow 0$
+\State $w_{j+1} = A q_j - \sum_{i=1}^j h_{i,j} q_i$
+\State $h_{j+1,j} = \| w_{j+1} \|$
+\State $h_{i,j} = \frac {w_{j+1}} {h_{j+1,j}}$
+\EndFor
+\EndFor
+\State Calculer la solution approchÃ©e $x_{m}$
+\State $x_{m} = x_0 + Q_m y_m \hspace{0.1cm} tel \hspace{0.1cm} que \hspace{0.1cm} y_m \hspace{0.1cm} minimise \hspace{0.1cm} \| \tilde{H}_m y - \hspace{0.1cm} \|b\| \hspace{0.1cm} e_1 \|, y \in R^m.$ 
+\State RedÃ©marrage
+\State $r_m \leftarrow b - Ax_m$ 
+\State RÃ©initialiser pour le redÃ©marrage
+\State $x_0 \leftarrow x_m$
+\State $r_0 \leftarrow r_m$
+\State $q_1 \leftarrow \frac{r_0}{\|r_0\|}$ 
+\State \textbf{Until} {( Obtention de la condition de convergence : $\| r_m \|$ \hspace{0.1cm} est satisfaisant )} 
+\Statex
+\end{algorithmic}
+\caption{Algorithme itÃ©ratif GMRES avec redÃ©marrage}
+\label{algo:02}
+\end{figure}
+
+%%%% ?? Version Â« two-stage Â»
 
 \subsection{Solveur multisplitting} 
 
-Version simple
+Dans cette classe des mÃ©thodes itÃ©ratives de rÃ©solution de systÃ¨me d'Ã©quations linÃ©aires $AX=B$, le solveur "multisplitting" reste une des plus utilisÃ©es et une des plus efficaces en version parallÃ¨le. On suppose qu'on va rÃ©partir le traitement de la rÃ©solution du problÃ¨me entre les $L$ clusters d'une grille de calcul donnÃ©. La base de la mÃ©thode est de trouver un dÃ©coupage efficient de la matrice initiale $A$ en plusieurs sous-matrices $(A_{lm}), l,m \in \{1,...,L\}$ de taille $n_l \times n_m$ [3,4,5]. Ce dÃ©coupage doit se faire sans recouvrement et doit Ãªtre exhaustif, c'est-Ã -dire on doit retrouver la matrice $A$ avec l'union des sous-matrices, c'est-Ã -dire $\sum_l n_l = \sum_m n_m = n$. A chaque sous-matrice sera associÃ© d'une part, les sous vecteurs $X_l$ du vecteur inconnu $X$ et $B_l$, sous vecteur du deuxiÃ¨me membre $B$, tous les deux de taille $n_l$. Ainsi, l'Ã©quation initiale peut s'Ã©crire aprÃ¨s dÃ©coupage : 
 
-Version amÃ©liorÃ©e
+Ainsi, \eqref{eq:2} peut s'Ã©crire : 
 
-\section{Simulateurs d'exÃ©cution d'algorithmes parallÃ¨les MPI dans une grille de calcul}
+\begin{equation}
+  \label{eq:13bis}
+  \left(\begin{array}{ccc}
+      A_{1,1} & \cdots & A_{1,L} \\
+      \vdots & \ddots & \vdots\\
+      A_{n,1} & \cdots & A_{L,L}
+    \end{array} \right)
+  \times
+  \left(\begin{array}{c}
+      X_1 \\
+      \vdots\\
+      X_L
+    \end{array} \right)
+	=
+  \left(\begin{array}{c}
+      B_1 \\
+      \vdots\\
+      B_n
+    \end{array} \right)
+\end{equation}
+   
+Une fois le dÃ©coupage effectuÃ©, chaque sous-systÃ¨me \ref{eq:13bis} est attribuÃ© Ã  un cluster pour sa rÃ©solution indÃ©pendante de faÃ§on itÃ©rative dans ce que la mÃ©thode de multisplitting dÃ©crit comme les $"iterations$ $internes"$ (interne au cluster). Dans le cadre de nos travaux, l'algorithme GMRES, prÃ©cÃ©demment Ã©tudiÃ©, est utilisÃ© pour rÃ©soudre localement le sous-systÃ¨me \ref{eq:13}. 
 
-\subsection{Calcul sur grille}
+\begin{equation}
+  \label{eq:13}
+  \left\{
+    \begin{array}{l}
+      A_{\ell\ell}X_\ell = Y_\ell \text{, tel que}\\
+      Y_\ell = B_\ell - \displaystyle\sum_{\substack{m=1\\ m\neq \ell}}^{L}A_{\ell m}X_m
+    \end{array}
+  \right.
+\end{equation}
+Les rÃ©sultats intermÃ©diaires sont Ã©changÃ©s entre les clusters voisins Ã  la fin de chaque itÃ©ration de la $"boucle$ $externe$. Le pseudo-code dÃ©crit dans la figure Figure~\ref{algo:03} montre les Ã©tapes essentielles de l'algorithme de multisplitting en parallÃ¨le.\\
+La convergence globale de l'algorithme sera dÃ©tectÃ©e dÃ¨s que la convergence locale dans chaque cluster est atteinte. La condition de convergence est donnÃ©e par \ref{eq:14} oÃ¹ Ã  chaque itÃ©ration externe k, $X^k_l$ et $X^{k+1}_l$ donne le rÃ©sidu entre deux rÃ©sultats consÃ©cutifs $k$ et $k+1$ au niveau du cluster $l$, $\epsilon$ le seuil d'erreur acceptÃ© et $MaxIter$ le nombre maximum d'itÃ©rations convenu. 
+  
+\begin{equation}
+  \label{eq:14}
+  (k=\MI) \text{ or } (\|X_\ell^k - X_\ell^{k+1}\|\leq\epsilon)
+\end{equation} 
+
+\begin{figure}[!t]
+\begin{algorithmic}[1]
+\Input $A_\ell$ (Matrice d'entrÃ©e), $B_\ell$ (Vecteur du membre droit)
+\Output $x_{m}$ (Vecteur solution)\medskip
+
+\State Charger $A_\ell$, $B_\ell$ 
+\State Assigner la valeur initiale $x^0$ 
+\For {$k=0,1,2,\ldots$ jusqu'Ã  la convergence globale}
+\State RedÃ©marrer la boucle d'iterations externes $x^0=x^k$
+\State Boucle d'iterations internes : \Call{InnerSolver}{$x^0$, $k+1$}
+\State\label{algo:03:send} Envoyer les Ã©lÃ©ments partagÃ©s $X_\ell^{k+1}$ aux clusters voisins
+\State\label{algo:03:recv} Recevoir les Ã©lÃ©ments partagÃ©s dans $\{X_m^{k+1}\}_{m\neq \ell}$
+\EndFor
+
+\Statex
+
+\Function {InnerSolver}{$x^0$, $k$}
+\State Calculer le membre droit local $Y_\ell$:
+       \begin{equation*}
+         Y_\ell = B_\ell - \sum\nolimits^L_{\substack{m=1\\ m\neq \ell}}A_{\ell m}X_m^0
+       \end{equation*}
+\State RÃ©soudre le sous-systÃ¨me $A_{\ell\ell}X_\ell^k=Y_\ell$ avec la mÃ©thode GMRES parallÃ¨le
+\State \Return $X_\ell^k$
+\EndFunction
+\end{algorithmic}
+\caption{Solveur Multisplitting utilisant la mÃ©thode GMRES en local (version parallÃ¨le)}
+\label{algo:03}
+\end{figure}
+
+%%%%Version amÃ©liorÃ©e
+
+\section{Simulateurs d'exÃ©cution d'algorithmes parallÃ¨les dans une grille de calcul}
+
+\subsection{Calcul sur grille de calcul}
 Une grille de calcul est caractÃ©risÃ©e par "un type de systÃ¨me parallÃ¨le et distribuÃ© qui permet le partage, la sÃ©lection et l'aggrÃ©gation de ressources distribuÃ©es gÃ©ographiquement selon leurs capacitÃ©s" [25] afin de rÃ©soudre un problÃ¨me complexe donnÃ©. Ainsi, une grille est composÃ©e d'un ensemble de grappes de machines interconnectÃ©es entre elles Ã  travers un rÃ©seau de communication qui peut s'Ã©tendre sur des zones gÃ©ographiques Ã©loignÃ©es (Figure \figref{gridA}). Les capacitÃ©s de calcul, les mÃ©moires, les applications et les systÃ¨mes de stockage sont partagÃ©es par les applications parallÃ¨les et distribuÃ©es. Le calcul sur une grille est caractÃ©risÃ© par un environnement "hÃ©tÃ©rogÃ¨ne, dynamique et scalable". \\
 
-\mfigure[h]{width=8cm, height=8cm}{"Grid architecture"} {Architecture d'une grille de calcul} {gridA}
+\mfigure[h]{width=8cm}{"Grid architecture"} {Architecture d'une grille de calcul} {gridA}
 
-L'hÃ©tÃ©rogÃ©nÃ©itÃ© montre la variÃ©tÃ© des Ã©lÃ©ments composant la grille de calcul. On peut Ãªtre en prÃ©sence de diffÃ©rentes architectures de processeurs dans les machines d'une grappe ou entre les grappes. Les frÃ©quences d'horloge de ces processeurs peuvent Ãªtre aussi diffÃ©rentes. De mÃªme, l'architecture ou la mÃ©thode d'accÃ¨s des mÃ©moires (DRAM, stockage) utilisÃ©es dans la grille de calcul peut Ãªtre aussi Ãªtre aussi de types diffÃ©rents. Enfin, la topologie ainsi que la performance des rÃ©seaux de communications interconnectant les Ã©lÃ©ments de la grille peuvent Ãªtre aussi avoir des dÃ©bits complÃ¨tement hÃ©tÃ©rogÃ¨nes. \\
+L'hÃ©tÃ©rogÃ©nÃ©itÃ© montre la variÃ©tÃ© des Ã©lÃ©ments composant la grille de calcul. On peut Ãªtre en prÃ©sence de diffÃ©rentes architectures de processeurs dans les machines d'une grappe ou entre les grappes. Les frÃ©quences d'horloge de ces processeurs peuvent Ãªtre aussi diffÃ©rentes. De mÃªme, l'architecture ou la mÃ©thode d'accÃ¨s aux mÃ©moires (DRAM, stockage) utilisÃ©es dans la grille de calcul peut Ãªtre aussi Ãªtre aussi de types diffÃ©rents. Enfin, la topologie ainsi que la performance des rÃ©seaux de communications interconnectant les Ã©lÃ©ments de la grille peuvent Ãªtre aussi avoir des dÃ©bits complÃ¨tement hÃ©tÃ©rogÃ¨nes. \\
 Le caractÃ©ristique dynamique de la grille rÃ©sulte de la relative facilitÃ© de changer de configuration. On peut ainsi tailler dynamiquement l'allocation des ressources de la grille aux utilisateurs selon les besoins de leur demande respective. Cet aspect a Ã©tÃ© Ã©largi Ã  "l'Ã©lasticitÃ©" de l'environnement dans le cadre du "cloud computing". \\
 Enfin, la scalabilitÃ© de la grille de calcul dÃ©coule de sa conception modulaire permettant d'ajouter d'autres composants selon les besoins.  Pour augmenter par exemple la capacitÃ© de calcul de la grille, il suffit d'ajouter de nouveaux clusters pour une plus grande puissance globale de la grille. \\
 
 Le milieu de la recherche dispose d'une grille de calcul dÃ©diÃ© : le Grid'5000 [26, 27] est une grille rÃ©partie gÃ©ographiquement dans diffÃ©rentes villes de France (Figure \figref{grid5000RG} )  mettant Ã  disposition un "banc d'essai polyvalent Ã  grande Ã©chelle" pour les expÃ©rimentations de la recherche en informatique particuliÃ¨rement le calcul parallÃ¨le sur grille, sur le cloud, le calcul Ã  haute performance mais aussi sur le Big Data. Grid'5000 permet aux utilisateurs l'accÃ¨s Ã  des ressources importantes de calcul dans un environnement complÃ¨tement configurable et controllable. Il peut aussi fournir une trace dÃ©taillÃ©e ainsi que d'autres informations de mesure sur le comportement de l'application lors de l'exÃ©cution pour une Ã©tude ultÃ©rieure.
 
-\mfigure[h]{width=8cm, height=8cm}{"Grid5000 sites"} {Grid'5000 : RÃ©partition gÃ©ographique} {grid5000RG}
+\mfigure[h]{width=8cm}{"Grid5000 sites"} {Grid'5000 : RÃ©partition gÃ©ographique} {grid5000RG}
    
 
 Grid'5000 est construit autour de plus de 1000 noeuds physiques de diffÃ©rents constructeurs composÃ©s de plus de 2000 processeurs (Intel Xeon et AMD Opteron) avec un total de plus de 10.000 coeurs. Plus de 650 diffÃ©rentes cartes  d'interface rÃ©seau Ethernet, Infiniband et Myrinet sont interconnectÃ©s  avec plus de 40 accÃ©lÃ©rateurs de type NVIDIA GPU et Intel Xeon Phi.
@@ -481,7 +840,7 @@ DÃ¨s sa conception, Grid'5000 a pris en compte la diversitÃ© des intÃªrets et de
 \subsection{GÃ©nÃ©ralitÃ©s sur la simulation}
 
 La simulation est largement utilisÃ©e dans divers domaines de la recherche scientifique. Elle consiste au processus de la mise en oeuvre et "de la conduite d'expÃ©rimentations sur un modÃ¨le (une reprÃ©sentation simplifiÃ©e du rÃ©el) dans le but de comprendre le comportement du systÃ¨me modÃ©lisÃ© sous des conditions sÃ©lectionnÃ©es ou de l'Ã©valuation de diverses stratÃ©gies pour le fonctionnement du systÃ¨me sous la limite imposÃ©e par les critÃ¨res de dÃ©veloppement et d'exploitation" [29]. ParticuliÃ¨rement, la simulation de l'exÃ©cution d'une application parallÃ¨le distribuÃ©e Ã©tudie son comportement (rÃ©sutats en sortie, temps de performance, scalabilitÃ©, ...) sur un environnement virtuel imitant au mieux le fonctionnement d'une plateforme physique rÃ©el ou d'un systÃ¨me en cours d'Ã©laboration (banc d'essai) ou encore d'une hypothÃ©tique machine non encore rÃ©alisÃ©e. Ainsi, la simulation informatique se focalise sur le comportement dynamique du modÃ¨le Ã  travers le temps. Plusieurs raisons motivent une telle simulation: Ã  titre d'exemple, de rÃ©duire les coÃ»ts de la conception d'un systÃ¨me et d'Ã©viter les erreurs, de produire dans un temps raisonnable des rÃ©sultats en sortie d'un modÃ¨le ayant un temps d'exÃ©cution Ã©levÃ©, de rÃ©pondre Ã  des scÃ©narions d'exÃ©cution avec des questions "what-if" (tests et Ã©valuations), ou encore de crÃ©er des outils de simulation pour des formations ou des jeux. \\      
-Dans le cadre d'une grille de calcul, les simulateurs ou les outils de simulation permettent Ã  l'inverse des plateformes rÃ©elles l'Ã©valuation de la performance des expÃ©rimentations "rÃ©pÃ©tables et controllables" [25] sur des configurations flexibles et scalables. En effet, les environnements rÃ©els montrent leurs limites sur leur rigiditÃ© de passage Ã  l'echelle mais aussi sur la flexibilitÃ© de disposer un environnement de calcul particulier rÃ©pondant aux besoins prÃ©cis de l'application Ã  un moment donnÃ©. Selon la classification dans [30], la simulation d'applications sur une grille de calcul rejoint la classe de simulation "virtuelle" par l'utilisation d'Ã©quipements de simulation par des personnes rÃ©elles. De faÃ§on gÃ©nÃ©rale, le simulateur utilise une Ã©chelle de temps "discret", c'est-Ã -dire le temps est dÃ©coupÃ© en intervalles qui peuvent Ãªtre rÃ©guliers ou non. Dans le cas d'un systÃ¨me Ã  temps discret rÃ©gulier, le simulateur maintient et met Ã  jour Ã©ventuellement un ensemble de "variables d'Ã©tat" qui reflÃ¨tent l'Ã©tat du systÃ¨me physique Ã  un instant t donnÃ©. Un "Ã©venement" est associÃ© Ã  chaque instant donnÃ© Ã  une "transition d'Ã©tat". Pour des comparaisons futures, on distingue le "temps physique" comme Ã©tant le temps considÃ©rÃ© au niveau du systÃ¨me physique, du "temps de simulation" et "le temps de l'horloge murale" dÃ©signe le temps de simulation du modÃ¨le. Toutefois, le "temps de simulation" est une notion abstraite utilisÃ©e par le simulateur pour Ã©valuer le temps de simulation. Il est dÃ©fini [30] comme Ã©tant "un ensemble de valeurs totalement ordonnÃ© E oÃ¹ chaque valeur reprÃ©sente un temps du systÃ¨me physique Ã  modÃ©liser et qui vÃ©rifie les conditions suivantes:" \\
+Dans le cadre d'une grille de calcul, les simulateurs ou les outils de simulation permettent Ã  l'inverse des plateformes rÃ©elles l'Ã©valuation de la performance des expÃ©rimentations "rÃ©pÃ©tables et controllables" [25] sur des configurations flexibles et scalables. En effet, les environnements rÃ©els montrent leurs limites sur leur rigiditÃ© de passage Ã  l'echelle mais aussi sur la flexibilitÃ© de disposer d'un environnement de calcul particulier rÃ©pondant aux besoins prÃ©cis de l'application Ã  un moment donnÃ©. Selon la classification dans [30], la simulation d'applications sur une grille de calcul rejoint la classe de simulation "virtuelle" par l'utilisation d'Ã©quipements de simulation par des personnes rÃ©elles. De faÃ§on gÃ©nÃ©rale, le simulateur utilise une Ã©chelle de temps "discret", c'est-Ã -dire le temps est dÃ©coupÃ© en intervalles qui peuvent Ãªtre rÃ©guliers ou non. Dans le cas d'un systÃ¨me Ã  temps discret rÃ©gulier, le simulateur maintient et met Ã  jour Ã©ventuellement un ensemble de "variables d'Ã©tat" qui reflÃ¨tent l'Ã©tat du systÃ¨me physique Ã  un instant t donnÃ©. Un "Ã©venement" est associÃ© Ã  chaque instant donnÃ© Ã  une "transition d'Ã©tat". Pour des comparaisons futures, on distingue le "temps physique" comme Ã©tant le temps considÃ©rÃ© au niveau du systÃ¨me physique, du "temps de simulation" et "le temps de l'horloge murale" dÃ©signe le temps de simulation du modÃ¨le. Toutefois, le "temps de simulation" est une notion abstraite utilisÃ©e par le simulateur pour Ã©valuer le temps de simulation. Il est dÃ©fini [30] comme Ã©tant "un ensemble de valeurs totalement ordonnÃ© E oÃ¹ chaque valeur reprÃ©sente un temps du systÃ¨me physique Ã  modÃ©liser et qui vÃ©rifie les conditions suivantes:" \\
 
 Soient E l'ensemble des temps discrets de simulation et P l'ensemble des temps du systÃ¨me physique.
 
@@ -552,7 +911,7 @@ Plusieurs domaines sont couverts par les spÃ©cifications de MPI dont les plus im
 
 \item[$\bullet$] La gestion de l'environnement MPI: Permet Ã  l'utilisateur d'interagir avec l'environnement MPI crÃ©Ã© lors du lancement du programme parallÃ¨le. Elle assure par abstraction la portabilitÃ© de l'application entre des plateformes matÃ©rielles et logicielles diffÃ©rentes.
 
-\item[$\bullet$] La gestion des processus: DÃ©finit la crÃ©ation des processus participant Ã  l'exÃ©cution de l'application mais aussi dÃ©termine la topologie et la gestiobn des groupes de processus en accord par exemple avec des architectures complexes comme les grilles de calcul. 
+\item[$\bullet$] La gestion des processus: DÃ©finit la crÃ©ation des processus participant Ã  l'exÃ©cution de l'application mais aussi dÃ©termine la topologie et la gestion des groupes de processus en accord par exemple avec des architectures complexes comme les grilles de calcul. 
 
 \item[$\bullet$] Les types de donnÃ©es : Permettent de crÃ©er des structures de donnÃ©es complexes en mÃ©moire Ã  partir des types de donnÃ©es de base comme l'entier, le float, etc...
 
@@ -562,16 +921,49 @@ Plusieurs domaines sont couverts par les spÃ©cifications de MPI dont les plus im
  
 Le programme MPI s'exÃ©cute sur chaque processeur une fois que l'environnement logique est crÃ©Ã© par la routine MPI\_Init. Ce dernier est constituÃ© d'un groupe de processus, d'un contexte et d'un communicateur (par dÃ©faut MPI\_COMM\_WORLD), voir la figure \figref{MPI}-a. Chaque processus est identifiÃ© par son rang dans le groupe associÃ© au communicateur (MPI\_Comm\_rank). Le nombre total de processus en jeu est donnÃ© par MPI\_Comm\_size. A la fin du code, MPI\_Finalize termine l'exÃ©cution en environnement MPI. De faÃ§on gÃ©nÃ©rale, une erreur arrÃªte tous les processus en jeu. Toutefois, le programmeur peut gÃ©rer et personnaliser les erreurs au niveau de chaque processus ou globalement. Une routine MPI qui se termine avec succÃ¨s retourne le code MPI\_SUCCESS. \\
 
-\mfigure[h]{width=8cm, height=8cm}{"MPI"} {Groupes et communicateur (a) - MPI - OpÃ©rations collectives (b)} {MPI}
+\mfigure[h]{width=8cm}{"MPI"} {Groupes et communicateur (a) - MPI - OpÃ©rations collectives (b)} {MPI}
 
-Au niveau de la communication, le transfert de message peut se faire d'un processus vers un autre (point Ã  point). Pour cela, les routines MPI\_SEND et MPI\_RECV et leus variantes permettent respectivement d'envoyer et de recevoir un message. L'adresse du tampon contenant le message Ã  traiter sont passÃ©es Ã  ces fonctions avec le type de donnÃ©es ainsi que le nombre d'objets. La destination dans le cas d'un envoi est spÃ©cifiÃ©e par le rang du processus d'arrivÃ©e du message dans le communicateur considÃ©rÃ©. Une variable de statut de l'opÃ©ration permet de connaitre si l'opÃ©ration a rÃ©ussi ou a Ã©chouÃ©. Cet Ã©change peut se faire de maniÃ¨re synchrone ou asynchrone(resp. bloquant ou non bloquant). \\
-Contrairement Ã  une communication point Ã  point, une communication dite collective transfÃ¨re un message Ã  partir d'un processeur vers un ensemble de processeurs. L'exemple le plus courant est le "broadcast" ou diffusion oÃ¹ un processeur envoie le mÃªme message Ã  destination d'un ensemble de processeurs. La figure \figref{MPI}-b montre les Ã©changes entre les processus aprÃ¨s l'appel Ã  cette opÃ©ration mais aussi d'autres types de communications collectives. Un processus avec MPI\_Scatter distribue une structure de donnÃ©es Ã  d'autres processus participants tandis que MPI\_Gather rassemble des donnÃ©es de plusieurs processus participant en une seule structure. Enfin, les opÃ©rations de rÃ©duction appliquent une opÃ©ration (somme, produit, maximum, minimum, etc ...)Ã  un ensemble de processus et retourne le rÃ©sultat vers le processus appellant.
+Au niveau de la communication, le transfert de message peut se faire d'un processus vers un autre (point Ã  point). Pour cela, les routines MPI\_SEND et MPI\_RECV et leus variantes permettent respectivement d'envoyer et de recevoir un message. L'adresse du tampon contenant le message Ã  traiter est passÃ©e Ã  ces fonctions avec le type de donnÃ©es ainsi que le nombre d'objets. La destination dans le cas d'un envoi est spÃ©cifiÃ©e par le rang du processus d'arrivÃ©e du message dans le communicateur considÃ©rÃ©. Une variable de statut de l'opÃ©ration permet de connaitre si l'opÃ©ration a rÃ©ussi ou a Ã©chouÃ©. Cet Ã©change peut se faire de maniÃ¨re synchrone ou asynchrone(resp. bloquant ou non bloquant). \\
+Contrairement Ã  une communication point Ã  point, une communication dite collective transfÃ¨re un message Ã  partir d'un processeur vers un ensemble de processeurs. L'exemple le plus courant est le "broadcast" ou diffusion oÃ¹ un processeur envoie le mÃªme message Ã  destination d'un ensemble de processeurs. La figure \figref{MPI}-b montre les Ã©changes entre les processus aprÃ¨s l'appel Ã  cette opÃ©ration mais aussi d'autres types de communications collectives. Un processus distribue avec MPI\_Scatter une structure de donnÃ©es Ã  d'autres processus participants tandis que MPI\_Gather rassemble des donnÃ©es de plusieurs processus participant en une seule structure. Enfin, les opÃ©rations de rÃ©duction appliquent une opÃ©ration (somme, produit, maximum, minimum, etc ...)Ã  un ensemble de processus et retourne le rÃ©sultat vers le processus appellant.
 La synchronisation des processus peut Ãªtre obtenue avec la routine MPI\_Barrier qui, une fois lancÃ©e par un processus, bloque ce dernier jusqu'Ã  ce que tous les processus de son groupe atteigne cette barriÃ¨re comme un point de rendez-vous.
 
 \subsection{Simulateur SIMGRID - SMPI}      
-SimGrid est utilisÃ© pour la simulation et l'Ã©tude du comportement d'applications parallÃ¨les dans un contexte d'un environnement complexe, hÃ©tÃ©rogÃ¨ne, distribuÃ© et dynamique. Il est conÃ§u sur une simulation basÃ©e sur les Ã©venements ("event driven") Ã  un niveau d'abstraction et de fonctionnalitÃ©s rÃ©pondant aux applications et aux infrastructures [26].
+SimGrid est utilisÃ© pour la simulation et l'Ã©tude du comportement d'applications parallÃ¨les dans un contexte d'un environnement complexe, hÃ©tÃ©rogÃ¨ne, distribuÃ© et dynamique. Comme son nom l'indique, dÃ©veloppÃ© par la communautÃ© des utilisateurs de grille de calcul, il est utilisÃ© aussi largement dans les domaines des applications pair-Ã -pair, du calcul Ã  haute performance et du cloud computing [5,9]. Le choix de Simgrid comme outil de simulation dans le cadre de ces travaux a Ã©tÃ© motivÃ© par son efficacitÃ© pour la simulation d'applications parallÃ¨les Ã  large Ã©chelle. En effet, Simgrid rassemble au mieux les caractÃ©ristiques requises pour un simulateur dans un environnement de grille de calcul telles que la robustesse, la scalabilitÃ© et la justesse des rÃ©sultats accompagnÃ©es d'un temps de rÃ©ponse correct et d'une tolÃ©rance aux pannes de l'exÃ©cution [34].
+
+Simgrid est conÃ§u sur une simulation basÃ©e sur les Ã©venements ("event driven") [26, 35] Ã  un niveau d'abstraction et de fonctionnalitÃ©s rÃ©pondant aux applications et aux infrastructures. Cinq composants d'abstraction constituent le fonctionnement de Simgrid : 
+
+\begin{itemize}
+
+\item[$\bullet$]Un "agent" est une entitÃ© qui assure l'ordonnancement de l'application et exÃ©cute le code sur une "location";
+
+\item[$\bullet$]Une "location" est une hÃ´te de l'environnement de simulation sur laquelle l'agent s'exÃ©cute. Outre les donnÃ©es propres Ã  la location, des boÃ®tes aux lettres sont conÃ§ues pour permettre les Ã©changes de donnÃ©es avec d'autres agents;
+
+\item[$\bullet$]Une "tÃ¢che" est une activitÃ© de l'application simulÃ©e. Elle se dÃ©cline sous forme d'un calcul (temps de calcul nÃ©cessaire) ou d'un transfert de donnÃ©es (volume de donnÃ©es Ã  Ã©changer);
+
+\item[$\bullet$]Un "chemin" dÃ©crit la liaison entre les locations. Il est utilisÃ© par les agents lors d'un transfert de donnÃ©es Ã  calculer le temps de transfert en tenant compte du routage Ã  appliquer pour une telle liaison.
 
-\section{Motivations}
+\item[$\bullet$]La communication entre agents se fait Ã  travers un "canal". Cette abstraction modÃ©lise la communication Ã  travers un port entre des agents dans les locations.
+
+\end{itemize}
+
+Simgrid offre pour l'utilisateur plusieurs types d'interfaces de programmation [5,9]: MSG qui simule les "processus sÃ©quentiels conccurents", SimDAG qui est utilisÃ© pour simuler des tÃ¢ches parallÃ¨les modÃ©lisÃ©es en graphe acyclique direct et SMPI qui simule et exÃ©cute les applications Ã©crites en MPI sans ou avec des modifications mineures. Outre le langage C natif, Simgrid accepte des applications Ã©crites en C++, Java, Fortran, Lua ou encore Ruby.
+  
+De point de vue pratique, la figure \figref{simgrid1} prÃ©sente la structure et les Ã©lÃ©ments de la plateforme de simulation Simgrid. Elle est composÃ©e des trois parties diffÃ©rentes suivantes : 
+
+\begin{itemize}
+
+\item[$\bullet$] Le scÃ©nario de la simulation qui constitue les "modÃ¨les de ressources" du systÃ¨me. Evidemment, il comprend le code de l'application Ã  exÃ©cuter dans le simulateur avec ses diffÃ©rents paramÃ¨tres d'entrÃ©e mais aussi son modÃ¨le de dÃ©ploiement. Un autre composant important de ce scÃ©nario aussi est le fichier, gÃ©nÃ©ralement au format XML, modÃ©lisant les dÃ©tails de la topologie et l'architecture de l'environnement d'exÃ©cution. Il dÃ©termine par exemple pour le cas d'une grille de calcul, le nombre et les caractÃ©ristiques des clusters contribuant Ã  cet environnement. Pour chaque cluster, les spÃ©cifications des serveurs (nombre de cores ou de processeurs, puissance en Flops, taux de disponibilitÃ©, ...)sont dÃ©finies ainsi que les propriÃ©tÃ©s des rÃ©seaux de liaison entre ces diffÃ©rents composants de la grille (topologie du rÃ©seau, dÃ©bit et latence, table de routage, ...).
+
+\item[$\bullet$] Le simulateur proprement dit comprenant l'application Ã  exÃ©cuter et le nouay du simulateur.
+
+\item[$\bullet$] Les fichiers de sortie comprenant les rÃ©sultats de la simulation de l'application ainsi que d'autres fichiers de monitoring de l'exÃ©cution comme un fichier de logging et de statistiques. Simgrid peut gÃ©nÃ©rer aussi des donnÃ©es pouvant Ãªtre utilisÃ©es pour reprÃ©senter visuellement le dÃ©roulement et la trace de la simulation dans le temps.
+     
+\end{itemize}
+
+\mfigure[h]{width=8cm}{"Simgrid - In a nutshell"} {SIMGRID : Les Ã©lÃ©ments de la plateforme de simulation} {simgrid1}
+
+Les applications sous-tendant les expÃ©rimentations effectuÃ©es dans le cadre de ces travaux ont Ã©tÃ© ecrites en C et utilisent les librairies MPI. Simgrid dispose de l'interface SMPI (Simulated MPI) qui peut exÃ©cuter un code MPI parallÃ¨les sans aucune ou Ã  la limite trÃ¨s peu de modifications. A titre d'exemple, les variables globales doivent Ãªtre transfÃ©rÃ©es dans un contexte local dans l'application SMPI. Simgrid/SMPI assure l'implÃ©mentation de plus de 80\% des routines de la librairie MPI 2.0. Le code est exÃ©cutÃ© rÃ©ellement dans le simulateur dans l'environnement virtuel spÃ©cifiÃ© sauf que les communications sont interceptÃ©es et le temps de transfert calculÃ© en tenant compte du partage des ressources existantes (par exemple le partage de la bande passante entre processus concurrents sur les rÃ©seaux de liaison).La scalabilitÃ© de Simgrid peut Ãªtre obtenue par appel Ã  des routines SMPI qui utilisent des structures de donnÃ©es partagÃ©es entre les processus parallÃ¨les rÃ©duisant ainsi la quantitÃ© de mÃ©moire utilisÃ©e et permettant une montÃ©e en charge non nÃ©gligeable. Toutefois, dans ce cas, comme tous les processus utilisent la mÃªme structure de donnÃ©es, la vÃ©racitÃ© des rÃ©sultats obtenus n'est pas importante.
+ 
 
 \section{Conclusion partielle}
 
@@ -683,9 +1075,9 @@ S(n) \leqslant \dfrac{1}{f+ \dfrac{1-f}{n}}
 
 Pour un systÃ¨me parallÃ¨le Â« idÃ©al Â», le speedup est Ã©gal Ã  n et l'efficacitÃ©
 Ã  1. Dans la pratique, le speedup est toujours infÃ©rieur Ã  n avec
-une limite haute dÃ»e Ã  la loi de Amdahl et l'efficacitÃ©
+une limite haute dÃ»e Ã  la loi de Amdahl tandis que l'efficacitÃ©
 a une valeur entre 0 et 1. On peut dÃ©montrer que l'efficacitÃ©
-est une fnction dÃ©croissante du nombre de processeurs n tandis qu'elle
+est une fonction dÃ©croissante du nombre de processeurs n tandis qu'elle
 est une fonction croissante de la taille du problÃ¨me.
 
 Dans le cadre de nos travaux, nous avions introduit une mÃ©trique utilisÃ©e
@@ -725,7 +1117,7 @@ repart pour une nouvelle itÃ©ration.
 A l'itÃ©ration k, la convergence est atteinte quand
 : 
 \begin{equation*}
-(\|X_l^k - X_l^{k+1}\|_{\infty}\leq\epsilon)	
+(\|X_l^k - X_l^{k+1}\|\leq\epsilon)	
 \end{equation*}
 
 \subsection{Weak contre strong scaling}
@@ -747,7 +1139,7 @@ essaie de rÃ©soudre un problÃ¨me donnÃ© plus vite. Ainsi, dans ce cas,
 la taille du problÃ¨me en entrÃ©e reste constante mÃªme si on adjoint
 une capacitÃ© plus grande aux unitÃ©s de calcul.
 
-\mfigure[h]{width=8cm, height=8cm}{"Weak vs Strong scaling"} {Weak vs Strong scaling: Temps d'exÃ©cution et Speedup} {scaling}
+\mfigure[h]{width=10cm}{"Weak vs Strong scaling"} {Weak vs Strong scaling: Temps d'exÃ©cution et Speedup} {scaling}
 
 
 La figure \figref{scaling} montre que le temps d'exÃ©cution dÃ©croit (resp. reste constant) quand le nombre de processeurs augmente en strong mode (resp. en weak mode). De mÃªme, le speedup croit avec le nombre de processeur en strong mode tandis qu'il reste constant en weak mode.
@@ -843,7 +1235,7 @@ Les scientifiques et les utilisateurs dÃ©sirant lancer l'exÃ©cution
 d'un programme en environnement parallÃ¨le ont tous
 Ã©tÃ© confrontÃ©s Ã  la mÃªme problÃ©matique de mise Ã  disponibilitÃ© de
 l'environnement d'exÃ©cution. En effet,
-la rÃ©servation des ressources nÃ©cessaires pour lancer le systÃ¨me n'est
+la rÃ©ponse Ã  une rÃ©servation des ressources nÃ©cessaires pour lancer le systÃ¨me n'est
 pas toujours immÃ©diate mais en plus, le coÃ»t peut ne pas Ãªtre nÃ©gligeable
 dans un contexte de raretÃ© des machines super puissantes pourtant
 trÃ¨s sollicitÃ©es par diffÃ©rents acteurs {[}\dots {]}. Cette problÃ©matique
@@ -881,9 +1273,9 @@ la structure du rÃ©seau de communication dans la grille, on peut distinguer
 $(1)$ d'abord, les Ã©changes internes au niveau d'un
 Ã©lÃ©ment d'un bloc (entre les coeurs d'un
 processeur et entre les processeurs d'un mÃªme serveur
-physique), (2) ensuite, les Ã©changes Â« intra-blocs Â» caractÃ©risant
+physique), $(2)$ ensuite, les Ã©changes Â« intra-blocs Â» caractÃ©risant
 le trafic entre les diffÃ©rents Ã©lÃ©ments d'un bloc et
-(3) enfin, les Ã©changes Â« inter-blocs Â» dÃ©finissant la communication
+$(3)$ enfin, les Ã©changes Â« inter-blocs Â» dÃ©finissant la communication
 entre les blocs de la grille. Tant au niveau de leur topologie qu'en
 termes d'efficacitÃ©, ces trois niveaux de communication
 peuvent prÃ©senter des caractÃ©ristiques complÃ¨tement diffÃ©rentes et
@@ -932,7 +1324,7 @@ du processeur (Â« socket Â») emmenant un parallÃ©lisme au niveau de la
 puce. La Figure~\ref{fig:4} donne un aperÃ§u de l'architecture
 d'un processeur multi-coeurs.
 
-\mfigure[h]{width=8cm, height=8cm}{"Architecture des CPU multi-coeurs"} {Architecture des CPU multicoeurs} {cpumulti}
+\mfigure[h]{width=8cm}{"Architecture des CPU multi-coeurs"} {Architecture des CPU multicoeurs} {cpumulti}
 
 La performance d'une
 telle entitÃ© de calcul repose sur la vitesse d'accÃ¨s
@@ -945,16 +1337,16 @@ multiple data), MISD et MIMD (Multiple instruction, multiple data).
 Cette derniÃ¨re classe regroupant les machines parallÃ¨les gÃ©nÃ©ralistes
 actuelles se dÃ©cline en trois sous-catÃ©gories : 
 
-\mfigure[h]{width=8cm, height=8cm}{"MIMD Distributed Memory"} {ModÃ¨le MIMD DistribuÃ©} {MIMDDM}
+\mfigure[h]{width=8cm}{"MIMD Distributed Memory"} {ModÃ¨le MIMD MÃ©moire DistribuÃ©} {MIMDDM}
 
-\mfigure[h]{width=8cm, height=8cm}{"MIMD Shared memory - SMP"} {ModÃ¨le MIMD partagÃ©} {MIMDSM}
+\mfigure[h]{width=8cm}{"MIMD Shared memory - SMP"} {ModÃ¨le MIMD MÃ©moire partagÃ©} {MIMDSM}
 
-\mfigure[h]{width=8cm, height=8cm}{"MIMD Hybride"} {ModÃ¨le MIMD hybride} {MIMDHY}
+\mfigure[h]{width=8cm}{"MIMD Hybride"} {ModÃ¨le MIMD hybride} {MIMDHY}
 
 \begin{itemize}
 
 \item [$\bullet$] - Machine MIMD Ã  mÃ©moire partagÃ©e (Figure \figref{MIMDSM}) : Les unitÃ©s de calcul
-accÃ¨de Ã  la mÃ©moire partagÃ©e via un rÃ©seau d'interconnection
+accÃ¨dent Ã  la mÃ©moire partagÃ©e via un rÃ©seau d'interconnection
 (gÃ©nÃ©ralement, de type GigabitEthernet (renvoi) ou Infiniband (renvoi)).
 Il existe trois types d'implÃ©mentation : le crossbar,
 le Omega-Network et le Central Databus.
@@ -971,7 +1363,7 @@ rÃ©seau.
 
 \end{itemize}
 
-A titre d'exemple de machines parallÃ¨les, le site Top500.org
+A titre d'exemple de machines parallÃ¨les, le site Top5000.org
 {[}14{]} classe suivant diffÃ©rents critÃ¨res les plus performantes.
 Ainsi, la figure \figref {power} montre l'Ã©volution de la puissance
 de calcul mondiale dont le top actuel dÃ©veloppe un pic de performance
@@ -983,7 +1375,7 @@ de la machine Tianhe-2 (MilkyWay-2) de la National Super Computer
 Center Ã  Guangzhou en Chine {[}15{]}. A la tendance actuelle, l'atteinte
 de l'exaflops n'est pas loin.
 
-\mfigure[h]{width=8cm, height=8cm}{"Evolution de la puissance de calcul mondiale"} {Evolution de la puissance de calcul mondiale} {power}
+\mfigure[h]{width=8cm}{"Evolution de la puissance de calcul mondiale"} {Evolution de la puissance de calcul mondiale} {power}
 
 Pour arriver Ã  de telles puissances, diverses architectures de processeurs
 ont vu le jour ces derniÃ¨res annÃ©es. Outre l'Intel
@@ -1033,28 +1425,28 @@ des CPU aux mÃ©moires : (1) UMA ou Â« Uniform Memory Access Â» oÃ¹ tous
 les CPU accÃ¨dent une page mÃ©moire physique de faÃ§on Â« uniforme Â»,
 avec le mÃªme temps d'accÃ¨s tolÃ©rant ainsi la mise Ã 
 l'Ã©chelle. Dans ce cas, les CPU sont tous connectÃ©s
-aux mÃ©moires via un bus ((Figure \figref{UMA}). Un systÃ¨me d'adressage
+aux mÃ©moires via un bus (Figure \figref{UMA}). Un systÃ¨me d'adressage
 global est appliquÃ© Ã  l'ensemble des mÃ©moires physiques.
 (2) NUMA ou Â« Non Uniform Memory Access Â» oÃ¹ les groupes de CPU accÃ¨dent
 Ã  des mÃ©moires locales Ã  travers des buses et les groupes sont interconnectÃ©s
-par un rÃ©seau de communication ((Figure \figref{NUMA}). Dans ce cas, le temps
+par un rÃ©seau de communication (Figure \figref{NUMA}). Dans ce cas, le temps
 d'accÃ¨s des CPU aux pages mÃ©moires varie selon que
 ces derniÃ¨res sont locales ou distantes. L'espace d'adressage
 des mÃ©moires se fait au niveau de chaque groupe de CPU. (3) L'architecture
 COMA (Â« Cache Only Memory Access Â») est un hybride avec un modÃ¨le
 de programmation de mÃ©moire partagÃ©e mais une implÃ©mentation physique
-de mÃ©moire distribuÃ© ((Figure \figref{COMA}). Dans ce cas, chaque noeud dÃ©tient
+de mÃ©moire distribuÃ© (Figure \figref{COMA}). Dans ce cas, chaque noeud dÃ©tient
 une partie du systÃ¨me de l'espace d'adressage.
 Le partitionnement des donnÃ©es Ã©tant dynamique, la structure COMA
 n'associe pas la mÃªme adresse Ã  une page physique de
 la mÃ©moire. Les mÃ©moires locales dans ce cas de figure jouent finalement
 un rÃ´le de cache au processeur.
 
-\mfigure[h]{width=8cm, height=8cm}{"UMA architecture"} {MÃ©moire MIMD: Architecture UMA} {UMA}
+\mfigure[h]{width=8cm}{"UMA architecture"} {MÃ©moire MIMD: Architecture UMA} {UMA}
 
-\mfigure[h]{width=8cm, height=8cm}{"NUMA architecture"} {MÃ©moire MIMD: Architecture NUMA} {NUMA}
+\mfigure[h]{width=8cm}{"NUMA architecture"} {MÃ©moire MIMD: Architecture NUMA} {NUMA}
 
-\mfigure[h]{width=8cm, height=8cm}{"COMA architecture"} {MÃ©moire MIMD: Architecture COMA} {COMA}
+\mfigure[h]{width=7cm}{"COMA architecture"} {MÃ©moire MIMD: Architecture COMA} {COMA}
 
 MalgrÃ© que dans le cadre de nos travaux, nous n'avions
 pas eu une contrainte particuliÃ¨re en termes de systÃ¨me de stockage,
@@ -1318,17 +1710,17 @@ Dans le domaine du calcul parallÃ¨le, l'analyse du code d'une application suit l
 \end{itemize}
 Les deux derniers points sont regroupÃ©s sous le nom gÃ©nÃ©rique de "profiling" ou de "tracing" selon le modÃ¨le adoptÃ© de l'acquistion des donnÃ©es. La figure \figref{anaperf} montre ces trois couches de l'analyse de performance et dÃ©crit les diffÃ©rentes techniques utilisÃ©es pour cette analyse. Les flÃ¨ches tracÃ©es sur la figure montrent les combinaisons possibles entre les techniques prÃ©sentÃ©es. D'ailleurs, dans la pratique, d'autres combinaisons peuvent Ãªtre expÃ©rimentÃ©es pour atteindre les objectifs fixÃ©s.
 
-\mfigure[h]{width=8cm, height=8cm}{"Performance Analysis techniques"} {Classification des techniques d'analyse de la performance} {anaperf}
+\mfigure[h]{width=8cm}{"Performance Analysis techniques"} {Classification des techniques d'analyse de la performance} {anaperf}
 
 Cette approche Ã  trois Ã©tapes commence par la collecte des donnÃ©es sur la performance du code qui consiste Ã  deux techniques les plus utilisÃ©es Ã  savoir le "sampling" (ou "l'Ã©chantillonage") et "l'instrumentation basÃ©e sur les Ã©venements".
 \begin{itemize}
-\item [$\bullet$] Le "sampling" ou "l'echantillonage" capture les donnÃ©es dÃ©crivant l'Ã©tat du code lors de l'exÃ©cution du programme Ã  chaque instant dÃ©fini par la frÃ©quence de l'echantillonage. IL est rÃ©alisÃ© gÃ©nÃ©ralement avec la mise en place d'un timer qui dÃ©clenche la collecte des donnÃ©es selon une pÃ©riode dÃ©finie. Ces derniÃ¨res se rapportent sur les statistiques relatives aux appels de fonctions ("call-path" des fonctions) mais aussi sur les compteurs matÃ©riels [22]. Ainsi, il est d'usage de collecter le temps d'exÃ©cution d'un fonction ou combien de fois la fonction a Ã©tÃ© appellÃ©e ou encore de faÃ§on plus dÃ©taillÃ©e, combien de fois une ligne de code est exÃ©cutÃ©e. Evidemment, l'efficacitÃ© de la mÃ©thode dÃ©pend du taux d'Ã©chantillonnage: les informations entre deux points de collecte ne sont pas disponibles pour l'analyse ultÃ©rieure. Par contre, la surcharge engrendrÃ©e par la technique peut Ãªtre contrÃ´lÃ©e par l'utilisateur par un choix adÃ©quet de la frÃ©quence de l'echantillonage. \\
+\item [$\bullet$] Le "sampling" ou "l'echantillonage" capture les donnÃ©es dÃ©crivant l'Ã©tat du code lors de l'exÃ©cution du programme Ã  chaque instant dÃ©fini par la frÃ©quence de l'echantillonage. Il est rÃ©alisÃ© gÃ©nÃ©ralement avec la mise en place d'un timer qui dÃ©clenche la collecte des donnÃ©es selon une pÃ©riode dÃ©finie. Ces derniÃ¨res se rapportent sur les statistiques relatives aux appels de fonctions ("call-path" des fonctions) mais aussi sur les compteurs matÃ©riels [22]. Ainsi, il est d'usage de collecter le temps d'exÃ©cution d'une fonction ou combien de fois la fonction a Ã©tÃ© appellÃ©e ou encore de faÃ§on plus dÃ©taillÃ©e, combien de fois une ligne de code est exÃ©cutÃ©e. Evidemment, l'efficacitÃ© de la mÃ©thode dÃ©pend du taux d'Ã©chantillonnage: les informations entre deux points de collecte ne sont pas disponibles pour l'analyse ultÃ©rieure. Par contre, la surcharge engrendrÃ©e par la technique peut Ãªtre contrÃ´lÃ©e par l'utilisateur par un choix adÃ©quat de la frÃ©quence de l'echantillonage. \\
 L'alternative pour collecter les donnÃ©es de la performance d'une application parallÃ¨le se porte sur l'instrumentation basÃ©e sur les Ã©venements. D'abord, de faÃ§on gÃ©nÃ©rale, l'instrumentation du code consiste Ã  ajouter manuellement ou automatiquement des instructions supplÃ©mentaires Ã  des endroits choisis afin de rapporter Ã  chaque passage des informations spÃ©cifiques. A titre d'exemple, on peut positionner un timer au dÃ©but d'une portion du code et d'arrÃªter ce timer Ã  la sortie de cette rÃ©gion. On peut ainsi collecter le temps total d'execution consommÃ© par l'application pour exÃ©cuter cette partie du programme. Cette technique est largement utilisÃ©e par exemple pour dÃ©termijner le temps de communication nÃ©cessaire lors d'un appel d'une instruction MPI de transfert ou collective (MPI\_send, MPI\_receive ou autre MPI\_Barrier). Cette modification directe qui nÃ©cessite une rÃ©compilation du code est aussi appellÃ©e "instrumentation au niveau de la source". D'autres techniques utilisant des outils existent telles que les "libraries wrapping" ou la "rÃ©Ã©criture du code binaire" [22]. Ces derniÃ¨res n'ont pas besoin d'une recompilation du code.
 
 \item [$\bullet$] La deuxiÃ¨me Ã©tape du processus de la collecte des donnÃ©es en vue d'une future analyse consiste Ã  enregister soit en mÃ©moire soit sur un support de stockage externe les donnÃ©es obtenues lors de l'Ã©tape prÃ©cÃ©dente. Deux techniques peuvent Ãªtre exploitÃ©es Ã  cette fin. D'abord, le "logging" ou le "tracing" permet d'ajouter le facteur temps sur les donnÃ©es collectÃ©es. Ainsi, avant le stockage, chaque entrÃ©e de donnÃ©es est estampillÃ©e d'une date de l'Ã©venement (au format date - heure). Cette opÃ©ration peut ajouter un temps de surcharge non nÃ©gligeable lors de l'exÃ©cution.\\
 Afin de rÃ©duire cette derniÃ¨re mais aussi pour optimiser la taille du fichier de trace obtenu, la technique de "summarization" consiste Ã  agrÃ©ger les donnÃ©es aprÃ¨s la collecte et de ne stocker que le minimum d'informations utiles. Ce dernier est gÃ©nÃ©ralement appellÃ© le "profile" de l'application [21,22]. Certains dÃ©tails peuvent Ãªtre perdus avec cette mÃ©thode mais il s'agit ici de faire une balance entre la taille la granularitÃ© de l'information et la taille des donnÃ©es stockÃ©es.   
   
-\item [$\bullet$] La troisiÃ¨me et derniÃ¨re Ã©tape de l'analyse de la performance concerne la visualisation des donnÃ©es collectÃ©es en vue de l'analyse proporement dite et des dÃ©cisions Ã  prendre pour amÃ©liorer et optimiser l'exÃ©cution de l'application. Dans la mÃªme ligne de l'Ã©tape prÃ©cÃ©dente, soient les donnÃ©es sont visualisÃ©es "au fil du temps" en suivant l'exÃ©cution du code sur les diffÃ©rentes machines de l'environnement parallÃ¨le, soient elles sont reprÃ©sentÃ©es par un groupement selon un facteur comprÃ©hensible par l'analyste (par fonction par exemple), on est en prÃ©sence d'une technique gÃ©nÃ©rant un "timelines" ou un "profile" de l'application respectivement. 
+\item [$\bullet$] La troisiÃ¨me et derniÃ¨re Ã©tape de l'analyse de la performance concerne la visualisation des donnÃ©es collectÃ©es en vue de l'analyse proporement dite et des dÃ©cisions Ã  prendre pour amÃ©liorer et optimiser l'exÃ©cution de l'application. Dans la mÃªme ligne de l'Ã©tape prÃ©cÃ©dente, soient les donnÃ©es sont visualisÃ©es "au fil du temps" en suivant l'exÃ©cution du code sur les diffÃ©rentes machines de l'environnement parallÃ¨le, soient elles sont reprÃ©sentÃ©es par un groupement selon un facteur comprÃ©hensible par l'analyste (par fonction par exemple), on est en prÃ©sence d'une technique gÃ©nÃ©rant un "timeline" ou un "profile" de l'application respectivement. 
 
 \end{itemize}
 
@@ -1337,20 +1729,55 @@ Plusieurs outils d'analyse de la performance parallÃ¨le utilisant une ou des com
 
 
 \subsection{Quelques outils d'analyse de performance}
+Quelques outils d'analyse de performance sont passÃ©s en revue dans cette section. Ils mettent en exergue les diffÃ©rentes approches pour aborder ce problÃ¨me crucial de performance pour les applications parallÃ¨les et distribuÃ©es.
+
+\begin{itemize}
 
-	- IPM
+\item [$\bullet$] IPM (Integrated Performance Monitoring), comme tous les outils d'analyse de la performance particuliÃ¨rement pour un code MPI, fournit d'une part les statistiques du profiling du code comprenant les indicateurs lors des appels de routines MPI mais aussi d'autre part, le tracing du code collectant les dÃ©tails de l'historique et l'ordre des Ã©vÃ¨nemments passÃ©s MPI lors de l'exÃ©cution du code [37, 38]. L'inventaire de ces Ã©venements se fait par une "mesure directe". IPM se montre particulÃ¨rement efficace pour dÃ©tecter les dÃ©sequilibres de charge entre les processeurs pour une application parallÃ¨le. De plus, son utilisation entraÃ®ne une surcharge de calcul nÃ©gligeable. 
 
-TAU a Ã©tÃ© conÃ§u Ã  l'UniversitÃ© d'Oregon comme un outil open source d'Ã©valuation de performance [24]. Il intÃ¨gre le profiling et le tracing constituant une platerme complÃ¨te couvrant les trois Ã©tapes de l'analyse d'une applicatio parallÃ¨le. L'instrumentation du code peut Ãªtre effectuÃ©e d'une faÃ§on complÃ¨tement automatique avec un package fourni ("PDT - Program Database Toolkit - for routines")collectant toutes les informations sur les rÃ©gions et hotspots du code, l'utilisation mÃ©moire, les boucles, les entrÃ©es/sorties,...Selon le paramÃ¨trage de lancement, TAU peut collecter des informations les plus fines telles que le temps passÃ© Ã  chaque instruction dans une boucle ou le temps passÃ© dans les communications Ã  une Ã©tape du programme particuliÃ¨rement dans les instructions collectives MPI par exemple. Toutes ces donnÃ©es peuvent par la suite Ãªtre visualisÃ©es sous forme graphique (Paraprof 3D browser) pour une analyse fine afin d'optimiser la performance.
+\item [$\bullet$] TAU (Tuning and Analysis Utilities) a Ã©tÃ© conÃ§u Ã  l'UniversitÃ© d'Oregon comme un outil open source d'Ã©valuation de performance [24, 42]. Il intÃ¨gre de faÃ§on non intrusive le profiling et le tracing constituant une plateforme complÃ¨te couvrant les trois Ã©tapes de l'analyse d'une application parallÃ¨le. L'instrumentation du code peut Ãªtre effectuÃ©e d'une faÃ§on complÃ¨tement automatique avec un package fourni ("PDT - Program Database Toolkit - for routines")collectant toutes les informations sur les rÃ©gions et hotspots du code, l'utilisation mÃ©moire, les boucles, les entrÃ©es/sorties,...Selon le paramÃ¨trage de lancement, TAU peut collecter des informations les plus fines telles que le temps passÃ© Ã  chaque instruction dans une boucle ou le temps passÃ© dans les communications Ã  une Ã©tape du programme particuliÃ¨rement dans les instructions collectives MPI par exemple. Toutes ces donnÃ©es peuvent par la suite Ãªtre visualisÃ©es sous forme graphique (Paraprof 3D browser) pour une analyse fine afin d'optimiser la performance.
 
-	- SCALASCA
+\item [$\bullet$] SCALA ou SCAlabity Analyzer est orientÃ© particulÃ¨rement dans l'analyse de la performance des applications sur sa scalabilitÃ© lors de la montÃ©e en charge. Outre la prÃ©diction de la performance (voir la section suivante), SCALA utilise les fonctionnalitÃ©s avancÃ©es actuelles du compilateur pour la mise au point (debugging) de la dite performance et d'une Ã©ventuelle restructuration du code parallÃ¨le d'une part mais aussi d'estimer l'impact des variations sur l'environnement matÃ©riel d'exÃ©cution. L'outil permet de gÃ©nÃ©rer des suggestions de modifications du code pour une stratÃ©gie d'optimisation une fois l'analyse de la performance achevÃ©e.
 
+\end{itemize}
 
 \section{MÃ©thodes de prÃ©diction de la performance des applications parallÃ¨les}
+La prÃ©diction de la performance des applications distribuÃ©es se prÃ©sente comme une suite logique de l'analyse de la performance des dites applications. En effet, outre la comprÃ©hension du systÃ¨me ainsi que la collecte des dÃ©tails sur l'exÃ©cution du systÃ¨me qui constituent fondamentalement l'analyse de la performance, la prÃ©diction de cette performance du code est plus complexe parce que dans ce cas, on essaie, Ã  partir des rÃ©sultats des analyses sur une plateforme matÃ©rielle donnÃ©e, d'estimer les rÃ©sultats et le comportement du systÃ¨me sur une plateforme cible globalement plus puissante mais aussi avec des paramÃ¨tres d'entrÃ©es diffÃ©rents. Dans la classe d'applications considÃ©rÃ©e dans ces travaux, les rÃ©sultats de prÃ©diction les plus importants sont le temps d'exÃ©cution et le temps de communication estimÃ©s. Les objectifs de la prÃ©diction sont axÃ©s sur la minimisation du coÃ»t de l'opÃ©ration mais aussi et surtout son efficacitÃ© et sa justesse exprimÃ©es par le taux d'erreur de la prÃ©diction.\\
+Plusieurs mÃ©thodes sont utilisÃ©es pour rÃ©aliser une prÃ©diction de la performance des programmes parallÃ¨les distribuÃ©s en particulier sur une grille de calcul. On peut les classer en trois catÃ©gories : les mÃ©thodes "analytiques", celles basÃ©es sur le profiling et enfin, les mÃ©thodes de prÃ©diction utilisant la simulation. Des auteurs ont proposÃ© des combinaisons dÃ©nommÃ©es "hybrides" de ces mÃ©thodes  [39].
+\begin{itemize}
+
+\item [$\bullet$] La mÃ©thode analytique de prÃ©diction de la performance consiste Ã  la modÃ©lisation mathÃ©matique du comportement et l'exÃ©cution du code Ã  analyser. Une fois le modÃ¨le construit, on peut calculer les temps d'exÃ©cution et de communication en fonction des paramÃ¨tres passÃ©s comme la taille du problÃ¨me, la puissance de calcul disponible, les paramÃ¨tres du rÃ©seau. La mÃ©thode est rÃ©alisÃ©e en deux Ã©tapes [39, 40]: 
+\begin{itemize}
+\item [$\bullet$] (1) la collecte des informations sur l'ensemble ou uniquement sur des rÃ©gions choisies du code par instrumentation en utilisant des outils existant ou par l'ajout de pragmas et des lignes de capture d'informations dans le code. Cette opÃ©ration peut Ãªtre rÃ©pÃ©tÃ©es plusieurs fois pour avoir une sÃ©rie de rÃ©sultats Ã©liminant ainsi des Ã©ventuels effets de bord. Les donnÃ©es collectÃ©es sont consignÃ©es dans un fichier au format convenu pour la prochaine Ã©tape.
+\item [$\bullet$] (2) la modÃ©lisation mathÃ©matique par la construction du modÃ¨le incluant la partie calcul mais aussi le volet rÃ©seau pour Ã©tablir les formules reliant les paramÃ¨tres en entrÃ©e de l'application avec les rÃ©sultats obtenus. Cette Ã©tape peut Ãªtre rÃ©alisÃ©e avec des techniques de statistiques d'analyse prÃ©dictive ou encore avec d'autres mÃ©thodes analytiques. La ou l'ensemble de fonctions dÃ©crivant le modÃ¨le peut Ãªtre obtenue par itÃ©rations successives jusqu'Ã  l'btention d'une erreur infÃ©rieure Ã  un seuil prÃ©alablement Ã©tabli.   
+\end{itemize}
 
-%Voir [23]
+PMaC ou "Performance Modelling and Characterization" de l'UniversitÃ© de San Diego [42] montre un exemple d'une mÃ©thode analytique de prÃ©diction de la perfomance. Il consiste d'une part Ã  dÃ©terminer la "signature" de l'application qui regroupe les rÃ©sumÃ©s dÃ©taillÃ©s des diffÃ©rentes opÃ©rations fondamentales effectuÃ©es par l'application [41]. D'autre part, le "profile" de l'environnement d'exÃ©cution est aussi modÃ©lisÃ© en donnant une "caractÃ©risation" du matÃ©riel (CPU, mÃ©moire, rÃ©seau, ...) par des mÃ©triques d'exÃ©cution des opÃ©rations fondamentales pour une application donnÃ©e. Dans une seconde Ã©tape, Ã  partir de ces donnÃ©es collectÃ©es, un modÃ¨le mathÃ©matique est Ã©tabli pour construire un mapping entre l'environnement d'exÃ©cution et la signature de l'applcation. Ce modÃ¨le sera utilisÃ© pour une prÃ©diction de la performance sur un autre environnement mais aussi Ã©ventuellement pour une autre taille du problÃ¨me. 
+
+\item [$\bullet$] Les mÃ©thodes de prÃ©diction basÃ©es sur le profiling du code sont toujours accompagnÃ©es d'un tracing de l'exÃ©cution de l'application [40,41].Des outils de profiling et de tracing peuvent Ãªtre utilisÃ©s afin de collecter les informations essentielles sur les diffÃ©rents blocs du code. Une fois ces informations disponibles, afin de dÃ©terminer la performance de l'application sur un autre environnement d'exÃ©cution, la prÃ©diction de cette performance est obtenue en rejouant le fichier de trace sur cet environnement cible.
+TAU, un outil d'analyse de performance dÃ©jÃ  mentionnÃ© plus haut, utilise cette mÃ©thode de prÃ©diction. En effet, il incorpore des outils d'instrumentation, de mesures de performance matÃ©rielle et d'analyse.   
+
+\end{itemize}
 
 \section{Conclusion partielle}
 
+
+\chapter{Motivations}
+
+MalgrÃ© les grandes avancÃ©es dues aux performances des nouveaux processeurs, mÃ©moires mais aussi des rÃ©seaux de communication, le milieu acadÃ©mique comme le domaine industriel sont toujours confrontÃ©s Ã  des dÃ©fis et challenges de plus en plus ambitieux. Ce fait est surtout accentuÃ© par des besoins de plus en plus variÃ©s et importants de calcul scientifique nÃ©cessitant de plus en plus de moyens mais aussi de mÃ©thodes plus efficientes et performantes. Ces besoins requiÃ¨rent le traitement de donnÃ©es de plus en plus volumineuses mais aussi l'Ã©criture d'algorithmes donnant des rÃ©sultats probants dans un laps de temps correct. Le dÃ©fi actuel serait donc l'exploitation de la puissance de calcul des matÃ©riels actuels dans un environnement de calcul optimisÃ© pour traiter un volume de donnÃ©es de plus en plus important. \\
+Dans le cadre de nos travaux, l'objectif final est d'aider les utilisateurs finals (scientifiques, chercheurs, industriels, Ã©tudiants, ...) en calcul Ã  haute performance Ã  rentabiliser au maximum l'accÃ¨s aux infrastructures de calcul physiques existantes, Ã©tant donnÃ© le cÃ´ut et la difficultÃ© (mÃªme des fois l'impossibilitÃ©) d'accÃ¨s Ã  ces derniÃ¨res. En effet, la demande d'utilisation de ces infrastructures dÃ©passe largement l'offre Ã©tablie, entraÃ®nant des longues listes d'attente avant de pouvoir y accÃ©der pour une durÃ©e trÃ¨s limitÃ©es. \\
+Pour atteindre ces objectifs, nous proposons d'utiliser des outils de simulation pour exÃ©cuter les applications pour Ã©tudier leurs comportements Ã  large Ã©chelle mais aussi pour pouvoir dÃ©terminer les conditions optimales pour obtenir des rÃ©sultats optimaux. Le simulateur permet d'Ã©tudier le comportement des algorithmes sous diffÃ©rentes conditions et sur des plateformes variÃ©es et paramÃ©trables. Plusieurs modes d'exÃ©cution peuvent Ãªtre essayÃ©s lors de l'expÃ©rimentation. De plus, la flexibilitÃ© de l'outil permet l'estimation de la performance des algorithmes lors du passage Ã  l'Ã©chelle.\\
+Les questionnements suivants rÃ©sument les motivations des travaux consignÃ©s dans cette thÃ¨se.
+\begin{itemize}
+\item [$\bullet$] a. Quelles solutions pratiques peut-on apporter pour rÃ©duire le coÃ»t de lâexÃ©cution dâapplications parallÃ¨les et distribuÃ©es dans un environnement de grille de calcul durant tout son cycle de vie de dÃ©veloppement ?
+\item [$\bullet$] b. Quel est le comportement de lâalgorithme distribuÃ© Ã  large Ã©chelle dans cette architecture de grille de clusters en particulier lors de son exÃ©cution en mode asynchrone ? 
+\item [$\bullet$] c. Dans ce contexte, quels sont les facteurs importants identifiÃ©s permettant dâavoir un gain de temps dâexÃ©cution en mode asynchrone comparativement au mode synchrone ? A quel niveau peut-on estimer le gain obtenu en comparant l'exÃ©cution en mode asynchrone par rapport au mode classique synchrone.
+\item [$\bullet$] d. Quel est le taux d'erreur de validation obtenue en comparant les rÃ©sultats du lancement de l'application entre une exÃ©cution simulÃ©e et une execution sur un environnement rÃ©Ã©l Ã©quivalent.
+\end{itemize} 
+
+La partie suivante va exposer la mÃ©thodologie adoptÃ©e et les travaux de contributions pour apporter des rÃ©ponses Ã  ces questions. 
+
+
 \part{PARTIE II - Travaux de contributions, rÃ©sultats et perspectives}
 
 \chapter{Comparaison par simulation Ã  large Ã©chelle de la performance de deux algorithmes itÃ©ratifs parallÃ¨les en mode asynchrone}
@@ -1431,6 +1858,13 @@ TAU a Ã©tÃ© conÃ§u Ã  l'UniversitÃ© d'Oregon comme un outil open source d'Ã©valu
 
 \part*{BIBLIOGRAPHIE ET REFERENCES}
 
+
+{[}3{]} J. M. Bahi, S. Contassot-Vivier, R. Couturier - Parallel Iterative Algorithms: from Sequential to Grid Computing - \textit{CRC PRESS - Boca Raton London New York Washington, D.C.}
+
+{[}4{]} R. Couturier - RÃ©solution de systÃ¨mes linÃ©aires Ã  trÃ¨s large Ã©chelle : mÃ©thodes classiques versus mÃ©thodes Ã  large Ã©chelle - \textit{2014 - FEMTO-ST, UniversitÃ© de Franche-ComtÃ©}
+
+{[}5{]} C. E. Ramamonjisoa, L. Z. Khodjav, D. Laiymani, A. Giersch and R. Couturier. - Grid-enabled simulation of large-scale linear iterative solvers - \textit{2014 Femto-ST Institute - DISC Department - UniversitÃ© de Franche-ComtÃ©, IUT de Belfort-MontbÃ©liard}
+
 {[}6{]} J.M. Bahi, S. Contassot-Vivier, R. Couturier. Interest of the asynchronism in parallel iterative algorithms on meta-clusters. \textit{LIFC - UniversitÃ© de Belford-MontbÃ©liard}.
 
 {[}7{]} T.P. Collignon and M.B. van Gijzen. Fast iterative solution of large sparse linear systems on geographically separated clusters. \textit{The International Journal of High Performance Computing Applications} 25(4) 440\textendash 450.
@@ -1492,6 +1926,31 @@ of Sparse Random Matrices". \textit{UC Berkeley, INRIA Paris Rocquencourt, Tel-A
 {[}32{]} MPICH : www.mpich.org
 
 {[}33{]} OpenMPI : www.openmpi.org
+
+{[}34{]} M. Quinson et Al. - Experimenting HPC Systems with Simulation - \textit{Nancy University, France, Caen, HPCS/IWCMC 2010.}
+
+{[}35{]} A. Legrand, L. Marchal, H. Casanova - Scheduling Distributed Applications: the SimGrid Simulation Framework - \textit{Laboratoire de lâInformatique du ParallÃ¨lisme - Ecole Normale SupÃ©rieure de Lyon, Dept. of Computer Science and Engineering San Diego Supercomputer Center - University of California at San Diego}
+
+{[}36{]} Xian-He Sun, T. Fahringer, M. Pantano - SCALA: A perfformance system for scalable computing - \textit{Department Of Computer Science, Illinois Institute of Technology Chicago, Institute for software technology and parallel systems, University of Vienna Liechtenstein - The International Journal of High Performance Computing Applications,Volume 16, No. 4, Autumn 2002,}
+
+{[}37{]} IPM : Integrated Performance Monitoring - ipm-hpc.sourceforge.net 
+
+{[}38{]} K. Fuerlinger, D. Skinner - Performance Analysis and Workload Workload Characterization with IPM - 
+\textit{University of California Berkeley}
+
+{[}39{]} B. Florin Cornea et J. Bourgeois - Performance Prediction of Distributed Applications Using Block Benchmarking Methods - \textit{LIFC, University of Franche-ComtÃ©,MontbÃ©liard, France}
+
+{[}40{]} D. R. Martinez, V. Blanco, M. Boullon, J. C. Cabaleiro, T. F. Pena - Analytical Performance Models of Parallel Programs in Clusters - \textit {University of Santiago de Compostela, Spain - La Laguna University, Spain}
+
+{[}41{]} R. Allan, A. Mills - Survey of HPC Performance Modelling and Prediction Tools - \textit {Computational Science and Engineering Department, Daresbury Laboratory, Warrington - High Performance Systems Group, Department of Computer Science, University of Warwick, Coventry} 
+
+{[}42{]} PMaC : Performance Modeling and Characterization - http://www.sdsc.edu/pmac/
+
+{[}43{]} Haiwu He. Analyses avancÃ©es de la mÃ©thode hybride GMRES/LS-ARNOLDI asynchrone parallÃ¨le et distribuÃ©e pour les grilles de calcul et les supercalculateurs. \textit {UniversitÃ© des Sciences et Technologie de Lille, 2005}.
+
+{[}44{]} GMRES : Generalized minimal residual method. \textit {https://en.wikipedia.org/wiki/Generalized\_minimal\_residual\_method}.
+
+{[}45{]} G. Fasshauer - Numerical linear algebra - Illinois Institute of Technology - Department of Applied Mathematics - Chicago. 2006. Chapitre 14 - \textit {http://www.math.iit.edu/~fass/477577\_Chapter\_14.pdf}.
 %%--------------------
 %% List of figures and tables
  
