\chapter{Calcul haute performance}
\label{ch:hpc}

Dans ce chapitre, nous décrivons le contexte et les enjeux du traitement
intensif des informations et proposons une approche méthodologique non
restrictive afin de parvenir à un calcul efficace sur des données volumineuses.

Nous commençons par une description haut niveau des technologies de traitement
parallèle existantes en exhibant les avantages et limitations pour la
manipulation intensive de données. La seconde partie expose une méthodologie
permettant de réaliser un traitement parallèle à partir d'un problème
séquentiel. Enfin, dans une dernière partie, nous exposerons des modèles pour
évaluer l'efficacité des implémentations parallèles.



\section{Introduction}
Les performances atteignables par un algorithme ou un programme séquentiel
traitant un problème scientifique dépendent fortement du processeur sur lequel
il est exécuté. Le processeur se définit par son architecture, englobant la
cadence d'horloge, la finesse de gravure, le jeu d'instructions implémenté,
l'organisation des chemins de données et la taille des registres.

À cette échelle, trois aspects sont importants pour le calcul : la vitesse de
traitement autorisée par la cadence d'horloge, l'espace mémoire disponible à
travers la taille et le nombre des registres et l'organisation des calculs qui,
au niveau de la micro-architecture, peut se traduire par la présence d'unités
fonctionnelles spécialisées ou l'utilisation des chaînes de traitements. Chacun
de ces aspects a subi de nombreuses améliorations dans l'évolution des
microprocesseurs. Néanmoins, et pendant de très nombreuses années, la principale
source d'amélioration des performances d'un processeur a été liée à
l'augmentation de sa vitesse d'horloge. Ainsi, en ne considérant que la
fréquence d'un processeur, consécutive à la densification des transistors qui le
constituent, la multiplication par deux de celle-ci rend l'exécution deux fois
plus rapide.

Cette tendance est visible dans la conception logicielle et l'implémentation des
méthodes utilisées. Ainsi, les algorithmes et structures de données sont écrits
de manière à traiter séquentiellement les informations. En supposant qu'il n'y
ait qu'une unique unité de traitement fonctionnelle, les instructions issues de
l'implémentation sont gérées de manière centralisée par un processeur. Sur ce
processeur: une seule instruction est réalisée à la fois, au terme de laquelle
l'instruction suivante est lancée. En doublant la fréquence du processeur, on
divise par deux le temps nécessaire pour atteindre la solution.

Pour bénéficier des améliorations des autres caractéristiques d'un processeur,
il est nécessaire de s'appuyer sur les capacités des compilateurs à optimiser
les programmes. Cela permet également de diminuer les temps de développement,
d'améliorer la maintenabilité\index{maintenabilité} et la flexibilité sans avoir une spécialisation
des codes pour chaque type de processeur.

Cette évolution continue des processeurs a entraîné des performances croissantes
pour le calcul jusqu'au milieu des années 2000. Pour des raisons d'efficacité
énergétique par rapport à la vitesse d'exécution des opérations, la stratégie
d'augmentation simple du nombre de transistor n'est plus l'option privilégiée
par les concepteurs de processeurs.


\subsection{Motivations}

La stagnation des performances individuelles des processeurs pour des raisons
d'ingénierie a nécessité de s'intéresser à d'autres organisations des
architectures de calculs, avec notamment les GPGPU (General Purpose computing on
Graphics Processing Units). Le classement des 500 machines de calcul les plus
puissantes du monde reflètent ces évolutions (figure \ref{fig:chap3:top500}).
\begin{figure}[ht]
  \centering
  \begin{minipage}[c]{\linewidth}
    \includegraphics[width=\textwidth]{Figs/chapter-HPC/top500}
  \end{minipage}
  \caption{\'Evolution des puissances de calcul des machines du Top 500 \hspace{8mm}{\url{https://top500.org}}}
  \label{fig:chap3:top500}
\end{figure}

L'idée principale de ces nouvelles organisations est de diminuer les capacités
des processeurs en termes de fréquence, d'instructions disponibles et d'accès
aux ressources mémoire, compensées par une augmentation du nombre d'unités de
traitement.

Ce changement d'organisation des architectures se traduit d'un point de vue
développement par le recours à des méthodes de programmation parallèles.

Cette évolution est similaire à celle réalisée dans les années 1960 et qui a
contribué à l'émergence du calcul parallèle, notamment du calcul distribué. La
principale différence entre les deux époques est la facilité d'accès à ces
nouveaux matériels : le coût et la maturité des approches pour la programmation
parallèle.

Pour discuter du calcul haute performance, nous devons ainsi considérer les
approches parallèles pour le traitement des données et la réalisation des
calculs. Dans la suite, nous parlerons de calcul parallèle dès lors qu'une étape
de traitement réalisera plusieurs opérations simultanément. L'idée de base est
que les problèmes de taille suffisamment importante peuvent être divisés en
tâches plus petites exécutées en même temps.

La définition que nous adopterons pour le parallélisme est la suivante :
combinaison d'une architecture matérielle (réseaux, processeurs, mémoires) et
d'une organisation logicielle (bibliothèques, algorithmes, structures de
données) permettant de traiter simultanément des informations.

Le rôle du parallélisme est donc multiple : diminuer le temps de réalisation
d'une tâche, augmenter le nombre de données traitées simultanément, accroître la
complexité du problème que l'on souhaite résoudre.

Dans ce qui suit, nous nous intéressons uniquement aux aspects de la conception
logicielle du parallélisme pour des applications travaillant avec un grand
nombre de données.

Le calcul parallèle s'appuie sur des ordinateurs travaillant simultanément. Ces
derniers peuvent être classés en fonction du niveau de parallélisme qu'ils
supportent d'un point de vue matériel. Les processeurs multic\oe{}ur et les
GPGPU possèdent ainsi un grand nombre d'unités de traitement sur une seule
machine, réduisant le temps d'accès aux données mais avec un espace mémoire
limité; à l'inverse, les grappes ou les grilles de calcul associent plusieurs
ordinateurs, multipliant ainsi la taille de l'espace mémoire disponible mais en
augmentant le temps d'accès aux données.

% \begin{definition}[HPC]
  Le calcul haute performance est le développement d'approches algorithmiques et
  mathématiques s'appuyant sur les technologies disponibles pour traiter un
  problème donné le plus efficacement possible.
% \end{definition}

La notion de performance est fortement connectée à l'organisation  matérielle au
sens large. Le calcul haute performance vise donc à utiliser les meilleurs
outils disponibles.

L'application et l'utilisation efficaces du parallélisme s'appuient sur une
combinaison de différents éléments de poids égaux : le matériel, le logiciel et
la connaissance du problème à traiter. Comprendre les atouts du calcul haute
performance, et plus particulièrement du calcul parallèle, est crucial afin de
réaliser des investissements réussis.

\subsection{Hiérarchies du parallélisme}
\paragraph{Parallélisme de bits}
L'organisation séquentielle classique d'un ordinateur considère trois éléments :
le processeur, la mémoire et les chemins de données. Individuellement, chacun de
ces éléments présente des limitations qui réduisent les performances globales
d'un système. Afin de limiter ces effets, les concepteurs prévoient une
redondance matérielle des différents éléments exploitable par les logiciels. Une
première étape pour obtenir des logiciels de traitement efficaces est
d'exploiter ces redondances. Ceci se fait souvent implicitement, c'est-à-dire
sans intervention directe au moment du développement. Cependant, cela permet
d'illustrer les premiers éléments du parallélisme.

Le parallélisme de plus bas niveau réalisable se passe au niveau de la
représentation binaire des données. On parle de parallélisme de
bits\index{parallélisme!de bits}. L'amélioration de la vitesse de traitement
reposait en partie sur le doublement de la taille des mots informatiques
jusqu'au développement du 32 bits dans les années 1980. Le parallélisme de bits
permet d'augmenter le nombre d'informations qu'une unité de traitement est
capable de traiter par cycle. En augmentant la taille des mots, on réduit le
nombre d'opérations que l'unité de traitement doit réaliser sur une variable
dont la longueur est plus grande que celle du mot. Ainsi, sur des processeurs 32
bits, pour réaliser une opération arithmétique sur deux entiers 64 bits, deux
instructions sont nécessaires, alors que, sur un processeur 64 bits, une seule
est nécessaire. Le parallélisme de bits peut être utilisé pour comparer des
chaînes de caractères (\cite{chitty:2012:SC}).

\paragraph{Parallélisme d'instructions}
D'un point de vue logique, un programme peut être vu comme un flux continu
d'instructions exécutées par un processeur. Dans un modèle simple, l'instruction
est décomposée en sous-instructions permettant la préparation de l'exécution,
l'exécution et la restitution de cette dernière. Chacune de ces
sous-instructions nécessite un cycle d'horloge pour sa réalisation, ce qui dans
le cas d'un processeur simple nécessite 5 cycles pour exécuter une seule
instruction.

Étant donné que l'on considère un flux d'instructions, les processeurs modernes
permettent l'exécution de plusieurs sous-instructions différentes simultanément.
C'est une des formes du parallélisme d'instruction. Cette décomposition en
sous-composants simples d'une opération complexe permet, dans le cas de flux
d'instructions longs, d'exécuter en moyenne une instruction par cycle.

En augmentant le nombre de chaînes de traitement, le processeur traite plusieurs
instructions par cycle. Dans ce cas, on parle de processeur super-scalaire.
Dès lors que l'on considère la gestion des flux d'instructions, on parle de
parallélisme d'instructions\index{parallélisme!d'instructions}.

Sur les différentes approches présentées jusqu'ici, le parallélisme est
principalement le fait du processeur et le développeur n'a qu'un faible contrôle
sur elles. On parle de parallélisme implicite\index{parallélisme!implicite}.

\paragraph{Parallélisme de tâches}
Les instructions sont regroupées en files d'instructions (tâches), organisées
afin d'optimiser l'utilisation des unités de traitement matérielles. Les files
d'instructions indépendantes sont ordonnancées par le système d'exploitation
pour s'exécuter sur un seul c\oe{}ur de processeur. Si le processeur se compose
de plusieurs c\oe{}urs, l'ordonnancement est réalisé sur ce dernier. En
décomposant le programme en plusieurs fils d'instructions, on sollicite de
manière indirecte l'ordonnanceur du système d'exploitation qui réalise du
parallélisme de tâches\index{parallélisme!de tâches}.

Ce niveau de parallélisme doit s'envisager dès la conception du programme.

\paragraph{Parallélisme de données}
Les niveaux identifiés jusqu'à présent se concentrent sur un aspect fonctionnel
du traitement à réaliser. De manière conjointe, on peut s'intéresser à l'aspect
données du traitement. Lorsque les données manipulées présentent des dépendances
spatiales et temporelles faibles, il est envisageable de les diviser. Chaque
portion ainsi divisée peut être manipulée individuellement par différentes
unités de traitement jusqu'à ce que des données produites par d'autres unités
soient nécessaires.

Dans ces deux dernières formes de parallélisme, l'organisation est
principalement réalisée au niveau logiciel et par le développeur, qui peut
utiliser sa connaissance du problème à traiter. On parle de parallélisme
explicite\index{parallélisme!explicite}.


\subsection{Classification des plateformes}

Afin de mettre en \oe{}uvre le parallélisme explicite, soit par tâches, soit par
données, la connaissance des différents types de plateformes parallèles permet
de construire des méthodes de résolution et des algorithmes efficaces.

Les architectures pour le calcul parallèle sont très diverses. On retrouve les
processeurs multic\oe{}urs, les processeurs graphiques (GPGPU), les circuits
logiques programmes (FGPA), les grappes de calcul, les grilles, les nuages ou
encore les supercalculateurs.

La diversité des plateformes parallèles amène à s'interroger sur les
méthodologies de développement et de portabilité des approches. Les techniques
de programmation pour des architectures à mémoire partagée ou en nuage seront
très différentes bien que l'espace mémoire soit accessible par l'ensemble des
unités de traitement. Chacune des plateforme présente des spécificités qui
limitent l'application de méthodes de traitements développées pour d'autres
architectures.

Pour classer ces plateformes, il est courant de les distinguer par leur
structure globale, l'accès aux données ou au flux, le nombre d'instructions
réalisables.

La première classification a été proposée par Flynn en 1972
(\cite{flynn:1972:ITC}).

\begin{figure}[ht]
  \centering
    \includegraphics[width=0.85\textwidth]{Figs/chapter-HPC/flynn}
  \caption{Classification de Flynn}
  \label{fig:chap3:flynn}
\end{figure}

Cette classification, sous forme de matrice comme l'illustre la figure
\ref{fig:chap3:flynn}, utilise les concepts de flux de données et de flux
d'instructions :
\begin{itemize}
  \item SISD (Single Instruction Single Data) : le flux d'instructions s'exécute
  sur une unique unité de traitement contenant une seule unité fonctionnelle. Ce
  type de plateforme correspond au processeur idéal de Von Neumann et ne possède
  pas de réalisation moderne.
  \item SIMD (Single Instruction Multiple Data) : une unité de contrôle
  orchestre les tâches à réaliser sur l'ensemble des unités de traitement. Ces
  dernières reçoivent toutes le même flux d'instructions. L'espace de mémoire
  principal est divisé en blocs, chacun étant associé à un flux de données.
  Chaque unité de traitement réalise une instruction sur le flux qui lui est
  associé. Les instructions sont synchrones. Cette organisation du traitement se
  retrouve dans les plateformes GPGPU.
  \item MISD (Multiple Instructions Single Data) : cette organisation est peu
  courante. Chaque unité de contrôle s'occupe d'un flux d'instructions exécutées
  par l'unité de traitement associée. Toutes les unités de traitement ont accès
  à un espace mémoire partagé. Cette structuration est applicable pour
  construire des systèmes tolérants aux pannes.
  \item MIMD (Multiple Instructions Multiple Data) : chaque unité de traitement
  manipule des données qui lui sont propres en utilisant des flux d'instructions
  spécifiques. Les unités peuvent travailler de manière asynchrones et
  indépendantes. Les architectures modernes sont en grande majorité classées
  dans cette catégorie.
\end{itemize}

\subsection{Coûts de communication}
La classification proposée par Flynn ne prend pas en compte l'accès aux données
intervenant dans le traitement. Dans l'ensemble des plateformes parallèles, les
connexions entre les c\oe{}urs d'un processeur ou entre les processeurs d'une
grappe de calcul vont affecter les performances optimales atteignables.

Lorsque les unités de traitement accèdent à toutes les données stockées dans un
espace de mémoire commun, le système est dit à \textit{mémoire partagée}. Dans
le cas idéal, l'accès se fait de manière uniforme par toutes les unités. On
parle alors d'architectures UMA (Uniform Access Memory). Dans les systèmes
modernes, chaque c\oe{}ur possède une mémoire locale. Le regroupement de ces
mémoires locales constitue la mémoire globale du système. L'accès à la mémoire
locale est non uniforme, c'est-à-dire que le temps d'accès aux données va
dépendre de la proximité du c\oe{}ur. On parle de mémoire NUMA (Non Uniform
Memory Access).

Pour les grilles, les grappes ou les supercalculateurs, les mémoires sont
uniquement locales et l'accès global aux données n'est pas possible directement.
On dit alors que le système est à \textit{mémoire distribuée}. L'échange de
données entre les unités de traitement, les processeurs dans ce cas-là, se fait
uniquement par messages explicites. Ce sont les systèmes NORMA (No Remote Memory
Access).

Pour la plupart, les systèmes ne permettent donc pas un accès uniforme aux
données. Les coûts d'accès sont fonction de deux grandeurs : la latence et la
bande passante.

La latence est le temps nécessaire afin de préparer le canal de communication.
C'est une constante indépendante du type et de la taille des données.

La bande passante correspond au temps nécessaire pour recevoir et envoyer un
mot. On la décrit le plus souvent comme la quantité de données envoyée ou reçue
par seconde.

Le temps de transfert d'un message ou d'accès à une donnée est modélisé par
l'équation suivante :
\begin{equation}\label{eq:chap3:comm_cost}
  t = \alpha + l \beta
\end{equation}

$\alpha$ représente la latence, $l$ la longueur du
message et $\beta$ la bande passante. Les grandeurs $\alpha$ et $\beta$ sont
dépendantes de la plateforme, c'est-à-dire du matériel utilisé, des
bibliothèques implémentant les protocoles de communication et enfin de la
topologie du réseau.

Un ensemble de $p$ unités de traitement demanderait $O(p^2)$ connexions
directes. En dehors de la complexité matérielle pour réaliser un tel nombre de
connexions dans les grappes ou les supercalculateurs, il serait nécessaire de
gérer des priorités de communication entre les unités de traitement. La
topologie de connexion est donc structurée afin que l'accès aux données ou les
échanges soient optimisés pour les problèmes traités sur la plateforme. Dans les
centres de calcul, les grappes et supercalculateurs utilisent une topologie en
hypercube pour échanger les données.


La prise en compte de l'ensemble de ces contraintes demande donc des méthodes de
résolution adaptées à chaque architecture cible. L'objectif de la section
suivante est de proposer une approche de conception suffisamment abstraite pour
que les solutions proposées soient transposables à différentes plateformes.

\section{Principes de conception \\ des algorithmes}

Le développement d'une approche parallèle permettant de réaliser un traitement
ne se réduit pas à l'application de techniques simples. Il est souvent
indispensable de s'appuyer sur la connaissance avancée du problème pour proposer
une approche satisfaisante. De plus, différentes solutions parallèles sont
susceptibles de répondre à une problématique donnée. La meilleure solution
parallèle est rarement la transposition de la meilleure solution séquentielle.

À partir de cette remarque, le processus de conception d'une approche parallèle
a été formalisé (\cite{foster:1995:Book}). Cette méthode dissocie les aspects
qui sont indépendants des caractéristiques matérielles des plateformes de
traitement, de ceux qui dépendent du matériel et des outils de développement
(langages, bibliothèques) choisis pour réaliser la solution. Les quatre phases
qui constituent cette méthode sont la décomposition, la planification, la
structuration et l'affectation . L'objectif des deux premières est de se
focaliser sur la scalabilité (capacité de passer à l'échelle) et la concurrence
des algorithmes. Les deux dernières phases sont axées sur la localité des
traitements et la performance globale de l'approche.

\begin{figure}[ht]
  \centering
  \begin{minipage}[c]{\linewidth}
    \includegraphics[width=\textwidth]{Figs/chapter-HPC/decomposition}
  \end{minipage}
  \caption{Méthodologie de conception d'une approche parallèle}
  \label{fig:chap3:decomposition}
\end{figure}

Ces quatre phases illustrées par la figure \ref{fig:chap3:decomposition} peuvent
être synthétisées de la manière suivante :
\begin{enumerate}
  \item \textbf{Décomposition} : les traitements à réaliser et les données
  concernées sont décomposés en éléments de petite taille. Cette atomisation du
  problème permet d'identifier les formes de parallélisme envisageables.
  \item \textbf{Planification} : les relations entre les tâches et les données
  sont organisées. Dans les cas les plus favorables, cette organisation
  s'exprime sous forme d'un graphe de dépendances entre les tâches et/ou
  données. L'analyse de cette organisation facilite le choix des algorithmes et
  des structures de données les plus adaptés.
  \item \textbf{Structuration} : les tâches et les relations identifiées dans
  les deux étapes précédentes sont évaluées par rapport aux besoins en
  performances et aux coûts d'implémentation. Les tâches sont éventuellement
  combinées en un ensemble plus important, limitant ainsi les coûts de
  développement et améliorant les performances.
  \item \textbf{Affectation} : chaque tâche est associée à une unité de
   traitement de manière à ce que les coûts de communications entre les unités
   et leur taux d'utilisation soient optimaux. L'association peut être soit
   statique, soit dynamique, afin de mieux équilibrer les charges.
\end{enumerate}

\subsection{Techniques de décomposition}
Le degré de décomposition du problème à traiter est le premier élément
permettant de construire une approche parallèle efficace. On appelle
granularité\index{granularité} le degré de décomposition du problème à traiter.
Elle exprime le nombre de tâches à réaliser et la taille de chacune d'entre
elles. Plus le grain de la décomposition sera fin, plus il sera possible
d'extraire du parallélisme. Il n'est cependant pas souhaitable de réduire trop
fortement la granularité. En effet, le parallélisme implicite, qui est
intrinsèque aux unités de traitement, ne sera exploitable que si la granularité
le permet.

La méthodologie de division  du travail à réaliser va dépendre de la nature du
problème. Plusieurs techniques de décompositions sont envisageables.

\paragraph{Décomposition récursive}
\index{décomposition!récursive}Elle repose sur une stratégie de \guil{diviser pour
régner} s'applique lorsque la tâche principale à réaliser sur l'ensemble des
données  s'exprime comme la combinaison de cette même tâche sur des
sous-ensembles de ces données (par exemple, déterminer le maximum d'un tableau
par un algorithme de tri rapide ou calculer un produit scalaire entre deux
vecteurs).

\paragraph{Décomposition de données}
\index{décomposition!de données}Elle repose sur un partitionnement des données
d'entrée et/ou de sortie en sous-ensembles de même taille. Les tâches à réaliser
sur chacun des sous-ensembles de données sont similaires en termes de complexité
algorithmique. Les structures de données doivent être adaptées à la plateforme
de traitement parallèle. L'exemple le plus simple de la décomposition des
données de sortie est le produit matriciel. La matrice de sortie est décomposée
en blocs de même taille et chaque unité de traitement réalise le produit
matrice-vecteur sur le bloc qui lui est associé (\cite{choi:1994:CPE}). La
décomposition des données d'entrée s'applique par exemple pour la résolution
d'équations aux dérivées partielles en utilisant des techniques de décomposition
de domaines (\cite{toselli:2005:book}).

\paragraph{Décomposition exploratoire}
\index{décomposition!exploratoire}Cette approche est similaire à la
décomposition de données. Le calcul principal consiste à rechercher une
solution dans un espace donné. L'espace de recherche est alors séparé en entités
indépendantes de tailles inférieures. L'exploration est terminée dès qu'une
solution est identifiée par l'une des unités de traitement. Cette décomposition
est utilisé en optimisation discrète (programmation quadratique, résolution de
jeux, démonstration de théorèmes).

\paragraph{Décomposition spéculative}
\index{décomposition!spéculative}Pour certaines applications, l'identification
de tâches indépendantes n'est pas possible a priori. La première approche
consiste à réaliser une décomposition conservative qui identifie les tâches
comme étant indépendantes si et seulement si il n'y a pas de risques de
dépendances. En étant conservatif, la réalisation concurrente de tâches peut
être impossible. À l'opposé, l'approche optimiste qui consiste à réaliser de
manière concurrente des tâches dont on ne connaît pas les dépendances a priori
demande un mécanisme de rembobinage des instructions. La décomposition
spéculative est principalement utilisée lorsque les conditions qui conduisent à
un branchement sont inconnues, comme dans la simulation d'événements discrets.

Pour bénéficier du parallélisme, l'étape de décomposition doit produire des
tâches avec une granularité suffisamment petite.

\subsection{Caractéristiques des tâches \\ et des interactions}
En réalisant la décomposition par l'une des techniques précédentes, les entrées
et sorties de chacune des tâches et les dépendances entre les données se
représentent à l'aide d'un graphe. Les n\oe{}uds du graphe représentent les
données issues de la décomposition et les tâches sont associées aux arêtes du
graphe.

La planification consiste en l'analyse des tâches et de leurs interactions.
Chaque tâche possède une complexité, autrement dit un coût, et des dépendances
par rapport aux données et aux autres tâches, c'est-à-dire des interactions.

Dans les applications pour lesquelles le parallélisme est le plus simple à
mettre en place, les tâches sont toutes connues à l'avance, possèdent des
complexités spatiales et temporelles déterminées et uniformes et les données
associées sont de tailles équivalentes et limitées.

Ainsi, dans le cas du produit entre deux matrices carrées de taille $n\times n$
et en considérant comme granularité le produit scalaire entre une ligne et une
colonne, il y a $n^2$ tâches indépendantes à réaliser. Chaque tâche a besoin
d'une ligne de taille $n$ et d'une colonne de taille $n$ accessibles en lecture
et le résultat est écrit sur un scalaire. A priori, aucune donnée n'est à
échanger.

À l'opposé, pour certaines applications, des tâches de tailles différentes sont
générées au cours de la décomposition, susceptibles d'avoir des complexités
différentes, des dépendances variables et des données en entrée et sortie de
tailles inconnues a priori. Ces situations sont les plus courantes lorsque
l'application explore un espace de solutions, par exemple en théorie des jeux ou
intelligence artificielle en utilisant l'élagage $\alpha-\beta$
(\cite{fishburn:1984:book}).

Les interactions entre les tâches exhibent des différences également très
importantes. Si le graphe des interactions est connu avant l'exécution, on
parlera d'interaction statique, alors que si le graphe évolue au cours du
déroulement de l'application, l'interaction sera dynamique. Cette différence
provient essentiellement de la manière de créer la décomposition. Dans une
décomposition de données, les interactions seront généralement statiques
(produit matriciel), alors que pour une décomposition par exploration (élagage
$\alpha-\beta$), elles seront dynamiques.

Cette première classification ne permet pas de rendre compte de la diversité des
interactions. Leur régularité des interactions par rapport à l'ensemble des
tâches est aussi un facteur déterminant. Par exemple, la résolution de
l'équation de Poisson sur une grille cartésienne, c'est-à-dire dont le nombre de
voisins de chaque point de discrétisation est uniforme, permet de construire des
interactions régulières en taille et en volume, alors que la résolution de la
même équation sur une grille non structurée requiert des interactions
spécifiques pour chaque tâche.

La dernière caractéristique importante est la portée d'interaction de la tâche.
Dans la résolution d'une équation aux dérivées partielles, les interactions sont
essentiellement locales, c'est-à-dire que le calcul en chaque élément d'une
grille  ne dépend que des points voisins. Cette localité se traduit par un
faible nombre d'arêtes entrantes et sortantes dans le graphe des dépendances. Les
interactions globales, que l'on retrouve par exemple en calculant la fonction de
transfert d'une couche d'un réseau de neurones, impliquent des interactions avec
un grand nombre d'autres tâches. Cela se traduit par la présence d'un très grand
nombre d'arêtes entrantes et/ou sortantes pour la plupart des n\oe{}uds du
graphe.


Le tableau \ref{tab:chap3:caract} propose une synthèse des caractéristiques des
tâches et interactions en fonction de la difficulté de réalisation du
parallélisme.

\begin{table}
  \begin{tabular}{ccc}
    \toprule
    & Favorable & Difficile \\
    \midrule
    Tâche & génération statique & génération dynamique \\
    & complexité uniforme & complexité non uniforme \\
    & complexité statique & complexité dynamique \\
    \midrule
    Interaction & régulière & irrégulière \\
    & statique & dynamique \\
    & locale & globale \\
    \bottomrule
  \end{tabular}
  \caption{Synthèse des caractéristiques des tâches et de leurs interactions}
  \label{tab:chap3:caract}
\end{table}

\subsection{Équilibrage des ressources}
\index{equilibrage des ressources@équilibrage des ressources}Les étapes
d'association et de planification rendent compte de la structure algorithmique
du traitement. La décomposition a permis d'identifier un nombre de tâches bien
supérieur au nombre d'unités de traitement disponibles. L'objectif de la phase
de structuration est d'utiliser les résultats de l'analyse afin de regrouper les
tâches qui permettent de minimiser le temps de résolution global. À l'exception
de quelques applications, la mise en place du parallélisme introduit un surcoût
au temps d'exécution notamment à cause des interactions : le temps d'attente
d'un processus ayant terminé l'ensemble des tâches qui lui sont associées et le
temps d'échange dans les interactions entre processus.

En supposant que la plateforme parallèle soit idéale et que les interactions
entre les tâches soient négligeables, le temps d'attente entre les processus
peut être négligé en fusionnant les tâches en ensembles de complexités
identiques. La difficulté est de s'assurer que les données en entrée et sortie
de ces ensembles de tâches soient locales. De façon plus générale, minimiser ce
temps d'attente correspond à identifier des ensembles de tâches qui minimisent
les fréquences des interactions. Les simulations de Monte-Carlo permettent un
découpage en tâches parfaitement adapté au parallélisme
(\cite{rosenthal:1999:FEJTS}).

Pour contrôler le surcoût lié aux temps d'échanges entre les interactions, il
est indispensable de minimiser le volume des données à transférer, en regroupant
des tâches qui se les échangent. On crée ainsi une augmentation de la
localité\index{localité}. En complément de cette amélioration de la localité,
l'agglomération cherche à regrouper les tâches qui masquent certaines
interactions par la réalisation des tâches (\cite{hahnfeld:2017:SOEPP}). De
cette manière, une granularité suffisamment fine de la décomposition réussit à
limiter les effets des accès aux données.

Une autre approche limitant le coût des échanges consiste à dupliquer une partie
des données.


\subsection{Modèles d'algorithmes parallèles}
Pour différentes classes d'applications, les méthodologies utilisées pourront
être très différentes. Savoir reconnaître dans quelle classe on se situe conduit
à utiliser les méthodes les plus adaptées pour obtenir un parallélisme efficace.

\paragraph{Parallélisme de données}
\index{parallélisme!de données}Dans ce modèle de parallélisme, l'association des
tâches aux processus est réalisée de manière statique et chaque tâche applique
les mêmes opérations sur des données différentes. Ce type de parallélisme se
focalise plus particulièrement sur les données. Il découle souvent d'une
décomposition de données suivie par une génération statique de tâches de
complexité uniforme et statique. Les interactions sont le plus souvent locales
et il est donc possible de recouvrir les interactions entre les tâches par des
calculs.

Ce modèle est adapté à toutes les plateformes parallèles et le degré de
parallélisme augmente avec la taille du problème à traiter. C'est le type le
plus couramment utilisé pour résoudre les équations différentielles avec par
exemple des techniques de décomposition de domaines (\cite{toselli:2005:book})
ou les produits matriciels (\cite{choi:1994:CPE}).


\paragraph{Parallélisme de tâches}
\index{parallélisme!de tâches}Dans ce modèle, l'accent est mis sur les tâches.
On considère que le traitement à réaliser sur les données est un enchaînement de
tâches. Le parallélisme est construit directement à partir du graphe de
dépendances obtenu durant la phase de décomposition.

Cette approche est particulièrement adaptée pour renforcer la localité des
traitements et ainsi limiter les interactions entre les tâches. Plus
particulièrement, ce modèle est très performant lorsque les données à traiter
sont nombreuses et que la tâche à réaliser sur chacune est de faible complexité
temporelle. L'objectif de cette approche est de minimiser la fréquence et le
volume des interactions. Dans les approches \guil{diviser pour régner}, elle offre de
meilleures performances parallèles que les autres modèles
(\cite{danelutto:2016:DPP}).

\paragraph{Pipelining}
En s'inspirant du parallélisme implicite présent au niveau des processeurs, il
est possible de construire une approche par chaîne de traitements
(pipelining\index{pipelining}). Dans ce modèle, les données sont traitées sous
forme de flux par différentes tâches. Chaque tâche est associée à une unité de
traitement spécifique qui est, à l'exception de la première, un producteur de
données pour la suivante et un consommateur de la précédente. Les interactions
entre les tâches sont limitées à la propagation des données de l'une à la
suivante. Pour que ce modèle soit efficace, il est nécessaire de trouver un
équilibre entre la granularité de la décomposition et le nombre d'étapes dans le
pipeline.

Lorsque le graphe de dépendances se présente sous la forme d'une chaîne ou, plus
généralement, d'un graphe orienté acyclique, c'est le modèle de parallélisme le
plus adapté. On l'utilisera notamment lorsque les unités de traitement sont des
circuits intégrés dédiés (FPGA) et dans les réseaux de neurones.


\paragraph{Modèle maître-esclave}
\index{modèle!maître-esclave}Les tâches sont générées par un processus principal
en fonction des données à traiter et de celles qui ont déjà été utilisées. Les
tâches sont ensuite attribuées à des processus esclaves en fonction de la
disponibilité des ressources disponibles.

Ces approches concernent les applications pour lesquelles la synchronisation
entre les tâches n'est pas nécessaire à la poursuite du traitement, par exemple
dans la simulation de processus stochastiques (\cite{baldo:2005:ENTCS}) ou le
calcul participatif (\cite{anderson:2004:IWGC}).

\section{Modèles analytiques}
Afin de valider que l'approche choisie est adaptée pour la plateforme parallèle
cible, différentes métriques ont été développées au cours des années.


\subsection{Métriques de performances}
Le coût d'exécution $C_p(n)$ d'un programme parallèle sur $n$ données en
utilisant $p$ processeurs est modélisé par :
\begin{equation}
  \label{eq:chap3:parallel_cost}
  C(n,p) = p \tau(n,p)
\end{equation}
avec $\tau(n,p)$ le temps d'exécution sur $p$ processeurs. La réalisation
parallèle est dite à coût optimal si $C(n,p) = p *\tau_0(n)$ avec $\tau_0(n)$ le
temps d'exécution du programme séquentiel le plus rapide capable de traiter le
problème.

\paragraph{Accélération}
Le principal objectif du calcul haute performance est de diminuer le temps
d'obtention d'un résultat. Cela permet par la suite d'augmenter la taille du
problème ou de le complexifier.

L'accélération\index{accélération} (\it{speedup} en anglais) est donnée par:
\begin{equation*}
  \sigma(n,p) = \dfrac{\tau_0(n)}{\tau(n,p)}
\end{equation*}

Dans le cas d'un coût optimal, ce ratio est égal à $p$. Cependant, le temps
$\tau(n,p)$ se décompose en trois parties : le temps séquentiel correspondant à
la partie du programme qui ne peut pas être parallélisée, le temps optimal
correspondant à la partie de l'approche séquentielle pouvant être parallélisée
et le temps lié au surcoût du parallélisme :
\begin{equation}
  \label{eq:chap3:temps}
  \tau(n,p) = \upsilon(n) + \phi(n,p) + \kappa(n,p)
\end{equation}
avec $\upsilon(n)$ la fraction séquentielle du programme parallèle, $\phi(n,p)$
la partie pouvant être exécutée en parallèle et $\kappa(n,p)$ le surcoût lié au
parallélisme.

Dans le cas d'un programme séquentiel, il n'y a pas de surcoût lié au
parallélisme, donc $\tau(n,1) = \tau_0(n)$. En pratique, il est nécessaire
d'ajouter le surcoût lié au parallélisme, donc : $$\tau(n,1) = \upsilon(n) +
\phi_0(n) + \kappa(n,1)$$

Dans le cas d'un parallélisme optimal, les tâches peuvent être distribuées
équitablement entre toutes les unités de traitement, donc $\tau(n,p) =
\tau(n,1)/p$. Cependant, le surcoût lié au parallélisme reste présent. On
obtient donc l'optimale suivante $\tau(n,p) = \upsilon(n) + \phi(n)/p +
\kappa(n,p)$.

L'accélération optimale n'est cependant jamais atteinte car les tâches ne sont
pas distribuées équitablement entre les processus, ces derniers doivent gérer
d'autres tâches système et le nombre d'interactions entre les tâches augmente.
L'accélération est donc majorée par :
\begin{equation}
  \label{eq:chap3:speedup}
  \sigma(n,p) \leq \dfrac{\upsilon(n) + \tau_0(n)}{\upsilon(n)+ \phi(n)/p + \kappa(n,p)}
\end{equation}

En faisant croître $p$, le temps consacré au calcul diminue linéairement.
Cependant, dans toutes les approches parallèles, il existe un seuil à partir
duquel la croissance de $\kappa(n,p)$ devient super-linéaire, ce qui fait tendre
l'accélération vers $0$ et rend inefficace tout ajout de processeur
complémentaire à la plateforme parallèle. L'étude expérimentale de $\phi(n,p)$
permet donc de définir une stratégie de déploiement, voire d'investissement,
dans les plateformes parallèles.

\paragraph{Efficacité}
\index{efficacité}La seconde métrique d'intérêt pour le calcul haute performance
est l'efficacité. Il s'agit de mesurer le pourcentage moyen de temps d'un
algorithme passé à réellement résoudre le problème. L'efficacité s'écrit :
\begin{equation}
  \label{eq:chap3:efficiency}
  \epsilon(n,p) = \dfrac{\sigma(n,p)}{p}
\end{equation}
Dans le cas idéal, $\epsilon(n,p) = 1$.

\subsection{Passage à l'échelle des systèmes parallèles}

\begin{figure}[ht]
  \centering
  \begin{subfigure}[b]{0.3\textwidth}
    \includegraphics[width=\textwidth]{Figs/chapter-HPC/amdahl}
  \label{fig:chap3:amdahl}
  \caption{Amdahl}
  \end{subfigure}
  %
  \begin{subfigure}[b]{0.3\textwidth}
    \includegraphics[width=\textwidth]{Figs/chapter-HPC/gustafson}
  \label{fig:chap3:gustafson}
  \caption{Gustafson-Barsis}
  \end{subfigure}
  %
  \begin{subfigure}[b]{0.3\textwidth}
    \includegraphics[width=\textwidth]{Figs/chapter-HPC/iso}
  \label{fig:chap3:iso}
  \caption{l'iso-efficacité}
  \end{subfigure}
     \caption{\'Evolution de l'accélération pour différentes lois}
     \label{fig:chap3:iso}
\end{figure}

\paragraph{Loi d'Amdahl}
Cette loi, proposée par Amdahl\index{loi!d'Amdahl} en 1972, suggère qu'il existe une limite à
l'accélération atteignable par le parallélisme. Si on appelle $f$ la fraction
non parallélisable d'un algorithme, la loi s'écrit :
\begin{equation}
  \label{eq:chap3:amdahl}
  \sigma(n,p) \leq \dfrac{1}{f + \dfrac{1-f}{p}}
\end{equation}
Ainsi, lorsque l'on fait tendre $p$ vers $+\infty$, l'accélération tend vers
$1/f$, ce qui signifie que, pour une taille de problème donnée, la partie
séquentielle est irréductible et que l'accélération est bornée par l'inverse de
la partie séquentielle. Cependant, cette loi ne prend pas en compte la partie
$\kappa$ de l'équation \ref{eq:chap3:speedup}. Le comportement de la loi
d'Amdahl est illustré sur la figure \ref{fig:chap3:iso}.

\paragraph{Loi de Gustafson-Barsis}
Dans la loi de Amdahl, la taille du problème à résoudre reste constante lorsque
l'on augmente le nombre de processeurs. Étant donné, d'une part, la limite de
l'accélération exprimée par cette loi et, d'autre part, l'augmentation  du
nombre d'unités de traitement, Gustafson et Barsis ont proposé d'étudier
l'accélération lorsque la taille du problème et le nombre de processeurs
croissent conjointement.

Soit $s$ la fraction de temps prise par un programme parallèle pour résoudre la
portion séquentielle. Si on ne prend pas en compte le facteur $\kappa$ dans
l'équation \ref{eq:chap3:speedup}, on a :
\begin{equation*}
  s = \dfrac{\upsilon(n)}{\upsilon(n) + \phi(n,p)}
\end{equation*}

On définit  l'accélération normalisée $\sigma_n(n,p)$ par le ratio entre le
temps hypothétique pris pour résoudre le problème en séquentiel et le temps de
résolution effectif. On obtient ainsi la loi de Gustafson-Barsis :
\begin{equation}
  \label{eq:chap3:gustafson}
  \sigma_n(n,p) = p + (1-p)s
\end{equation}
Une représentation est proposée sur la figure \ref{fig:chap3:iso}.

\paragraph{Métrique de Karp-Flatt}
Les lois d'Amdahl et de Gustafson-Barsis ne prennent pas en compte le surcoût
lié au parallélisme $\kappa(n,p)$. La métrique développée  par Karp et Flatt
propose de mesurer expérimentalement l'accélération du programme parallèle afin
de donner la fraction séquentielle réelle. La métrique s'écrit :
\begin{equation}
  \label{eq:chap3:karp}
  f_s = \dfrac{\dfrac{\tau(n,1)}{\tau(n,p)} - \dfrac{1}{p}}{1-\dfrac{1}{p}}
\end{equation}
Cette métrique permet de déterminer si, pour une machine donnée, le surcoût lié
au parallélisme dans l'implémentation est dominant.

\subsection{Effet de la granularité}
Le degré de parallélisme est lié à la granularité de la décomposition. Si le
problème permet un parallélisme des données à la granularité de la
décomposition, il devient possible d'utiliser des plateformes parallèles
hiérarchiques de type supercalculateurs.

L'analyse de l'efficacité doit être réalisée pour chaque niveau de la hiérarchie
parallèle. Pour cela, on remplace le temps séquentiel présenté dans la relation
(\ref{eq:chap3:temps}) par le temps d'exécution au niveau précédent. On note
$\tau_d(n_d,p_d)$ le temps d'exécution du programme parallèle au niveau $d$ de
la hiérarchie. On obtient ainsi~:
\begin{equation*}
  \tau_d(n_d,p_d) = \upsilon_{d-1}(n_{d-1},p_{d-1} ) + \phi(n_{d},p_{d}) + \kappa(n_d, p_d)
\end{equation*}

En développant cette expression pour l'ensemble des niveaux de la hiérarchie, on
obtient la décomposition temporelle :
\begin{equation}
  \label{eq:chap3:granularity_cost}
  \tau_d(n_d,p_d) = \sum_{k=1}^d \phi(n_k,p_k) + \kappa(n_k,p_k)
\end{equation}
L'équation \ref{eq:chap3:granularity_cost} permet de mesurer l'impact du
parallélisme implicite lié au matériel et aux optimisations du système et
également d'identifier pour quels niveaux il est pertinent de modifier les
approches parallèles ou d'augmenter le nombre d'unités de traitement.


\subsection{Notion d'iso-efficacité}
La notion d'efficacité n'a en fait de sens que lorsque l'on étudie le couple
plateforme et programme parallèle. C'est ce que l'on appelle le système
parallèle. L'une des métriques servant à quantifier les performances d'un
système parallèle est la scalabilité\index{scalabilité}. Elle traduit la
capacité à conserver son efficacité lorsque le nombre d'unités de traitement et
la taille du problème augmentent dans les mêmes proportions.

La scalabilité d'un système est déterminée à l'aide de la relation
d'iso-efficacité\index{iso-efficacité} (\cite{grama:1993:PDT}). On note
$\tau_0(n,p)$ le temps nécessaire à l'ensemble des unités de traitement pour
réaliser la partie parallèle du programme, c'est-à-dire incluant le surcoût lié
au parallélisme.

En repartant de l'équation \ref{eq:chap3:efficiency} et en remplaçant
$p\tau(n,p)$ par $\tau(n,1) + \tau_0(n,p)$ on obtient :
\begin{equation*}
  \epsilon(n,p) = \dfrac{\tau(n,1)}{\tau_0(n,p)+\tau(n,1)}
\end{equation*}
Cette équation permet d'exprimer le temps d'exécution en parallèle sur $1$
processeur en fonction de l'efficacité, c'est-à-dire la fonction
d'iso-efficacité :
\begin{equation}
  \label{eq:chap3:isoefficiency}
  \tau(n,1) = \dfrac{\epsilon(n,p)}{1-\epsilon(n,p)}\tau_0(n,p) = C \tau_0(n,p)
\end{equation}
En supposant $C$ constant, la relation d'iso-efficacité $\tau(n,1) \geq C
\tau_0(n,p)$ permet de déterminer quelles sont les limites à la scalabilité d'un
système. $\tau_0(n,p)$ mesure le surcoût lié au parallélisme. Pour conserver un
système parallèle à efficacité constante, il est donc nécessaire de choisir un
nombre de processeurs qui augmente à la même vitesse que $(\tau_0(n,p) -
\tau(n,1))/p$. Si la croissance de cette fonction est linéaire, alors le
problème sera dit scalable. Dans le cas contraire, il n'est pas nécessaire
d'augmenter le nombre d'unités de traitement. Une comparaison de l'accélération
obtenue pour différentes lois de coût est proposée sur la figure
\ref{fig:chap3:iso}.

\section{Conclusion}

Dans ce chapitre, nous avons expliqué les principaux éléments permettant de
comprendre la construction de systèmes parallèles. Nous avons dans un premier
temps présenté des éléments permettant de distinguer les différents niveaux  de
parallélisme présents dans une architecture moderne. Ensuite, nous avons exposé
une méthodologie de construction d'approche parallèle qui se fait en quatre
phases. Enfin, nous avons proposé des métriques pour estimer les performances
d'une plateforme parallèle.

