X-Git-Url: https://bilbo.iut-bm.univ-fcomte.fr/and/gitweb/these_charles_emile.git/blobdiff_plain/a84d210b4e8cc45730579629651a610559792413..475623f243d1b5dc486976079df057e9b4a2154b:/These_RCE.tex diff --git a/These_RCE.tex b/These_RCE.tex index e22ad09..7455573 100644 --- a/These_RCE.tex +++ b/These_RCE.tex @@ -1,193 +1,338 @@ -%% 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[]{Simulations à très large échelle d'algorithmes parallèles numériques itératifs et asynchrones}{XX XXX 2016}{XXX} + +%%-------------------- +%% Set the author of the PhD thesis +\addauthor[email]{C. E.}{RAMAMONJISOA} + +%%-------------------- +%% 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} + +Cette première partie met en exergue d'une part, le contexte scientifique de nos travaux et d'autre part, une revue de l'état de l'art dans le domaine de la recherche concerné ainsi que les travaux associés existant actuellement. \\ +Elle introduit ainsi dans un premier chapitre, la classe des algorithmes itératifs parallèles de systèmes d'équations linéaires ou non à large échelle et les méthodes de résolution particulièrement, dans un environnement de type grille. Différents algorithmes seront présentés et les étapes d'approche pour exécuter l'application, en particulier, le problématique du partitionnement du problème ainsi que les mécanismes des communications synchrone et asynchrone seront rappellés. Une section de ce chapitre montre les interêts et principes de la simulation d'exécution des algorithmes de calcul sur grille. Différents outils de simulation seront présentés et comparés en insistant particulièrement sur SIMGRID, l'outil choisi pour réaliser nos travaux. Comme les algorithmes utilisés sont écrits en MPI (Message Passing Interface), les primitives MPI les plus utilisés sont passées en revue. Enfin, le chapitre se ferme sur l'utilisation du module SMPI (Simulation MPI) de SIMGRID qui simule le comportement et l'exécution réelle des applications MPI.\\ +Un second chapitre est consacré à l'étude de la performance des applications parallèles et distribuées, en particulier, la classe d'algorithmes qui nous interesse. Deux volets principaux sont concernés par cette étude : l'analyse de la performance et la prédiction de cette même performance à grande échelle. L'analyse de la performance de l'application essaie de déterminer le comportement du code selon les différents environnement d'exécution, mais aussi de chercher à optimiser le code en identifant les parties du code les plus consommatrices de ressources (CPU, mémoire, communications, ...) tout en éliminant certains bugs du code. Par ailleurs, la prédiction de la performance, comme son nom l'indique, essaie de reporter le comportement du code à grande échelle à partir de benchmarks effectués à moindre echelle. Surtout, les indicateurs de temps de calcul et de communication dans la grille sont capturés lors d'une telle prédiction. Une telle opération peut se faire sur une plateforme difficilement accessible dans la pratique ou même encore inexistante. Plusieurs outils d'analyse de la performance du code seront présentés ainsi qu' une méthode pour la prédiction de la performance du code. \\ +Le dernier chapitre de cette première partie avance nos motivations sur les contributions dans ce domaine choisi, pour la simulation de l'exécution des algorithmes concernés sur une grille de calcul afin d'analyser leurs performances mais surtout de pouvoir simuler et prédire les résultats d'exécution à grande échelle avec une grille composée de plus en plus de grappes d'ordinateurs et de plus en plus de processeurs et de coeurs. -\chapter*{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*} - (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 +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 +conccurente jusqu'à la détection de la convergence +locale qui peut être obtenue soit par l'atteinte d'un +nombre maximum fixé d'itérations soit que la différence +entre les valeurs du vecteur inconnu entre deux itérations successives est devenue +inférieure à la valeur résiduelle convenue. Cette condition de convergence +locale peut être écrite comme suit : +\begin{equation} + (k\leq \MI) \text{ or } (\|X_l^k - X_l^{k+1}\|\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 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} +\subsection{Partitionnement du problème} -\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} -\end{figure} +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. -%\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{figure}[!ht] +\centering +\begin{minipage}[t]{6.5cm} +\centering +\includegraphics [ width =5.5cm]{"3D data partitionning btw 2 clusters"} +\caption {Découpage d'une matrice tridimensionnelle entre deux clusters formés de 18 processeurs chacun} +\end{minipage} +\begin{minipage}[t]{1.4cm} +\centering +\end{minipage} +\begin{minipage}[t]{6.5cm} +\centering +\includegraphics [ width =5.5cm]{"1D-2D-3D Domain decomposition"} +\caption {Décomposition en domaines 1D, 2D et 3D} +\end{minipage} +%\caption{Partitionnement du problème} +\end{figure} -%\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 +340,722 @@ 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} +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}[!ht] +\centering +\begin{minipage}[t]{6.5cm} +\centering +\includegraphics [ width =5.5cm]{"Synchronous iterations model"} +\caption {Modèle de communication synchrone} +\end{minipage} +\begin{minipage}[t]{1.4cm} +\centering +\end{minipage} +\begin{minipage}[t]{6.5cm} +\centering +\includegraphics [ width =5.5cm]{"Asynchronous iterations model"} +\caption {Modèle de communication asynchrone} +\end{minipage} +%\caption{Partitionnement du problème} \end{figure} -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 + + +%\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 \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 d'une part et la variante multi-décomposition(multisplitting) d'autre part. + \subsection{Algorithme de Jacobi} +L'algorithme de Jacobi est une des plus simples méthodes de résolutions d'un système d'équations linéaires [3,4]. + +Soit le système d'équations linéaires suivant : + +\begin{equation} +\label{eq:2} +Ax = b +\end{equation} +où : + +\begin{tabbing} +\hspace{2cm}\=\kill + \> A est une matrice carrée réelle creuse inversible de taille n, \\ + \> x le vecteur inconnu de taille n, \\ + \> et b un vecteur constant.\\ +\end{tabbing} + +\eqref{eq:2} peut s'écrire : + +\begin{equation*} + \left(\begin{array}{ccc} + a_{1,1} & \cdots & a_{1,n} \\ + \vdots & \ddots & \vdots\\ + a_{n,1} & \cdots & a_{n,n} + \end{array} \right) + \times + \left(\begin{array}{c} + x_1 \\ + \vdots\\ + x_n + \end{array} \right) + = + \left(\begin{array}{c} + b_1 \\ + \vdots\\ + b_n + \end{array} \right) +\end{equation*} + +Notons : \\ +D la matrice carrée de taille n formée par la diagonale de A. On suppose qu'aucun élément $a_{i,i}$ n'est égal à 0. \\ +L (resp. U) la matrice carrée de taille n formée par les éléments du bas (resp. haut) de A.\\ +On a donc : + +\begin{equation*} +D=\left( \begin{array}{ccc} +a_{1,1} & \cdots & 0 \\ +\vdots & \ddots & \vdots \\ +0 & \cdots & a_{n,n} +\end{array}\right) +\space +, \hspace{0,1cm}L=\left( \begin{array}{ccc} +0 & \cdots & 0 \\ +\vdots & \ddots & \vdots \\ +a_{n,1} & \cdots & 0 +\end{array}\right) +\space +et \hspace{0,2cm}U=\left( \begin{array}{ccc} +0 & \cdots & a_{1,n} \\ +\vdots & \ddots & \vdots \\ +0 & \cdots & 0 +\end{array}\right) +\end{equation*} + +Comme A = D + (L + U) et si $D^{-1}$ est l'inverse de la matrice diagonale D, on peut écrire : + +\begin{equation*} +Ax = b \Leftrightarrow ( D + L + U )x = b +\end{equation*} + +\begin{equation*} +\Leftrightarrow Dx = -(L+U)x + b +\end{equation*} + +\begin{equation} +\label{eq:3} +\Leftrightarrow ( x = D^{-1} \times [-(L+U)] x + D^{-1} b) +\end{equation} +Cette dernière égalité est l'equation $du point fixe$. L'algorithme itératif de Jacobi Figure~\ref{algo:01} (version séquentielle) et ses variantes découle de cette équation [4]. Si $x^{(k)}$ est la valeur approchée du vecteur inconnu à l'itération $k$, on a d'après \eqref{eq:3} avec un $x^{0}$ initial donné : + +\begin{equation} +x^{(k+1)} = D^{-1} \times [-(L+U)] x^{(k)} + D^{-1} b +\end{equation} + +\begin{figure}[!t] +\begin{algorithmic}[1] +\Input $A_{ij}$ (Matrice d'entrée), $b_{i}$ (Vecteur du membre droit), $n$ (Taille des vecteurs) et des matrices, $xOld_{i}$ (vecteur solution à l'itération précédente) +\Output $x_{i}$ (Vecteur solution)\medskip + +\State Charger $A_{ij}$, $b_{i}$, $n$, +\State Assigner la valeur initiale $x^0$ +\State \textbf{repeat} +\For {$i=0,1,2,\ldots (n-1)$} +\State $x_i \leftarrow 0$ +\For {$j=0,1,2,\ldots (n-1) \hspace{0.1cm} et \hspace{0.1cm} j \neq i$} +\State $x_{i} \leftarrow x_{i} + A_{ij} \times xOld_{j}$ +\EndFor +\For {$i=0,1,2,\ldots (n-1)$} +\State $xOld_{i} \leftarrow ( b_{i} - x_{i} ) \quad {/} \quad A_{ii}$ +\EndFor +\EndFor +\State \textbf{Until} {( Obtention de la condition de convergence )} + +\Statex +\end{algorithmic} +\caption{Algorithme itératif de Jacobi} +\label{algo:01} +\end{figure} + +La condition de convergence est déterminée au début du traitement. La méthode permet de passer à large échelle en distribuant l'exécutuion de l'algorithme sur un environnement de grille de calcul. + +\subsection{Méthode de résolution GMRES} + +La méthode native GMRES ou "Generalized Minimal Residual", développée par Saad et Schultz en 1986, est une des méthodes itératives les plus utilisées pour résoudre un système d'équations linéaires ou non [3,4,43,44,45]. Elle est basée sur la minimisation de la norme euclidienne d'un vecteur résidu obtenu à chaque itération par une projection sur un espace de Krylov. Plus précisement, soit le système d'équations \eqref{eq:2}. Un sous-espace de Krylov d'ordre {m} est défini comme suit : + +\begin{equation} +\label{eq:Krylov} +K_m = Vect \{ b, Ab, A^2b, ..., A^{m-1}b \} +\end{equation} + +où : Vect désigne l'espace généré par les vecteurs en argument. + +Il est démontré [3,..] que le vecteur projeté $x_m$ sur $K_m$ donne une valeur approchée de la solution exacte du système d'équations en minimisant le résidu $r_m$ tel que : + +\begin{equation} +\label{eq:residu} +r_m = Ax_m - b +\end{equation} +On suppose que les vecteurs de l'équation \eqref{eq:Krylov} sont linéairement indépendants. Comme le montre cette équation, la taille des vecteurs de base augmente linéairement avec m qui varie de 0 à $n-1$ (n étant la taille initiale de la matrice A) entrainant à chaque itération un besoin de stockage de plus en plus grand. \\ + +Afin de réduire et optimiser l'algorithme, on peut combiner avec d'autres méthodes telles que les itérations de Arnoldi [] utilisant la procédure d'orthogonalisation de Gram-Shmidt [] pour trouver une base orthonormée de l'espace $K_m$ notée $Q_m = [q_1, ..., q_m]$. On peut donc écrire : + +\begin{equation} +\label{eq:proj} +\forall x_m \in K_m, x_m = Q_m y +\end{equation} + +et le résidu dont la norme est à minimiser peut s'écrire : +\begin{equation} +\label{eq:residu} +r_m = A Q_m y - b +\end{equation} + +D'après cette procédure, il existe une matrice de Hessenberg $H_m$ de taille m telle que : +\begin{equation} +\label{eq:hessen} +H_m = Q^T_m A Q_m +\end{equation} +En introduisant la matrice notée $\tilde{H}_m$ obtenue par l'ajout d'une ligne supplémentaire à $H_m$ avec la seule valeur non nulle est celle à la position (m+1,m), on démontre qu'on a la relation suivante [3,43,44,45] : + +\begin{equation} +\label{eq:hessen1} +A Q_m = Q_{m+1} \tilde{H}_m +\end{equation} + +Ainsi, le résidu donné par l'équation \eqref{eq:residu} peut s'écrire en utilisant \eqref{eq:hessen1} : +\begin{equation*} +\label{eq:residu1} +(r_m = Q_{m+1} \tilde{H}_m y - b) \\ +\Leftrightarrow (\|r_m\| = \|Q_{m+1} \tilde{H}_m y - b\|) +\end{equation*} + +Comme la norme ne change pas après la multiplication avec la matrice unitaire $Q^{-1}_m$, on a : +\begin{equation*} +\label{eq:norme1} +\|r_m\| = \|Q_{m+1} \tilde{H}_m y - b\| = \|Q^{-1}_m Q_{m+1} \tilde{H}_m y - Q^{-1}_m b\| +\end{equation*} + +Ou : + +\begin{equation} +\label{eq:norme2} +\|r_m\| = \|\tilde{H}_m y - Q^{-1}_m b\| +\end{equation} + +Or : +\begin{equation} +\label{eq:q_1} +Q^{-1}_m b = \left( \begin{array}{c} +q^{-1}_1 b \\ +q^{-1}_2 b \\ +\vdots \\ +q^{-1}_{m+1} b +\end{array}\right) +\end{equation} + +Et comme les colonnes $q_j$ de $Q_m$ forment une base orthonormale de l'espace de Krylov $K_m$, on a : -\subsection{Méthode de résolution GMRES} +\begin{equation*} +\label{eq:q1} +q_1 = \frac{b}{\|b\|} +\end{equation*} +et : +\begin{equation*} +\label{eq:q_1j} +\forall j > 1, q^{-1}_{j} b = 0 \text { et } q^{-1}_1 b = \|b\| +\end{equation*} +Donc, l'équation \eqref{eq:q_1} peut s'ecrire : -Native +\begin{equation} +\label{eq:q_f} +Q^{-1}_m b = \|b\| e_1 \text{ avec } e_1 = (1,0, ..., 0)^T +\end{equation} + +Finalement, la norme du résidu à minimiser peut s'écrire à partie de \eqref{eq:norme2} et \eqref{eq:q_f} : + +\begin{equation} +\label{eq:norme3} +\|r_m\| = \| \tilde{H}_m y - \text { } \|b\| \text { } e_1 \| +\end{equation} +La méthode des moindres carrés peut être utilisée pour effectuer cette minimisation et trouver $y$. On utilise après la relation \eqref{eq:proj} pour déterminer la valeur approchée de la solution à l'itération m. + +\begin{equation*} +\label{eq:proj1} +x_m = Q_m y +\end{equation*} +L'algorithme de GMRES repose sur ces deux dernières equations. +Une autre amélioration de l'algorithme, surtout en terme de réduction des vecteurs à maintenir en mémoire mais aussi en termes de temps de calcul pour atteindre la convergence, est le "redémarrage" [43]. Il s'agit de "redémarrer" l'algorithme après une tranche de k itérations, k étant fixé par l'utilisateur au départ. A chaque redémarrage, la valeur initiale $x_0$ est remplacée par le dernier $x_m$ trouvé et $r_0$ par le dernier $r_m$. \\ + +Le pseudo-code de l'algorithme GMRES optimisé avec les itérations d'Arnoldi avec un redémarrage est donné à la Figure~\ref{algo:02}. + +\begin{figure}[!t] +\begin{algorithmic}[1] +\Input \\ +$A_{ij}$ (Matrice d'entrée), $b_{i}$ (Vecteur du membre droit), $n$ (Taille des vecteurs) et des matrices, \\ +$m$ (Nombre d'itérations avant redémarrage), $h_{ij}$ (Matrice de Hessenberg), \\ +$q_i$(Suite de vecteurs constituant une base orthonormée de l'espace de Krylov $K_i$), \\ +$w_i$ (variable intermédiaire) +\Output $x_{m}$ (Vecteur solution)\medskip + +\State Charger $A_{ij}$, $b_{i}$, $n$, +\State Assigner la valeur initiale $x^0$ +\State $r_0 \leftarrow b - Ax_0$ +\State $q_1 \leftarrow \frac{r_0}{\|r_0\|}$ +\State \textbf{repeat} +\For {$j=0,1,2,\ldots m$} +\For {$i=1,2,\ldots j$} +\State $h_{i,j} = (A q_j, q_i)$ +\State $x_i \leftarrow 0$ +\State $w_{j+1} = A q_j - \sum_{i=1}^j h_{i,j} q_i$ +\State $h_{j+1,j} = \| w_{j+1} \|$ +\State $h_{i,j} = \frac {w_{j+1}} {h_{j+1,j}}$ +\EndFor +\EndFor +\State Calculer la solution approchée $x_{m}$ +\State $x_{m} = x_0 + Q_m y_m \hspace{0.1cm} tel \hspace{0.1cm} que \hspace{0.1cm} y_m \hspace{0.1cm} minimise \hspace{0.1cm} \| \tilde{H}_m y - \hspace{0.1cm} \|b\| \hspace{0.1cm} e_1 \|, y \in R^m.$ +\State Redémarrage +\State $r_m \leftarrow b - Ax_m$ +\State Réinitialiser pour le redémarrage +\State $x_0 \leftarrow x_m$ +\State $r_0 \leftarrow r_m$ +\State $q_1 \leftarrow \frac{r_0}{\|r_0\|}$ +\State \textbf{Until} {( Obtention de la condition de convergence : $\| r_m \|$ \hspace{0.1cm} est satisfaisant )} +\Statex +\end{algorithmic} +\caption{Algorithme itératif GMRES avec redémarrage} +\label{algo:02} +\end{figure} -Version « two-stage » +%%%% ?? Version « two-stage » \subsection{Solveur multisplitting} -Version simple +Dans cette classe des méthodes itératives de résolution de système d'équations linéaires $AX=B$, le solveur "multisplitting" reste une des plus utilisées et une des plus efficaces en version parallèle. On suppose qu'on va répartir le traitement de la résolution du problème entre les $L$ clusters d'une grille de calcul donné. La base de la méthode est de trouver un découpage efficient de la matrice initiale $A$ en plusieurs sous-matrices $(A_{lm}), l,m \in \{1,...,L\}$ de taille $n_l \times n_m$ [3,4,5]. Ce découpage doit se faire sans recouvrement et doit être exhaustif, c'est-à-dire on doit retrouver la matrice $A$ avec l'union des sous-matrices, c'est-à-dire $\sum_l n_l = \sum_m n_m = n$. A chaque sous-matrice sera associé d'une part, les sous vecteurs $X_l$ du vecteur inconnu $X$ et $B_l$, sous vecteur du deuxième membre $B$, tous les deux de taille $n_l$. Ainsi, l'équation initiale peut s'écrire après découpage : -Version améliorée +Ainsi, \eqref{eq:2} peut s'écrire : -\section*{1.3 SIMGRID/SMPI : Simulateur d'exécution d'algorithmes -parallèles MPI dans une grille de calcul} +\begin{equation} + \label{eq:13bis} + \left(\begin{array}{ccc} + A_{1,1} & \cdots & A_{1,L} \\ + \vdots & \ddots & \vdots\\ + A_{n,1} & \cdots & A_{L,L} + \end{array} \right) + \times + \left(\begin{array}{c} + X_1 \\ + \vdots\\ + X_L + \end{array} \right) + = + \left(\begin{array}{c} + B_1 \\ + \vdots\\ + B_n + \end{array} \right) +\end{equation} + +Une fois le découpage effectué, chaque sous-système \ref{eq:13bis} est attribué à un cluster pour sa résolution indépendante de façon itérative dans ce que la méthode de multisplitting décrit comme les $"iterations$ $internes"$ (interne au cluster). Dans le cadre de nos travaux, l'algorithme GMRES, précédemment étudié, est utilisé pour résoudre localement le sous-système \ref{eq:13}. + +\begin{equation} + \label{eq:13} + \left\{ + \begin{array}{l} + A_{\ell\ell}X_\ell = Y_\ell \text{, tel que}\\ + Y_\ell = B_\ell - \displaystyle\sum_{\substack{m=1\\ m\neq \ell}}^{L}A_{\ell m}X_m + \end{array} + \right. +\end{equation} +Les résultats intermédiaires sont échangés entre les clusters voisins à la fin de chaque itération de la $"boucle$ $externe$. Le pseudo-code décrit dans la figure Figure~\ref{algo:03} montre les étapes essentielles de l'algorithme de multisplitting en parallèle.\\ +La convergence globale de l'algorithme sera détectée dès que la convergence locale dans chaque cluster est atteinte. La condition de convergence est donnée par \ref{eq:14} où à chaque itération externe k, $X^k_l$ et $X^{k+1}_l$ donne le résidu entre deux résultats consécutifs $k$ et $k+1$ au niveau du cluster $l$, $\epsilon$ le seuil d'erreur accepté et $MaxIter$ le nombre maximum d'itérations convenu. + +\begin{equation} + \label{eq:14} + (k=\MI) \text{ or } (\|X_\ell^k - X_\ell^{k+1}\|\leq\epsilon) +\end{equation} + +\begin{figure}[!t] +\begin{algorithmic}[1] +\Input $A_\ell$ (Matrice d'entrée), $B_\ell$ (Vecteur du membre droit) +\Output $x_{m}$ (Vecteur solution)\medskip + +\State Charger $A_\ell$, $B_\ell$ +\State Assigner la valeur initiale $x^0$ +\For {$k=0,1,2,\ldots$ jusqu'à la convergence globale} +\State Redémarrer la boucle d'iterations externes $x^0=x^k$ +\State Boucle d'iterations internes : \Call{InnerSolver}{$x^0$, $k+1$} +\State\label{algo:03:send} Envoyer les éléments partagés $X_\ell^{k+1}$ aux clusters voisins +\State\label{algo:03:recv} Recevoir les éléments partagés dans $\{X_m^{k+1}\}_{m\neq \ell}$ +\EndFor + +\Statex + +\Function {InnerSolver}{$x^0$, $k$} +\State Calculer le membre droit local $Y_\ell$: + \begin{equation*} + Y_\ell = B_\ell - \sum\nolimits^L_{\substack{m=1\\ m\neq \ell}}A_{\ell m}X_m^0 + \end{equation*} +\State Résoudre le sous-système $A_{\ell\ell}X_\ell^k=Y_\ell$ avec la méthode GMRES parallèle +\State \Return $X_\ell^k$ +\EndFunction +\end{algorithmic} +\caption{Solveur Multisplitting utilisant la méthode GMRES en local (version parallèle)} +\label{algo:03} +\end{figure} + +%%%%Version améliorée + +\section{Simulateurs d'exécution d'algorithmes parallèles dans une grille de calcul} + +\subsection{Calcul sur grille de calcul} +Une grille de calcul est caractérisée par "un type de système parallèle et distribué qui permet le partage, la sélection et l'aggrégation de ressources distribuées géographiquement selon leurs capacités" [25] afin de résoudre un problème complexe donné. Ainsi, une grille est composée d'un ensemble de grappes de machines interconnectées entre elles à travers un réseau de communication qui peut s'étendre sur des zones géographiques éloignées (Figure \figref{gridA}). Les capacités de calcul, les mémoires, les applications et les systèmes de stockage sont partagées par les applications parallèles et distribuées. Le calcul sur une grille est caractérisé par un environnement "hétérogène, dynamique et scalable". \\ + +\mfigure[h]{width=8cm}{"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 aux mémoires (DRAM, stockage) utilisées dans la grille de calcul peut être aussi être aussi de types différents. Enfin, la topologie ainsi que la performance des réseaux de communications interconnectant les éléments de la grille peuvent être aussi avoir des débits complètement hétérogènes. \\ +Le caractéristique dynamique de la grille résulte de la relative facilité de changer de configuration. On peut ainsi tailler dynamiquement l'allocation des ressources de la grille aux utilisateurs selon les besoins de leur demande respective. Cet aspect a été élargi à "l'élasticité" de l'environnement dans le cadre du "cloud computing". \\ +Enfin, la scalabilité de la grille de calcul découle de sa conception modulaire permettant d'ajouter d'autres composants selon les besoins. Pour augmenter par exemple la capacité de calcul de la grille, il suffit d'ajouter de nouveaux clusters pour une plus grande puissance globale de la grille. \\ + +Le milieu de la recherche dispose d'une grille de calcul dédié : le Grid'5000 [26, 27] est une grille répartie géographiquement dans différentes villes de France (Figure \figref{grid5000RG} ) mettant à disposition un "banc d'essai polyvalent à grande échelle" pour les expérimentations de la recherche en informatique particulièrement le calcul parallèle sur grille, sur le cloud, le calcul à haute performance mais aussi sur le Big Data. Grid'5000 permet aux utilisateurs l'accès à des ressources importantes de calcul dans un environnement complètement configurable et controllable. Il peut aussi fournir une trace détaillée ainsi que d'autres informations de mesure sur le comportement de l'application lors de l'exécution pour une étude ultérieure. + +\mfigure[h]{width=8cm}{"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 d'un environnement de calcul particulier répondant aux besoins précis de l'application à un moment donné. Selon la classification dans [30], la simulation d'applications sur une grille de calcul rejoint la classe de simulation "virtuelle" par l'utilisation d'équipements de simulation par des personnes réelles. De façon générale, le simulateur utilise une échelle de temps "discret", c'est-à-dire le temps est découpé en intervalles qui peuvent être réguliers ou non. Dans le cas d'un système à temps discret régulier, le simulateur maintient et met à jour éventuellement un ensemble de "variables d'état" qui reflètent l'état du système physique à un instant t donné. Un "évenement" est associé à chaque instant donné à une "transition d'état". Pour des comparaisons futures, on distingue le "temps physique" comme étant le temps considéré au niveau du système physique, du "temps de simulation" et "le temps de l'horloge murale" désigne le temps de simulation du modèle. Toutefois, le "temps de simulation" est une notion abstraite utilisée par le simulateur pour évaluer le temps de simulation. Il est défini [30] comme étant "un ensemble de valeurs totalement ordonné E où chaque valeur représente un temps du système physique à modéliser et qui vérifie les conditions suivantes:" \\ +Soient E l'ensemble des temps discrets de simulation et P l'ensemble des temps du système physique. + +\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 gestion des groupes de processus en accord par exemple avec des architectures complexes comme les grilles de calcul. + +\item[$\bullet$] Les types de données : Permettent de créer des structures de données complexes en mémoire à partir des types de données de base comme l'entier, le float, etc... + +\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}{"MPI"} {Groupes et communicateur (a) - MPI - Opérations collectives (b)} {MPI} -\subsection{Simulateur SIMGRID} +Au niveau de la communication, le transfert de message peut se faire d'un processus vers un autre (point à point). Pour cela, les routines MPI\_SEND et MPI\_RECV et leus variantes permettent respectivement d'envoyer et de recevoir un message. L'adresse du tampon contenant le message à traiter est passée à ces fonctions avec le type de données ainsi que le nombre d'objets. La destination dans le cas d'un envoi est spécifiée par le rang du processus d'arrivée du message dans le communicateur considéré. Une variable de statut de l'opération permet de connaitre si l'opération a réussi ou a échoué. Cet échange peut se faire de manière synchrone ou asynchrone(resp. bloquant ou non bloquant). \\ +Contrairement à une communication point à point, une communication dite collective transfère un message à partir d'un processeur vers un ensemble de processeurs. L'exemple le plus courant est le "broadcast" ou diffusion où un processeur envoie le même message à destination d'un ensemble de processeurs. La figure \figref{MPI}-b montre les échanges entre les processus après l'appel à cette opération mais aussi d'autres types de communications collectives. Un processus distribue avec MPI\_Scatter une structure de données à d'autres processus participants tandis que MPI\_Gather rassemble des données de plusieurs processus participant en une seule structure. Enfin, les opérations de réduction appliquent une opération (somme, produit, maximum, minimum, etc ...)à un ensemble de processus et retourne le résultat vers le processus appellant. +La synchronisation des processus peut être obtenue avec la routine MPI\_Barrier qui, une fois lancée par un processus, bloque ce dernier jusqu'à ce que tous les processus de son groupe atteigne cette barrière comme un point de rendez-vous. -\section*{1.4 Motivations} +\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 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]. -\section*{1.5 Conclusion partielle} +Simgrid est conçu sur une simulation basée sur les évenements ("event driven") [26, 35] à un niveau d'abstraction et de fonctionnalités répondant aux applications et aux infrastructures. Cinq composants d'abstraction constituent le fonctionnement de Simgrid : +\begin{itemize} + +\item[$\bullet$]Un "agent" est une entité qui assure l'ordonnancement de l'application et exécute le code sur une "location"; + +\item[$\bullet$]Une "location" est une hôte de l'environnement de simulation sur laquelle l'agent s'exécute. Outre les données propres à la location, des boîtes aux lettres sont conçues pour permettre les échanges de données avec d'autres agents; + +\item[$\bullet$]Une "tâche" est une activité de l'application simulée. Elle se décline sous forme d'un calcul (temps de calcul nécessaire) ou d'un transfert de données (volume de données à échanger); + +\item[$\bullet$]Un "chemin" décrit la liaison entre les locations. Il est utilisé par les agents lors d'un transfert de données à calculer le temps de transfert en tenant compte du routage à appliquer pour une telle liaison. + +\item[$\bullet$]La communication entre agents se fait à travers un "canal". Cette abstraction modélise la communication à travers un port entre des agents dans les locations. + +\end{itemize} + +Simgrid offre pour l'utilisateur plusieurs types d'interfaces de programmation [5,9]: MSG qui simule les "processus séquentiels conccurents", SimDAG qui est utilisé pour simuler des tâches parallèles modélisées en graphe acyclique direct et SMPI qui simule et exécute les applications écrites en MPI sans ou avec des modifications mineures. Outre le langage C natif, Simgrid accepte des applications écrites en C++, Java, Fortran, Lua ou encore Ruby. + +De point de vue pratique, la figure \figref{simgrid1} présente la structure et les éléments de la plateforme de simulation Simgrid. Elle est composée des trois parties différentes suivantes : + +\begin{itemize} + +\item[$\bullet$] Le scénario de la simulation qui constitue les "modèles de ressources" du système. Evidemment, il comprend le code de l'application à exécuter dans le simulateur avec ses différents paramètres d'entrée mais aussi son modèle de déploiement. Un autre composant important de ce scénario aussi est le fichier, généralement au format XML, modélisant les détails de la topologie et l'architecture de l'environnement d'exécution. Il détermine par exemple pour le cas d'une grille de calcul, le nombre et les caractéristiques des clusters contribuant à cet environnement. Pour chaque cluster, les spécifications des serveurs (nombre de cores ou de processeurs, puissance en Flops, taux de disponibilité, ...)sont définies ainsi que les propriétés des réseaux de liaison entre ces différents composants de la grille (topologie du réseau, débit et latence, table de routage, ...). + +\item[$\bullet$] Le simulateur proprement dit comprenant l'application à exécuter et le nouay du simulateur. + +\item[$\bullet$] Les fichiers de sortie comprenant les résultats de la simulation de l'application ainsi que d'autres fichiers de monitoring de l'exécution comme un fichier de logging et de statistiques. Simgrid peut générer aussi des données pouvant être utilisées pour représenter visuellement le déroulement et la trace de la simulation dans le temps. + +\end{itemize} + +\mfigure[h]{width=8cm}{"Simgrid - In a nutshell"} {SIMGRID : Les éléments de la plateforme de simulation} {simgrid1} + +Les applications sous-tendant les expérimentations effectuées dans le cadre de ces travaux ont été ecrites en C et utilisent les librairies MPI. Simgrid dispose de l'interface SMPI (Simulated MPI) qui peut exécuter un code MPI parallèles sans aucune ou à la limite très peu de modifications. A titre d'exemple, les variables globales doivent être transférées dans un contexte local dans l'application SMPI. Simgrid/SMPI assure l'implémentation de plus de 80\% des routines de la librairie MPI 2.0. Le code est exécuté réellement dans le simulateur dans l'environnement virtuel spécifié sauf que les communications sont interceptées et le temps de transfert calculé en tenant compte du partage des ressources existantes (par exemple le partage de la bande passante entre processus concurrents sur les réseaux de liaison).La scalabilité de Simgrid peut être obtenue par appel à des routines SMPI qui utilisent des structures de données partagées entre les processus parallèles réduisant ainsi la quantité de mémoire utilisée et permettant une montée en charge non négligeable. Toutefois, dans ce cas, comme tous les processus utilisent la même structure de données, la véracité des résultats obtenus n'est pas importante. + + +\section{Conclusion partielle} -\chapter*{Chapitre 2 : Etat de l'art et travaux de recherche associés} -\section*{2.1 Concepts et définitions} +\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 +1064,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 +1073,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 tandis que l'efficacité +a une valeur entre 0 et 1. On peut démontrer que l'efficacité +est une fonction décroissante du nombre de processeurs n tandis qu'elle +est une fonction croissante de la taille du problème. + +Dans le cadre de nos travaux, nous avions introduit une métrique utilisée +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,575 +1094,539 @@ 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) +(\|X_l^k - X_l^{k+1}\|\leq\epsilon) \end{equation*} \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=10cm}{"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. +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. -\section*{2.2 Problématique sur la prédiction à large échelle de la performance des applications} +\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 +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éponse à une réservation des ressources nécessaires pour lancer le système n'est +pas toujours immédiate mais en plus, le coût peut ne pas être négligeable +dans un contexte de rareté des machines super puissantes pourtant +très sollicitées par différents acteurs {[}\dots {]}. Cette problématique +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}{"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}{"MIMD Distributed Memory"} {Modèle MIMD Mémoire Distribué} {MIMDDM} +\mfigure[h]{width=8cm}{"MIMD Shared memory - SMP"} {Modèle MIMD Mémoire partagé} {MIMDSM} + +\mfigure[h]{width=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èdent à la mémoire partagée via un réseau d'interconnection +(généralement, de type GigabitEthernet (renvoi) ou Infiniband (renvoi)). +Il existe trois types d'implémentation : le crossbar, le Omega-Network et le Central Databus. -\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 Top5000.org +{[}14{]} classe suivant différents critères les plus performantes. +Ainsi, la figure \figref {power} montre l'évolution de la puissance +de calcul mondiale dont le top actuel développe un pic de performance +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}{"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}{"UMA architecture"} {Mémoire MIMD: Architecture UMA} {UMA} + +\mfigure[h]{width=8cm}{"NUMA architecture"} {Mémoire MIMD: Architecture NUMA} {NUMA} + +\mfigure[h]{width=7cm}{"COMA architecture"} {Mémoire MIMD: Architecture COMA} {COMA} + +Malgré que dans le cadre de nos travaux, nous n'avions +pas eu une contrainte particulière en termes de système de stockage, +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 +1635,346 @@ 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. + +\mfigure[h]{width=8cm}{"Performance Analysis techniques"} {Classification des techniques d'analyse de la performance} {anaperf} + +Cette approche à trois étapes commence par la collecte des données sur la performance du code qui consiste à deux techniques les plus utilisées à savoir le "sampling" (ou "l'échantillonage") et "l'instrumentation basée sur les évenements". +\begin{itemize} +\item [$\bullet$] Le "sampling" ou "l'echantillonage" capture les données décrivant l'état du code lors de l'exécution du programme à chaque instant défini par la fréquence de l'echantillonage. Il est réalisé généralement avec la mise en place d'un timer qui déclenche la collecte des données selon une période définie. Ces dernières se rapportent sur les statistiques relatives aux appels de fonctions ("call-path" des fonctions) mais aussi sur les compteurs matériels [22]. Ainsi, il est d'usage de collecter le temps d'exécution d'une fonction ou combien de fois la fonction a été appellée ou encore de façon plus détaillée, combien de fois une ligne de code est exécutée. Evidemment, l'efficacité de la méthode dépend du taux d'échantillonnage: les informations entre deux points de collecte ne sont pas disponibles pour l'analyse ultérieure. Par contre, la surcharge engrendrée par la technique peut être contrôlée par l'utilisateur par un choix adéquat de la fréquence de l'echantillonage. \\ +L'alternative pour collecter les données de la performance d'une application parallèle se porte sur l'instrumentation basée sur les évenements. D'abord, de façon générale, l'instrumentation du code consiste à ajouter manuellement ou automatiquement des instructions supplémentaires à des endroits choisis afin de rapporter à chaque passage des informations spécifiques. A titre d'exemple, on peut positionner un timer au début d'une portion du code et d'arrêter ce timer à la sortie de cette région. On peut ainsi collecter le temps total d'execution consommé par l'application pour exécuter cette partie du programme. Cette technique est largement utilisée par exemple pour détermijner le temps de communication nécessaire lors d'un appel d'une instruction MPI de transfert ou collective (MPI\_send, MPI\_receive ou autre MPI\_Barrier). Cette modification directe qui nécessite une récompilation du code est aussi appellée "instrumentation au niveau de la source". D'autres techniques utilisant des outils existent telles que les "libraries wrapping" ou la "réécriture du code binaire" [22]. Ces dernières n'ont pas besoin d'une recompilation du code. + +\item [$\bullet$] La deuxième étape du processus de la collecte des données en vue d'une future analyse consiste à enregister soit en mémoire soit sur un support de stockage externe les données obtenues lors de l'étape précédente. Deux techniques peuvent être exploitées à cette fin. D'abord, le "logging" ou le "tracing" permet d'ajouter le facteur temps sur les données collectées. Ainsi, avant le stockage, chaque entrée de données est estampillée d'une date de l'évenement (au format date - heure). Cette opération peut ajouter un temps de surcharge non négligeable lors de l'exécution.\\ +Afin de réduire cette dernière mais aussi pour optimiser la taille du fichier de trace obtenu, la technique de "summarization" consiste à agréger les données après la collecte et de ne stocker que le minimum d'informations utiles. Ce dernier est généralement appellé le "profile" de l'application [21,22]. Certains détails peuvent être perdus avec cette méthode mais il s'agit ici de faire une balance entre la taille la granularité de l'information et la taille des données stockées. + +\item [$\bullet$] La troisième et dernière étape de l'analyse de la performance concerne la visualisation des données collectées en vue de l'analyse proporement dite et des décisions à prendre pour améliorer et optimiser l'exécution de l'application. Dans la même ligne de l'étape précédente, soient les données sont visualisées "au fil du temps" en suivant l'exécution du code sur les différentes machines de l'environnement parallèle, soient elles sont représentées par un groupement selon un facteur compréhensible par l'analyste (par fonction par exemple), on est en présence d'une technique générant un "timeline" 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 (Integrated Performance Monitoring), comme tous les outils d'analyse de la performance particulièrement pour un code MPI, fournit d'une part les statistiques du profiling du code comprenant les indicateurs lors des appels de routines MPI mais aussi d'autre part, le tracing du code collectant les détails de l'historique et l'ordre des évènemments passés MPI lors de l'exécution du code [37, 38]. L'inventaire de ces évenements se fait par une "mesure directe". IPM se montre particulèrement efficace pour détecter les désequilibres de charge entre les processeurs pour une application parallèle. De plus, son utilisation entraîne une surcharge de calcul négligeable. + +\item [$\bullet$] TAU (Tuning and Analysis Utilities) a été conçu à l'Université d'Oregon comme un outil open source d'évaluation de performance [24, 42]. Il intègre de façon non intrusive le profiling et le tracing constituant une plateforme complète couvrant les trois étapes de l'analyse d'une application parallèle. L'instrumentation du code peut être effectuée d'une façon complètement automatique avec un package fourni ("PDT - Program Database Toolkit - for routines")collectant toutes les informations sur les régions et hotspots du code, l'utilisation mémoire, les boucles, les entrées/sorties,...Selon le paramètrage de lancement, TAU peut collecter des informations les plus fines telles que le temps passé à chaque instruction dans une boucle ou le temps passé dans les communications à une étape du programme particulièrement dans les instructions collectives MPI par exemple. Toutes ces données peuvent par la suite être visualisées sous forme graphique (Paraprof 3D browser) pour une analyse fine afin d'optimiser la performance. + +\item [$\bullet$] SCALA ou SCAlabity Analyzer est orienté particulèrement dans l'analyse de la performance des applications sur sa scalabilité lors de la montée en charge. Outre la prédiction de la performance (voir la section suivante), SCALA utilise les fonctionnalités avancées actuelles du compilateur pour la mise au point (debugging) de la dite performance et d'une éventuelle restructuration du code parallèle d'une part mais aussi d'estimer l'impact des variations sur l'environnement matériel d'exécution. L'outil permet de générer des suggestions de modifications du code pour une stratégie d'optimisation une fois l'analyse de la performance achevée. +\end{itemize} + +\section{Méthodes de prédiction de la performance des applications parallèles} +La prédiction de la performance des applications distribuées se présente comme une suite logique de l'analyse de la performance des dites applications. En effet, outre la compréhension du système ainsi que la collecte des détails sur l'exécution du système qui constituent fondamentalement l'analyse de la performance, la prédiction de cette performance du code est plus complexe parce que dans ce cas, on essaie, à partir des résultats des analyses sur une plateforme matérielle donnée, d'estimer les résultats et le comportement du système sur une plateforme cible globalement plus puissante mais aussi avec des paramètres d'entrées différents. Dans la classe d'applications considérée dans ces travaux, les résultats de prédiction les plus importants sont le temps d'exécution et le temps de communication estimés. Les objectifs de la prédiction sont axés sur la minimisation du coût de l'opération mais aussi et surtout son efficacité et sa justesse exprimées par le taux d'erreur de la prédiction.\\ +Plusieurs méthodes sont utilisées pour réaliser une prédiction de la performance des programmes parallèles distribués en particulier sur une grille de calcul. On peut les classer en trois catégories : les méthodes "analytiques", celles basées sur le profiling et enfin, les méthodes de prédiction utilisant la simulation. Des auteurs ont proposé des combinaisons dénommées "hybrides" de ces méthodes [39]. +\begin{itemize} + +\item [$\bullet$] La méthode analytique de prédiction de la performance consiste à la modélisation mathématique du comportement et l'exécution du code à analyser. Une fois le modèle construit, on peut calculer les temps d'exécution et de communication en fonction des paramètres passés comme la taille du problème, la puissance de calcul disponible, les paramètres du réseau. La méthode est réalisée en deux étapes [39, 40]: +\begin{itemize} +\item [$\bullet$] (1) la collecte des informations sur l'ensemble ou uniquement sur des régions choisies du code par instrumentation en utilisant des outils existant ou par l'ajout de pragmas et des lignes de capture d'informations dans le code. Cette opération peut être répétées plusieurs fois pour avoir une série de résultats éliminant ainsi des éventuels effets de bord. Les données collectées sont consignées dans un fichier au format convenu pour la prochaine étape. +\item [$\bullet$] (2) la modélisation mathématique par la construction du modèle incluant la partie calcul mais aussi le volet réseau pour établir les formules reliant les paramètres en entrée de l'application avec les résultats obtenus. Cette étape peut être réalisée avec des techniques de statistiques d'analyse prédictive ou encore avec d'autres méthodes analytiques. La ou l'ensemble de fonctions décrivant le modèle peut être obtenue par itérations successives jusqu'à l'btention d'une erreur inférieure à un seuil préalablement établi. +\end{itemize} + +PMaC ou "Performance Modelling and Characterization" de l'Université de San Diego [42] montre un exemple d'une méthode analytique de prédiction de la perfomance. Il consiste d'une part à déterminer la "signature" de l'application qui regroupe les résumés détaillés des différentes opérations fondamentales effectuées par l'application [41]. D'autre part, le "profile" de l'environnement d'exécution est aussi modélisé en donnant une "caractérisation" du matériel (CPU, mémoire, réseau, ...) par des métriques d'exécution des opérations fondamentales pour une application donnée. Dans une seconde étape, à partir de ces données collectées, un modèle mathématique est établi pour construire un mapping entre l'environnement d'exécution et la signature de l'applcation. Ce modèle sera utilisé pour une prédiction de la performance sur un autre environnement mais aussi éventuellement pour une autre taille du problème. -\section*{2.4 Méthodes de prédiction de la performance de l'application parallèle} +\item [$\bullet$] Les méthodes de prédiction basées sur le profiling du code sont toujours accompagnées d'un tracing de l'exécution de l'application [40,41].Des outils de profiling et de tracing peuvent être utilisés afin de collecter les informations essentielles sur les différents blocs du code. Une fois ces informations disponibles, afin de déterminer la performance de l'application sur un autre environnement d'exécution, la prédiction de cette performance est obtenue en rejouant le fichier de trace sur cet environnement cible. +TAU, un outil d'analyse de performance déjà mentionné plus haut, utilise cette méthode de prédiction. En effet, il incorpore des outils d'instrumentation, de mesures de performance matérielle et d'analyse. +\end{itemize} -\section*{2.5 Conclusion partielle} +\section{Conclusion partielle} -\part*{PARTIE II - Travaux de contributions, résultats et perspectives} -\chapter*{Chapitre 3 : Comparaison par simulation à large échelle de la performance de deux algorithmes itératifs parallèles en mode asynchrone} +\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} -\section*{3.1 Protocoles et expérimentations} +La partie suivante va exposer la méthodologie adoptée et les travaux de contributions pour apporter des réponses à ces questions. -\section*{3.2 Résultats} -\section*{3.3 Conclusion partielle} +\part{PARTIE II - Travaux de contributions, résultats et perspectives} -\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} +\chapter{Comparaison par simulation à large échelle de la performance de deux algorithmes itératifs parallèles en mode asynchrone} -\section*{4.1 Protocoles et expérimentations} +\section{Protocoles et expérimentations} -\section*{4.2 Résultats} +\section{Résultats} -\section*{4.3 Conclusion partielle} +\section{Conclusion partielle} -\chapter*{Chapitre 5 : Modèle de prédiction de la performance à large échelle d'un algorithme itératif parallèle} +\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*{5.1 Approche et méthodologie} +\section{Protocoles et expérimentations} -\section*{5.2 Expérimentations et résultats} +\section{Résultats} -\section*{5.3 Conclusion partielle} +\section{Conclusion partielle} -\chapter*{Chapitre 6 : Conclusion générale et perspectives} +\chapter{Modèle de prédiction de la performance à large échelle d'un algorithme itératif parallèle} -\section*{6.1 Conclusion générale} +\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.} -{[}8{]} D. BERTSEKAS and J. TSITSIKLIS. Parallel and Distributed Computation, Numerical +{[}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. + +{[}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,} + +{[}37{]} IPM : Integrated Performance Monitoring - ipm-hpc.sourceforge.net + +{[}38{]} K. Fuerlinger, D. Skinner - Performance Analysis and Workload Workload Characterization with IPM - +\textit{University of California Berkeley} + +{[}39{]} B. Florin Cornea et J. Bourgeois - Performance Prediction of Distributed Applications Using Block Benchmarking Methods - \textit{LIFC, University of Franche-Comté,Montbéliard, France} + +{[}40{]} D. R. Martinez, V. Blanco, M. Boullon, J. C. Cabaleiro, T. F. Pena - Analytical Performance Models of Parallel Programs in Clusters - \textit {University of Santiago de Compostela, Spain - La Laguna University, Spain} + +{[}41{]} R. Allan, A. Mills - Survey of HPC Performance Modelling and Prediction Tools - \textit {Computational Science and Engineering Department, Daresbury Laboratory, Warrington - High Performance Systems Group, Department of Computer Science, University of Warwick, Coventry} + +{[}42{]} PMaC : Performance Modeling and Characterization - http://www.sdsc.edu/pmac/ + +{[}43{]} Haiwu He. Analyses avancées de la méthode hybride GMRES/LS-ARNOLDI asynchrone parallèle et distribuée pour les grilles de calcul et les supercalculateurs. \textit {Université des Sciences et Technologie de Lille, 2005}. + +{[}44{]} GMRES : Generalized minimal residual method. \textit {https://en.wikipedia.org/wiki/Generalized\_minimal\_residual\_method}. + +{[}45{]} G. Fasshauer - Numerical linear algebra - Illinois Institute of Technology - Department of Applied Mathematics - Chicago. 2006. Chapitre 14 - \textit {http://www.math.iit.edu/~fass/477577\_Chapter\_14.pdf}. +%%-------------------- +%% List of figures and tables + +%% 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}