[these_charles_emile.git] / These_RCE.tex

%% 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}
 
%%--------------------
%% Set the title, subtitle, defense date, and
%% the registration number of the PhD thesis.
%% The optional parameter is the subtitle of the PhD thesis.
%% The first mandatory parameter is the title of the PhD thesis.
%% The second mandatory parameter is the date of the PhD defense.
%% The third mandatory parameter is the reference number given by
%% the University Library after the PhD defense.
\declarethesis[Sous-titre]{Titre}{17 septembre 2012}{XXX}
 
%%--------------------
%% Set the author of the PhD thesis
\addauthor[email]{Prénom}{Nom}
 
%%--------------------
%% Add a member of the jury
%% \addjury{Firstname}{Lastname}{Role in the jury}{Position}
\addjury{Incroyable}{Hulk}{Rapporteur}{Professeur à l'Université de Gotham City \\ Commentaire secondaire}
\addjury{Super}{Man}{Examinateur}{Professeur à l'Université de Gotham City}
\addjury{Bat}{Man}{Directeur de thèse}{Professeur à l'Université de Gotham City}
 
%%--------------------
%% Change style of the table of the jury
%% \Set{jurystyle}{put macros for the style}
%\Set{jurystyle}{\small}

%%--------------------
%% Add the laboratory where the thesis was made
%\addlaboratory{Laboratoire Waynes Industry}

%%--------------------
%% Clear the list of the laboratories
%\resetlaboratories
 
%%--------------------
%% Set the English abstract
\thesisabstract[english]{This is the abstract in English}
 
%%--------------------
%% Set the English keywords. They only appear if
%% there is an English abstract
\thesiskeywords[english]{Keyword 1, Keyword 2}
 
%%--------------------
%% Set the French abstract
\thesisabstract[french]{Ceci est le résumé en français}
 
%%--------------------
%% Set the French keywords. They only appear if
%% there is an French abstract
\thesiskeywords[french]{Algorithmes itératifs, Performance, Simulation, Simgrid, Grid Computing}
 
%%--------------------
%% Change the layout and the style of the text of the "primary" abstract.
%% If your document is written in French, the primary abstract is in French,
%% otherwise it is in English.
%\Set{primaryabstractstyle}{\tiny}
 
%%--------------------
%% Change the layout and the style of the text of the "secondary" abstract.
%% If your document is written in French, the secondary abstract is in English,
%% otherwise it is in French.
%\Set{secondaryabstractstyle}{\tiny}
 
%%--------------------
%% Change the layout and the style of the text of the "primary" keywords.
%% If your document is written in French, the primary keywords are in French,
%% otherwise they are in English.
%\Set{primarykeywordstyle}{\tiny}
 
%%--------------------
%% Change the layout and the style of the text of the "secondary" keywords.
%% If your document is written in French, the secondary keywords are in English,
%% otherwise they are in French.
%\Set{secondarykeywordstyle}{\tiny}
 
%%--------------------
%% Change the speciality of the PhD thesis
%\Set{speciality}{Informatique}
 
%%--------------------
%% Change the institution
%\Set{universityname}{Universit\'e de Franche-Comt\'e}
 
%%--------------------
%% Add the logos of the partners or the sponsors on the front page
%\addpartner[image options]{image name}

%%--------------------
%% Clear the list of the partner/sponsor logos
%\resetpartners

%%--------------------
%% Change the header and the foot of the pages.
%% You must include the package "fancyhdr" to
%% have access to these macros.
%% Left header
%\lhead{}
%% Center header
%\chead{}
%% Right header
%\rhead{}
%% Left footer
%\lfoot{}
%% Center footer
%\cfoot{}
%% Right footer
%\rfoot{}
 
%%--------------------
% Declare several theorems
\declareupmtheorem{mytheorem}{My Theorem}{List of my Theorems}

%%--------------------
%% Change the message on the backcover.
%\Set{backcovermessage}{%
%       Some text
%}

\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

%%--------------------
%% The content of the PhD thesis
\mainmatter

\part*{INTRODUCTION}
\newpage

\part{PARTIE I: Contexte scientifique et revue de l'état de l'art}

\chapter{Cadre de travail et contexte scientifique}

\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
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. 
\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
$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
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 \figref{decoupage} présente un exemple de découpage en domaines de la
matrice initiale entre deux clusters constitués chacun de 18 processeurs, soit un total de 36 processeurs.

\mfigure[h]{width=8cm, height=8cm}{"3D data partitionning btw 2 clusters"} {Partitionnement : Découpage d'une matrice tridimensionnelle entre deux clusters formés de 18 processeurs chacun} {decoupage}

\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
aussi entre les clusters en suivant une organisation logique d'un
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 :
\begin{equation}
x_{k+1} = (x_1^k, x_2^k, \dots , x_n^k), k=1,\dots n  
\end{equation}
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} 
X_{k+1} = F (X_k)
\end{equation}

\begin{equation} 
\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} 
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 :
\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. 
\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 \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$] 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}

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. 

\mfigure[h]{width=8cm, height=8cm}{"Synchronous iterations model"} {Modèle de communication synchrone} {sync}

\mfigure[h]{width=8cm, height=8cm}{"Asynchronous iterations model"} {Modèle de communication asynchrone} {async}

%\begin{figure}[h]
%\begin{subfigure}{0.5\textwidth}
%\includegraphics[width=5cm, height=5cm, scale=3]{"Synchronous iterations model"} 
%\caption{Modèle de communication synchrone}
%\label{fig:2.a}
%\end{subfigure}
%\begin{subfigure}{0.5\textwidth}
%\includegraphics[width=5cm, height=5cm, scale=3]{"Asynchronous iterations model"}
%\caption{Modèle de communication asynchrone}
%\label{fig:2.b}
%\end{subfigure}
%\caption{Modèles de communication}
%%\label{fig:1}
%\end{figure}

D'une part, ces paquets de données peuvent être transférés
de façon « synchrone » : dans ce cas, une coordination de l'échange
est assurée par les deux parties. A la fin de chaque itération, l'émetteur,
une fois la poignée de main établie, envoie les données et attend
jusqu'à la réception d'un accusé de
réception par le récepteur. L'algorithme même est en
mode synchrone parce qu'une étape de synchronisation
de tous les processeurs est nécessaire avant d'entamer
une nouvelle itération. La figure \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 \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 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é
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{Méthodes de résolution parallèles du problème de Poisson et de
l'algorithme two-stage multisplitting de Krylov}

\subsection{Algorithme de Jacobi}

\subsection{Méthode de résolution GMRES}

Native

Version « two-stage »

\subsection{Solveur multisplitting} 

Version simple

Version améliorée

\section{SIMGRID/SMPI : Simulateur d'exécution d'algorithmes
parallèles MPI dans une grille de calcul}

\subsection{MPI - Message Passing Interface}

\subsection{Simulateur SIMGRID}

\section{Motivations}

\section{Conclusion partielle}


\chapter{Etat de l'art et travaux de recherche associés}

\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é} 

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
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)
{[}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 : 

\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 \\
\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
des calculs tandis que le temps de communication enregistre le temps
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
aux temps de calcul et de communication.

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
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.
\begin{equation}
\label{eq:6}
S(n) = T_{Exec\_Seq} / T_{Exec\_Par}(n) 
\end{equation}
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.

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
nombre de processeurs n.
\begin{equation}
\label{eq:7}
E(n) = S(n) / n \\
= T_{Exec\_Seq} / ( n \times T_{Exec\_Par}(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
du code, on a : 

\begin{equation}
\label{eq:8}
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
selon le mode retenu pour chaque code.

\begin{equation}
\label{eq:9}
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
: 
\begin{equation*}
(\|X_l^k - X_l^{k+1}\|_{\infty}\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
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
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.

\mfigure[h]{width=8cm, height=8cm}{"Weak vs Strong scaling"} {Weak vs Strong scaling: Temps d'exécution et Speedup} {scaling}


La figure \figref{scaling} montre que le temps d'exécution décroit (resp. reste constant) quand le nombre de processeurs augmente en strong mode (resp. en weak mode). De même, le speedup croit avec le nombre de processeur en strong mode tandis qu'il reste constant en weak mode.

\section{Problématique sur la prédiction à large échelle de la performance des applications}

La prédiction de la performance des applications parallèles à large
échelle constitue ces dernières années une des préoccupations majeures
des scientifiques et des utilisateurs des systèmes de calcul à haute
performance. En effet, en considérant le coût de lancement nécessaire
mais aussi le temps d'exécution imparti pour une telle
application, il est toujours d'intérêt de disposer
d'un outil ou d'un moyen afin de connaître
le comportement de l'application en montant en charge. Pour cela, il s'agit
d'estimer le temps total d'exécution $T_{exec}$ dans ces conditions. De plus,
dans le cadre d'un calcul sur la grille,l'objectif est de 
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
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.

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. 

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
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
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. 

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
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
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
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
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
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
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
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
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 \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
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.
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 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.

\mfigure[h]{width=8cm, height=8cm}{"Architecture des CPU multi-coeurs"} {Architecture des CPU multicoeurs} {cpumulti}

La performance d'une
telle entité de calcul repose sur la vitesse d'accès
des 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 : 

\mfigure[h]{width=8cm, height=8cm}{"MIMD Distributed Memory"} {Modèle MIMD Distribué} {MIMDDM}

\mfigure[h]{width=8cm, height=8cm}{"MIMD Shared memory - SMP"} {Modèle MIMD partagé} {MIMDSM}

\mfigure[h]{width=8cm, height=8cm}{"MIMD Hybride"} {Modèle MIMD hybride} {MIMDHY}

\begin{itemize}

\item [$\bullet$] - Machine MIMD à mémoire partagée (Figure \figref{MIMDSM}) : Les unités de calcul
accède à la mémoire partagée via un réseau d'interconnection
(généralement, de type GigabitEthernet (renvoi) ou Infiniband (renvoi)).
Il existe trois types d'implémentation : le crossbar,
le Omega-Network et le Central Databus.

\item [$\bullet$] Machine MIMD à mémoire distribuée (Figure \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 \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 figure \figref {power} montre l'évolution de la puissance
de calcul mondiale dont le top actuel développe un pic de performance
théorique proche de 50 PetaFlops (33 Linpack PetaFlops (renvoi)) avec
3.120.000 cores ( 16 noeuds avec des processeurs de 2x12 cores par
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
de l'exaflops n'est pas loin.

\mfigure[h]{width=8cm, height=8cm}{"Evolution de la puissance de calcul mondiale"} {Evolution de la puissance de calcul mondiale} {power}

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
(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
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
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
{[}16{]}. 

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 \figref{UMA}). Un système d'adressage
global est appliqué à l'ensemble des mémoires physiques.
(2) NUMA ou « Non Uniform Memory Access » où les groupes de CPU accèdent
à des mémoires locales à travers des buses et les groupes sont interconnectés
par un réseau de communication ((Figure \figref{NUMA}). Dans ce cas, le temps
d'accès des CPU aux pages mémoires varie selon que
ces dernières sont locales ou distantes. L'espace d'adressage
des mémoires se fait au niveau de chaque groupe de CPU. (3) L'architecture
COMA (« Cache Only Memory Access ») est un hybride avec un modèle
de programmation de mémoire partagée mais une implémentation physique
de mémoire distribué ((Figure \figref{COMA}). Dans ce cas, chaque noeud détient
une partie du système de l'espace d'adressage.
Le partitionnement des données étant dynamique, la structure COMA
n'associe pas la même adresse à une page physique de
la mémoire. Les mémoires locales dans ce cas de figure jouent finalement
un rôle de cache au processeur.

\mfigure[h]{width=8cm, height=8cm}{"UMA architecture"} {Mémoire MIMD: Architecture UMA} {UMA}

\mfigure[h]{width=8cm, height=8cm}{"NUMA architecture"} {Mémoire MIMD: Architecture NUMA} {NUMA}

\mfigure[h]{width=8cm, height=8cm}{"COMA architecture"} {Mémoire MIMD: Architecture COMA} {COMA}

Malgré que dans le cadre de nos travaux, nous n'avions
pas eu une contrainte particulière en termes de système de stockage,
une brève revue des problématiques liées à ce sous-système en environnement
de calcul parallèle est présentée parce qu'il peut
influencer à large echelle sur la prédiction de la performance de
l'application. Les systèmes traditionnels ont opté
pour des architectures NFS (Network File System) ou de type NAS (Network
Attached Storage) ou encore de type SAN (Storage Access Network).
Malgré que les systèmes de stockage NFS et NAS sont relativement faciles
à mettre en oeuvre, l'inconvénient majeur est qu'ils
présentent un point de défaillance unique (SPOF) et ont des difficultés
de monter en échelle. Pour le système SAN, les données sont stockées
dans des baies de stockage accessibles par les unités de calcul à
travers un réseau basé sur des canaux de fibres et des adapteurs de
haut débit (HBA) ; ce qui rend le coût de l'implémentation rapidement
excessif dès que le nombre de noeuds augmente. Dans un environnement
d'applications parallèles, le réseau de communication
doit avoir une très haute performance pour répondre aux besoins d'échange
mais aussi d'accès aux données. En plus, il doit
avoir la flexibilité et la capacité de monter en échelle suivant la
demande du système. Ces caractéristiques requis sont accentués par
la variabilité des besoins en entrées/sorties des applications HPC: dans le même lot d'applications exécutées, certaines
accèdent à des données de manière séquentielle tandis que d'autres
demandent des entrées/sorties aléatoires fortement sensibles. Les
solutions apportées dénommées « système de fichiers parallèle » reposent
sur la conception d'une architecture répondant à ces
prérequis. Dans ce type de système de fichiers, les blocs de données
sont répartis par morceaux dans différents serveurs et dans différentes
locations du système de stockage. On peut ainsi accroitre le débit
de stockage et d'extraction au fur et à mesure que
le nombre de serveurs ou de baies de stockage augmentent.L'architecture sera réalisée par:

\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
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.
\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
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 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
grilles de calcul, de clusters ou de P2P, d'autres
types de réseaux de communication influencent cette performance. 

%Ethernet, Infiniband (56 à 100 Gb/s), Omni-path {[}15{]}

%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} 

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}

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
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
du nombre de processeurs / coeurs, le temps de calcul global attendu
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
du code.

\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 : 

\begin{equation}
\label{eq:10}
  \eta Parallel =LB \times Ser \times Trf       
\end{equation}
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
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.

\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 : 

\begin{equation}
\label{eq:12}
Trf = max( T_i/T ) / Ser
\end{equation}

\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
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é
ou l'aspect scientifique du code, l'application
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. 

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
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
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
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}
 

\section{Techniques de profiling et instrumentation des applications parallèles}


\section{Méthodes de prédiction de la performance de l'application parallèle}


\section{Conclusion partielle}

\part{PARTIE II - Travaux de contributions, résultats et perspectives}

\chapter{Comparaison par simulation à large échelle de la performance de deux algorithmes itératifs parallèles en mode asynchrone}

\section{Protocoles et expérimentations}

\section{Résultats}

\section{Conclusion partielle}

\chapter{Simulation avec SIMGRID de l\textquoteright exécution des solveurs linéaires en mode synchrone et asynchrone sur un environnement multi-coeurs simulés}

\section{Protocoles et expérimentations}

\section{Résultats}

\section{Conclusion partielle}

\chapter{Modèle de prédiction de la performance à large échelle d'un algorithme itératif parallèle}

\section{Approche et méthodologie}

\section{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.

{[}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}

{[}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}.

{[}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

{[}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".
\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
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.
\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}. 

{[}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
 
 
%%--------------------
%% 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}