X-Git-Url: https://bilbo.iut-bm.univ-fcomte.fr/and/gitweb/these_charles_emile.git/blobdiff_plain/b85aac77ff9f56f7c83108ff7d3c8732d3045889..c9389c5838efd5d6872ab508eaa000e3a769ed18:/These_RCE.tex

diff --git a/These_RCE.tex b/These_RCE.tex
index b03acd2..ae7e4d8 100644
--- a/These_RCE.tex
+++ b/These_RCE.tex
@@ -66,6 +66,14 @@
 \newcommand{\MI}{\mathit{MaxIter}}
 %\usepackage{subcaption}
 \usepackage{graphicx}
+
+\usepackage{algpseudocode}
+\algnewcommand\algorithmicinput{\textbf{Input:}}
+\algnewcommand\Input{\item[\algorithmicinput]}
+\algnewcommand\algorithmicoutput{\textbf{Output:}}
+\algnewcommand\Output{\item[\algorithmicoutput]}
+
+\usepackage{multirow}
  
 %%--------------------
 %% Set the title, subtitle, defense date, and
@@ -275,9 +283,24 @@ le calcul en des tÃ¢ches indÃ©pendantes assignÃ©es aux processeurs. La
 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.
 
-\mfigure[h]{width=8cm, height=8cm}{"3D data partitionning btw 2 clusters"} {Partitionnement : DÃ©coupage d'une matrice tridimensionnelle entre deux clusters formÃ©s de 18 processeurs chacun} {decoupage}
+\begin{figure}[!ht]
+%\centering
+\begin{minipage}[t]{5.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}
+\centering
+\includegraphics [ width =5.5cm]{"1D-2D-3D Domain decomposition"}
+\caption {DÃ©composition en domaines 1D, 2D et 3D}
+\end{minipage}
+%\caption{Partitionnement du problÃ¨me}
+\end{figure}
+
+%\mfigure[!]{width=8cm, height=8cm}{"3D data partitionning btw 2 clusters"} {Partitionnement : DÃ©coupage %d'une matrice tridimensionnelle entre deux clusters formÃ©s de 18 processeurs chacun} {decoupage}
 
-\mfigure[h]{width=8cm, height=8cm}{"1D-2D-3D Domain decomposition"} {Partitionnement : DÃ©composition en domaines 1D, 2D et 3D} {Decompo}
+%\mfigure[h]{width=8cm, height=8cm}{"1D-2D-3D Domain decomposition"} {Partitionnement : DÃ©composition en %domaines 1D, 2D et 3D} {Decompo}
 
 %\begin{figure}[h]
 %\begin{subfigure}{0.5\textwidth}
@@ -428,7 +451,120 @@ 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 et la version "two-stage" 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}
+
+Ainsi, \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} {jusqu'Ã  l'obtention de la condition de convergence} \textbf{do}
+\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{end repeat}
+
+\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}
 
@@ -442,14 +578,152 @@ Version simple
 
 Version amÃ©liorÃ©e
 
-\section{SIMGRID/SMPI : Simulateur d'exÃ©cution d'algorithmes
-parallÃ¨les MPI dans une grille de calcul}
+\section{Simulateurs d'exÃ©cution d'algorithmes parallÃ¨les MPI dans une grille de calcul}
+
+\subsection{Calcul sur grille}
+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}
+
+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. \\
+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}
+   
+
+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.
+DÃ¨s sa conception, Grid'5000 a pris en compte la diversitÃ© des intÃªrets et des besoins des diffÃ©rents utilisateurs. En effet, dÃ©pendant de leur centre d'intÃªret peuvent se focaliser sur les protocoles rÃ©seau ou les systÃ¨mes d'exploitation particuliers ou d'autres problÃ©matiques sur la tolÃ©rance aux pannes,ces derniers peuvent configurer leur propre environnement de lancement de leurs applications. La reproductbilitÃ© des rÃ©sultats a Ã©tÃ© soigneusement Ã©tudiÃ©e pour permettre une analyse utlÃ©rieure de la performance. De plus, Grid'5000 assure la scalabilitÃ©, la qualitÃ© de service (QoS) mais aussi et surtout la sÃ©curitÃ© de l'environnement par le verouillage de la connexion vers Internet par exemple.   
 
+\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:" \\
+
+Soient E l'ensemble des temps discrets de simulation et P l'ensemble des temps du systÃ¨me physique.
+
+\begin{equation}
+\label{eqsim}
+\begin{split}
+\texttt{Si } ( T_1 \in E, T_2 \in E ) \texttt{ et }( P_1 \in P, P_2 \in P ) \texttt{ et } (T_1 \textless T_2) \\
+\Rightarrow ( (P1 \textless P2)  \texttt{ et }  \exists K \in \mathbb{N},  T_2 - T_1 = K \times ( P_2 - P_1 )
+\end{split}
+\end{equation}
+
+La dÃ©finition prÃ©cÃ©dente montre le lien linÃ©aire Ã©troit entre les intervalles de temps de simulation et celles des temps physiques. Ce qui permet d'estimer entre autres le temps d'exÃ©cution probable d'une application Ã  partir du temps de simulation observÃ©. Outre ce temps global de l'outil de simulation et les variables d'Ã©tat, une liste des Ã©venements Ã  exÃ©cuter complÃ¨te la composition du simulateur au temps discret. \\
+Le changement des variables d'Ã©tat peut s'effectuer soit Ã  une frÃ©quence rÃ©guliÃ¨re du temps de simulation (exÃ©cution rythmÃ©e par le temps) soit au dÃ©but et Ã  la fin d'un Ã©venement donnÃ© (exÃ©cution rythmÃ©e par les Ã©venements). 
+Dans le cas d'une simulation d'une application parallÃ¨le et distribuÃ©e oÃ¹ plusieurs processeurs ou coeurs interconnectÃ©s concourent Ã  rÃ©soudre ensemble le problÃ¨me posÃ©, plusieurs autres aspects liÃ©s Ã  l'environnement doivent Ãªtre considÃ©rÃ©s : \\
+\begin{itemize}
+\item [$\bullet$] L'initialisation du systÃ¨me; 
+\item [$\bullet$] Les Ã©changes de donnÃ©es entre les processus;
+\item [$\bullet$] La synchronisation des processus;
+\item [$\bullet$] La dÃ©tection de deadlock et la reprise;
+\item [$\bullet$] L'arrÃªt et la fermeture du systÃ¨me.
+\end{itemize}
+Le tableau \ref{table1} donne quelques exemples de simulateurs pour des applications parallÃ¨les et distribuÃ©es sur une grille de calcul [28, 25].
+
+\begin{table}[htbp]
+\centering
+%\tiny
+\fontsize{8}{9}\selectfont
+\begin{tabular}{|c|c|c|c|p{1cm}p{1cm}p{1cm}p{1cm}|}
+\hline \\
+%{     } & {           } & {           } & {                  } & \\
+\textbf{OUTIL} & \textbf{DESCRIPTION} & \textbf{DEVELOPPEUR} & \textbf{APPLICATIONS CIBLE} \\ \hline
+\multirow{ 3}{*}{SimJava} & SimJava fournit un processus de simulation & UniversitÃ© de  & Simulation d'Ã©venements \\
+{ } & avec une animation Ã  travers d'entitÃ©s communiquant entre elles & Edinburgh (UK) & discrets \\ 
+{ } & http://www.dcs.ed.ac.uk/home/hase/simjava/ & { } & { } \\ \hline
+
+\multirow{ 4}{*}{Bricks} & Bricks est un outil d'Ã©valuation de performance & Tokyo Institute of  & Simulation \\
+{ } & analysant divers schÃ©mas d'ordonnancement & Technology (Japan) & de grille \\ 
+{ } & dans un environnement de grille de calcul & { } & { }  \\ 
+{ } & http://matsu-www.is.titech.ac.jp/~takefusa/bricks/  & { } & { }  \\ \hline
+
+\multirow{ 4}{*}{Microgrid} & Microcrid permet la simulation d'une montÃ©e & University of   & Simulation \\
+{ } & en charge des applications sur grille de calcul  & California at & de grille \\ 
+{ } & en utilisant des ressources clusterisÃ©es & San Diego (USA) & { }  \\ 
+{ } & http://www-csag.ucsd.edu/projects/grid/microgrid.html  & { } & { }  \\ \hline
+
+\multirow{ 3}{*}{Simgrid} & Simgrid simule les applications & University of   & Simulation \\
+{ } & distribuÃ©es dans un environnement distribuÃ© hÃ©tÃ©rogÃ¨ne & California at & de grille \\ 
+{ } & http://grail.sdsc.edu/projects/simgrid/ & San Diego (USA) & { }  \\  \hline
+
+\multirow{ 4}{*}{Gridsim} & Gridsim permet la modÃ©lisation et la simulation & Monash   & Simulation \\
+{ } & d'entitÃ©s impliquÃ©es dans le calcul parallÃ¨le et distribuÃ©  & University & de grille \\ 
+{ } & par la crÃ©ation et le pilotage de diffÃ©rentes ressources & Australie & { }  \\ 
+{ } & http://www.buyya.com/gridsim/  & { } & { }  \\ \hline
+
+\end{tabular}
+\caption{Quelques outils de simulation pour une grille de calcul}
+\label{table1}
+\end{table}
+
+Simgrid est l'outil choisi dans le cadre de ces travaux pour Ã©tudier le comportement et Ã©valuer la performance d'applications parallÃ¨les distribuÃ©es Ã  grande Ã©chelle. Une section de ce chapitre sera dÃ©diÃ©e Ã  la description plus dÃ©taillÃ©e de cette plateforme.
+ 
 \subsection{MPI - Message Passing Interface}
+MPI ou "Message Passing Interface" est les spÃ©cifications d'une librairie d'interface pour le transfert de message entre les processus d'une application parallÃ¨le. A sa version MPI-3 (2015), elle est largement utilisÃ©e dans la recherche dans le domaine du calcul Ã  haute performance avec des compilateurs C/C++ et Fortran gÃ©nÃ©ralement. La facilitÃ© de l'utilisation et la portabilitÃ© Ã  travers diffÃ©rents systÃ¨mes hÃ©tÃ©rogÃ¨nes ont guidÃ© le dÃ©veloppement de ces spÃ©cifications MPI standards. Ces derniers peuvent Ãªtre matÃ©rialisÃ©s sur diffÃ©rentes plateformes cibles telles qu'une grille de calcul, des machines multiprocesseurs et multicores Ã  mÃ©moires partagÃ©es ou distribuÃ©es, un rÃ©seau de stations de travail interconnectÃ©s ou encore des environnements hybrides obtenus par la combinaison de ces architectures. Principalement, les standards MPI sont implÃ©mentÃ©s sur diffÃ©rents systÃ¨mes d'exploitation soit avec MPICH [32] ou OpenMPI [33] tous les deux des logiciels libres Ã  haute performance et portable dÃ©veloppÃ©s par des consortiums de chercheurs et des partenaires et collaborateurs industriels.
+Plusieurs domaines sont couverts par les spÃ©cifications de MPI dont les plus importants sont citÃ©s ci-dessous [31,32,33].
+\begin{itemize}
+
+\item[$\bullet$] Groupes, contexte et communicateur: DÃ©finit l'initialisation de l'environnement d'exÃ©cution du programme parallÃ¨le MPI. Un groupe de processeurs est formÃ© et un unique contexte de communication est crÃ©Ã© et les deux sont intÃ©grÃ©s ensemble dans un communicateur.
+
+\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$] 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...
+
+\item[$\bullet$] Les communications: Rassemblent les spÃ©cifications des protocoles d'Ã©changes de messages entre les processus. On distingue les communications point Ã  point, les communications collectives mais aussi les entrÃ©es / sorties parallÃ¨les. 
+
+\end{itemize}
+ 
+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}
+
+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.
+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. Comme son nom l'indique, dÃ©veloppÃ© par la communautÃ© des utilisateurs de grille de calcul, il est utilisÃ© aussi largement sur 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 constitue le fonctionnement de Simgrid : 
 
-\subsection{Simulateur 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.
+
+\item[$\bullet$]La communication entre agents se fait Ã  travers un "channel". 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 "processes 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, 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.
+
+\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}
 
-\section{Motivations}
+\mfigure[h]{width=8cm, height=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 utilise 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 obtenu 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}
 
@@ -618,7 +892,7 @@ La diffÃ©rence entre ces deux modes repose sur la variation de la taille
 du problÃ¨me lors de la montÃ©e en charge (scaling). Pour le Â« weak
 Â» scaling, on essaie d'observer le comportement du
 programme en gardant le mÃªme nombre d'Ã©lÃ©ments Ã  traiter
-par processeur ou core. Dans ce cas, les ressources
+par processeur ou coeur. Dans ce cas, les ressources
 de calcul additionnelles 
 va augmenter proportionnellement Ã  la taille du problÃ¨me en entrÃ©e. Ainsi, la problÃ©matique ici est de rÃ©soudre un problÃ¨me de plus grande taille. Par ailleurs, le Â« strong Â» scaling
 essaie de rÃ©soudre un problÃ¨me donnÃ© plus vite. Ainsi, dans ce cas,
@@ -854,7 +1128,7 @@ A titre d'exemple de machines parallÃ¨les, le site Top500.org
 Ainsi, la figure \figref {power} montre l'Ã©volution de la puissance
 de calcul mondiale dont le top actuel dÃ©veloppe un pic de performance
 thÃ©orique proche de 50 PetaFlops (33 Linpack PetaFlops (renvoi)) avec
-3.120.000 cores ( 16 noeuds avec des processeurs de 2x12 cores par
+3.120.000 coeurs ( 16 noeuds avec des processeurs de 2x12 coeurs par
 noeud) et plus de 1.240.000 Gb de mÃ©moire (64 Gb par noeud) avec des
 accÃ©lÃ©rateurs 3 $\times$ Intel Xeon Phi par noeud. Il s'agit
 de la machine Tianhe-2 (MilkyWay-2) de la National Super Computer
@@ -1180,14 +1454,76 @@ de calcul reste bloquÃ© (stalled).
 %\section*{Solutions apportÃ©es}
  
 
-\section{Techniques de profiling et instrumentation des applications parallÃ¨les}
+\section{Techniques d'analyse de performance des applications parallÃ¨les}
+\subsection{GÃ©nÃ©ralitÃ©s et objectifs}
+L'analyse de la performance des applications parallÃ¨les est largement utilisÃ©e et mÃªme recommandÃ©e lors de l'Ã©criture et la mise au point du programme. En effet, pour dÃ©terminer et estimer le coÃ»t de l'execution du code, il est d'usage de procÃ©der Ã  l'analyse de la performance dans le but d'optimiser le programme parallÃ¨le afin de trouver la meilleure performance en termes de coÃ»ts (rÃ©duction du temps d'exÃ©cution, efficacitÃ© de l'utilisation des ressources, ...). \\
+Cette opÃ©ration consiste surtout Ã  dÃ©tecter les "rÃ©gions" et "hotspots" qui correspondent aux parties du code les plus consommatrices de ressources (CPU, mÃ©moire) en particulier celles qui consomment le plus de temps de calcul ou de communication. Elle permet aussi de localiser les Ã©ventuels goulots d'Ã©tranglement lors de l'exÃ©cution du code. Les rÃ©sultats de cette analyse permet de guider le dÃ©veloppeur sur ses actions pour amÃ©liorer le code par la rÃ©Ã©crire de certaines parties du code par exemple ou de procÃ©der Ã  un meilleur dÃ©coupage du problÃ¨me pour une meilleure rÃ©partition des charges et l'utilisation des mÃ©moires ou encore par la modification de l'algorithme pour permettre une parallÃ©lisation plus poussÃ©e.
+Plusieurs outils existent avec diffÃ©rentes approches pour effectuer cette analyse.  
+La section suivante montre que le modÃ¨le de performance Ã©tabli lors de cette analyse permet aussi d'anticiper sur la prÃ©diction de la performance de l'application parallÃ¨le avec la montÃ©e en charge [21].   En effet, l'analyse de la performance d'un code peut Ãªtre utilisÃ©e pour prÃ©dire le comportement du programme soit d'une part sur un environnement de machines dÃ©terminÃ© (benchmarking) soit d'autre part, avec une taille de problÃ¨me plus importante.
+
+\subsection{Approches et mÃ©thodologie}
+Dans le domaine du calcul parallÃ¨le, l'analyse du code d'une application suit les trois Ã©tapes suivantes [21,22]:
+\begin{itemize}
+\item [$\bullet$] L'acquisition et la collecte des donnÃ©es
+\item [$\bullet$] L'enregistrement des donnÃ©es collectÃ©es
+\item [$\bullet$] La reprÃ©sentation des rÃ©sultats de l'analyse 
+\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}
+
+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. \\
+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. 
+
+\end{itemize}
+
+Noter que l'approche prÃ©sentÃ©e dans cette section prÃ©sente les techniques en vue d'optimiser le code de l'application pour un meilleur temps d'exÃ©cution en l'occurrence. Ainsi, elle ne prend pas en compte la performance lors de la scalabilitÃ© de l'application pour une prÃ©diction du comportement du code lors du passage Ã  l'echelle. Cette partie sera traitÃ©e au paragraphe ...
+Plusieurs outils d'analyse de la performance parallÃ¨le utilisant une ou des combinaisons de ces diffÃ©rentes techniques tels que Gprof, PerfExpert, IPM, TAU, PAPI, HPCToolkit, SCala [...] sont largement utilisÃ©s. La prochaine section donne plus de dÃ©tails sur certains de ces produits.
+
+
+\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}
+
+\item [$\bullet$] IPM
+
+\item [$\bullet$] 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$] 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, SCALA utilise les fonctionnalitÃ©s avancÃ©es actuelles 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.
 
+\end{itemize}
 
-\section{MÃ©thodes de prÃ©diction de la performance de l'application parallÃ¨le}
+\section{MÃ©thodes de prÃ©diction de la performance des applications parallÃ¨les}
 
+%Voir [23]
 
 \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}
@@ -1268,6 +1604,13 @@ de calcul reste bloquÃ© (stalled).
 
 \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.
@@ -1305,8 +1648,38 @@ Multiprocessor Scheduling Policy Design. \textit{Department of Computer Science
 
 {[}21{]} G. Ballard et Al. Communication Optimal Parallel Multiplication
 of Sparse Random Matrices". \textit{UC Berkeley, INRIA Paris Rocquencourt, Tel-Aviv University}. http://www.eecs.berkeley.edu/\textasciitilde{}odedsc/papers/spaa13-sparse.pdf
+
+{[}22{]} T. Ilsche, J. Schuchart, R. SchÃ¶ne, and Daniel Hackenberg. Combining Instrumentation and Sampling for Trace-based Application Performance Analysis. \textit{Technische UniversitÃ¤t Dresden, Center for Information Services and High Performance Computing (ZIH), 01062 Dresden, Germany}
+
+{[}23{]} J.A. Smitha, S.D. Hammond, G.R. Mudalige - J.A. Davis, A.B. Mills, S.DJarvis. A New Profiling Tool for Large Scale Parallel Scientific Codes. \textit{Department of Computer Science, University of Warwick,Coventry, UK} 
  
+{[}24{]} S. Shende - New Features in the TAU Performance System - \textit{ParaTools, Inc and University of Oregon. 2014}.
+
+{[}25{]} M. Mollamotalebi1, R. Maghami1, A. S. Ismail - "Grid and Cloud Computing Simulation Tools" - \textit{International Journal of Networks and Communications 2013, 3(2): 45-52 - DOI: 10.5923/j.ijnc.20130302.02}
+
+{[}26{]} F. Cappello et al. - Gridâ5000: a large scale and highly reconfigurable Grid experimental testbed - \textit{INRIA, LRI, LIP, IRISA, LORIA, LIFL, LABRI, IMAG}
+
+{[}27{]} Grid'5000 - http://www.grid5000.org 
  
+{[}28{]} A. Sulistio, C. Shin Yeo et R. Buyya - Simulation of Parallel and Distributed Systems: A Taxonomy and Survey of Tools  Grid Computing and Distributed Systems (GRIDS)- \textit{Laboratory Dept of Computer Science and Software Engineering The University of Melbourne, Australia}.
+
+{[}29{]} http://www.dau.mil/ - Defense Acquisition University (DAU) - Ft Belvoir (VA) - USA.
+
+{[}30{]} R. M. Fujimoto - Parallel and Distributed Simulation Systems - \textit{Georgia Institute of Technology - John Wiley \& Sons, Inc. - ISBN 0-471-18383-0} - 2000
+
+{[}31{]} MPI: A Message-Passing Interface Standard Version 3.- \textit{University of Tennessee, Knoxville, Tennessee.} - 2015
+
+{[}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,}
+
+
 %%--------------------
 %% List of figures and tables
  
