X-Git-Url: https://bilbo.iut-bm.univ-fcomte.fr/and/gitweb/these_charles_emile.git/blobdiff_plain/a84d210b4e8cc45730579629651a610559792413..c9389c5838efd5d6872ab508eaa000e3a769ed18:/These_RCE.tex?ds=inline

diff --git a/These_RCE.tex b/These_RCE.tex
index e22ad09..ae7e4d8 100644
--- a/These_RCE.tex
+++ b/These_RCE.tex
@@ -1,193 +1,330 @@
-%% LyX 2.1.4 created this file.  For more info, see http://www.lyx.org/.
-%% Do not edit unless you really know what you are doing.
-\documentclass[french]{report}
-
-% Font type and font size
-\usepackage{times}
-\fontsize{12}{15}
-
-%Espacement des paragraphes
-\setlength{\parskip}{0.3cm}
-%interligne paragraphe : voir spacing ci-dessous
-\usepackage{setspace}
-
-%setting margins
-\usepackage
-[
-        a4paper,
-        left=2.5cm,
-        right=1.5cm,
-        top=2cm,
-        bottom=2cm,
-        % use vmargin=2cm to make vertical margins equal to 2cm.
-        % us  hmargin=3cm to make horizontal margins equal to 3cm.
-        % use margin=3cm to make all margins  equal to 3cm.
-]
-{geometry}
-
-\usepackage[T1]{fontenc}
-\usepackage[latin9]{inputenc}
-\usepackage{babel}
-\usepackage{amsmath, amsthm, amssymb}
-
-\usepackage{url}
-\DeclareUrlCommand\email{\urlstyle{same}}
-
-\usepackage[autolanguage,np]{numprint}
-\AtBeginDocument{%
-  \renewcommand*\npunitcommand[1]{\text{#1}}
-  \npthousandthpartsep{}}
-
-\usepackage{xspace}
-\usepackage[textsize=footnotesize]{todonotes}
-
-%Affichage des figures
-%%%\usepackage{caption}
-%\usepackage{wrapfig}
-\usepackage{subcaption}
-\usepackage{graphicx}
-
+%% Use the standard UP-methodology class
+%% with French language.
+%%
+%% You may specify the option 'twoside' or 'oneside' for
+%% the document.
+%%
+%% See the documentation tex-upmethodology on
+%% http://www.arakhne.org/tex-upmethodology/
+%% for details about the macros that are provided by the class and
+%% to obtain the list of the packages that are already included. 
+ 
+\documentclass[french]{spimufcphdthesis}
+ 
+%%--------------------
+%% The TeX code is entering with UTF8
+%% character encoding (Linux and MacOS standards)
+\usepackage[utf8]{inputenc}
+ 
+%%-------------------
+%% You want to use the NatBib extension
+%\usepackage[authoryear]{natbib}
+ 
+%%--------------------
+%% Include the 'multibib' package to enable to
+%% have different types of bibliographies in the
+%% document (see at the end of this template for
+%% an example with a personnal bibliography and
+%% a general bibliography)
+%%
+%% Each bibliography defined with 'multibib'
+%% adds a chapter with the corresponding
+%% publications (in addition to the chapter for
+%% the standard/general bibliography).
+%% CAUTION:
+%% There is no standard way to do include this type of
+%% personnal bibliography.
+%% We propose to use 'multibib' package to help you,
+%% for example.
+%\usepackage{multibib}
+ 
+%% Define a "type" of bibliography, here the PERSONAL one,
+%% that is supported by 'multibib'.
+%\newcites{PERSO}{Liste de mes publications}
+ 
+%% To cite one of your PERSONAL papers with the style
+%% of the PERSONAL bibliography: \citePERSO{key}
+%% To force to show one of your PERSONAL papers into
+%% the PERSONAL bibliography, even if not cited in the
+%% text: \nocitePERSO{key}
+ 
+%% REMARK: When you are using 'multibib', you
+%% must compile the PERSONAL bibliography by hand.
+%% For example, the sequence of commands to run
+%% when you had defined the bibliography PERSO is:
+%%   $ pdflatex my_document.tex
+%%   $ bibtex my_document.aux
+%%   $ bibtex PERSO.aux
+%%   $ pdflatex my_document.tex
+%%   $ pdflatex my_document.tex
+%%   $ pdflatex my_document.tex
+ 
+%%--------------------
+%% Add here any other packages that are needed for your document.
+%\usepackage{eurosim}
+%\usepackage{amsmath}
 \newcommand{\MI}{\mathit{MaxIter}}
+%\usepackage{subcaption}
+\usepackage{graphicx}
 
-%Table des matières
-\setcounter{secnumdepth}{3}
-\setcounter{tocdepth}{3} 
-
-\begin{document}
-\begin{spacing}{1.5}
+\usepackage{algpseudocode}
+\algnewcommand\algorithmicinput{\textbf{Input:}}
+\algnewcommand\Input{\item[\algorithmicinput]}
+\algnewcommand\algorithmicoutput{\textbf{Output:}}
+\algnewcommand\Output{\item[\algorithmicoutput]}
 
-Page de garde
+\usepackage{multirow}
+ 
+%%--------------------
+%% Set the title, subtitle, defense date, and
+%% the registration number of the PhD thesis.
+%% The optional parameter is the subtitle of the PhD thesis.
+%% The first mandatory parameter is the title of the PhD thesis.
+%% 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}
+ 
+%%--------------------
+%% Set the author of the PhD thesis
+\addauthor[email]{PrÃ©nom}{Nom}
+ 
+%%--------------------
+%% Add a member of the jury
+%% \addjury{Firstname}{Lastname}{Role in the jury}{Position}
+\addjury{Incroyable}{Hulk}{Rapporteur}{Professeur Ã  l'UniversitÃ© de Gotham City \\ Commentaire secondaire}
+\addjury{Super}{Man}{Examinateur}{Professeur Ã  l'UniversitÃ© de Gotham City}
+\addjury{Bat}{Man}{Directeur de thÃ¨se}{Professeur Ã  l'UniversitÃ© de Gotham City}
+ 
+%%--------------------
+%% Change style of the table of the jury
+%% \Set{jurystyle}{put macros for the style}
+%\Set{jurystyle}{\small}
+
+%%--------------------
+%% Add the laboratory where the thesis was made
+%\addlaboratory{Laboratoire Waynes Industry}
+
+%%--------------------
+%% Clear the list of the laboratories
+%\resetlaboratories
+ 
+%%--------------------
+%% Set the English abstract
+\thesisabstract[english]{This is the abstract in English}
+ 
+%%--------------------
+%% Set the English keywords. They only appear if
+%% there is an English abstract
+\thesiskeywords[english]{Keyword 1, Keyword 2}
+ 
+%%--------------------
+%% Set the French abstract
+\thesisabstract[french]{Ceci est le rÃ©sumÃ© en franÃ§ais}
+ 
+%%--------------------
+%% Set the French keywords. They only appear if
+%% there is an French abstract
+\thesiskeywords[french]{Algorithmes itÃ©ratifs, Performance, Simulation, Simgrid, Grid Computing}
+ 
+%%--------------------
+%% Change the layout and the style of the text of the "primary" abstract.
+%% If your document is written in French, the primary abstract is in French,
+%% otherwise it is in English.
+%\Set{primaryabstractstyle}{\tiny}
+ 
+%%--------------------
+%% Change the layout and the style of the text of the "secondary" abstract.
+%% If your document is written in French, the secondary abstract is in English,
+%% otherwise it is in French.
+%\Set{secondaryabstractstyle}{\tiny}
+ 
+%%--------------------
+%% Change the layout and the style of the text of the "primary" keywords.
+%% If your document is written in French, the primary keywords are in French,
+%% otherwise they are in English.
+%\Set{primarykeywordstyle}{\tiny}
+ 
+%%--------------------
+%% Change the layout and the style of the text of the "secondary" keywords.
+%% If your document is written in French, the secondary keywords are in English,
+%% otherwise they are in French.
+%\Set{secondarykeywordstyle}{\tiny}
+ 
+%%--------------------
+%% Change the speciality of the PhD thesis
+%\Set{speciality}{Informatique}
+ 
+%%--------------------
+%% Change the institution
+%\Set{universityname}{Universit\'e de Franche-Comt\'e}
+ 
+%%--------------------
+%% Add the logos of the partners or the sponsors on the front page
+%\addpartner[image options]{image name}
+
+%%--------------------
+%% Clear the list of the partner/sponsor logos
+%\resetpartners
+
+%%--------------------
+%% Change the header and the foot of the pages.
+%% You must include the package "fancyhdr" to
+%% have access to these macros.
+%% Left header
+%\lhead{}
+%% Center header
+%\chead{}
+%% Right header
+%\rhead{}
+%% Left footer
+%\lfoot{}
+%% Center footer
+%\cfoot{}
+%% Right footer
+%\rfoot{}
+ 
+%%--------------------
+% Declare several theorems
+\declareupmtheorem{mytheorem}{My Theorem}{List of my Theorems}
 
-Remerciements
+%%--------------------
+%% Change the message on the backcover.
+%\Set{backcovermessage}{%
+%	Some text
+%}
 
-%Table des matières
+\begin{document}
+ 
+%%--------------------
+%% The following line does nothing until
+%% the class option 'nofrontmatter' is given.
+%\frontmatter
+
+%%--------------------
+%% The following line permits to add a chapter for "acknowledgements"
+%% at the beginning of the document. This chapter has not a chapter
+%% number (using the "star-ed" version of \chapter) to prevent it to
+%% be in the table of contents
+\chapter*{Remerciements}
+ 
+%%--------------------
+%% Include a general table of contents
 \tableofcontents
 
-
-Table des figures
-
-Table des abréviations
-
-
-Résumé (Mots clefs) 
-
-Abstract (Key words)
-
-Bibliographie et références
-
-Annexes
-
+%%--------------------
+%% The content of the PhD thesis
+\mainmatter
 
 \part*{INTRODUCTION}
 \newpage
 
-\part*{PARTIE I : Contexte scientifique et revue de l\textquoteright état de l'art}
+\part{PARTIE I: Contexte scientifique et revue de l'Ã©tat de l'art}
 
-\chapter*{Chapitre 1 : Cadre de travail et contexte scientifique}
+\chapter{Cadre de travail et contexte scientifique}
 
-\section*{1.1 Classe des algorithmes itératifs parallèles à large échelle dans une grille de calcul}
+\section{Classe des algorithmes itÃ©ratifs parallÃ¨les Ã  large Ã©chelle dans une grille de calcul}
 
-Dans le cadre de ces travaux, nous nous sommes intéressés particulièrement
+Dans le cadre de ces travaux, nous nous sommes intÃ©ressÃ©s particuliÃ¨rement
 sur la performance d'une classe d'algorithmes
-parallèles dits itératifs. De plus en plus, cette méthode itérative
-est utilisée pour résoudre des problèmes dans différents domaines
-scientifiques tels que la mécanique, la prévision du temps, le traitement
-d'images ou encore l'économie financière.
-Elle consiste à appliquer, contrairement à la méthode de résolution
-« directe », à partir d'une valeur initiale $X_0$ une
-transformation à un vecteur inconnu de rang n par des itérations successives
-afin de s'approcher par approximation à la solution
-recherchée X{*} avec une valeur résiduelle la plus réduite possible. 
+parallÃ¨les dits itÃ©ratifs. De plus en plus, cette mÃ©thode itÃ©rative
+est utilisÃ©e pour rÃ©soudre des problÃ¨mes dans diffÃ©rents domaines
+scientifiques tels que la mÃ©canique, la prÃ©vision du temps, le traitement
+d'images ou encore l'Ã©conomie financiÃ¨re.
+Elle consiste Ã  appliquer, contrairement Ã  la mÃ©thode de rÃ©solution
+Â« directe Â», Ã  partir d'une valeur initiale $X_0$ une
+transformation Ã  un vecteur inconnu de rang n par des itÃ©rations successives
+afin de s'approcher par approximation Ã  la solution
+recherchÃ©e X{*} avec une valeur rÃ©siduelle la plus rÃ©duite possible. 
 \begin{equation}
 \label{eq:1}
   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
-(X{*}), c'est-à-dire X{*} est un point fixe de f.
-
-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
-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*}
+La solution du problÃ¨me sera donc le vecteur X{*} tel que X{*} = f
+(X{*}), c'est-Ã -dire X{*} est un point fixe de f.
+
+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
+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)	
-\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
-travaux ont démontré la convergence de ces méthodes itératives pour
-la résolution de systèmes linéaires ou non linéaires avec un taux
-de convergence élevé {[}7, 8{]}. Lors de l'exécution
-dans chaque bloc de calcul, l'algorithme peut demander l'échange
-de données comme des résultats intermédiaires par exemple entre des
-processeurs voisins avant d'entamer une nouvelle itération.
-Les sections suivantes vont détailler les notions liées à la résolution
+\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
+travaux ont dÃ©montrÃ© la convergence de ces mÃ©thodes itÃ©ratives pour
+la rÃ©solution de systÃ¨mes linÃ©aires ou non linÃ©aires avec un taux
+de convergence Ã©levÃ© {[}7, 8{]}. Lors de l'exÃ©cution
+dans chaque bloc de calcul, l'algorithme peut demander l'Ã©change
+de donnÃ©es comme des rÃ©sultats intermÃ©diaires par exemple entre des
+processeurs voisins avant d'entamer une nouvelle itÃ©ration.
+Les sections suivantes vont dÃ©tailler les notions liÃ©es Ã  la rÃ©solution
 de cet algorithme.
 
-\subsection{Partitionnement du problème} 
-
-Comme expliqué plus haut et appliquant le principe du "diviser pour regner", le problème de résolution d'un
-algorithme itératif parallèle commence par un découpage de la matrice $n \times n$
-en entrée en plus petits blocs dont le nombre dépend du nombre
-de processeurs disponibles. On parle de « décomposition de domaine
-» en considérant les données en priorité en opposition à la « décomposition
-fonctionnelle » où le partitionnement se base sur le calcul : diviser
-le calcul en des tâches indépendantes assignées aux processeurs. La
-figure Figure~\ref{fig:1.a} 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}[!t]
-%%\centering
-%  \includegraphics[width=60mm,keepaspectratio]{"3D data partitionning btw 2 clusters"}
-%\caption{Découpage d'une matrice tridimensionnelle entre deux clusters formés de 18 processeurs %chacun.}
-%\label{fig:1.1}
-%\end{figure}
-
-\begin{figure}[h]
-\begin{subfigure}{0.5\textwidth}
-\includegraphics[width=0.9\linewidth, height=6cm]{"3D data partitionning btw 2 clusters"} 
-\caption{Découpage d'une matrice tridimensionnelle entre deux clusters formés de 18 processeurs chacun}
-\label{fig:1.a}
-\end{subfigure}
-\begin{subfigure}{0.5\textwidth}
-\includegraphics[width=1\linewidth, height=5cm]{"1D-2D-3D Domain decomposition"}
-\caption{Décomposition en domaines 1D, 2D et 3D}
-\label{fig:1.b}
-\end{subfigure}
-\caption{Partitionnement du problème}
-%\label{fig:1}
+\subsection{Partitionnement du problÃ¨me} 
+
+Comme expliquÃ© plus haut et appliquant le principe du "diviser pour regner", le problÃ¨me de rÃ©solution d'un
+algorithme itÃ©ratif parallÃ¨le commence par un dÃ©coupage de la matrice $n \times n$
+en entrÃ©e en plus petits blocs dont le nombre dÃ©pend du nombre
+de processeurs disponibles. On parle de Â« dÃ©composition de domaine
+Â» en considÃ©rant les donnÃ©es en prioritÃ© en opposition Ã  la Â« dÃ©composition
+fonctionnelle Â» oÃ¹ le partitionnement se base sur le calcul : diviser
+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.
+
+\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}
 
-%\noindent%
-%\begin{minipage}{\linewidth}% to keep image and caption on one page
-%\makebox[\linewidth]{%        to center the image
-%  \includegraphics[keepaspectratio=true,scale=0.6]{"3D data partitionning btw 2 clusters"}}
-%\captionof{figure}{Découpage d'une matrice tridimensionnelle entre deux clusters formés de 18 %processeurs chacun.}\label{fig:1.1}  
-%\end{minipage}
-
-%\begin{wrapfigure}{l}{0.3\textwidth}
-%\includegraphics[width=0.8\linewidth]{"3D data partitionning btw 2 clusters"} 
-%\caption{Découpage d'une matrice tridimensionnelle entre deux clusters.}
-%\label{fig:1.1}
-%\end{wrapfigure}
+%\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}
+
+%\begin{figure}[h]
+%\begin{subfigure}{0.5\textwidth}
+%\includegraphics[width=6cm, height=6cm]{"3D data partitionning btw 2 clusters"} 
+%\caption{DÃ©coupage d'une matrice tridimensionnelle entre deux clusters formÃ©s de 18 processeurs chacun}
+%\label{fig:1.a}
+%\end{subfigure}
+%\begin{subfigure}{0.5\textwidth}
+%\includegraphics[width=1\linewidth, height=5cm]{"1D-2D-3D Domain decomposition"}
+%\caption{DÃ©composition en domaines 1D, 2D et 3D}
+%\label{fig:1.b}
+%\end{subfigure}
+%\caption{Partitionnement du problÃ¨me}
+%\end{figure}
 
 Chaque cluster va prendre en charge un bloc de 18 "sous-domaines". Chaque
 processeur $P_i$ tournera l'algorithme sur le cube qui
-lui est assigné. Les sous domaines s'échangent des
-données par leurs points périphériques {[}9{]} au niveau du cluster mais
+lui est assignÃ©. Les sous domaines s'Ã©changent des
+donnÃ©es par leurs points pÃ©riphÃ©riques {[}9{]} au niveau du cluster mais
 aussi entre les clusters en suivant une organisation logique d'un
-anneau virtuel dont les n½uds sont les processeurs $P_i$.
+anneau virtuel dont les noeuds sont les processeurs $P_i$.
 
-Une fois partitionnée en m blocs, la relation reccurente de l'équation \eqref{eq:1} peut
-s'écrire :
+Une fois partitionnÃ©e en m blocs, la relation reccurente de l'Ã©quation \eqref{eq:1} peut
+s'Ã©crire :
 \begin{equation}
 x_{k+1} = (x_1^k, x_2^k, \dots , x_n^k), k=1,\dots n  
 \end{equation}
@@ -195,235 +332,490 @@ ou en termes de blocs :
 \begin{equation}
 X_{k+1} = (X_1^k, X_2^k, \dots , X_n^k), k=1,\dots m 
 \end{equation}
-Donc, on peut écrire :
-\begin{equation*} 
+Donc, on peut Ã©crire :
+\begin{equation} 
 X_{k+1} = F (X_k)
-\end{equation*}
+\end{equation}
+
 \begin{equation} 
-(X_1^{k+1} ,X_2^{k+1} , \dots{}, X_m^{k+1}) = (F_1(X_k), F_2(X_k), \dots , F_m(X_k))
+\iff (  \exists F_k   ) (X_1^{k+1} ,X_2^{k+1} , \dots{}, X_m^{k+1}) = (F_1(X_k), F_2(X_k), \dots , F_m(X_k))
 \end{equation} 
-Où : 
-\begin{equation*} 
+OÃ¹ : 
+\begin{equation} 
 X_i^{k+1} = F_i (X^k) = Fi ( X_1^k , X_2^k , \dots{} , X_m^k)\>pour \>i=1,\dots,k
-\end{equation*}
-L'exemple donné montre un partitionnement « naturel
-» du problème initial par un découpage uniforme avec des blocs de même taille. Il met en exergue deux facteurs importants
-à tenir en compte lors de cette opération :
+\end{equation}
+L'exemple donnÃ© montre un partitionnement Â« naturel
+Â» du problÃ¨me initial par un dÃ©coupage uniforme avec des blocs de mÃªme taille. Il met en exergue deux facteurs importants
+Ã  tenir en compte lors de cette opÃ©ration :
 \begin{itemize}
-\item [$\bullet$] essayer de répartir
-uniformément la charge assignée à chaque processeur : effectivement,
-un déséquilibre de charge entre les unités de calcul peut impacter
-négativement la performance globale du système;
-\item[$\bullet$] réduire au maximum
-les communications entre les processeurs : ces temps d'échange
-coûtent aussi chers au niveau de la performance globale. 
+\item [$\bullet$] essayer de rÃ©partir
+uniformÃ©ment la charge assignÃ©e Ã  chaque processeur : effectivement,
+un dÃ©sÃ©quilibre de charge entre les unitÃ©s de calcul peut impacter
+nÃ©gativement la performance globale du systÃ¨me;
+\item[$\bullet$] rÃ©duire au maximum
+les communications entre les processeurs : ces temps d'Ã©change
+coÃ»tent aussi chers au niveau de la performance globale. 
 \end{itemize}
 Selon le
 type de l'algorithme, on peut faire un classement en
-trois catégories {[}21{]} selon le partitionnement ou la décomposition
-de domaine choisie (Figure~\ref{fig:1.b} ) : 
+trois catÃ©gories {[}21{]} selon le partitionnement ou la dÃ©composition
+de domaine choisie (Figure \figref{Decompo}) : 
 \begin{itemize}
-\item[$\bullet$] 1D où la matrice est découpée
-suivant des briques dont deux dimensions de longueur n et la dernière plus courte que n.
+\item[$\bullet$] 1D oÃ¹ la matrice est dÃ©coupÃ©e
+suivant des briques dont deux dimensions de longueur n et la derniÃ¨re plus courte que n.
 \item [$\bullet$] 2D avec des briques dont une dimension est de longueur n et les
 deux autres plus courtes que n; 
 \item [$\bullet$] et enfin, 3D avec des briques dont les
 3 dimensions sont plus courtes que n. 
 \end{itemize}
+ 
+ \subsection{Modes d'exÃ©cution synchrone et asynchrone}
 
-\subsection{Modes d'exécution synchrone et asynchrone}
-
-Lors de l'exécution des algorithmes itératifs parallèles
+Lors de l'exÃ©cution des algorithmes itÃ©ratifs parallÃ¨les
 sur un environnement de type grille de calcul, le temps de communication
-résultant des échanges de données entre les unités de calcul est aussi
-important que le temps de calcul lui-même. En effet, un ratio montrant
-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. 
-
-\begin{figure}[h]
-\begin{subfigure}{0.5\textwidth}
-\includegraphics[width=5cm, height=5cm, scale=3]{"Synchronous iterations model"} 
-\caption{Modèle de communication synchrone}
-\label{fig:2.a}
-\end{subfigure}
-\begin{subfigure}{0.5\textwidth}
-\includegraphics[width=5cm, height=5cm, scale=3]{"Asynchronous iterations model"}
-\caption{Modèle de communication asynchrone}
-\label{fig:2.b}
-\end{subfigure}
-\caption{Modèles de communication}
-%\label{fig:1}
-\end{figure}
+rÃ©sultant des Ã©changes de donnÃ©es entre les unitÃ©s de calcul est aussi
+important que le temps de calcul lui-mÃªme. En effet, un ratio montrant
+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}[h]
+%\begin{subfigure}{0.5\textwidth}
+%\includegraphics[width=5cm, height=5cm, scale=3]{"Synchronous iterations model"} 
+%\caption{ModÃ¨le de communication synchrone}
+%\label{fig:2.a}
+%\end{subfigure}
+%\begin{subfigure}{0.5\textwidth}
+%\includegraphics[width=5cm, height=5cm, scale=3]{"Asynchronous iterations model"}
+%\caption{ModÃ¨le de communication asynchrone}
+%\label{fig:2.b}
+%\end{subfigure}
+%\caption{ModÃ¨les de communication}
+%%\label{fig:1}
+%\end{figure}
 
-D'une part, ces paquets de données peuvent être transférés
-de façon « synchrone » : dans ce cas, une coordination de l'échange
-est assurée par les deux parties. A la fin de chaque itération, l'émetteur,
-une fois la poignée de main établie, envoie les données et attend
-jusqu'à la réception d'un accusé de
-réception par le récepteur. L'algorithme même est en
-mode synchrone parce qu'une étape de synchronisation
-de tous les processeurs est nécessaire avant d'entamer
-une nouvelle itération. La figure Figure~\ref{fig:2.a} montre les actions dans
-le temps lors d'un échange en mode synchrone entre
-deux processeurs. Les flèches montrent la date d'envoi
-par $P_1$ et la date de réception du paquet par $P_2$. On parle ici de mode
-de communication « bloquante » : la nouvelle itération ne peut commencer
+D'une part, ces paquets de donnÃ©es peuvent Ãªtre transfÃ©rÃ©s
+de faÃ§on Â« synchrone Â» : dans ce cas, une coordination de l'Ã©change
+est assurÃ©e par les deux parties. A la fin de chaque itÃ©ration, l'Ã©metteur,
+une fois la poignÃ©e de main Ã©tablie, envoie les donnÃ©es et attend
+jusqu'Ã  la rÃ©ception d'un accusÃ© de
+rÃ©ception par le rÃ©cepteur. L'algorithme mÃªme est en
+mode synchrone parce qu'une Ã©tape de synchronisation
+de tous les processeurs est nÃ©cessaire avant d'entamer
+une nouvelle itÃ©ration. La figure \figref{sync} montre les actions dans
+le temps lors d'un Ã©change en mode synchrone entre
+deux processeurs. Les flÃ¨ches montrent la date d'envoi
+par $P_1$ et la date de rÃ©ception du paquet par $P_2$. On parle ici de mode
+de communication Â« bloquante Â» : la nouvelle itÃ©ration ne peut commencer
 tant que tous les processus n'ont pas fini leurs communications.
 
-D'autre part, l'échange de données peut
-s'effectuer en mode « asynchrone ». Dans ce cas, l'émetteur
-peut envoyer de l'information au destinataire à tout
-moment et aucune synchronisation n'est nécessaire.
-Chaque processeur travaille avec les données qu'il
-reçoit au fil du temps. La communication est ici non bloquante. La
-conséquence immédiate de ce mode de communication est l'absence
-des périodes où le traitement est arrêté (CPU stalled ou idle) parce
-qu'il doit attendre l'accusé de réception
-du récepteur (Figure~\ref{fig:2.b} ). En mode asynchrone, le temps entre chaque
-itération peut varier notablement dû à la différence éventuelle de
+D'autre part, l'Ã©change de donnÃ©es peut
+s'effectuer en mode Â« asynchrone Â». Dans ce cas, l'Ã©metteur
+peut envoyer de l'information au destinataire Ã  tout
+moment et aucune synchronisation n'est nÃ©cessaire.
+Chaque processeur travaille avec les donnÃ©es qu'il
+reÃ§oit au fil du temps. La communication est ici non bloquante. La
+consÃ©quence immÃ©diate de ce mode de communication est l'absence
+des pÃ©riodes oÃ¹ le traitement est arrÃªtÃ© (CPU stalled ou idle) parce
+qu'il doit attendre l'accusÃ© de rÃ©ception
+du rÃ©cepteur (Figure \figref{async}). En mode asynchrone, le temps entre chaque
+itÃ©ration peut varier notablement dÃ» Ã  la diffÃ©rence Ã©ventuelle de
 la puissance de chaque processeur ou encore de la performance des
-différents réseaux de communication utilisés. {[}7{]} montre à travers
-des algorithmes itératifs classiques les intérêts de la mise en ½uvre
-de communication asynchrone lors de la résolution mais aussi les éventuels
-inconvénients. Parmi les avantages de ce mode de communication, la
-réduction du temps de synchronisation entre processeurs peut impacter
-positivement le temps global d'exécution surtout en
-environnement hétérogène. De même, le chevauchement du calcul avec
-la communication des données peut aussi améliorer la performance de
+diffÃ©rents rÃ©seaux de communication utilisÃ©s. {[}7{]} montre Ã  travers
+des algorithmes itÃ©ratifs classiques les intÃ©rÃªts de la mise en oeuvre
+de communication asynchrone lors de la rÃ©solution mais aussi les Ã©ventuels
+inconvÃ©nients. Parmi les avantages de ce mode de communication, la
+rÃ©duction du temps de synchronisation entre processeurs peut impacter
+positivement le temps global d'exÃ©cution surtout en
+environnement hÃ©tÃ©rogÃ¨ne. De mÃªme, le chevauchement du calcul avec
+la communication des donnÃ©es peut aussi amÃ©liorer la performance de
 l'application. Enfin, un partitionnement lors de de
-la décomposition du domaine tenant compte de l'absence
-de synchronisation en mode asynchrone peut aussi contribuer à la performance
-en répartissant efficacement le calcul. Les inconvénients de l'asynchronisme
-peuvent venir de la détection de la convergence globale étant donné
+la dÃ©composition du domaine tenant compte de l'absence
+de synchronisation en mode asynchrone peut aussi contribuer Ã  la performance
+en rÃ©partissant efficacement le calcul. Les inconvÃ©nients de l'asynchronisme
+peuvent venir de la dÃ©tection de la convergence globale Ã©tant donnÃ©
 qu'il n'y a pas de synchronisation des
-opérations. L'arrêt doit être décidé après une forme
-de communication globale à un certain point de l'algorithme
-; il peut se faire lors de la communication inévitable entre processus
-pour annoncer la convergence locale. Un autre problème est aussi la
-tolérance aux pannes quoique cette défaillance peut aussi concerner
-le mode synchrone : si un des processus contribuant dans la résolution
-du problème se plante, tout le processus itératif peut s'écrouler
-si un mécanisme de reprise sur panne est mis en place. 
-
-\section*{1.2 Méthodes de résolution parallèles du problème de Poisson et de
+opÃ©rations. L'arrÃªt doit Ãªtre dÃ©cidÃ© aprÃ¨s une forme
+de communication globale Ã  un certain point de l'algorithme
+; il peut se faire lors de la communication inÃ©vitable entre processus
+pour annoncer la convergence locale. Un autre problÃ¨me est aussi la
+tolÃ©rance aux pannes quoique cette dÃ©faillance peut aussi concerner
+le mode synchrone : si un des processus contribuant dans la rÃ©solution
+du problÃ¨me se plante, tout le processus itÃ©ratif peut s'Ã©crouler
+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*}
 
-\subsection{Méthode de résolution GMRES}
+\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}
 
 Native
 
-Version « two-stage »
+Version Â« two-stage Â»
 
 \subsection{Solveur multisplitting} 
 
 Version simple
 
-Version améliorée
+Version amÃ©liorÃ©e
+
+\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.
 
-\section*{1.3 SIMGRID/SMPI : Simulateur d'exécution d'algorithmes
-parallèles MPI dans une grille de calcul}
+\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}
 
-\subsection{Simulateur SIMGRID}
+\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.
 
-\section*{1.4 Motivations}
+\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.
 
-\section*{1.5 Conclusion partielle}
+\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...
 
-\chapter*{Chapitre 2 : Etat de l'art et travaux de recherche associés}
+\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. 
 
-\section*{2.1 Concepts et définitions}
+\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 : 
+
+\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}
+
+\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}
+
+
+\chapter{Etat de l'art et travaux de recherche associÃ©s}
 
-Dans cette section, des concepts et des définitions relatifs à nos
-travaux sont passés en revue.
+\section{Concepts et dÃ©finitions}
+Dans cette section, des concepts et des dÃ©finitions relatifs Ã  nos
+travaux sont passÃ©s en revue.
 
-\subsection{Performance de l'application parallèle et scalabilité} 
+\subsection{Performance de l'application parallÃ¨le et scalabilitÃ©} 
 
 La performance d'une application dans un environnement
-distribué peut être définie comme « la capacité de réduire le temps
-pour résoudre le problème quand les ressources de calcul augmentent
-» {[}20{]}. L'objectif est de minimiser le
-temps d'exécution globale de l'application
-en ajoutant des ressources supplémentaires (processeurs, mémoire,
-\dots ). D'où la notion de « scalabilité » ou "montée
-en charge" ou encore "passage à l'echelle" dont l'objectif principal est d'accroitre
-la performance quand la complexité ou la taille du problème augmentent.
-Comme nous allons voir tout au long de ce chapitre, deux catégories
-de facteurs concourent à la difficulté de la prédiction des applications
-parallèles en considérant leur performance après la montée en charge
-des ressources : d'une part, on peut énumérer les facteurs
-liés à l'écosystème d'exécution tels
-que le nombre de processeurs, la taille de la mémoire et de sous-système
-de stockage, la latence et la bande passante des réseaux de communication
-; d'autre part, les facteurs liés au code lui-même
+distribuÃ© peut Ãªtre dÃ©finie comme Â« la capacitÃ© de rÃ©duire le temps
+pour rÃ©soudre le problÃ¨me quand les ressources de calcul augmentent
+Â» {[}20{]}. L'objectif est de minimiser le
+temps d'exÃ©cution globale de l'application
+en ajoutant des ressources supplÃ©mentaires (processeurs, mÃ©moire,
+\dots ). D'oÃ¹ la notion de Â« scalabilitÃ© Â» ou "montÃ©e
+en charge" ou encore "passage Ã  l'echelle" dont l'objectif principal est d'accroitre
+la performance quand la complexitÃ© ou la taille du problÃ¨me augmentent.
+Comme nous allons voir tout au long de ce chapitre, deux catÃ©gories
+de facteurs concourent Ã  la difficultÃ© de la prÃ©diction des applications
+parallÃ¨les en considÃ©rant leur performance aprÃ¨s la montÃ©e en charge
+des ressources : d'une part, on peut Ã©numÃ©rer les facteurs
+liÃ©s Ã  l'Ã©cosystÃ¨me d'exÃ©cution tels
+que le nombre de processeurs, la taille de la mÃ©moire et de sous-systÃ¨me
+de stockage, la latence et la bande passante des rÃ©seaux de communication
+; d'autre part, les facteurs liÃ©s au code lui-mÃªme
 impactent aussi la performance de l'application affectant
-ainsi la prédiction : il s'agit par exemple de la fréquence
-de la communication et de la synchronisation, la faible parallélisation
-mais aussi le mauvais ordonnancement des tâches (équilibrage de charge)
+ainsi la prÃ©diction : il s'agit par exemple de la frÃ©quence
+de la communication et de la synchronisation, la faible parallÃ©lisation
+mais aussi le mauvais ordonnancement des tÃ¢ches (Ã©quilibrage de charge)
 {[}20{]}. 
 
 Afin de quantifier la performance d'un code, plusieurs
-métriques ont été définies mais le temps d'exécution
-global nécessaire pour atteindre la fin du programme reste le plus
-simple. On peut écrire : 
+mÃ©triques ont Ã©tÃ© dÃ©finies mais le temps d'exÃ©cution
+global nÃ©cessaire pour atteindre la fin du programme reste le plus
+simple. On peut Ã©crire : 
 
 \begin{equation}
 \label{eq:5}
 T_{exec} = T_{calc} + T_{comm} + T_{surcharge} 
 \end{equation}
-où : 
-\indent\indent$T_{exec}$ 	: Temps d'exécution global \\
+oÃ¹ : 
+\indent\indent$T_{exec}$ 	: Temps d'exÃ©cution global \\
 \indent\indent$T_{calc}$ 	: Temps de calcul \\
 \indent\indent$T_{comm}$	: Temps de communication \\
 \indent\indent$T_{surcharge}$ : Temps de surcharge.
 
 
-Le temps de calcul représente le temps pris par le code pour effectuer
+Le temps de calcul reprÃ©sente le temps pris par le code pour effectuer
 des calculs tandis que le temps de communication enregistre le temps
-des échanges de données ou d'instructions entre les
+des Ã©changes de donnÃ©es ou d'instructions entre les
 processeurs. Le temps de surcharge comprend le temps pris lors des
-initialisations telles que la création des threads au début du programme
-mais aussi le temps de fermeture de l'application à
-la fin. En général, le temps de surcharge est négligeable par rapport
+initialisations telles que la crÃ©ation des threads au dÃ©but du programme
+mais aussi le temps de fermeture de l'application Ã 
+la fin. En gÃ©nÃ©ral, le temps de surcharge est nÃ©gligeable par rapport
 aux temps de calcul et de communication.
 
-Des métriques liées directement à la performance du processeur sont
+Des mÃ©triques liÃ©es directement Ã  la performance du processeur sont
 bien connues telles que le MIPS (Millions d'instructions
 par seconde), FLOPS (Floating Point Operations per second), SPECint
-ou encore SPECfp qui sont des benchmarks pour évaluer la performance
-du processeur sur des opérations arithmétiques respectivement sur
-des entiers ou des nombres réels. Par ailleurs, plusieurs métriques
-rapportées à la performance de l'application parallèle
-ont été définies mais nous allons retenir les trois les plus utilisées,
-à savoir le « speedup », « l'efficacité » du code et
+ou encore SPECfp qui sont des benchmarks pour Ã©valuer la performance
+du processeur sur des opÃ©rations arithmÃ©tiques respectivement sur
+des entiers ou des nombres rÃ©els. Par ailleurs, plusieurs mÃ©triques
+rapportÃ©es Ã  la performance de l'application parallÃ¨le
+ont Ã©tÃ© dÃ©finies mais nous allons retenir les trois les plus utilisÃ©es,
+Ã  savoir le Â« speedup Â», Â« l'efficacitÃ© Â» du code et
 la loi d'Amdahl.
 
-Le speedup est le rapport entre le temps utilisé pour l'exécution
-séquentielle du code et le temps pour son exécution en parallèle.
-Ce rapport peut être obtenu aussi comme le ratio entre le temps d'exécution
-du code sur un processeur et le temps d'exécution avec
-n processeurs. Ainsi, il mesure le gain escompté en résolvant le problème
-en parallèle au lieu d'un lancement en séquentiel.
+Le speedup est le rapport entre le temps utilisÃ© pour l'exÃ©cution
+sÃ©quentielle du code et le temps pour son exÃ©cution en parallÃ¨le.
+Ce rapport peut Ãªtre obtenu aussi comme le ratio entre le temps d'exÃ©cution
+du code sur un processeur et le temps d'exÃ©cution avec
+n processeurs. Ainsi, il mesure le gain escomptÃ© en rÃ©solvant le problÃ¨me
+en parallÃ¨le au lieu d'un lancement en sÃ©quentiel.
 \begin{equation}
 \label{eq:6}
 S(n) = T_{Exec\_Seq} / T_{Exec\_Par}(n) 
 \end{equation}
-où : 
+oÃ¹ : 
 \indent\indent S(n) : speedup pour n processeurs \\
 \indent\indent n : nombre de processeurs \\
-\indent\indent $T_{Exec\_Seq}$ le temps d'exécution en mode séquentiel \\
-\indent\indent $T_{Exec\_Par}$ le temps d'exécution en en parallèle.
+\indent\indent $T_{Exec\_Seq}$ le temps d'exÃ©cution en mode sÃ©quentiel \\
+\indent\indent $T_{Exec\_Par}$ le temps d'exÃ©cution en en parallÃ¨le.
 
-L'efficacité E(n) représente la performance de chaque unité
+L'efficacitÃ© E(n) reprÃ©sente la performance de chaque unitÃ©
 de calcul. Elle s'obtient en divisant le speedup par
-le nombre de processeurs n. On peut aussi l'écrire
-comme le rapport entre le temps d'exécution séquentielle
-et le temps d'exécution parallèle multiplié par le
+le nombre de processeurs n. On peut aussi l'Ã©crire
+comme le rapport entre le temps d'exÃ©cution sÃ©quentielle
+et le temps d'exÃ©cution parallÃ¨le multipliÃ© par le
 nombre de processeurs n.
 \begin{equation}
 \label{eq:7}
@@ -432,8 +824,8 @@ E(n) = S(n) / n \\
 \end{equation}
 
 La loi de Amdahl donne une limite du speedup maximum qu'on
-peut obtenir avec un nombre de processeurs n donné. Elle stipule que
-si f compris entre 0 et 1 est la fraction du temps de la partie séquentielle
+peut obtenir avec un nombre de processeurs n donnÃ©. Elle stipule que
+si f compris entre 0 et 1 est la fraction du temps de la partie sÃ©quentielle
 du code, on a : 
 
 \begin{equation}
@@ -441,20 +833,20 @@ du code, on a :
 S(n) \leqslant \dfrac{1}{f+ \dfrac{1-f}{n}}	
 \end{equation}
 
-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é
-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 croissante de la taille du problème.
-
-Dans le cadre de nos travaux, nous avions introduit une métrique utilisée
-lors de la comparaison de différentes variantes d'algorithmes
-résolvant le même problème exécutés en différents mode de communication
-(synchrone ou asynchrone). Ainsi, le « gain relatif » entre l'exécution
-de deux variantes de code résolvant un problème donné est le ratio
-entre le temps d'exécution global du premier algorithme
-et le temps d'exécution global du deuxième algorithme
+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Ã©
+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 croissante de la taille du problÃ¨me.
+
+Dans le cadre de nos travaux, nous avions introduit une mÃ©trique utilisÃ©e
+lors de la comparaison de diffÃ©rentes variantes d'algorithmes
+rÃ©solvant le mÃªme problÃ¨me exÃ©cutÃ©s en diffÃ©rents mode de communication
+(synchrone ou asynchrone). Ainsi, le Â« gain relatif Â» entre l'exÃ©cution
+de deux variantes de code rÃ©solvant un problÃ¨me donnÃ© est le ratio
+entre le temps d'exÃ©cution global du premier algorithme
+et le temps d'exÃ©cution global du deuxiÃ¨me algorithme
 selon le mode retenu pour chaque code.
 
 \begin{equation}
@@ -462,26 +854,27 @@ selon le mode retenu pour chaque code.
 G_{relatif} = T_{Exec\_Algo\_1}  /  T_{Exec\_Algo\_2} \times {100}
 \end{equation}
 
-\subsection{Taux d'erreur lors de la prédiction}
-
-Lors de l'exercice de prédiction sur la performance
-d'une application parallèle, un modèle est construit
-à partir des observations passées  des
-variables considérées (données empiriques observées)afin de pouvoir prédire les résultats (données calculées) pour des nouvelles valeurs de ces variables. L'objectif
-lors de cette modélisation est de minimiser l'écart
-entre les valeurs calculées théoriques et les valeurs réelles observées. 
-
-Dans le cadre de la classe des algorithmes numériques itératifs consacrée
-à ces travaux, un autre taux d'erreur $\epsilon$ est déterminé
-d'avance et qui sert à détecter la convergence locale
-de l'algorithme {[}9{]}. A chaque itération, la différence
-entre la valeur approchée calculée, solution du problème, et celle obtenue
-à l'itération précédente est calculeé : si elle est
-inférieure au taux d'erreur accepté, l'algorithme
-s'arrête en ayant atteint la convergence sinon, on
-repart pour une nouvelle itération.
-
-A l'itération k, la convergence est atteinte quand
+
+\subsection{Taux d'erreur lors de la prÃ©diction}
+
+Lors de l'exercice de prÃ©diction sur la performance
+d'une application parallÃ¨le, un modÃ¨le est construit
+Ã  partir des observations passÃ©es  des
+variables considÃ©rÃ©es (donnÃ©es empiriques observÃ©es)afin de pouvoir prÃ©dire les rÃ©sultats (donnÃ©es calculÃ©es) pour des nouvelles valeurs de ces variables. L'objectif
+lors de cette modÃ©lisation est de minimiser l'Ã©cart
+entre les valeurs calculÃ©es thÃ©oriques et les valeurs rÃ©elles observÃ©es. 
+
+Dans le cadre de la classe des algorithmes numÃ©riques itÃ©ratifs consacrÃ©e
+Ã  ces travaux, un autre taux d'erreur $\epsilon$ est dÃ©terminÃ©
+d'avance et qui sert Ã  dÃ©tecter la convergence locale
+de l'algorithme {[}9{]}. A chaque itÃ©ration, la diffÃ©rence
+entre la valeur approchÃ©e calculÃ©e, solution du problÃ¨me, et celle obtenue
+Ã  l'itÃ©ration prÃ©cÃ©dente est calculeÃ© : si elle est
+infÃ©rieure au taux d'erreur acceptÃ©, l'algorithme
+s'arrÃªte en ayant atteint la convergence sinon, on
+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)	
@@ -489,548 +882,511 @@ A l'it
 
 \subsection{Weak contre strong scaling}
 
-Un des objectifs de nos travaux consistent à exécuter les algorithmes
-choisis en simulant leur exécution sur des plateformes de plus en
+Un des objectifs de nos travaux consistent Ã  exÃ©cuter les algorithmes
+choisis en simulant leur exÃ©cution sur des plateformes de plus en
 plus larges avec un nombre de processeurs et de cores de plus en plus
-grand. Deux modes existent pour cette montée en charge donnant des résultats différents
- : le « weak » et le « strong » scaling.
-
-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
+grand. Deux modes existent pour cette montÃ©e en charge donnant des rÃ©sultats diffÃ©rents
+ : le Â« weak Â» et le Â« strong Â» scaling.
+
+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 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,
-la taille du problème en entrée reste constante même si on adjoint
-une capacité plus grande aux unités de calcul.
-\begin{figure}[h]
-\centering
-\includegraphics[width=100mm,keepaspectratio]{"Weak vs Strong scaling"} 
-\caption{Weak vs Strong scaling: Temps d'exécution et Speedup}
-\label{fig:3}
-\end{figure}
+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,
+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}
 
-La figure Figure~\ref{fig:3} 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.
 
-\section*{2.2 Problématique sur la prédiction à large échelle de la performance des applications}
+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.
 
-La prédiction de la performance des applications parallèles à large
-échelle constitue ces dernières années une des préoccupations majeures
-des scientifiques et des utilisateurs des systèmes de calcul à haute
-performance. En effet, en considérant le coût de lancement nécessaire
-mais aussi le temps d'exécution imparti pour une telle
-application, il est toujours d'intérêt de disposer
-d'un outil ou d'un moyen afin de connaître
+\section{ProblÃ©matique sur la prÃ©diction Ã  large Ã©chelle de la performance des applications}
+
+La prÃ©diction de la performance des applications parallÃ¨les Ã  large
+Ã©chelle constitue ces derniÃ¨res annÃ©es une des prÃ©occupations majeures
+des scientifiques et des utilisateurs des systÃ¨mes de calcul Ã  haute
+performance. En effet, en considÃ©rant le coÃ»t de lancement nÃ©cessaire
+mais aussi le temps d'exÃ©cution imparti pour une telle
+application, il est toujours d'intÃ©rÃªt de disposer
+d'un outil ou d'un moyen afin de connaÃ®tre
 le comportement de l'application en montant en charge. Pour cela, il s'agit
-d'estimer le temps total d'exécution $T_{exec}$ dans ces conditions. De plus,
+d'estimer le temps total d'exÃ©cution $T_{exec}$ dans ces conditions. De plus,
 dans le cadre d'un calcul sur la grille,l'objectif est de 
-déterminer la configuration idéale, en termes de blocs et
+dÃ©terminer la configuration idÃ©ale, en termes de blocs et
 de nombre de noeuds (processeurs, coeurs) par bloc, pour obtenir le
-meilleur coût mais aussi le temps optimal d'exécution
+meilleur coÃ»t mais aussi le temps optimal d'exÃ©cution
 de l'application. 
 
-Dans ce chapitre, dans un premier temps, les problématiques et difficultés
-inhérentes à cet exercice de prédiction de la performance des applications
-parallèles sont abordées. Ensuite, nous allons passer en revue les
-solutions possibles apportées à ces problèmes.
+Dans ce chapitre, dans un premier temps, les problÃ©matiques et difficultÃ©s
+inhÃ©rentes Ã  cet exercice de prÃ©diction de la performance des applications
+parallÃ¨les sont abordÃ©es. Ensuite, nous allons passer en revue les
+solutions possibles apportÃ©es Ã  ces problÃ¨mes.
 
 De prime abord, on peut diviser en deux grands groupes, selon leurs
-objectifs, les travaux relatifs à la prédiction de la performance
-en environnement parallèle et de calcul à haute performance. 
+objectifs, les travaux relatifs Ã  la prÃ©diction de la performance
+en environnement parallÃ¨le et de calcul Ã  haute performance. 
 
-D'une part, la prédiction peut viser l'objectif
-de la conception, le développement et la mise au point de systèmes
-qui n'existent pas encore physiquement. Cette catégorie
+D'une part, la prÃ©diction peut viser l'objectif
+de la conception, le dÃ©veloppement et la mise au point de systÃ¨mes
+qui n'existent pas encore physiquement. Cette catÃ©gorie
 regroupe entre autres la conception de nouvelles architectures de
-matériels (CPU, Mémoire, Stockage) {[}\dots {]} mais aussi par exemple,
-la mise en oeuvre d'une nouvelle infrastructure de réseaux
-de communication {[}\dots {]}. Plusieurs utilisations peuvent être
-exploitées pour ce type de prédiction. En effet, outre le calibrage
-de systèmes pour une exécution optimale, il permet le débogage et
+matÃ©riels (CPU, MÃ©moire, Stockage) {[}\dots {]} mais aussi par exemple,
+la mise en oeuvre d'une nouvelle infrastructure de rÃ©seaux
+de communication {[}\dots {]}. Plusieurs utilisations peuvent Ãªtre
+exploitÃ©es pour ce type de prÃ©diction. En effet, outre le calibrage
+de systÃ¨mes pour une exÃ©cution optimale, il permet le dÃ©bogage et
 la mise au point des applications avec un ensemble de contraintes,
-que ce soit matérielles ou logicielles {[}..{]}. Notons tout de suite
-que cette dernière application sur le réseau a fait l'objet
-de nombreux travaux ces dernières années, permettant de déterminer
+que ce soit matÃ©rielles ou logicielles {[}..{]}. Notons tout de suite
+que cette derniÃ¨re application sur le rÃ©seau a fait l'objet
+de nombreux travaux ces derniÃ¨res annÃ©es, permettant de dÃ©terminer
 ou d'estimer d'avance la performance
-et l'efficacité de la solution future projetée et éventuellement
-de corriger et d'améliorer les imperfections. 
+et l'efficacitÃ© de la solution future projetÃ©e et Ã©ventuellement
+de corriger et d'amÃ©liorer les imperfections. 
 
-D'autre part, la prédiction de la performance d'une
-application parallèle se porte sur la détermination du temps d'exécution
-de la dite application en montant en charge sur une large échelle.
+D'autre part, la prÃ©diction de la performance d'une
+application parallÃ¨le se porte sur la dÃ©termination du temps d'exÃ©cution
+de la dite application en montant en charge sur une large Ã©chelle.
 Encore une fois, dans ce cas aussi, on ne dispose pas de l'environnement
-d'exécution cible mais on essaie de déterminer quel
-serait le temps total, donc le coût imputé au lancement de l'application
-sous diverses conditions. Ces dernières sont déterminées par plusieurs
-facteurs dont les principaux sont les paramètres d'entrée
-de l'application tels que la taille du problème à résoudre
-mais aussi les caractéristiques et la puissance globale intrinsèque
+d'exÃ©cution cible mais on essaie de dÃ©terminer quel
+serait le temps total, donc le coÃ»t imputÃ© au lancement de l'application
+sous diverses conditions. Ces derniÃ¨res sont dÃ©terminÃ©es par plusieurs
+facteurs dont les principaux sont les paramÃ¨tres d'entrÃ©e
+de l'application tels que la taille du problÃ¨me Ã  rÃ©soudre
+mais aussi les caractÃ©ristiques et la puissance globale intrinsÃ¨que
 de la grille de calcul de lancement : nombre de blocs, de processeurs
-/ coeurs, les paramètres de la capacité du réseau de communication
-inter et intra-noeuds de la grille, \dots{} Ainsi, une telle prédiction
-permet de conduire une analyse « what-if » du comportement de l'application
-si par exemple, on va multiplier par 10 ou 100 la taille du problème
-en entrée, mais aussi si on double la capacité de l'environnement
-cible en ajoutant d'autres blocs à la grille ou en
-apportant plus de processeurs dans chaque bloc. Les travaux rapportés
-dans cette thèse se focalisent plutôt sur cette seconde catégorie
-de prédiction de la performance d'applications spécifiquement
-écrites en MPI dans un environnement de grille de calcul.
-
-\subsection*{Facteurs liés à l'écosystème}
-
-La prédiction de la performance des applications parallèles approchant
-le plus possible de la réalité avec un taux d'erreur
-minimal dépend de plusieurs facteurs pouvant avoir des impacts
-décisifs sur les résultats. En effet, à titre d'exemple,
-la modification de la topologie ou des paramètres de l'infrastructure
-du réseau de communication tels que la latence ou la taille de la
-bande passante aura inévitablement des conséquences sur la performance
-globale de l'application parallèle. En donnant un autre
-exemple, il est clair que la montée en charge en augmentant la taille
-du problème avec une plus grande capacité de calcul proposant un plus
+/ coeurs, les paramÃ¨tres de la capacitÃ© du rÃ©seau de communication
+inter et intra-noeuds de la grille, \dots{} Ainsi, une telle prÃ©diction
+permet de conduire une analyse Â« what-if Â» du comportement de l'application
+si par exemple, on va multiplier par 10 ou 100 la taille du problÃ¨me
+en entrÃ©e, mais aussi si on double la capacitÃ© de l'environnement
+cible en ajoutant d'autres blocs Ã  la grille ou en
+apportant plus de processeurs dans chaque bloc. Les travaux rapportÃ©s
+dans cette thÃ¨se se focalisent plutÃ´t sur cette seconde catÃ©gorie
+de prÃ©diction de la performance d'applications spÃ©cifiquement
+Ã©crites en MPI dans un environnement de grille de calcul.
+
+\subsection{Facteurs liÃ©s Ã  l'Ã©cosystÃ¨me}
+
+La prÃ©diction de la performance des applications parallÃ¨les approchant
+le plus possible de la rÃ©alitÃ© avec un taux d'erreur
+minimal dÃ©pend de plusieurs facteurs pouvant avoir des impacts
+dÃ©cisifs sur les rÃ©sultats. En effet, Ã  titre d'exemple,
+la modification de la topologie ou des paramÃ¨tres de l'infrastructure
+du rÃ©seau de communication tels que la latence ou la taille de la
+bande passante aura inÃ©vitablement des consÃ©quences sur la performance
+globale de l'application parallÃ¨le. En donnant un autre
+exemple, il est clair que la montÃ©e en charge en augmentant la taille
+du problÃ¨me avec une plus grande capacitÃ© de calcul proposant un plus
 grand nombre de processeurs ou de coeurs modifiera la performance
-de l'application. Ainsi, de façon générale, plusieurs
-problématiques se posent quant au lancement d'une application
-parallèle dans une grille de calcul mais aussi, plusieurs facteurs
-influencent directement le comportement et la performance du système.
-Nombreux travaux ont déjà proposé des modèles de prédiction à large
-échelle sur la performance du code parallèle avec un taux d'efficacité
-plus ou moins acceptable. Certains de ces modèles seront détaillés
+de l'application. Ainsi, de faÃ§on gÃ©nÃ©rale, plusieurs
+problÃ©matiques se posent quant au lancement d'une application
+parallÃ¨le dans une grille de calcul mais aussi, plusieurs facteurs
+influencent directement le comportement et la performance du systÃ¨me.
+Nombreux travaux ont dÃ©jÃ  proposÃ© des modÃ¨les de prÃ©diction Ã  large
+Ã©chelle sur la performance du code parallÃ¨le avec un taux d'efficacitÃ©
+plus ou moins acceptable. Certains de ces modÃ¨les seront dÃ©taillÃ©s
 dans le paragraphe 2.4.
 
-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
-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
-peut être parfois accentuée par la non disponibilité de l'infrastructure
-cible parce que justement, les résultats obtenus par le lancement
-de l'application qui pourra déterminer les caractéristiques
+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
+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
+peut Ãªtre parfois accentuÃ©e par la non disponibilitÃ© de l'infrastructure
+cible parce que justement, les rÃ©sultats obtenus par le lancement
+de l'application qui pourra dÃ©terminer les caractÃ©ristiques
 techniques de l'environnement cible. Ainsi, cette contrainte
-majeure doit être levée durant tout le cycle de vie de développement
-de l'application. En effet, les coûteux développements
-et écritures du code de l'application, les opérations
-répétitives lors de sa mise au point ainsi que les tests itératifs
-de lancement requièrent un environnement réel disposant de la capacité
-nécessaire à ces opérations, ce qui n'est pas évident.
-Un autre facteur lié à cette problématique a toujours été aussi l'estimation
-à l'avance de cette capacité de calcul nécessaire afin
-d'avoir un environnement le plus adéquat afin d'éviter
-le gaspillage en cas de surestimation ou l'échec d'exécution
+majeure doit Ãªtre levÃ©e durant tout le cycle de vie de dÃ©veloppement
+de l'application. En effet, les coÃ»teux dÃ©veloppements
+et Ã©critures du code de l'application, les opÃ©rations
+rÃ©pÃ©titives lors de sa mise au point ainsi que les tests itÃ©ratifs
+de lancement requiÃ¨rent un environnement rÃ©el disposant de la capacitÃ©
+nÃ©cessaire Ã  ces opÃ©rations, ce qui n'est pas Ã©vident.
+Un autre facteur liÃ© Ã  cette problÃ©matique a toujours Ã©tÃ© aussi l'estimation
+Ã  l'avance de cette capacitÃ© de calcul nÃ©cessaire afin
+d'avoir un environnement le plus adÃ©quat afin d'Ã©viter
+le gaspillage en cas de surestimation ou l'Ã©chec d'exÃ©cution
 en cas de sous-estimation. Cette estimation concerne les ressources
-primaires requises telles que le processeur, la taille mémoire DRAM
-et cache ainsi que le sous-système de stockage pour la capacité de
-calcul d'une part mais aussi les paramètres du réseau
+primaires requises telles que le processeur, la taille mÃ©moire DRAM
+et cache ainsi que le sous-systÃ¨me de stockage pour la capacitÃ© de
+calcul d'une part mais aussi les paramÃ¨tres du rÃ©seau
 de communication (local ou distant) pour le temps de communication
-et d'échange de messages d'autre part.
-L'architecture inhérente à la grille de calcul composée
-d'entités reliées par des réseaux distants ajoute une
-autre considération pour la communication entre les processus parallèles
-sur le caractère hétérogène de l'infrastructure que
-ce soit la puissance de calcul des serveurs (différents types de processeurs)
-que le type des liaisons existants entre les blocs de la grille (réseaux
-hétérogènes). En effet, les environnements complexes de type grille
-de calcul actuels sont composés généralement de machines physiques
-dotées de processeurs multi-coeurs de différentes architectures (niveau
+et d'Ã©change de messages d'autre part.
+L'architecture inhÃ©rente Ã  la grille de calcul composÃ©e
+d'entitÃ©s reliÃ©es par des rÃ©seaux distants ajoute une
+autre considÃ©ration pour la communication entre les processus parallÃ¨les
+sur le caractÃ¨re hÃ©tÃ©rogÃ¨ne de l'infrastructure que
+ce soit la puissance de calcul des serveurs (diffÃ©rents types de processeurs)
+que le type des liaisons existants entre les blocs de la grille (rÃ©seaux
+hÃ©tÃ©rogÃ¨nes). En effet, les environnements complexes de type grille
+de calcul actuels sont composÃ©s gÃ©nÃ©ralement de machines physiques
+dotÃ©es de processeurs multi-coeurs de diffÃ©rentes architectures (niveau
 de cache, latence entre processeurs, \dots ). De plus, en analysant
-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
-le trafic entre les différents éléments d'un bloc et
-(3) enfin, les échanges « inter-blocs » définissant la communication
+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
+le trafic entre les diffÃ©rents Ã©lÃ©ments d'un bloc et
+(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
-hétérogènes. Ainsi, les deux premiers réseaux sont implémentés généralement
-dans un contexte de réseau local avec un temps de latence très court
-et une bande passante large. Tandis que le réseau de liaison entre
-les blocs de la grille peuvent être de type distant (lignes spécialisées
-distantes, canaux satellites de communication, réseau de type Internet,
-\dots ) donc d'une efficacité moindre en termes de
-latence et de bande passante mais aussi sujet à des perturbations
-diverses (Figure~\ref{fig:4}). Ces aspects liés à l'architecture
-de grille de calcul rendent la prédiction de la performance des applications
-parallèles plus difficiles. En effet, une surcharge élevée due à des
-perturbations sur le réseau inter-blocs de la grille peut fausser
-complètement les résultats de la prédiction du temps de communication
+termes d'efficacitÃ©, ces trois niveaux de communication
+peuvent prÃ©senter des caractÃ©ristiques complÃ¨tement diffÃ©rentes et
+hÃ©tÃ©rogÃ¨nes. Ainsi, les deux premiers rÃ©seaux sont implÃ©mentÃ©s gÃ©nÃ©ralement
+dans un contexte de rÃ©seau local avec un temps de latence trÃ¨s court
+et une bande passante large. Tandis que le rÃ©seau de liaison entre
+les blocs de la grille peuvent Ãªtre de type distant (lignes spÃ©cialisÃ©es
+distantes, canaux satellites de communication, rÃ©seau de type Internet,
+\dots ) donc d'une efficacitÃ© moindre en termes de
+latence et de bande passante mais aussi sujet Ã  des perturbations
+diverses (Figure \figref{cpumulti}). Ces aspects liÃ©s Ã  l'architecture
+de grille de calcul rendent la prÃ©diction de la performance des applications
+parallÃ¨les plus difficiles. En effet, une surcharge Ã©levÃ©e due Ã  des
+perturbations sur le rÃ©seau inter-blocs de la grille peut fausser
+complÃ¨tement les rÃ©sultats de la prÃ©diction du temps de communication
 global de l'application.
 
+
 \subsubsection{Facteur architecture des processeurs}
 
-Un autre facteur ayant un impact sur le temps d'exécution
-global est d'une part, le modèle d'architecture
+Un autre facteur ayant un impact sur le temps d'exÃ©cution
+global est d'une part, le modÃ¨le d'architecture
 des processeurs de calcul et d'autre part, la puissance
-intrinsèque de ces derniers.
-
-La course à la puissance nécessaire aux applications de calcul de
-haute performance ne cesse de s'accélérer de plus en
-plus vite exigeant une capacité de calcul de plus en plus grande.
-C. Willard {[}12{]} résume ce phénomène en disant que lorsqu'un
-problème - la conception d'un pont par exemple -
-est résolu, la solution trouvée n'est plus utile parce
-qu'on ne va pas refaire la conception. On passe généralement
-à un problème plus complexe - la conception d'un
-autre ouvrage plus complexe par exemple. La conséquence de cette course
-(actuellement du pentascale vers l'exascale) a suscité
-le développement des architectures de processeurs multi-coeurs dont
-l'accroissement de la puissance a dépassé la traditionnelle
-loi de Moore (renvoi). De plus, des co-processeurs spécialisés et
-autres accélérateurs (GPU : Graphic Processing Units {[}{]}) ont été
-adjoints aux processeurs multi-coeurs pour améliorer le temps de calcul.
+intrinsÃ¨que de ces derniers.
+
+La course Ã  la puissance nÃ©cessaire aux applications de calcul de
+haute performance ne cesse de s'accÃ©lÃ©rer de plus en
+plus vite exigeant une capacitÃ© de calcul de plus en plus grande.
+C. Willard {[}12{]} rÃ©sume ce phÃ©nomÃ¨ne en disant que lorsqu'un
+problÃ¨me - la conception d'un pont par exemple -
+est rÃ©solu, la solution trouvÃ©e n'est plus utile parce
+qu'on ne va pas refaire la conception. On passe gÃ©nÃ©ralement
+Ã  un problÃ¨me plus complexe - la conception d'un
+autre ouvrage plus complexe par exemple. La consÃ©quence de cette course
+(actuellement du pentascale vers l'exascale) a suscitÃ©
+le dÃ©veloppement des architectures de processeurs multi-coeurs dont
+l'accroissement de la puissance a dÃ©passÃ© la traditionnelle
+loi de Moore (renvoi). De plus, des co-processeurs spÃ©cialisÃ©s et
+autres accÃ©lÃ©rateurs (GPU : Graphic Processing Units {[}{]}) ont Ã©tÃ©
+adjoints aux processeurs multi-coeurs pour amÃ©liorer le temps de calcul.
 Une autre architecture variante du multi-coeurs est le MIC (Many Integrated
-Core) {[}Intel Xeon Phi{]}. Ce type d'unité de calcul
-joue au départ le rôle de co-processeur pour les applications à haute
-intensité de calcul. Ainsi, plusieurs c½urs ont été pressés au niveau
-du processeur (« socket ») emmenant un parallélisme au niveau de la
-puce. La Figure~\ref{fig:4} donne un aperçu de l'architecture
+Core) {[}Intel Xeon Phi{]}. Ce type d'unitÃ© de calcul
+joue au dÃ©part le rÃ´le de co-processeur pour les applications Ã  haute
+intensitÃ© de calcul. Ainsi, plusieurs coeurs ont Ã©tÃ© pressÃ©s au niveau
+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.
-\begin{figure}[h]
-\centering
-\includegraphics[width=100mm,keepaspectratio]{"Architecture des CPU multi-coeurs"} 
-\caption{Architecture des CPU multicoeurs}
-\label{fig:4}
-\end{figure}
+
+\mfigure[h]{width=8cm, height=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
-des c½urs aux données en mémoire. En effet, elle est dotée d'un
-bus rapide et une hiérarchie de cache mémoire beaucoup plus rapide
-d'accès que la RAM. En termes d'architecture,
-la classification de Flynn (1972) {[}{]} a créé quatre catégories
-de machines parallèles selon les flots de données et les flots d'instructions: SISD (Single instruction, single data), SIMD (Single instruction,
+telle entitÃ© de calcul repose sur la vitesse d'accÃ¨s
+des coeurs aux donnÃ©es en mÃ©moire. En effet, elle est dotÃ©e d'un
+bus rapide et une hiÃ©rarchie de cache mÃ©moire beaucoup plus rapide
+d'accÃ¨s que la RAM. En termes d'architecture,
+la classification de Flynn (1972) {[}{]} a crÃ©Ã© quatre catÃ©gories
+de machines parallÃ¨les selon les flots de donnÃ©es et les flots d'instructions: SISD (Single instruction, single data), SIMD (Single instruction,
 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 : 
-
-\begin{figure}[h]
-\begin{subfigure}{0.5\textwidth}
-\includegraphics[width=5cm, height=5cm, scale=3]{"MIMD Distributed Memory"} 
-\caption{Modèle MIMD Distribué}
-\label{fig:5.a}
-\end{subfigure}
-\begin{subfigure}{0.5\textwidth}
-\includegraphics[width=5cm, height=5cm, scale=3]{"MIMD Shared memory - SMP"}
-\caption{Modèle MIMD partagé}
-\label{fig:5.b}
-\end{subfigure}
-\begin{subfigure}{0.5\textwidth}
-\includegraphics[width=5cm, height=5cm, scale=3]{"MIMD Hybride"}
-\caption{Modèle MIMD hybride}
-\label{fig:5.c}
-\end{subfigure}
-\caption{Modèles de mémoire MIMD}
-%\label{fig:1}
-\end{figure}
+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, height=8cm}{"MIMD Shared memory - SMP"} {ModÃ¨le MIMD partagÃ©} {MIMDSM}
+
+\mfigure[h]{width=8cm, height=8cm}{"MIMD Hybride"} {ModÃ¨le MIMD hybride} {MIMDHY}
 
 \begin{itemize}
 
-\item [$\bullet$] - Machine MIMD à mémoire partagée (Figure~\ref{fig:5.b}) : Les unités de calcul
-accède à 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,
+\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
+(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.
 
-\item [$\bullet$] Machine MIMD à mémoire distribuée (Figure~\ref{fig:5.a}) : Chaque unité de
-calcul est doté de son espace mémoire propre. Un réseau d'interconnexion
-intègre l'ensemble assurant la communication entre
-ces unités. Il existe trois types de machines MIMD à mémoire distribuée: les hypercubes, les fat trees et les autres.
+\item [$\bullet$] Machine MIMD Ã  mÃ©moire distribuÃ©e (Figure \figref{MIMDDM}) : Chaque unitÃ© de
+calcul est dotÃ© de son espace mÃ©moire propre. Un rÃ©seau d'interconnexion
+intÃ¨gre l'ensemble assurant la communication entre
+ces unitÃ©s. Il existe trois types de machines MIMD Ã  mÃ©moire distribuÃ©e: les hypercubes, les fat trees et les autres.
 
-\item [$\bullet$] Machine MIMD hybride (Figure~\ref{fig:5.c}) : Dans ce cas, le système est la
-combinaison des deux modèles précédents : un ensemble de processeurs
-partage un espace mémoire et ces groupes sont interconnectés par un
-réseau.
+\item [$\bullet$] Machine MIMD hybride (Figure \figref{MIMDHY}) : Dans ce cas, le systÃ¨me est la
+combinaison des deux modÃ¨les prÃ©cÃ©dents : un ensemble de processeurs
+partage un espace mÃ©moire et ces groupes sont interconnectÃ©s par un
+rÃ©seau.
 
 \end{itemize}
 
-A titre d'exemple de machines parallèles, le site Top500.org
-{[}14{]} classe suivant différents critères les plus performantes.
-Ainsi, la fig. .. 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
-n½ud) 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
+A titre d'exemple de machines parallÃ¨les, le site Top500.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
+thÃ©orique proche de 50 PetaFlops (33 Linpack PetaFlops (renvoi)) avec
+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
-Center à Guangzhou en Chine {[}15{]}. A la tendance actuelle, l'atteinte
+Center Ã  Guangzhou en Chine {[}15{]}. A la tendance actuelle, l'atteinte
 de l'exaflops n'est pas loin.
 
-\begin{figure}[h]
-\centering
-\includegraphics[width=100mm,keepaspectratio]{"Evolution de la puissance de calcul mondiale"} 
-\caption{Evolution de la puissance de calcul mondiale}
-\label{fig:6}
-\end{figure}
+\mfigure[h]{width=8cm, height=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
-Xeon Phi cité plus haut, les processeurs basés sur les circuits intégrés
-FPGA (Field Programmable Gate Array) montrent une flexibilité efficace
+Pour arriver Ã  de telles puissances, diverses architectures de processeurs
+ont vu le jour ces derniÃ¨res annÃ©es. Outre l'Intel
+Xeon Phi citÃ© plus haut, les processeurs basÃ©s sur les circuits intÃ©grÃ©s
+FPGA (Field Programmable Gate Array) montrent une flexibilitÃ© efficace
 pour s'adapter par configuration au type d'applications
-à traiter {[}14{]}. En effet, cette architecture permet la programmation
-de la « matrice de blocs logiques » interconnectée par des liaisons
-toutes aussi programmables. Cette possibilité de programmation des
-circuits et des interconnexions entraine aussi la réduction de la
-consommation d'énergie. Par ailleurs, les unités GPU
+Ã  traiter {[}14{]}. En effet, cette architecture permet la programmation
+de la Â« matrice de blocs logiques Â» interconnectÃ©e par des liaisons
+toutes aussi programmables. Cette possibilitÃ© de programmation des
+circuits et des interconnexions entraine aussi la rÃ©duction de la
+consommation d'Ã©nergie. Par ailleurs, les unitÃ©s GPU
 (Graphics Processing Unit) sont initialement des co-processeurs produits
-par AMD et NVIDIA pour des applications à fort rendu graphique, libérant
-ainsi la charge au processeur. Par la suite, elles ont été complètement
-programmables et se sont montrées très efficaces pour les algorithmes
+par AMD et NVIDIA pour des applications Ã  fort rendu graphique, libÃ©rant
+ainsi la charge au processeur. Par la suite, elles ont Ã©tÃ© complÃ¨tement
+programmables et se sont montrÃ©es trÃ¨s efficaces pour les algorithmes
 vectoriels. 
 
-\subsubsection{Facteur : Mémoire et stockage}
 
-Les différentes architectures de processeurs parallèles vues plus
-haut se trouvent toutes confrontées au problème de chargement de données
-à traiter en mémoire. Ainsi, elles se sont dotées de contrôleurs de
-mémoire incorporés mais aussi divers niveaux de caches pour faire
-face à cette différence de vitesse de traitement entre les processeurs
-et les mémoires dynamiques. Par exemple, les machines SIMD utilisent
+\subsubsection{Facteur : MÃ©moire et stockage}
+
+Les diffÃ©rentes architectures de processeurs parallÃ¨les vues plus
+haut se trouvent toutes confrontÃ©es au problÃ¨me de chargement de donnÃ©es
+Ã  traiter en mÃ©moire. Ainsi, elles se sont dotÃ©es de contrÃ´leurs de
+mÃ©moire incorporÃ©s mais aussi divers niveaux de caches pour faire
+face Ã  cette diffÃ©rence de vitesse de traitement entre les processeurs
+et les mÃ©moires dynamiques. Par exemple, les machines SIMD utilisent
 des registres de communication internes pour communiquer avec les
-autres CPUs. Pour les machines de type MIMD où différentes tâches
-sont exécutées par chaque processeur à un instant donné entraînant
-ainsi une synchronisation obligatoire pour des échanges de données
-entre processeurs, ces derniers peuvent exploiter la mémoire partagée
-pour effectuer ces transferts ou prévoir des bus dédiés à cette fin
+autres CPUs. Pour les machines de type MIMD oÃ¹ diffÃ©rentes tÃ¢ches
+sont exÃ©cutÃ©es par chaque processeur Ã  un instant donnÃ© entraÃ®nant
+ainsi une synchronisation obligatoire pour des Ã©changes de donnÃ©es
+entre processeurs, ces derniers peuvent exploiter la mÃ©moire partagÃ©e
+pour effectuer ces transferts ou prÃ©voir des bus dÃ©diÃ©s Ã  cette fin
 {[}16{]}. 
 
-Par ailleurs, les mémoires, non intégrées au processeur, et les sous-systèmes
+Par ailleurs, les mÃ©moires, non intÃ©grÃ©es au processeur, et les sous-systÃ¨mes
 de stockage constituent aussi un facteur important ayant un impact
-sur le temps d'exécution de l'application
-parallèle. En effet, les mémoires externes sont utilisées soit pour
-échanger des données entre les CPU, soit pour accéder à la zone mémoire
-pour lire, écrire ou mettre à jour des données. Dans ce domaine, en
-considérant les architectures parallèles MIMD, on peut classer en
-deux grandes catégories selon les modèles de mémoire {[}17{]}: (1)
-les multiprocesseurs et (2) les multicomputers (Fig \dots ). La première
-catégorie regroupe les machines à mémoire partagée (« shared memory
-») qui se subdivisent en trois classes selon le mode d'accès
-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~\ref{fig:6.b})). 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~\ref{fig:6.a})). 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~\ref{fig:6.c})). 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.
-
-\begin{figure}[h]
-\begin{subfigure}{0.5\textwidth}
-\includegraphics[width=5cm, height=5cm, scale=3]{"UMA architecture"} 
-\caption{Architecture UMA}
-\label{fig:6.a}
-\end{subfigure}
-\begin{subfigure}{0.5\textwidth}
-\includegraphics[width=5cm, height=5cm, scale=3]{"NUMA architecture"}
-\caption{Architecture NUMA}
-\label{fig:6.b}
-\end{subfigure}
-\begin{subfigure}{0.5\textwidth}
-\includegraphics[width=5cm, height=5cm, scale=3]{"COMA architecture"}
-\caption{Architecture COMA}
-\label{fig:6.c}
-\end{subfigure}
-\caption{Modèles de mémoire MIMD}
-%\label{fig:1}
-\end{figure}
-
-Malgré que dans le cadre de nos travaux, nous n'avions
-pas eu une contrainte particulière en termes de système de stockage,
-une brève revue des problématiques liées à ce sous-système en environnement
-de calcul parallèle est présentée parce qu'il peut
-influencer à large echelle sur la prédiction de la performance de
-l'application. Les systèmes traditionnels ont opté
+sur le temps d'exÃ©cution de l'application
+parallÃ¨le. En effet, les mÃ©moires externes sont utilisÃ©es soit pour
+Ã©changer des donnÃ©es entre les CPU, soit pour accÃ©der Ã  la zone mÃ©moire
+pour lire, Ã©crire ou mettre Ã  jour des donnÃ©es. Dans ce domaine, en
+considÃ©rant les architectures parallÃ¨les MIMD, on peut classer en
+deux grandes catÃ©gories selon les modÃ¨les de mÃ©moire {[}17{]}: (1)
+les multiprocesseurs et (2) les multicomputers (Fig \dots ). La premiÃ¨re
+catÃ©gorie regroupe les machines Ã  mÃ©moire partagÃ©e (Â« shared memory
+Â») qui se subdivisent en trois classes selon le mode d'accÃ¨s
+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
+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
+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
+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, height=8cm}{"NUMA architecture"} {MÃ©moire MIMD: Architecture NUMA} {NUMA}
+
+\mfigure[h]{width=8cm, height=8cm}{"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,
+une brÃ¨ve revue des problÃ©matiques liÃ©es Ã  ce sous-systÃ¨me en environnement
+de calcul parallÃ¨le est prÃ©sentÃ©e parce qu'il peut
+influencer Ã  large echelle sur la prÃ©diction de la performance de
+l'application. Les systÃ¨mes traditionnels ont optÃ©
 pour des architectures NFS (Network File System) ou de type NAS (Network
 Attached Storage) ou encore de type SAN (Storage Access Network).
-Malgré que les systèmes de stockage NFS et NAS sont relativement faciles
-à mettre en oeuvre, l'inconvénient majeur est qu'ils
-présentent un point de défaillance unique (SPOF) et ont des difficultés
-de monter en échelle. Pour le système SAN, les données sont stockées
-dans des baies de stockage accessibles par les unités de calcul à
-travers un réseau basé sur des canaux de fibres et des adapteurs de
-haut débit (HBA) ; ce qui rend le coût de l'implémentation rapidement
-excessif dès que le nombre de noeuds augmente. Dans un environnement
-d'applications parallèles, le réseau de communication
-doit avoir une très haute performance pour répondre aux besoins d'échange
-mais aussi d'accès aux données. En plus, il doit
-avoir la flexibilité et la capacité de monter en échelle suivant la
-demande du système. Ces caractéristiques requis sont accentués par
-la variabilité des besoins en entrées/sorties des applications HPC: dans le même lot d'applications exécutées, certaines
-accèdent à des données de manière séquentielle tandis que d'autres
-demandent des entrées/sorties aléatoires fortement sensibles. Les
-solutions apportées dénommées « système de fichiers parallèle » reposent
-sur la conception d'une architecture répondant à ces
-prérequis. Dans ce type de système de fichiers, les blocs de données
-sont répartis par morceaux dans différents serveurs et dans différentes
-locations du système de stockage. On peut ainsi accroitre le débit
-de stockage et d'extraction au fur et à mesure que
-le nombre de serveurs ou de baies de stockage augmentent.L'architecture sera réalisée par:
+MalgrÃ© que les systÃ¨mes de stockage NFS et NAS sont relativement faciles
+Ã  mettre en oeuvre, l'inconvÃ©nient majeur est qu'ils
+prÃ©sentent un point de dÃ©faillance unique (SPOF) et ont des difficultÃ©s
+de monter en Ã©chelle. Pour le systÃ¨me SAN, les donnÃ©es sont stockÃ©es
+dans des baies de stockage accessibles par les unitÃ©s de calcul Ã 
+travers un rÃ©seau basÃ© sur des canaux de fibres et des adapteurs de
+haut dÃ©bit (HBA) ; ce qui rend le coÃ»t de l'implÃ©mentation rapidement
+excessif dÃ¨s que le nombre de noeuds augmente. Dans un environnement
+d'applications parallÃ¨les, le rÃ©seau de communication
+doit avoir une trÃ¨s haute performance pour rÃ©pondre aux besoins d'Ã©change
+mais aussi d'accÃ¨s aux donnÃ©es. En plus, il doit
+avoir la flexibilitÃ© et la capacitÃ© de monter en Ã©chelle suivant la
+demande du systÃ¨me. Ces caractÃ©ristiques requis sont accentuÃ©s par
+la variabilitÃ© des besoins en entrÃ©es/sorties des applications HPC: dans le mÃªme lot d'applications exÃ©cutÃ©es, certaines
+accÃ¨dent Ã  des donnÃ©es de maniÃ¨re sÃ©quentielle tandis que d'autres
+demandent des entrÃ©es/sorties alÃ©atoires fortement sensibles. Les
+solutions apportÃ©es dÃ©nommÃ©es Â« systÃ¨me de fichiers parallÃ¨le Â» reposent
+sur la conception d'une architecture rÃ©pondant Ã  ces
+prÃ©requis. Dans ce type de systÃ¨me de fichiers, les blocs de donnÃ©es
+sont rÃ©partis par morceaux dans diffÃ©rents serveurs et dans diffÃ©rentes
+locations du systÃ¨me de stockage. On peut ainsi accroitre le dÃ©bit
+de stockage et d'extraction au fur et Ã  mesure que
+le nombre de serveurs ou de baies de stockage augmentent.L'architecture sera rÃ©alisÃ©e par:
 
 \begin{itemize}
-\item [$\bullet$] l'introduction d'une couche de « noeuds
-de services de fichiers » entre les noeuds de calcul et les baies de
-stockage des données. Ces noeuds sont reliés en clusters via un réseau
+\item [$\bullet$] l'introduction d'une couche de Â« noeuds
+de services de fichiers Â» entre les noeuds de calcul et les baies de
+stockage des donnÃ©es. Ces noeuds sont reliÃ©s en clusters via un rÃ©seau
 rapide de type Infiniband.
 
-\item [$\bullet$] L'ajout des «serveurs de metadata » (MDS : MetaData
-Server) qui gèrent les métadonnées accessibles à partir des « baies
-de stockage des métadonnées » (MDA) avant d'extraire
-les données proprement dites sur les baies de stockage en arrière-plan.
+\item [$\bullet$] L'ajout des Â«serveurs de metadata Â» (MDS : MetaData
+Server) qui gÃ¨rent les mÃ©tadonnÃ©es accessibles Ã  partir des Â« baies
+de stockage des mÃ©tadonnÃ©es Â» (MDA) avant d'extraire
+les donnÃ©es proprement dites sur les baies de stockage en arriÃ¨re-plan.
 \end{itemize}
 
-Les métriques utilisées pour caractériser une telle architecture sont
-le nombre nominal d'entrées/sorties par seconde (IOPS)
-d'une part et le débit de la bande passante du réseau
-reliant les différents composants (Gb/s) d'autre part.
-Plusieurs solutions globalement efficaces ont été avancées respectant
-cette architecture. On peut citer les « systèmes de fichiers ouverts
-» tels que pNFS (Parallel NFS), GFS, XFS, PVFS (Clemson University),
-MogileFS {[}\dots {]} mais Lustre {[}\dots {]} présenté dans la figure
-\dots{} est largement utilisé en environnement de calcul parallèle
-: au moins, la moitié des clusters « top 10 » utilise ce modèle et
-plusieurs laboratoires l'ont aussi adopté (Pacific
+Les mÃ©triques utilisÃ©es pour caractÃ©riser une telle architecture sont
+le nombre nominal d'entrÃ©es/sorties par seconde (IOPS)
+d'une part et le dÃ©bit de la bande passante du rÃ©seau
+reliant les diffÃ©rents composants (Gb/s) d'autre part.
+Plusieurs solutions globalement efficaces ont Ã©tÃ© avancÃ©es respectant
+cette architecture. On peut citer les Â« systÃ¨mes de fichiers ouverts
+Â» tels que pNFS (Parallel NFS), GFS, XFS, PVFS (Clemson University),
+MogileFS {[}\dots {]} mais Lustre {[}\dots {]} prÃ©sentÃ© dans la figure
+\dots{} est largement utilisÃ© en environnement de calcul parallÃ¨le
+: au moins, la moitiÃ© des clusters Â« top 10 Â» utilise ce modÃ¨le et
+plusieurs laboratoires l'ont aussi adoptÃ© (Pacific
 Northwest National Lab (PNNL), Lawrence Livermore National Lab (LLNL)
 mais aussi Los Alamos National Lab (LANL). Lustre utilise les OST
-(«Object Storage Targets ») dans les serveurs de fichiers (en opposition
-au « Block Storage Device ») pour assurer la cohérence et la résilience
-du système de fichiers. A titre indicatif, le cluster de PNNL {[}19{]}
-avec 1800 processeurs Itanium délivrant jusqu'à 11
-TFlops utilise Lustre avec une capacité de stockage de 53 Toctets
-avec une bande passante de 3.2 Gbits/s. Chaque n½ud du cluster peut
-accéder au serveur parallèle Lustre avec un débit de 650 Mb/s.
-
-La mise en ½uvre des systèmes de fichiers parallèles pour les calculs
-à haute performance s'approche des technologies utilisées
-en entreprise pour exploiter les applications à données intensives
-traitant de très grandes masses de données. En effet, les « sciences
-de données », « big data », « analytics » (business intelligence,
-Datamart, Data Mining) demandent des accès très rapides à des grands
-volumes de données variées, structurées ou non structurées, pour en
-extraire une information utile. Pour cela, le principe « d'apporter
-le calcul auprès des données » (« Bring the compute to the data »)
-est appliqué en lieu et place du traditionnel « extraire et charger
-en mémoire les données du système de stockage pour traitement par
-l'unité de calcul ». Hadoop {[}\dots {]}, une plateforme
-de traitement de « big data » la plus utilisée, combine dans la même
-machine physique les « n½uds de calcul » et les « n½uds de données
-». Cet ensemble d'outils ayant une architecture fortement
-distribuée utilise le mécanisme de transfert des données du système
-de stockage « globalement partagé et persistent » ayant une large
-capacité vers le système de fichier local avant traitement.
-
-\subsubsection{Facteur : Réseaux de communication}
-
-Dans un contexte d'exécution parallèle et distribuée
+(Â«Object Storage Targets Â») dans les serveurs de fichiers (en opposition
+au Â« Block Storage Device Â») pour assurer la cohÃ©rence et la rÃ©silience
+du systÃ¨me de fichiers. A titre indicatif, le cluster de PNNL {[}19{]}
+avec 1800 processeurs Itanium dÃ©livrant jusqu'Ã  11
+TFlops utilise Lustre avec une capacitÃ© de stockage de 53 Toctets
+avec une bande passante de 3.2 Gbits/s. Chaque noeud du cluster peut
+accÃ©der au serveur parallÃ¨le Lustre avec un dÃ©bit de 650 Mb/s.
+
+La mise en oeuvre des systÃ¨mes de fichiers parallÃ¨les pour les calculs
+Ã  haute performance s'approche des technologies utilisÃ©es
+en entreprise pour exploiter les applications Ã  donnÃ©es intensives
+traitant de trÃ¨s grandes masses de donnÃ©es. En effet, les Â« sciences
+de donnÃ©es Â», Â« big data Â», Â« analytics Â» (business intelligence,
+Datamart, Data Mining) demandent des accÃ¨s trÃ¨s rapides Ã  des grands
+volumes de donnÃ©es variÃ©es, structurÃ©es ou non structurÃ©es, pour en
+extraire une information utile. Pour cela, le principe Â« d'apporter
+le calcul auprÃ¨s des donnÃ©es Â» (Â« Bring the compute to the data Â»)
+est appliquÃ© en lieu et place du traditionnel Â« extraire et charger
+en mÃ©moire les donnÃ©es du systÃ¨me de stockage pour traitement par
+l'unitÃ© de calcul Â». Hadoop {[}\dots {]}, une plateforme
+de traitement de Â« big data Â» la plus utilisÃ©e, combine dans la mÃªme
+machine physique les Â« noeuds de calcul Â» et les Â« noeuds de donnÃ©es
+Â». Cet ensemble d'outils ayant une architecture fortement
+distribuÃ©e utilise le mÃ©canisme de transfert des donnÃ©es du systÃ¨me
+de stockage Â« globalement partagÃ© et persistent Â» ayant une large
+capacitÃ© vers le systÃ¨me de fichier local avant traitement.
+
+
+\subsubsection{Facteur : RÃ©seaux de communication}
+
+Dans un contexte d'exÃ©cution parallÃ¨le et distribuÃ©e
 des applications, la communication entre les processus de calcul pour
-échange de données ou d'instructions est critique et
-peut constituer un goulot d'étranglement pour le temps
-d'exécution et la montée en charge de l'applicaiton.
-En effet, la performance globale quantifiée par le temps d'exécution
-de l'application dépend fortement de la nature et de
-la typologie des réseaux de communication. Il a été mis en exergue
-dans les paragraphes précédents l'importance du trafic
-de données entre chaque unité de calcul et les différentes couches
-de mémoire vive utilisées par le système. Dans un environnement de
+Ã©change de donnÃ©es ou d'instructions est critique et
+peut constituer un goulot d'Ã©tranglement pour le temps
+d'exÃ©cution et la montÃ©e en charge de l'applicaiton.
+En effet, la performance globale quantifiÃ©e par le temps d'exÃ©cution
+de l'application dÃ©pend fortement de la nature et de
+la typologie des rÃ©seaux de communication. Il a Ã©tÃ© mis en exergue
+dans les paragraphes prÃ©cÃ©dents l'importance du trafic
+de donnÃ©es entre chaque unitÃ© de calcul et les diffÃ©rentes couches
+de mÃ©moire vive utilisÃ©es par le systÃ¨me. Dans un environnement de
 grilles de calcul, de clusters ou de P2P, d'autres
-types de réseaux de communication influencent cette performance. 
+types de rÃ©seaux de communication influencent cette performance. 
 
-%Ethernet, Infiniband (56 à 100 Gb/s), Omni-path {[}15{]}
+%Ethernet, Infiniband (56 Ã  100 Gb/s), Omni-path {[}15{]}
 
-%Facteurs influençant le temps de communication : Type de comm (point
+%Facteurs influenÃ§ant le temps de communication : Type de comm (point
 %to point, collective comme broadcast, scatter, gather, reduce)
 
-\subsection{Facteurs liés au code de l'application} 
+\subsection{Facteurs liÃ©s au code de l'application} 
 
-Outre ces problématiques liées directement à l'environnement
-de lancement, plusieurs autres facteurs liés au code de l'application
-lors de son exécution peuvent influencer le comportement du système
-rendant aussi la prédiction de la performance complexe et difficile.
-Ces facteurs liés au comportement du code lors de son exécution en
-parallèle vont influencer la performance globale en impactant le temps
-de calcul et le temps de communication des données entre les unités
+Outre ces problÃ©matiques liÃ©es directement Ã  l'environnement
+de lancement, plusieurs autres facteurs liÃ©s au code de l'application
+lors de son exÃ©cution peuvent influencer le comportement du systÃ¨me
+rendant aussi la prÃ©diction de la performance complexe et difficile.
+Ces facteurs liÃ©s au comportement du code lors de son exÃ©cution en
+parallÃ¨le vont influencer la performance globale en impactant le temps
+de calcul et le temps de communication des donnÃ©es entre les unitÃ©s
 de calcul.
 
-\subsubsection{Facteur : Taille du problème}
+\subsubsection{Facteur : Taille du problÃ¨me}
 
-Parmi les facteurs impactant le temps de calcul, la taille du problème
+Parmi les facteurs impactant le temps de calcul, la taille du problÃ¨me
 peut avoir une grande influence sur le temps de calcul surtout en
-strong scaling. En effet, dans ce mode de scalabilité, la
-taille du problème étant fixe alors qu'on augmente
+strong scaling. En effet, dans ce mode de scalabilitÃ©, la
+taille du problÃ¨me Ã©tant fixe alors qu'on augmente
 la puissance de calcul par l'ajout de processeurs et
-coeurs supplémentaires, le temps de calcul va varier en fonction de
-ces changements. En mode weak scaling où la taille du problème
-augmente dans la même proportion que l'accroissement
+coeurs supplÃ©mentaires, le temps de calcul va varier en fonction de
+ces changements. En mode weak scaling oÃ¹ la taille du problÃ¨me
+augmente dans la mÃªme proportion que l'accroissement
 du nombre de processeurs / coeurs, le temps de calcul global attendu
-reste théoriquement plus ou moins constant. La taille du problème
+reste thÃ©oriquement plus ou moins constant. La taille du problÃ¨me
 qui ne cesse d'augmenter pour le besoin des applications
-parallèles constitue un élément impactant le temps total d'exécution
+parallÃ¨les constitue un Ã©lÃ©ment impactant le temps total d'exÃ©cution
 du code.
 
-\subsubsection{Performance de la parallélisation} 
+\subsubsection{Performance de la parallÃ©lisation} 
 
-Dans cette section, la notion de "performance de la parallélisation" est intrduite pour caractériser la performance d'un code une fois executé en mode parallèle. C. Rosas et Al. {[}\dots {]}
-définit cette mesure ($\eta$Parallel) comme étant le produit des trois facteurs fondamentaux "normalisés" suivants dont chaque facteur est quantifié par une valeur entre 0 et 1 : 
+Dans cette section, la notion de "performance de la parallÃ©lisation" est intrduite pour caractÃ©riser la performance d'un code une fois executÃ© en mode parallÃ¨le. C. Rosas et Al. {[}\dots {]}
+dÃ©finit cette mesure ($\eta$Parallel) comme Ã©tant le produit des trois facteurs fondamentaux "normalisÃ©s" suivants dont chaque facteur est quantifiÃ© par une valeur entre 0 et 1 : 
 
 \begin{equation}
 \label{eq:10}
   \eta Parallel =LB \times Ser \times Trf	
 \end{equation}
-Où :
+OÃ¹ :
 
 \begin{itemize}
-\item [$\bullet$] L'efficacité de la « répartition des charges » LB ("Load Balancing") est définie comme étant « la perte d'efficacité potentielle» sur le temps de calcul de chaque processus. Elle est mesurée comme
-étant le rapport entre le temps de calcul moyen par processeur et
-le temps de calcul maximum enregistré sur l'ensemble
+\item [$\bullet$] L'efficacitÃ© de la Â« rÃ©partition des charges Â» LB ("Load Balancing") est dÃ©finie comme Ã©tant Â« la perte d'efficacitÃ© potentielleÂ» sur le temps de calcul de chaque processus. Elle est mesurÃ©e comme
+Ã©tant le rapport entre le temps de calcul moyen par processeur et
+le temps de calcul maximum enregistrÃ© sur l'ensemble
 des processeurs participants: 
 
 \begin{equation}
 \label{eq:11}
 LB = {[}  \sum \limits_{k=1}^p  eff_k)  /  p  {]} / max(eff_k) 
 \end{equation}
-où : p est le nombre de processeurs et $eff_k$ ("Efficiency") le temps de calcul utilisé par le processeur k.
+oÃ¹ : p est le nombre de processeurs et $eff_k$ ("Efficiency") le temps de calcul utilisÃ© par le processeur k.
 
-\item [$\bullet$] L'efficacité de la « sérialisation » : Elle représente
-l'inefficacité causée par les « dépendances dans le
-code » qui se traduit par la nécessité d'échanger des
-données entre les processeurs. Ces dernières peuvent impacter de façon
-importante la performance du code parallèle. Ce facteur est mesuré comme étant 
-le temps maximum enregistré pour tous les processeurs présents lors de l'exécution
-du code en faisant abstraction du temps des échanges: on considère comme si on est en présence d'une architecture à « communication instantanée » c'est-à-dire un réseau avec une bande
-passante infinie et une latence égale à 0. Dans ce cas, ideal ($eff_i$) est l'efficacité du processeurs i sans le temps de communication.
+\item [$\bullet$] L'efficacitÃ© de la Â« sÃ©rialisation Â» : Elle reprÃ©sente
+l'inefficacitÃ© causÃ©e par les Â« dÃ©pendances dans le
+code Â» qui se traduit par la nÃ©cessitÃ© d'Ã©changer des
+donnÃ©es entre les processeurs. Ces derniÃ¨res peuvent impacter de faÃ§on
+importante la performance du code parallÃ¨le. Ce facteur est mesurÃ© comme Ã©tant 
+le temps maximum enregistrÃ© pour tous les processeurs prÃ©sents lors de l'exÃ©cution
+du code en faisant abstraction du temps des Ã©changes: on considÃ¨re comme si on est en prÃ©sence d'une architecture Ã  Â« communication instantanÃ©e Â» c'est-Ã -dire un rÃ©seau avec une bande
+passante infinie et une latence Ã©gale Ã  0. Dans ce cas, ideal ($eff_i$) est l'efficacitÃ© du processeurs i sans le temps de communication.
 
 \begin{equation}
 \label{eq:12}
 Ser = max ( ideal( eff_i ) )
 \end{equation}
 
-\item [$\bullet$] L'efficacité du « transfert » de données : La montée
-en charge de la taille du problème impactera la taille des données
-à échanger entre les processus. Ce facteur est défini comme étant
-la perte de performance globale due aux transferts des données. En
-prenant en compte le temps de communication, il est mesuré comme le
-ratio entre le maximum entre les temps relatifs d'exécution
-des processus concurrents (rapport entre le temps d'exécution $T_i$ 
-d'un processus et le temps total réel d'exécution T
-du code) et l'efficacité de la sérialisation Ser : 
+\item [$\bullet$] L'efficacitÃ© du Â« transfert Â» de donnÃ©es : La montÃ©e
+en charge de la taille du problÃ¨me impactera la taille des donnÃ©es
+Ã  Ã©changer entre les processus. Ce facteur est dÃ©fini comme Ã©tant
+la perte de performance globale due aux transferts des donnÃ©es. En
+prenant en compte le temps de communication, il est mesurÃ© comme le
+ratio entre le maximum entre les temps relatifs d'exÃ©cution
+des processus concurrents (rapport entre le temps d'exÃ©cution $T_i$ 
+d'un processus et le temps total rÃ©el d'exÃ©cution T
+du code) et l'efficacitÃ© de la sÃ©rialisation Ser : 
 
 \begin{equation}
 \label{eq:12}
@@ -1039,147 +1395,315 @@ Trf = max( T_i/T ) / Ser
 
 \end{itemize}
 
-Les auteurs ont montré que cette mesure de la performance de la parallélisation
-est indépendante du temps absolu total d'exécution.
-Pour les algorithmes itératifs, cette métrique ne dépend pas du nombre
-d'itérations avant l'arrêt de l'algorithme
-: le temps d'exécution d'une itération
+Les auteurs ont montrÃ© que cette mesure de la performance de la parallÃ©lisation
+est indÃ©pendante du temps absolu total d'exÃ©cution.
+Pour les algorithmes itÃ©ratifs, cette mÃ©trique ne dÃ©pend pas du nombre
+d'itÃ©rations avant l'arrÃªt de l'algorithme
+: le temps d'exÃ©cution d'une itÃ©ration
 reste constant.
 
-Cette quantification de la performance de la parallèlisation du code
-repose sur les trois paramètres suivants appelés aussi « inhibiteurs
-de la performance » qui décrivent selon {[}12{]} la "sensibilité"{}
-du code : (1) la sensibilité à la fréquence CPU, (2) la sensibilité
-à la bande passante mémoire et enfin (3) le temps consacré aux communications
-et les entrées / sorties. Selon l'algorithme considéré
+Cette quantification de la performance de la parallÃ¨lisation du code
+repose sur les trois paramÃ¨tres suivants appelÃ©s aussi Â« inhibiteurs
+de la performance Â» qui dÃ©crivent selon {[}12{]} la "sensibilitÃ©"{}
+du code : (1) la sensibilitÃ© Ã  la frÃ©quence CPU, (2) la sensibilitÃ©
+Ã  la bande passante mÃ©moire et enfin (3) le temps consacrÃ© aux communications
+et les entrÃ©es / sorties. Selon l'algorithme considÃ©rÃ©
 ou l'aspect scientifique du code, l'application
-peut être influencée par ces paramètres. L'analyse
+peut Ãªtre influencÃ©e par ces paramÃ¨tres. L'analyse
 du code par le profiling et l'optimisation pourront
-aider à cette sensibilité du code et à améliorer la performance de
-sa parallèlisation. 
+aider Ã  cette sensibilitÃ© du code et Ã  amÃ©liorer la performance de
+sa parallÃ¨lisation. 
 
-Dans le cadre de ces travaux, à plus large échelle, c'est-à-dire
-en augmentant la taille du problème en entrée comme la capacité de
+Dans le cadre de ces travaux, Ã  plus large Ã©chelle, c'est-Ã -dire
+en augmentant la taille du problÃ¨me en entrÃ©e comme la capacitÃ© de
 calcul disponible, les facteurs suivants vont influencer de plus en
-plus le temps d'exécution de l'application
-impactant ainsi la performance de la parallélisation du code. Selon
-{[}18{]}, même si la surcharge engendrée par la parallélisation du
-code (« surcharge due à la parallélisation ») ainsi que celle naturellement
-subie par le système comme dans une exécution séquentielle (« surcharge
-système ») peuvent ne pas être négligeables, on constate
-comme précédemment que les facteurs liés à « l'oisivité
-» des processeurs ainsi que la communication entre les différentes
-couches mémoires (DRAM, cache, « mémoire d'attraction
-» (renvoi) ) peuvent peser lourdement à grande échelle sur la performance
-globale de l'application. La surcharge due à la parallélisation
+plus le temps d'exÃ©cution de l'application
+impactant ainsi la performance de la parallÃ©lisation du code. Selon
+{[}18{]}, mÃªme si la surcharge engendrÃ©e par la parallÃ©lisation du
+code (Â« surcharge due Ã  la parallÃ©lisation Â») ainsi que celle naturellement
+subie par le systÃ¨me comme dans une exÃ©cution sÃ©quentielle (Â« surcharge
+systÃ¨me Â») peuvent ne pas Ãªtre nÃ©gligeables, on constate
+comme prÃ©cÃ©demment que les facteurs liÃ©s Ã  Â« l'oisivitÃ©
+Â» des processeurs ainsi que la communication entre les diffÃ©rentes
+couches mÃ©moires (DRAM, cache, Â« mÃ©moire d'attraction
+Â» (renvoi) ) peuvent peser lourdement Ã  grande Ã©chelle sur la performance
+globale de l'application. La surcharge due Ã  la parallÃ©lisation
 provient de l'initialisation par processeur pour une
-exécution parallèle (qui n'existe pas lors d'une
-exécution séquentielle). Le partitionnement des tâches mais aussi les tâches
-de vérrouillage et de déverrouillage lors d'une entrée
+exÃ©cution parallÃ¨le (qui n'existe pas lors d'une
+exÃ©cution sÃ©quentielle). Le partitionnement des tÃ¢ches mais aussi les tÃ¢ches
+de vÃ©rrouillage et de dÃ©verrouillage lors d'une entrÃ©e
 et de sortie d'une section critique du code contribue
-à l'importance de ce facteur. La surcharge système
-comme les défauts de pages, l'interruption horloge,
-le mécanisme de fork/join, \dots{} peut être accentuée par rapport
-à une exécution séquentielle surtout pour les programmes à haut degré
-de parallélisme parce que ces actions sont inhérentes à un processeur
+Ã  l'importance de ce facteur. La surcharge systÃ¨me
+comme les dÃ©fauts de pages, l'interruption horloge,
+le mÃ©canisme de fork/join, \dots{} peut Ãªtre accentuÃ©e par rapport
+Ã  une exÃ©cution sÃ©quentielle surtout pour les programmes Ã  haut degrÃ©
+de parallÃ©lisme parce que ces actions sont inhÃ©rentes Ã  un processeur
 et l'augmentation du nombre de processeurs lors d'une
-exécution parallèle peut engendrer une surcharge système non négligeable.
-Toutefois, comme avancé plus haut, ces surcharges peuvent ne pas être
-significatives comparées au temps perdu suite à l'oisivité
-(idle) des blocs de calcul. Cette dernière est surtout due à une parallélisation
-insuffisante ou encore par une répartition des charges non optimale.
-Enfin, le facteur communication nécessaire pour le thread courant
-de chercher des données qui ne sont pas localisées dans ses mémoires
-caches locales peut affecter dramatiquement la performance de la parallélisation
-du programme. En effet, pendant cette recherche, l'unité
-de calcul reste bloqué (stalled).
-
-
-%\section*{Solutions apportées}
+exÃ©cution parallÃ¨le peut engendrer une surcharge systÃ¨me non nÃ©gligeable.
+Toutefois, comme avancÃ© plus haut, ces surcharges peuvent ne pas Ãªtre
+significatives comparÃ©es au temps perdu suite Ã  l'oisivitÃ©
+(idle) des blocs de calcul. Cette derniÃ¨re est surtout due Ã  une parallÃ©lisation
+insuffisante ou encore par une rÃ©partition des charges non optimale.
+Enfin, le facteur communication nÃ©cessaire pour le thread courant
+de chercher des donnÃ©es qui ne sont pas localisÃ©es dans ses mÃ©moires
+caches locales peut affecter dramatiquement la performance de la parallÃ©lisation
+du programme. En effet, pendant cette recherche, l'unitÃ©
+de calcul reste bloquÃ© (stalled).
+
+
+%\section*{Solutions apportÃ©es}
  
 
-\section*{2.3 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.
 
-\section*{2.4 Méthodes de prédiction de la performance de l'application parallèle}
+\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.
 
-\section*{2.5 Conclusion partielle}
+\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. 
 
-\part*{PARTIE II - Travaux de contributions, résultats et perspectives}
+\end{itemize}
 
-\chapter*{Chapitre 3 : Comparaison par simulation à large échelle de la performance de deux algorithmes itératifs parallèles en mode asynchrone}
+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.
 
-\section*{3.1 Protocoles et expérimentations}
 
-\section*{3.2 Résultats}
+\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.
 
-\section*{3.3 Conclusion partielle}
+\begin{itemize}
 
-\chapter*{Chapitre 4 : Simulation avec SIMGRID de l\textquoteright exécution des solveurs linéaires en mode synchrone et asynchrone sur un environnement multi-coeurs simulés}
+\item [$\bullet$] IPM
 
-\section*{4.1 Protocoles et expérimentations}
+\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.
 
-\section*{4.2 Résultats}
+\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.
 
-\section*{4.3 Conclusion partielle}
+\end{itemize}
 
-\chapter*{Chapitre 5 : Modèle de prédiction de la performance à large échelle d'un algorithme itératif parallèle}
+\section{MÃ©thodes de prÃ©diction de la performance des applications parallÃ¨les}
 
-\section*{5.1 Approche et méthodologie}
+%Voir [23]
 
-\section*{5.2 Expérimentations et résultats}
+\section{Conclusion partielle}
 
-\section*{5.3 Conclusion partielle}
 
-\chapter*{Chapitre 6 : Conclusion générale et perspectives}
+\chapter{Motivations}
 
-\section*{6.1 Conclusion générale}
+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}
+
+\section{Protocoles et expÃ©rimentations}
+
+\section{RÃ©sultats}
+
+\section{Conclusion partielle}
+
+\chapter{Simulation avec SIMGRID de l\textquoteright exÃ©cution des solveurs linÃ©aires en mode synchrone et asynchrone sur un environnement multi-coeurs simulÃ©s}
+
+\section{Protocoles et expÃ©rimentations}
+
+\section{RÃ©sultats}
+
+\section{Conclusion partielle}
+
+\chapter{ModÃ¨le de prÃ©diction de la performance Ã  large Ã©chelle d'un algorithme itÃ©ratif parallÃ¨le}
+
+\section{Approche et mÃ©thodologie}
 
-\section*{6.2 Travaux futurs et perspectives}
+\section{ExpÃ©rimentations et rÃ©sultats}
+
+\section{Conclusion partielle}
+
+\chapter{Conclusion gÃ©nÃ©rale et perspectives}
+
+\section{Conclusion gÃ©nÃ©rale}
+
+\section{Travaux futurs et perspectives}
 
 
 \newpage
+%%--------------------
+%% Start the end of the thesis
+\backmatter
+
+%%--------------------
+%% Bibliography
+ 
+%% PERSONAL BIBLIOGRAPHY (use 'multibib')
+ 
+%% Change the style of the PERSONAL bibliography
+%\bibliographystylePERSO{phdthesisapa}
+ 
+%% Add the chapter with the PERSONAL bibliogaphy.
+%% The name of the BibTeX file may be the same as
+%% the one for the general bibliography.
+%\bibliographyPERSO{biblio.bib}
+ 
+%% Below, include a chapter for the GENERAL bibliography.
+%% It is assumed that the standard BibTeX tool/approach
+%% is used.
+ 
+%% GENERAL BIBLIOGRAPHY
+ 
+%% To cite one of your PERSONAL papers with the style
+%% of the PERSONAL bibliography: \cite{key}
+ 
+%% To force to show one of your PERSONAL papers into
+%% the PERSONAL bibliography, even if not cited in the
+%% text: \nocite{key}
+ 
+%% The following line set the style of
+%% the GENERAL bibliogaphy.
+%% The "phdthesisapa" is a "apalike" style with the following
+%% differences:
+%% a) The titles are output with the color of the institution.
+%% b) The name of the PhD thesis' author is underlined.
+\bibliographystyle{phdthesisapa}
+%% The following line may be used in place of the previous
+%% line if you prefer "numeric" citations.
+%\bibliographystyle{phdthesisnum}
+ 
+%% Link the GENERAL bibliogaphy to a BibTeX file.
+\bibliography{biblio.bib}
 
 \part*{BIBLIOGRAPHIE ET REFERENCES}
 
-{[}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.
+{[}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}.
 
-{[}8{]} D. BERTSEKAS and J. TSITSIKLIS. Parallel and Distributed Computation, Numerical
+{[}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.
+
+{[}8{]} D. Bertsekas and J. Tsitsiklis. Parallel and Distributed Computation, Numerical
 Methods. \textit{Prentice Hall Englewood Cliffs N. J., 1989}.
 
-{[}9{]} C. E. RAMAMONJISOA, L. Z. KHODJAV, D. LAIYMANI, A. Giersch and R. Couturier. Simulation of Asynchronous Iterative Algorithms Using SimGrid. \textit{2014 Femto-ST Institute - DISC Department - Université de Franche-Comté, IUT de Belfort-Montbéliard}
+{[}9{]} C. E. Ramamonjisoa, L. Z. Khodjav, D. Laiymani, A. Giersch and R. Couturier. Simulation of Asynchronous Iterative Algorithms Using SimGrid. \textit{2014 Femto-ST Institute - DISC Department - UniversitÃ© de Franche-ComtÃ©, IUT de Belfort-MontbÃ©liard}
 
-{[}10{]}  M. J. VOSS and R. EIGEMANN. Reducing Parallel Overheads Through Dynamic
+{[}10{]}  M. J. Voss and R. Eigemann. Reducing Parallel Overheads Through Dynamic
 Serialization. \textit{Purdue University School of Electrical and Computer Engineering}.
 
-{[}11{]} K. J. BARKER, K. DAVIS, A. HOISIE, D. J. KERBYSON, M. LANG, S. PAKIN and J. C. SANCHO. Using performance modeling to design large-scale systems. \textit{Los Alamos National Laboratory(LANL), New Mexico}.
+{[}11{]} K. J. Barker, K. Davis, A. Hoisie, D. J. Kerbyson, M. Lang, S. Pakin and J. C. Sancho. Using performance modeling to design large-scale systems. \textit{Los Alamos National Laboratory(LANL), New Mexico}.
 
-{[}12{]} M. DUBOIS and X. VIGOUROUX. Unleash your HPC performance with Bull.
+{[}12{]} M. Dubois and X. Vigouroux. Unleash your HPC performance with Bull.
 \textit{Maximizing computing performance while reducing power consumption}. http://www.hpctoday.fr/published/regional/operations/docs/W-HPCperformance-en1.pdf
 
 {[}14{]} Site du top500. http://www.top500.org
 
-{[}15{]} C. HARRIS et al. HPC Technology Update. \textit{Pawset Supercomputing Center - Sept 2015}. http://www.pawsey.org.au/wp-content/uploads/2015/09/Pawsey\_HPC\_Technology\_Update\_20150923.pdf
+{[}15{]} C. Harris et al. HPC Technology Update. \textit{Pawset Supercomputing Center - Sept 2015}. http://www.pawsey.org.au/wp-content/uploads/2015/09/Pawsey\_HPC\_Technology\_Update\_20150923.pdf
 
-{[}16{]} A. J. van der STEEN, J. J. DONGARRA. Overview of Recent Supercomputers.
+{[}16{]} A. J. van der Steen, J. J. Dongarra. Overview of Recent Supercomputers.
 \textit{Academic Computing Centre Utrecht, the Netherlands, Department of Computer Science, University of Tennessee, Knoxville, Mathematical Sciences Section, Oak Ridge, National Laboratory, Oak Ridge}. http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.49.3743\&rep=rep1\&type=pdf
 
-{[}17{]} V. RAJPUT , S. KUMAR, V.K.PATLE. Performance Analysis of UMA and NUMA Models".
+{[}17{]} V. Rajput , S. Kumar, V.K.Patle. Performance Analysis of UMA and NUMA Models".
 \textit{School of Studies in Computer Science Pt.Ravishankar Shukla University, Raipur,C.G.} http://www.ijcset.net/docs/Volumes/volume2issue10/ijcset2012021006.pdf
 
-{[}18{]} D. NGUYEN, Raj VASWANI and J. ZAHORIAN. Parallel Application Characterization for
+{[}18{]} D. Nguyen, Raj Vaswani and J. Zahorian. Parallel Application Characterization for
 Multiprocessor Scheduling Policy Design. \textit{Department of Computer Science and Engineering - University of Washington, Seattle, USA}.
 
-{[}19{]} M. EWAN. Exploring Clustered Parallel File Systems and Object Storage.
+{[}19{]} M. Ewan. Exploring Clustered Parallel File Systems and Object Storage.
 \textit{2012}. https://software.intel.com/en-us/articles/exploring-clustered-parallel-file-systems-and-object-storage
 
-{[}20{]} F. SILVA, R. ROCHA: Parallel and Distributed Programming - Performance Metrics. \textit{DCC-FCUP}. 
+{[}20{]} F. Silva, R. Rocha: Parallel and Distributed Programming - Performance Metrics. \textit{DCC-FCUP}. 
 
-{[}21{]} G. BALLARD et Al. Communication Optimal Parallel Multiplication
+{[}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
 
-\end{spacing}
+{[}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
+ 
+%% Include a chapter with a list of all the figures.
+%% In French typograhic standard, this list must be at
+%% the end of the document.
+\listoffigures
+ 
+%% Include a chapter with a list of all the tables.
+%% In French typograhic standard, this list must be at
+%% the end of the document.
+\listoftables
+ 
+%%--------------------
+%% Include a list of definitions
+\listofdefinitions
+
+%%--------------------
+%% Appendixes
+\appendix
+\part{Annexes}
+ 
+\chapter{Premier chapitre des annexes}
+
+\chapter{Second chapitre des annexes}
+ 
 \end{document}
