\newcommand{\MI}{\mathit{MaxIter}}
%\usepackage{subcaption}
\usepackage{graphicx}
+
+\usepackage{algpseudocode}
+\algnewcommand\algorithmicinput{\textbf{Input:}}
+\algnewcommand\Input{\item[\algorithmicinput]}
+\algnewcommand\algorithmicoutput{\textbf{Output:}}
+\algnewcommand\Output{\item[\algorithmicoutput]}
+
+\usepackage{multirow}
%%--------------------
%% Set the title, subtitle, defense date, and
figure \figref{decoupage} présente un exemple de découpage en domaines de la
matrice initiale entre deux clusters constitués chacun de 18 processeurs, soit un total de 36 processeurs.
-\mfigure[h]{width=8cm, height=8cm}{"3D data partitionning btw 2 clusters"} {Partitionnement : Découpage d'une matrice tridimensionnelle entre deux clusters formés de 18 processeurs chacun} {decoupage}
+\begin{figure}[!ht]
+%\centering
+\begin{minipage}[t]{5.5cm}
+\centering
+\includegraphics [ width =5.5cm]{"3D data partitionning btw 2 clusters"}
+\caption {Découpage d'une matrice tridimensionnelle entre deux clusters formés de 18 processeurs chacun}
+\end{minipage}
+\begin{minipage}[t]{5.5cm}
+\centering
+\includegraphics [ width =5.5cm]{"1D-2D-3D Domain decomposition"}
+\caption {Décomposition en domaines 1D, 2D et 3D}
+\end{minipage}
+%\caption{Partitionnement du problème}
+\end{figure}
+
+%\mfigure[!]{width=8cm, height=8cm}{"3D data partitionning btw 2 clusters"} {Partitionnement : Découpage %d'une matrice tridimensionnelle entre deux clusters formés de 18 processeurs chacun} {decoupage}
-\mfigure[h]{width=8cm, height=8cm}{"1D-2D-3D Domain decomposition"} {Partitionnement : Décomposition en domaines 1D, 2D et 3D} {Decompo}
+%\mfigure[h]{width=8cm, height=8cm}{"1D-2D-3D Domain decomposition"} {Partitionnement : Décomposition en %domaines 1D, 2D et 3D} {Decompo}
%\begin{figure}[h]
%\begin{subfigure}{0.5\textwidth}
\section{Méthodes de résolution parallèles du problème de Poisson et de
l'algorithme two-stage multisplitting de Krylov}
+Afin de valider les résultats de simulation d'applications distribuées parallèles effectuée dans le cadre de nos travaux, différents algorithmes, largement utilisés dans différents domaines scientifiques, écrits en MPI/C ont été utilisés. Ils font partie de la classe des méthodes de résolution numérique itérative qui, en opposition aux méthodes directes et par approches successives,calcule par approximation la solution du problème posé avec une erreur connue d'avance après l'initialisation d'une valeur initiale. Les méthodes itératives permettent la résolution des systèmes linéaires mais aussi non linéaires. Elles se prêtent à une parallèlisation plus aisée et supportent mieux le passage à l'echelle [4].
+Les sections suivantes vont décrire les algorithmes considérés à savoir la méthode de résolution de Jacobi et l'algorithme de Krylov avec deux variantes : le classique GMRES en mode native et la version "two-stage" d'une part et la variante multi-décomposition(multisplitting) d'autre part.
+
\subsection{Algorithme de Jacobi}
+L'algorithme de Jacobi est une des plus simples méthodes de résolutions d'un système d'équations linéaires [3,4].
+
+Soit le système d'équations linéaires suivant :
+
+\begin{equation}
+\label{eq:2}
+Ax = b
+\end{equation}
+où :
+
+\begin{tabbing}
+\hspace{2cm}\=\kill
+ \> A est une matrice carrée réelle creuse inversible de taille n, \\
+ \> x le vecteur inconnu de taille n, \\
+ \> et b un vecteur constant.\\
+\end{tabbing}
+
+Ainsi, \eqref{eq:2} peut s'écrire :
+
+\begin{equation*}
+ \left(\begin{array}{ccc}
+ a_{1,1} & \cdots & a_{1,n} \\
+ \vdots & \ddots & \vdots\\
+ a_{n,1} & \cdots & a_{n,n}
+ \end{array} \right)
+ \times
+ \left(\begin{array}{c}
+ x_1 \\
+ \vdots\\
+ x_n
+ \end{array} \right)
+ =
+ \left(\begin{array}{c}
+ b_1 \\
+ \vdots\\
+ b_n
+ \end{array} \right)
+\end{equation*}
+
+Notons : \\
+D la matrice carrée de taille n formée par la diagonale de A. On suppose qu'aucun élément $a_{i,i}$ n'est égal à 0. \\
+L (resp. U) la matrice carrée de taille n formée par les éléments du bas (resp. haut) de A.\\
+On a donc :
+
+\begin{equation*}
+D=\left( \begin{array}{ccc}
+a_{1,1} & \cdots & 0 \\
+\vdots & \ddots & \vdots \\
+0 & \cdots & a_{n,n}
+\end{array}\right)
+\space
+, \hspace{0,1cm}L=\left( \begin{array}{ccc}
+0 & \cdots & 0 \\
+\vdots & \ddots & \vdots \\
+a_{n,1} & \cdots & 0
+\end{array}\right)
+\space
+et \hspace{0,2cm}U=\left( \begin{array}{ccc}
+0 & \cdots & a_{1,n} \\
+\vdots & \ddots & \vdots \\
+0 & \cdots & 0
+\end{array}\right)
+\end{equation*}
+
+Comme A = D + (L + U) et si $D^{-1}$ est l'inverse de la matrice diagonale D, on peut écrire :
+
+\begin{equation*}
+Ax = b \Leftrightarrow ( D + L + U )x = b
+\end{equation*}
+
+\begin{equation*}
+\Leftrightarrow Dx = -(L+U)x + b
+\end{equation*}
+
+\begin{equation}
+\label{eq:3}
+\Leftrightarrow ( x = D^{-1} \times [-(L+U)] x + D^{-1} b)
+\end{equation}
+Cette dernière égalité est l'equation $du point fixe$. L'algorithme itératif de Jacobi Figure~\ref{algo:01} (version séquentielle) et ses variantes découle de cette équation [4]. Si $x^{(k)}$ est la valeur approchée du vecteur inconnu à l'itération $k$, on a d'après \eqref{eq:3} avec un $x^{0}$ initial donné :
+
+\begin{equation}
+x^{(k+1)} = D^{-1} \times [-(L+U)] x^{(k)} + D^{-1} b
+\end{equation}
+
+\begin{figure}[!t]
+\begin{algorithmic}[1]
+\Input $A_{ij}$ (Matrice d'entrée), $b_{i}$ (Vecteur du membre droit), $n$ (Taille des vecteurs) et des matrices, $xOld_{i}$ (vecteur solution à l'itération précédente)
+\Output $x_{i}$ (Vecteur solution)\medskip
+
+\State Charger $A_{ij}$, $b_{i}$, $n$,
+\State Assigner la valeur initiale $x^0$
+\State \textbf{repeat} {jusqu'à l'obtention de la condition de convergence} \textbf{do}
+\For {$i=0,1,2,\ldots (n-1)$}
+\State $x_i \leftarrow 0$
+\For {$j=0,1,2,\ldots (n-1) \hspace{0.1cm} et \hspace{0.1cm} j \neq i$}
+\State $x_{i} \leftarrow x_{i} + A_{ij} \times xOld_{j}$
+\EndFor
+\For {$i=0,1,2,\ldots (n-1)$}
+\State $xOld_{i} \leftarrow ( b_{i} - x_{i} ) \quad {/} \quad A_{ii}$
+\EndFor
+\EndFor
+\State \textbf{end repeat}
+
+\Statex
+\end{algorithmic}
+\caption{Algorithme itératif de Jacobi}
+\label{algo:01}
+\end{figure}
+
+La condition de convergence est déterminée au début du traitement. La méthode permet de passer à large échelle en distribuant l'exécutuion de l'algorithme sur un environnement de grille de calcul.
\subsection{Méthode de résolution GMRES}
Version améliorée
-\section{SIMGRID/SMPI : Simulateur d'exécution d'algorithmes
-parallèles MPI dans une grille de calcul}
+\section{Simulateurs d'exécution d'algorithmes parallèles MPI dans une grille de calcul}
+
+\subsection{Calcul sur grille}
+Une grille de calcul est caractérisée par "un type de système parallèle et distribué qui permet le partage, la sélection et l'aggrégation de ressources distribuées géographiquement selon leurs capacités" [25] afin de résoudre un problème complexe donné. Ainsi, une grille est composée d'un ensemble de grappes de machines interconnectées entre elles à travers un réseau de communication qui peut s'étendre sur des zones géographiques éloignées (Figure \figref{gridA}). Les capacités de calcul, les mémoires, les applications et les systèmes de stockage sont partagées par les applications parallèles et distribuées. Le calcul sur une grille est caractérisé par un environnement "hétérogène, dynamique et scalable". \\
+
+\mfigure[h]{width=8cm, height=8cm}{"Grid architecture"} {Architecture d'une grille de calcul} {gridA}
+
+L'hétérogénéité montre la variété des éléments composant la grille de calcul. On peut être en présence de différentes architectures de processeurs dans les machines d'une grappe ou entre les grappes. Les fréquences d'horloge de ces processeurs peuvent être aussi différentes. De même, l'architecture ou la méthode d'accès des mémoires (DRAM, stockage) utilisées dans la grille de calcul peut être aussi être aussi de types différents. Enfin, la topologie ainsi que la performance des réseaux de communications interconnectant les éléments de la grille peuvent être aussi avoir des débits complètement hétérogènes. \\
+Le caractéristique dynamique de la grille résulte de la relative facilité de changer de configuration. On peut ainsi tailler dynamiquement l'allocation des ressources de la grille aux utilisateurs selon les besoins de leur demande respective. Cet aspect a été élargi à "l'élasticité" de l'environnement dans le cadre du "cloud computing". \\
+Enfin, la scalabilité de la grille de calcul découle de sa conception modulaire permettant d'ajouter d'autres composants selon les besoins. Pour augmenter par exemple la capacité de calcul de la grille, il suffit d'ajouter de nouveaux clusters pour une plus grande puissance globale de la grille. \\
+
+Le milieu de la recherche dispose d'une grille de calcul dédié : le Grid'5000 [26, 27] est une grille répartie géographiquement dans différentes villes de France (Figure \figref{grid5000RG} ) mettant à disposition un "banc d'essai polyvalent à grande échelle" pour les expérimentations de la recherche en informatique particulièrement le calcul parallèle sur grille, sur le cloud, le calcul à haute performance mais aussi sur le Big Data. Grid'5000 permet aux utilisateurs l'accès à des ressources importantes de calcul dans un environnement complètement configurable et controllable. Il peut aussi fournir une trace détaillée ainsi que d'autres informations de mesure sur le comportement de l'application lors de l'exécution pour une étude ultérieure.
+
+\mfigure[h]{width=8cm, height=8cm}{"Grid5000 sites"} {Grid'5000 : Répartition géographique} {grid5000RG}
+
+
+Grid'5000 est construit autour de plus de 1000 noeuds physiques de différents constructeurs composés de plus de 2000 processeurs (Intel Xeon et AMD Opteron) avec un total de plus de 10.000 coeurs. Plus de 650 différentes cartes d'interface réseau Ethernet, Infiniband et Myrinet sont interconnectés avec plus de 40 accélérateurs de type NVIDIA GPU et Intel Xeon Phi.
+Dès sa conception, Grid'5000 a pris en compte la diversité des intêrets et des besoins des différents utilisateurs. En effet, dépendant de leur centre d'intêret peuvent se focaliser sur les protocoles réseau ou les systèmes d'exploitation particuliers ou d'autres problématiques sur la tolérance aux pannes,ces derniers peuvent configurer leur propre environnement de lancement de leurs applications. La reproductbilité des résultats a été soigneusement étudiée pour permettre une analyse utlérieure de la performance. De plus, Grid'5000 assure la scalabilité, la qualité de service (QoS) mais aussi et surtout la sécurité de l'environnement par le verouillage de la connexion vers Internet par exemple.
+\subsection{Généralités sur la simulation}
+
+La simulation est largement utilisée dans divers domaines de la recherche scientifique. Elle consiste au processus de la mise en oeuvre et "de la conduite d'expérimentations sur un modèle (une représentation simplifiée du réel) dans le but de comprendre le comportement du système modélisé sous des conditions sélectionnées ou de l'évaluation de diverses stratégies pour le fonctionnement du système sous la limite imposée par les critères de développement et d'exploitation" [29]. Particulièrement, la simulation de l'exécution d'une application parallèle distribuée étudie son comportement (résutats en sortie, temps de performance, scalabilité, ...) sur un environnement virtuel imitant au mieux le fonctionnement d'une plateforme physique réel ou d'un système en cours d'élaboration (banc d'essai) ou encore d'une hypothétique machine non encore réalisée. Ainsi, la simulation informatique se focalise sur le comportement dynamique du modèle à travers le temps. Plusieurs raisons motivent une telle simulation: à titre d'exemple, de réduire les coûts de la conception d'un système et d'éviter les erreurs, de produire dans un temps raisonnable des résultats en sortie d'un modèle ayant un temps d'exécution élevé, de répondre à des scénarions d'exécution avec des questions "what-if" (tests et évaluations), ou encore de créer des outils de simulation pour des formations ou des jeux. \\
+Dans le cadre d'une grille de calcul, les simulateurs ou les outils de simulation permettent à l'inverse des plateformes réelles l'évaluation de la performance des expérimentations "répétables et controllables" [25] sur des configurations flexibles et scalables. En effet, les environnements réels montrent leurs limites sur leur rigidité de passage à l'echelle mais aussi sur la flexibilité de disposer un environnement de calcul particulier répondant aux besoins précis de l'application à un moment donné. Selon la classification dans [30], la simulation d'applications sur une grille de calcul rejoint la classe de simulation "virtuelle" par l'utilisation d'équipements de simulation par des personnes réelles. De façon générale, le simulateur utilise une échelle de temps "discret", c'est-à-dire le temps est découpé en intervalles qui peuvent être réguliers ou non. Dans le cas d'un système à temps discret régulier, le simulateur maintient et met à jour éventuellement un ensemble de "variables d'état" qui reflètent l'état du système physique à un instant t donné. Un "évenement" est associé à chaque instant donné à une "transition d'état". Pour des comparaisons futures, on distingue le "temps physique" comme étant le temps considéré au niveau du système physique, du "temps de simulation" et "le temps de l'horloge murale" désigne le temps de simulation du modèle. Toutefois, le "temps de simulation" est une notion abstraite utilisée par le simulateur pour évaluer le temps de simulation. Il est défini [30] comme étant "un ensemble de valeurs totalement ordonné E où chaque valeur représente un temps du système physique à modéliser et qui vérifie les conditions suivantes:" \\
+
+Soient E l'ensemble des temps discrets de simulation et P l'ensemble des temps du système physique.
+
+\begin{equation}
+\label{eqsim}
+\begin{split}
+\texttt{Si } ( T_1 \in E, T_2 \in E ) \texttt{ et }( P_1 \in P, P_2 \in P ) \texttt{ et } (T_1 \textless T_2) \\
+\Rightarrow ( (P1 \textless P2) \texttt{ et } \exists K \in \mathbb{N}, T_2 - T_1 = K \times ( P_2 - P_1 )
+\end{split}
+\end{equation}
+
+La définition précédente montre le lien linéaire étroit entre les intervalles de temps de simulation et celles des temps physiques. Ce qui permet d'estimer entre autres le temps d'exécution probable d'une application à partir du temps de simulation observé. Outre ce temps global de l'outil de simulation et les variables d'état, une liste des évenements à exécuter complète la composition du simulateur au temps discret. \\
+Le changement des variables d'état peut s'effectuer soit à une fréquence régulière du temps de simulation (exécution rythmée par le temps) soit au début et à la fin d'un évenement donné (exécution rythmée par les évenements).
+Dans le cas d'une simulation d'une application parallèle et distribuée où plusieurs processeurs ou coeurs interconnectés concourent à résoudre ensemble le problème posé, plusieurs autres aspects liés à l'environnement doivent être considérés : \\
+\begin{itemize}
+\item [$\bullet$] L'initialisation du système;
+\item [$\bullet$] Les échanges de données entre les processus;
+\item [$\bullet$] La synchronisation des processus;
+\item [$\bullet$] La détection de deadlock et la reprise;
+\item [$\bullet$] L'arrêt et la fermeture du système.
+\end{itemize}
+Le tableau \ref{table1} donne quelques exemples de simulateurs pour des applications parallèles et distribuées sur une grille de calcul [28, 25].
+
+\begin{table}[htbp]
+\centering
+%\tiny
+\fontsize{8}{9}\selectfont
+\begin{tabular}{|c|c|c|c|p{1cm}p{1cm}p{1cm}p{1cm}|}
+\hline \\
+%{ } & { } & { } & { } & \\
+\textbf{OUTIL} & \textbf{DESCRIPTION} & \textbf{DEVELOPPEUR} & \textbf{APPLICATIONS CIBLE} \\ \hline
+\multirow{ 3}{*}{SimJava} & SimJava fournit un processus de simulation & Université de & Simulation d'évenements \\
+{ } & avec une animation à travers d'entités communiquant entre elles & Edinburgh (UK) & discrets \\
+{ } & http://www.dcs.ed.ac.uk/home/hase/simjava/ & { } & { } \\ \hline
+
+\multirow{ 4}{*}{Bricks} & Bricks est un outil d'évaluation de performance & Tokyo Institute of & Simulation \\
+{ } & analysant divers schémas d'ordonnancement & Technology (Japan) & de grille \\
+{ } & dans un environnement de grille de calcul & { } & { } \\
+{ } & http://matsu-www.is.titech.ac.jp/~takefusa/bricks/ & { } & { } \\ \hline
+
+\multirow{ 4}{*}{Microgrid} & Microcrid permet la simulation d'une montée & University of & Simulation \\
+{ } & en charge des applications sur grille de calcul & California at & de grille \\
+{ } & en utilisant des ressources clusterisées & San Diego (USA) & { } \\
+{ } & http://www-csag.ucsd.edu/projects/grid/microgrid.html & { } & { } \\ \hline
+
+\multirow{ 3}{*}{Simgrid} & Simgrid simule les applications & University of & Simulation \\
+{ } & distribuées dans un environnement distribué hétérogène & California at & de grille \\
+{ } & http://grail.sdsc.edu/projects/simgrid/ & San Diego (USA) & { } \\ \hline
+
+\multirow{ 4}{*}{Gridsim} & Gridsim permet la modélisation et la simulation & Monash & Simulation \\
+{ } & d'entités impliquées dans le calcul parallèle et distribué & University & de grille \\
+{ } & par la création et le pilotage de différentes ressources & Australie & { } \\
+{ } & http://www.buyya.com/gridsim/ & { } & { } \\ \hline
+
+\end{tabular}
+\caption{Quelques outils de simulation pour une grille de calcul}
+\label{table1}
+\end{table}
+
+Simgrid est l'outil choisi dans le cadre de ces travaux pour étudier le comportement et évaluer la performance d'applications parallèles distribuées à grande échelle. Une section de ce chapitre sera dédiée à la description plus détaillée de cette plateforme.
+
\subsection{MPI - Message Passing Interface}
+MPI ou "Message Passing Interface" est les spécifications d'une librairie d'interface pour le transfert de message entre les processus d'une application parallèle. A sa version MPI-3 (2015), elle est largement utilisée dans la recherche dans le domaine du calcul à haute performance avec des compilateurs C/C++ et Fortran généralement. La facilité de l'utilisation et la portabilité à travers différents systèmes hétérogènes ont guidé le développement de ces spécifications MPI standards. Ces derniers peuvent être matérialisés sur différentes plateformes cibles telles qu'une grille de calcul, des machines multiprocesseurs et multicores à mémoires partagées ou distribuées, un réseau de stations de travail interconnectés ou encore des environnements hybrides obtenus par la combinaison de ces architectures. Principalement, les standards MPI sont implémentés sur différents systèmes d'exploitation soit avec MPICH [32] ou OpenMPI [33] tous les deux des logiciels libres à haute performance et portable développés par des consortiums de chercheurs et des partenaires et collaborateurs industriels.
+Plusieurs domaines sont couverts par les spécifications de MPI dont les plus importants sont cités ci-dessous [31,32,33].
+\begin{itemize}
+
+\item[$\bullet$] Groupes, contexte et communicateur: Définit l'initialisation de l'environnement d'exécution du programme parallèle MPI. Un groupe de processeurs est formé et un unique contexte de communication est créé et les deux sont intégrés ensemble dans un communicateur.
+
+\item[$\bullet$] La gestion de l'environnement MPI: Permet à l'utilisateur d'interagir avec l'environnement MPI créé lors du lancement du programme parallèle. Elle assure par abstraction la portabilité de l'application entre des plateformes matérielles et logicielles différentes.
+
+\item[$\bullet$] La gestion des processus: Définit la création des processus participant à l'exécution de l'application mais aussi détermine la topologie et la gestiobn des groupes de processus en accord par exemple avec des architectures complexes comme les grilles de calcul.
+
+\item[$\bullet$] Les types de données : Permettent de créer des structures de données complexes en mémoire à partir des types de données de base comme l'entier, le float, etc...
+
+\item[$\bullet$] Les communications: Rassemblent les spécifications des protocoles d'échanges de messages entre les processus. On distingue les communications point à point, les communications collectives mais aussi les entrées / sorties parallèles.
+
+\end{itemize}
+
+Le programme MPI s'exécute sur chaque processeur une fois que l'environnement logique est créé par la routine MPI\_Init. Ce dernier est constitué d'un groupe de processus, d'un contexte et d'un communicateur (par défaut MPI\_COMM\_WORLD), voir la figure \figref{MPI}-a. Chaque processus est identifié par son rang dans le groupe associé au communicateur (MPI\_Comm\_rank). Le nombre total de processus en jeu est donné par MPI\_Comm\_size. A la fin du code, MPI\_Finalize termine l'exécution en environnement MPI. De façon générale, une erreur arrête tous les processus en jeu. Toutefois, le programmeur peut gérer et personnaliser les erreurs au niveau de chaque processus ou globalement. Une routine MPI qui se termine avec succès retourne le code MPI\_SUCCESS. \\
+
+\mfigure[h]{width=8cm, height=8cm}{"MPI"} {Groupes et communicateur (a) - MPI - Opérations collectives (b)} {MPI}
+
+Au niveau de la communication, le transfert de message peut se faire d'un processus vers un autre (point à point). Pour cela, les routines MPI\_SEND et MPI\_RECV et leus variantes permettent respectivement d'envoyer et de recevoir un message. L'adresse du tampon contenant le message à traiter sont passées à ces fonctions avec le type de données ainsi que le nombre d'objets. La destination dans le cas d'un envoi est spécifiée par le rang du processus d'arrivée du message dans le communicateur considéré. Une variable de statut de l'opération permet de connaitre si l'opération a réussi ou a échoué. Cet échange peut se faire de manière synchrone ou asynchrone(resp. bloquant ou non bloquant). \\
+Contrairement à une communication point à point, une communication dite collective transfère un message à partir d'un processeur vers un ensemble de processeurs. L'exemple le plus courant est le "broadcast" ou diffusion où un processeur envoie le même message à destination d'un ensemble de processeurs. La figure \figref{MPI}-b montre les échanges entre les processus après l'appel à cette opération mais aussi d'autres types de communications collectives. Un processus avec MPI\_Scatter distribue une structure de données à d'autres processus participants tandis que MPI\_Gather rassemble des données de plusieurs processus participant en une seule structure. Enfin, les opérations de réduction appliquent une opération (somme, produit, maximum, minimum, etc ...)à un ensemble de processus et retourne le résultat vers le processus appellant.
+La synchronisation des processus peut être obtenue avec la routine MPI\_Barrier qui, une fois lancée par un processus, bloque ce dernier jusqu'à ce que tous les processus de son groupe atteigne cette barrière comme un point de rendez-vous.
+
+\subsection{Simulateur SIMGRID - SMPI}
+SimGrid est utilisé pour la simulation et l'étude du comportement d'applications parallèles dans un contexte d'un environnement complexe, hétérogène, distribué et dynamique. Comme son nom l'indique, développé par la communauté des utilisateurs de grille de calcul, il est utilisé aussi largement sur dans les domaines des applications pair-à-pair,du calcul à haute performance et du cloud computing [5,9]. Le choix de Simgrid comme outil de simulation dans le cadre de ces travaux a été motivé par son efficacité pour la simulation d'applications parallèles à large échelle. En effet, Simgrid rassemble au mieux les caractéristiques requises pour un simulateur dans un environnement de grille de calcul telles que la robustesse, la scalabilité et la justesse des résultats accompagnées d'un temps de réponse correct et d'une tolérance aux pannes de l'exécution [34].
+
+Simgrid est conçu sur une simulation basée sur les évenements ("event driven")[26, 35] à un niveau d'abstraction et de fonctionnalités répondant aux applications et aux infrastructures. Cinq composants d'abstraction constitue le fonctionnement de Simgrid :
-\subsection{Simulateur SIMGRID}
+\begin{itemize}
+
+\item[$\bullet$]Un "agent" est une entité qui assure l'ordonnancement de l'application et exécute le code sur une "location";
+
+\item[$\bullet$]Une "location" est une hôte de l'environnement de simulation sur laquelle l'agent s'exécute. Outre les données propres à la location, des boîtes aux lettres sont conçues pour permettre les échanges de données avec d'autres agents;
+
+\item[$\bullet$]Une "tâche" est une activité de l'application simulée. Elle se décline sous forme d'un calcul (temps de calcul nécessaire) ou d'un transfert de données (volume de données à échanger;
+
+\item[$\bullet$]Un "chemin" décrit la liaison entre les locations. Il est utilisé par les agents lors d'un transfert de données à calculer le temps de transfert en tenant compte du routage à appliquer pour une telle liaison.
+
+\item[$\bullet$]La communication entre agents se fait à travers un "channel". Cette abstraction modélise la communication à travers un port entre des agents dans les locations.
+
+\end{itemize}
+
+Simgrid offre pour l'utilisateur plusieurs types d'interfaces de programmation [5,9]: MSG qui simule les "processes séquentiels conccurents", SimDAG qui est utilisé pour simuler des tâches parallèles modélisées en graphe acyclique direct et SMPI qui simule et exécute les applications écrites en MPI sans ou avec des modifications mineures. Outre le langage C natif, Simgrid accepte des applications écrites en C++, Java, Lua ou encore Ruby.
+
+De point de vue pratique, la figure \figref{simgrid1} présente la structure et les éléments de la plateforme de simulation Simgrid. Elle est composée des trois parties différentes suivantes :
+
+\begin{itemize}
+
+\item[$\bullet$] Le scénario de la simulation qui constitue les "modèles de ressources" du système. Evidemment, il comprend le code de l'application à exécuter dans le simulateur avec ses différents paramètres d'entrée mais aussi son modèle de déploiement. Un autre composant important de ce scénario aussi est le fichier, généralement au format XML, modélisant les détails de la topologie et l'architecture de l'environnement d'exécution. Il détermine par exemple pour le cas d'une grille de calcul, le nombre et les caractéristiques des clusters contribuant à cet environnement. Pour chaque cluster, les spécifications des serveurs (nombre de cores ou de processeurs, puissance en Flops, taux de disponibilité, ...)sont définies ainsi que les propriétés des réseaux de liaison entre ces différents composants de la grille (topologie du réseau, débit et latence, table de routage, ...).
+
+\item[$\bullet$] Le simulateur proprement dit.
+
+\item[$\bullet$] Les fichiers de sortie comprenant les résultats de la simulation de l'application ainsi que d'autres fichiers de monitoring de l'exécution comme un fichier de logging et de statistiques. Simgrid peut générer aussi des données pouvant être utilisées pour représenter visuellement le déroulement et la trace de la simulation dans le temps.
+
+\end{itemize}
-\section{Motivations}
+\mfigure[h]{width=8cm, height=8cm}{"Simgrid - In a nutshell"} {SIMGRID : Les éléments de la plateforme de simulation} {simgrid1}
+
+Les applications sous-tendant les expérimentations effectuées dans le cadre de ces travaux ont été ecrites en C et utilise les librairies MPI. Simgrid dispose de l'interface SMPI (Simulated MPI) qui peut exécuter un code MPI parallèles sans aucune ou à la limite très peu de modifications. A titre d'exemple, les variables globales doivent être transférées dans un contexte local dans l'application SMPI. Simgrid/SMPI assure l'implémentation de plus de 80\% des routines de la librairie MPI 2.0. Le code est exécuté réellement dans le simulateur dans l'environnement virtuel spécifié sauf que les communications sont interceptées et le temps de transfert calculé en tenant compte du partage des ressources existantes (par exemple le partage de la bande passante entre processus concurrents sur les réseaux de liaison).La scalabilité de Simgrid peut être obtenu par appel à des routines SMPI qui utilisent des structures de données partagées entre les processus parallèles réduisant ainsi la quantité de mémoire utilisée et permettant une montée en charge non négligeable. Toutefois, dans ce cas, comme tous les processus utilisent la même structure de données, la véracité des résultats obtenus n'est pas importante.
+
\section{Conclusion partielle}
du problème lors de la montée en charge (scaling). Pour le « weak
» scaling, on essaie d'observer le comportement du
programme en gardant le même nombre d'éléments à traiter
-par processeur ou core. Dans ce cas, les ressources
+par processeur ou coeur. Dans ce cas, les ressources
de calcul additionnelles
va augmenter proportionnellement à la taille du problème en entrée. Ainsi, la problématique ici est de résoudre un problème de plus grande taille. Par ailleurs, le « strong » scaling
essaie de résoudre un problème donné plus vite. Ainsi, dans ce cas,
Ainsi, la figure \figref {power} montre l'évolution de la puissance
de calcul mondiale dont le top actuel développe un pic de performance
théorique proche de 50 PetaFlops (33 Linpack PetaFlops (renvoi)) avec
-3.120.000 cores ( 16 noeuds avec des processeurs de 2x12 cores par
+3.120.000 coeurs ( 16 noeuds avec des processeurs de 2x12 coeurs par
noeud) et plus de 1.240.000 Gb de mémoire (64 Gb par noeud) avec des
accélérateurs 3 $\times$ Intel Xeon Phi par noeud. Il s'agit
de la machine Tianhe-2 (MilkyWay-2) de la National Super Computer
%\section*{Solutions apportées}
-\section{Techniques de profiling et instrumentation des applications parallèles}
+\section{Techniques d'analyse de performance des applications parallèles}
+\subsection{Généralités et objectifs}
+L'analyse de la performance des applications parallèles est largement utilisée et même recommandée lors de l'écriture et la mise au point du programme. En effet, pour déterminer et estimer le coût de l'execution du code, il est d'usage de procéder à l'analyse de la performance dans le but d'optimiser le programme parallèle afin de trouver la meilleure performance en termes de coûts (réduction du temps d'exécution, efficacité de l'utilisation des ressources, ...). \\
+Cette opération consiste surtout à détecter les "régions" et "hotspots" qui correspondent aux parties du code les plus consommatrices de ressources (CPU, mémoire) en particulier celles qui consomment le plus de temps de calcul ou de communication. Elle permet aussi de localiser les éventuels goulots d'étranglement lors de l'exécution du code. Les résultats de cette analyse permet de guider le développeur sur ses actions pour améliorer le code par la réécrire de certaines parties du code par exemple ou de procéder à un meilleur découpage du problème pour une meilleure répartition des charges et l'utilisation des mémoires ou encore par la modification de l'algorithme pour permettre une parallélisation plus poussée.
+Plusieurs outils existent avec différentes approches pour effectuer cette analyse.
+La section suivante montre que le modèle de performance établi lors de cette analyse permet aussi d'anticiper sur la prédiction de la performance de l'application parallèle avec la montée en charge [21]. En effet, l'analyse de la performance d'un code peut être utilisée pour prédire le comportement du programme soit d'une part sur un environnement de machines déterminé (benchmarking) soit d'autre part, avec une taille de problème plus importante.
+
+\subsection{Approches et méthodologie}
+Dans le domaine du calcul parallèle, l'analyse du code d'une application suit les trois étapes suivantes [21,22]:
+\begin{itemize}
+\item [$\bullet$] L'acquisition et la collecte des données
+\item [$\bullet$] L'enregistrement des données collectées
+\item [$\bullet$] La représentation des résultats de l'analyse
+\end{itemize}
+Les deux derniers points sont regroupés sous le nom générique de "profiling" ou de "tracing" selon le modèle adopté de l'acquistion des données. La figure \figref{anaperf} montre ces trois couches de l'analyse de performance et décrit les différentes techniques utilisées pour cette analyse. Les flèches tracées sur la figure montrent les combinaisons possibles entre les techniques présentées. D'ailleurs, dans la pratique, d'autres combinaisons peuvent être expérimentées pour atteindre les objectifs fixés.
+
+\mfigure[h]{width=8cm, height=8cm}{"Performance Analysis techniques"} {Classification des techniques d'analyse de la performance} {anaperf}
+
+Cette approche à trois étapes commence par la collecte des données sur la performance du code qui consiste à deux techniques les plus utilisées à savoir le "sampling" (ou "l'échantillonage") et "l'instrumentation basée sur les évenements".
+\begin{itemize}
+\item [$\bullet$] Le "sampling" ou "l'echantillonage" capture les données décrivant l'état du code lors de l'exécution du programme à chaque instant défini par la fréquence de l'echantillonage. IL est réalisé généralement avec la mise en place d'un timer qui déclenche la collecte des données selon une période définie. Ces dernières se rapportent sur les statistiques relatives aux appels de fonctions ("call-path" des fonctions) mais aussi sur les compteurs matériels [22]. Ainsi, il est d'usage de collecter le temps d'exécution d'un fonction ou combien de fois la fonction a été appellée ou encore de façon plus détaillée, combien de fois une ligne de code est exécutée. Evidemment, l'efficacité de la méthode dépend du taux d'échantillonnage: les informations entre deux points de collecte ne sont pas disponibles pour l'analyse ultérieure. Par contre, la surcharge engrendrée par la technique peut être contrôlée par l'utilisateur par un choix adéquet de la fréquence de l'echantillonage. \\
+L'alternative pour collecter les données de la performance d'une application parallèle se porte sur l'instrumentation basée sur les évenements. D'abord, de façon générale, l'instrumentation du code consiste à ajouter manuellement ou automatiquement des instructions supplémentaires à des endroits choisis afin de rapporter à chaque passage des informations spécifiques. A titre d'exemple, on peut positionner un timer au début d'une portion du code et d'arrêter ce timer à la sortie de cette région. On peut ainsi collecter le temps total d'execution consommé par l'application pour exécuter cette partie du programme. Cette technique est largement utilisée par exemple pour détermijner le temps de communication nécessaire lors d'un appel d'une instruction MPI de transfert ou collective (MPI\_send, MPI\_receive ou autre MPI\_Barrier). Cette modification directe qui nécessite une récompilation du code est aussi appellée "instrumentation au niveau de la source". D'autres techniques utilisant des outils existent telles que les "libraries wrapping" ou la "réécriture du code binaire" [22]. Ces dernières n'ont pas besoin d'une recompilation du code.
+
+\item [$\bullet$] La deuxième étape du processus de la collecte des données en vue d'une future analyse consiste à enregister soit en mémoire soit sur un support de stockage externe les données obtenues lors de l'étape précédente. Deux techniques peuvent être exploitées à cette fin. D'abord, le "logging" ou le "tracing" permet d'ajouter le facteur temps sur les données collectées. Ainsi, avant le stockage, chaque entrée de données est estampillée d'une date de l'évenement (au format date - heure). Cette opération peut ajouter un temps de surcharge non négligeable lors de l'exécution.\\
+Afin de réduire cette dernière mais aussi pour optimiser la taille du fichier de trace obtenu, la technique de "summarization" consiste à agréger les données après la collecte et de ne stocker que le minimum d'informations utiles. Ce dernier est généralement appellé le "profile" de l'application [21,22]. Certains détails peuvent être perdus avec cette méthode mais il s'agit ici de faire une balance entre la taille la granularité de l'information et la taille des données stockées.
+
+\item [$\bullet$] La troisième et dernière étape de l'analyse de la performance concerne la visualisation des données collectées en vue de l'analyse proporement dite et des décisions à prendre pour améliorer et optimiser l'exécution de l'application. Dans la même ligne de l'étape précédente, soient les données sont visualisées "au fil du temps" en suivant l'exécution du code sur les différentes machines de l'environnement parallèle, soient elles sont représentées par un groupement selon un facteur compréhensible par l'analyste (par fonction par exemple), on est en présence d'une technique générant un "timelines" ou un "profile" de l'application respectivement.
+
+\end{itemize}
+
+Noter que l'approche présentée dans cette section présente les techniques en vue d'optimiser le code de l'application pour un meilleur temps d'exécution en l'occurrence. Ainsi, elle ne prend pas en compte la performance lors de la scalabilité de l'application pour une prédiction du comportement du code lors du passage à l'echelle. Cette partie sera traitée au paragraphe ...
+Plusieurs outils d'analyse de la performance parallèle utilisant une ou des combinaisons de ces différentes techniques tels que Gprof, PerfExpert, IPM, TAU, PAPI, HPCToolkit, SCala [...] sont largement utilisés. La prochaine section donne plus de détails sur certains de ces produits.
+
+
+\subsection{Quelques outils d'analyse de performance}
+Quelques outils d'analyse de performance sont passés en revue dans cette section. Ils mettent en exergue les différentes approches pour aborder ce problème crucial de performance pour les applications parallèles et distribuées.
+
+\begin{itemize}
+
+\item [$\bullet$] IPM
+
+\item [$\bullet$] TAU a été conçu à l'Université d'Oregon comme un outil open source d'évaluation de performance [24]. Il intègre le profiling et le tracing constituant une platerme complète couvrant les trois étapes de l'analyse d'une applicatio parallèle. L'instrumentation du code peut être effectuée d'une façon complètement automatique avec un package fourni ("PDT - Program Database Toolkit - for routines")collectant toutes les informations sur les régions et hotspots du code, l'utilisation mémoire, les boucles, les entrées/sorties,...Selon le paramètrage de lancement, TAU peut collecter des informations les plus fines telles que le temps passé à chaque instruction dans une boucle ou le temps passé dans les communications à une étape du programme particulièrement dans les instructions collectives MPI par exemple. Toutes ces données peuvent par la suite être visualisées sous forme graphique (Paraprof 3D browser) pour une analyse fine afin d'optimiser la performance.
+
+\item [$\bullet$] SCALA ou SCAlabity Analyzer est orienté particulèrement dans l'analyse de la performance des applications sur sa scalabilité lors de la montée en charge. Outre la prédiction de la performance, SCALA utilise les fonctionnalités avancées actuelles pour la mise au point (debugging) de la dite performance et d'une éventuelle restructuration du code parallèle d'une part mais aussi d'estimer l'impact des variations sur l'environnement matériel d'exécution.
+\end{itemize}
-\section{Méthodes de prédiction de la performance de l'application parallèle}
+\section{Méthodes de prédiction de la performance des applications parallèles}
+%Voir [23]
\section{Conclusion partielle}
+
+\chapter{Motivations}
+
+Malgré les grandes avancées dues aux performances des nouveaux processeurs, mémoires mais aussi des réseaux de communication, le milieu académique comme le domaine industriel sont toujours confrontés à des défis et challenges de plus en plus ambitieux. Ce fait est surtout accentué par des besoins de plus en plus variés et importants de calcul scientifique nécessitant de plus en plus de moyens mais aussi de méthodes plus efficientes et performantes. Ces besoins requièrent le traitement de données de plus en plus volumineuses mais aussi l'écriture d'algorithmes donnant des résultats probants dans un laps de temps correct. Le défi actuel serait donc l'exploitation de la puissance de calcul des matériels actuels dans un environnement de calcul optimisé pour traiter un volume de données de plus en plus important. \\
+Dans le cadre de nos travaux, l'objectif final est d'aider les utilisateurs finals (scientifiques, chercheurs, industriels, étudiants, ...) en calcul à haute performance à rentabiliser au maximum l'accès aux infrastructures de calcul physiques existantes, étant donné le côut et la difficulté (même des fois l'impossibilité) d'accès à ces dernières. En effet, la demande d'utilisation de ces infrastructures dépasse largement l'offre établie, entraînant des longues listes d'attente avant de pouvoir y accéder pour une durée très limitées. \\
+Pour atteindre ces objectifs, nous proposons d'utiliser des outils de simulation pour exécuter les applications pour étudier leurs comportements à large échelle mais aussi pour pouvoir déterminer les conditions optimales pour obtenir des résultats optimaux. Le simulateur permet d'étudier le comportement des algorithmes sous différentes conditions et sur des plateformes variées et paramétrables. Plusieurs modes d'exécution peuvent être essayés lors de l'expérimentation. De plus, la flexibilité de l'outil permet l'estimation de la performance des algorithmes lors du passage à l'échelle.\\
+Les questionnements suivants résument les motivations des travaux consignés dans cette thèse.
+\begin{itemize}
+\item [$\bullet$] a. Quelles solutions pratiques peut-on apporter pour réduire le coût de l’exécution d’applications parallèles et distribuées dans un environnement de grille de calcul durant tout son cycle de vie de développement ?
+\item [$\bullet$] b. Quel est le comportement de l’algorithme distribué à large échelle dans cette architecture de grille de clusters en particulier lors de son exécution en mode asynchrone ?
+\item [$\bullet$] c. Dans ce contexte, quels sont les facteurs importants identifiés permettant d’avoir un gain de temps d’exécution en mode asynchrone comparativement au mode synchrone ? A quel niveau peut-on estimer le gain obtenu en comparant l'exécution en mode asynchrone par rapport au mode classique synchrone.
+\item [$\bullet$] d. Quel est le taux d'erreur de validation obtenue en comparant les résultats du lancement de l'application entre une exécution simulée et une execution sur un environnement réél équivalent.
+\end{itemize}
+
+La partie suivante va exposer la méthodologie adoptée et les travaux de contributions pour apporter des réponses à ces questions.
+
+
\part{PARTIE II - Travaux de contributions, résultats et perspectives}
\chapter{Comparaison par simulation à large échelle de la performance de deux algorithmes itératifs parallèles en mode asynchrone}
\part*{BIBLIOGRAPHIE ET REFERENCES}
+
+{[}3{]} J. M. Bahi, S. Contassot-Vivier, R. Couturier - Parallel Iterative Algorithms: from Sequential to Grid Computing - \textit{CRC PRESS - Boca Raton London New York Washington, D.C.}
+
+{[}4{]} R. Couturier - Résolution de systèmes linéaires à très large échelle : méthodes classiques versus méthodes à large échelle - \textit{2014 - FEMTO-ST, Université de Franche-Comté}
+
+{[}5{]} C. E. Ramamonjisoa, L. Z. Khodjav, D. Laiymani, A. Giersch and R. Couturier. - Grid-enabled simulation of large-scale linear iterative solvers - \textit{2014 Femto-ST Institute - DISC Department - Université de Franche-Comté, IUT de Belfort-Montbéliard}
+
{[}6{]} J.M. Bahi, S. Contassot-Vivier, R. Couturier. Interest of the asynchronism in parallel iterative algorithms on meta-clusters. \textit{LIFC - Université de Belford-Montbéliard}.
{[}7{]} T.P. Collignon and M.B. van Gijzen. Fast iterative solution of large sparse linear systems on geographically separated clusters. \textit{The International Journal of High Performance Computing Applications} 25(4) 440\textendash 450.
{[}21{]} G. Ballard et Al. Communication Optimal Parallel Multiplication
of Sparse Random Matrices". \textit{UC Berkeley, INRIA Paris Rocquencourt, Tel-Aviv University}. http://www.eecs.berkeley.edu/\textasciitilde{}odedsc/papers/spaa13-sparse.pdf
+
+{[}22{]} T. Ilsche, J. Schuchart, R. Schöne, and Daniel Hackenberg. Combining Instrumentation and Sampling for Trace-based Application Performance Analysis. \textit{Technische Universität Dresden, Center for Information Services and High Performance Computing (ZIH), 01062 Dresden, Germany}
+
+{[}23{]} J.A. Smitha, S.D. Hammond, G.R. Mudalige - J.A. Davis, A.B. Mills, S.DJarvis. A New Profiling Tool for Large Scale Parallel Scientific Codes. \textit{Department of Computer Science, University of Warwick,Coventry, UK}
+{[}24{]} S. Shende - New Features in the TAU Performance System - \textit{ParaTools, Inc and University of Oregon. 2014}.
+
+{[}25{]} M. Mollamotalebi1, R. Maghami1, A. S. Ismail - "Grid and Cloud Computing Simulation Tools" - \textit{International Journal of Networks and Communications 2013, 3(2): 45-52 - DOI: 10.5923/j.ijnc.20130302.02}
+
+{[}26{]} F. Cappello et al. - Grid’5000: a large scale and highly reconfigurable Grid experimental testbed - \textit{INRIA, LRI, LIP, IRISA, LORIA, LIFL, LABRI, IMAG}
+
+{[}27{]} Grid'5000 - http://www.grid5000.org
+{[}28{]} A. Sulistio, C. Shin Yeo et R. Buyya - Simulation of Parallel and Distributed Systems: A Taxonomy and Survey of Tools Grid Computing and Distributed Systems (GRIDS)- \textit{Laboratory Dept of Computer Science and Software Engineering The University of Melbourne, Australia}.
+
+{[}29{]} http://www.dau.mil/ - Defense Acquisition University (DAU) - Ft Belvoir (VA) - USA.
+
+{[}30{]} R. M. Fujimoto - Parallel and Distributed Simulation Systems - \textit{Georgia Institute of Technology - John Wiley \& Sons, Inc. - ISBN 0-471-18383-0} - 2000
+
+{[}31{]} MPI: A Message-Passing Interface Standard Version 3.- \textit{University of Tennessee, Knoxville, Tennessee.} - 2015
+
+{[}32{]} MPICH : www.mpich.org
+
+{[}33{]} OpenMPI : www.openmpi.org
+
+{[}34{]} M. Quinson et Al. - Experimenting HPC Systems with Simulation - \textit{Nancy University, France, Caen, HPCS/IWCMC 2010.}
+
+{[}35{]} A. Legrand, L. Marchal, H. Casanova - Scheduling Distributed Applications: the SimGrid Simulation Framework - \textit{Laboratoire de l’Informatique du Parallèlisme - Ecole Normale Supérieure de Lyon, Dept. of Computer Science and Engineering San Diego Supercomputer Center - University of California at San Diego}
+
+{[}36{]} Xian-He Sun, T. Fahringer, M. Pantano - SCALA: A perfformance system for scalable computing - \textit{Department Of Computer Science, Illinois Institute of Technology Chicago, Institute for software technology and parallel systems, University of Vienna Liechtenstein - The International Journal of High Performance Computing Applications,Volume 16, No. 4, Autumn 2002,}
+
+
%%--------------------
%% List of figures and tables
