Soutenance mémoire
Apparue initialement au 20ième siècle, la simulation numérique est devenue un outil incontournable pour la recherche scientifique dans de nombreux secteurs (biologie, métrologie, aéronautique, nucléaire, . . . ). Cet outil consiste à étudier plusieurs scénarios d’évolution d’un système de manière virtuelle. Il nous évite ainsi de courir le risque des expérimentations coûteuses et parfois irréalisables ou dangereuses en laboratoires (dans le domaine du nucléaire par exemple). D’après le cabinet international de conseil stratégique et d’analyse CIMdata , la simulation numérique occupe un marché en forte progression avec un rythme de l’ordre de 7,5% atteint en 2014. Ce progrès va de pair avec les avancées connues ces dernières années dans le domaine du calcul haute performance (HPC). Afin de résoudre des problèmes scientifiques de plus grande taille et pour réaliser les simulations le plus rapidement possible, les scientifiques ont eu recours à la programmation parallèle. Celle-ci consiste à utiliser plusieurs unités de calcul pour traiter de manière simultanée les informations.
Machines à mémoire partagée
Classification des architectures : Taxonomie de Flynn
Plusieurs travaux cherchent à classifier les architectures matérielles selon différents critères. La classification la plus courante est celle proposée par Flynn en 1972 [58]. Le critère utilisé dans cette taxonomie est basé sur le nombre de flots d’instructions et le nombre de flots de données pouvant être gérées par ces instructions. Selon ce critère, il a défini quatre types d’architectures [104, 128, 93] :
SISD (Single Instruction, Single Data) Ce type d’architecture est le moins complexe puisque un seul processeur exécute une seule instruction sur des données se trouvant dans une seule mémoire. Dans ces machines, il n’y a aucun parallélisme. Il s’agit de machines mono-processeur. L’architecture SISD est inspirée des architectures éponymes de Von Neumann décrites pour la première fois par ce dernier dans [130].
SIMD (Single Instruction, Multiple Data) Ce modèle utilise des architectures où plusieurs processeurs identiques sont contrôlés par une même unité de contrôle centralisée. Dans ces architectures, on applique sur un ensemble de données différentes une seule instruction de façon synchrone. Parmi les architectures SIMD, nous retrouvons les architectures vectorielles et les processeurs graphiques GPU (Graphics Processing Unit).
MISD (Multiple Instruction, Single Data) Dans ce modèle, plusieurs instructions sont exécutées en même temps sur la même donnée. Sur le plan pratique, ces architectures ne sont pas courantes étant donné l’étroitesse de leur champ d’application. Les architectures de pipeline sont basées sur le modèle MISD.
MIMD (Multiple Instruction, Multiple Data) Dans le modèle MIMD, plusieurs unités de calcul peuvent être regroupées dans le même système. Chaque unité dispose de son propre flot de données et de son propre flot d’instructions. Les interconnexions entre les différentes unités de calcul sont possibles dans la logique de ce modèle. De par sa grande flexibilité, ce modèle est le modèle le plus répandu dans les systèmes parallèles actuels et c’est celui d’ailleurs que nous allons utiliser dans le cadre de notre travail. Pour cette raison, nous allons consacrer la prochaine partie à la présentation des différentes architectures basées sur ce modèle.
Architectures à mémoire partagée
Le modèle MIMD de la taxonomie de Flynn permet de différencier deux familles d’architectures en se basant sur le type de mémoires dont elles disposent. On distingue, ainsi, les architectures parallèles à mémoire partagée et les architectures parallèles à mémoire distribuée. Dans une architecture à mémoire distribuée, chaque processeur accède à son espace de stockage local. Aucun accès direct au contenu de la mémoire d’un processeur distant n’est possible. Les échanges entre les différents processeurs s’effectuent moyennant des envois et des réceptions de messages à travers des interconnexions. Nous revenons sur ces communications dans le chapitre suivant. À la différence de la classe des architectures à mémoire distribuée, la classe des architectures à mémoire partagée réfère aux machines où les différents processeurs du système parallèle accèdent à un espace mémoire commun. Les opérations d’écriture et/ou de lecture effectuées par chaque processeur sont indépendantes et asynchrones entre les différentes unités de calcul. Ceci peut donc conduire à des conflits suite à des accès concurrents au même emplacement mémoire. Dans le cadre de cette thèse, nous nous intéressons à ce type d’architectures. Afin d’éviter l’accès d’une donnée partagée par différents processeurs à la fois, des outils de synchronisations sont utilisés. À ce titre, les développeurs utilisent des verrous, des sémaphores, des instructions atomiques et des barrières de synchronisation qui sont certes coûteux en matière de temps total d’exécution mais, inévitables pour gérer les accès concurrents.
Architectures à accès mémoire non uniforme
Un des points importants à traiter lors de l’étude des architectures à mémoire partagée est le coût d’accès de chaque processeur à la mémoire. Ce coût peut être identique pour tous les processeurs qui se partagent la même mémoire. Dans ce cas, les accès mémoire sont uniformes. Il s’agit de la sous-classe des architecture à accès mémoire uniforme : UMA (Uniform Memory Access). Si ce coût est dépendant de l’emplacement du processeur et de l’adresse mémoire à laquelle il accède, il est question d’une architecture à accès mémoire non uniforme: NUMA (Non Uniform Memory Access) [24]. Pour quantifier le temps d’accès mémoire dans ces architecture, on se base sur le facteur NUMA. Ce facteur informe sur le rapport entre le temps mis dans une architecture NUMA pour accéder à une mémoire distante et une mémoire locale. Il est défini formellement comme suit :
Remarque 1. Lorsqu’un cœur c accède à une donnée placée sur un nœud NUMA n, sa latence (temps d’accès) est Lcn . Si la donnée accédée est stockée dans sa mémoire locale, on définit par Lc loc sa latence locale.
Réduire l’impact du facteur NUMA est un défi qui préoccupe de nombreux chercheurs. Dans la littérature, des travaux de recherche proposent des techniques qui permettent de limiter l’impact de ce facteur. Dans ce contexte, des stratégies de placement optimal des données par rapport à la localisation de l’unité de calcul qui les utilise ont été développées [97, 29, 113, 108].
Mémoires à organisation hiérarchique
Bien que son rôle paraisse simple, la mémoire présente une grande complexité architecturale et intègre des technologies diverses pour répondre au rythme d’évolution de la puissance de calcul des processeurs. Ces mémoire peuvent contenir dans leur hiérarchie des bancs de mémoire dynamique et/ou des mémoires caches. L’accès aux différents nivaux obéit à une topologie d’accès. Ces topologies peuvent être indépendantes ; par exemple dans les mémoire des séries UV-XX de SGI, la topologie d’accès aux mémoires dynamiques est indépendante des mémoires caches. Dans cette topologie chaque saut (hop) rajoute une latence. De ce fait, pour résoudre ce problème de latence, la mémoire doit pouvoir suivre le rythme du processeur. Il faut éviter de laisser ce dernier passer des cycles à attendre le chargement des données ou des instructions à partir de la mémoire principale. Pour répondre à ce besoin, différents types de mémoires sont intégrés entre les unités de calcul et la mémoire centrale. Ces mémoires se distinguent par leurs capacités de stockage et leurs vitesses d’accès. Généralement, ces deux critères sont inversement proportionnels : les mémoires les plus rapides ont une capacité plus réduite et elles sont plus chères. Le dilemme vitesse d’accès – capacité de stockage nous conduit à parler d’une organisation hiérarchique des mémoires dans les machines de calcul. Voici ce que l’on peut rencontrer au fur et à mesure que l’on descend dans cette hiérarchie : au sommet de cette pyramide . se situent les registres internes. Ils sont considérés comme étant la mémoire la plus rapide et ils sont intégrés directement dans le circuit du processeur. Dans le deuxième niveau de cette hiérarchie, on trouve les mémoires caches (appelées aussi antémémoires [133]) situées entre les registres internes et la mémoire centrale (la mémoire RAM).
Mémoire cache
Introduite pour la première fois par M. V. Wilkes en 1965 [133], la mémoire cache est conçue pour combler la latence entre le processeur et la mémoire principale. Elle offre à ce dernier un accès rapide aux données et aux instructions les plus utilisées.
Les niveaux du cache
Dans les architectures actuelles, on distingue jusqu’à trois (voire même quatre) 1 niveaux de cache intégrés entre la mémoire principale et le processeur[17] :
– Le cache L1 est intégré sur le circuit du processeur. Il est le plus rapide et le plus petit en matière de capacité de stockage (de l’ordre de quelques Ko). Ce niveau est généralement divisé en deux parties, l’une pour stocker les instructions et l’autre est réservée aux données ;
– Le cache L2 a une capacité de stockage plus importante que celle du cache L1, mais avec une vitesse d’accès moins rapide. À la différence du cache L1, le cache L2 est généralement dédié au stockage des données et des instructions sans être physiquement divisé.
– Le cache L3 quant à lui, est disponible seulement sur certains processeurs des machines haut de gamme. Il est partagé entre les cœurs du processeur. Dans les architectures les plus récentes, il est logé dans le même circuit que celui du processeur. Sa capacité atteint quelques Méga octets. Il est moins rapide que les deux premiers niveaux.
Principe de fonctionnement du cache
Lorsque le processeur tente de lire des données, il commence par vérifier si cellesci sont disponibles dans son cache. Si c’est le cas, il récupère les données directement et il les utilise pour poursuivre son calcul. Il s’agit d’un succès de cache ou cache hit. Dans le cas contraire, l’ensemble des mots qui représentent les données demandées est chargé dans le cache à partir de la mémoire principale selon la loi d’associativité adoptée par la politique de gestion du cache (cf. § 1.4.3). Cet ensemble de mots consécutifs ainsi chargé est appelé ligne de cache. Quand le processeur échoue à trouver la donnée dans son cache, le temps de récupération des mots manquants est plus long. On parle ainsi d’un défaut de cache ou cache miss[124]. récapitule le principe de fonctionnement du cache. Pour toute donnée présente dans le cache il existe une copie dans la mémoire principale. Quand le processeur fait référence à une donnée dans le cache et qu’il y accède en écriture, une opération de mise à jour du contenu de la mémoire principale aura lieu.
Cette opération consiste à remplacer l’ancienne valeur de la donnée qui existe dans la mémoire du niveau supérieur (mémoire centrale) par la bonne valeur qui vient d’être calculée. Il existe différentes méthodes de mise à jour :
– Écriture immédiate (write through) : cette procédure consiste à recopier les données tout de suite après leur écriture dans la mémoire cache. Elle était largement utilisée dans les premiers caches mais elle tend à disparaître dans les nouvelles machines. Toutes les écritures se font dans la mémoire principale et engendrent une mise à jour directe des données présentes dans les différents niveaux du cache.
– Écriture différée (write back) : l’écriture en mémoire est effectuée lorsqu’on doit libérer la place occupée par la donnée pour y charger une autre selon l’algorithme de remplacement utilisé (cf. § 1.4.5). Cette technique est généralement utilisée au niveau des caches L2 et elle est considérée comme étant la plus performante car les écritures ne sont effectuées que lorsque la donnée a été modifiée. Chaque ligne possède un bit qui indique si une modification de la donnée a eu lieu ou pas.
Cependant, le bloc de données ainsi chargé suite à une requête du processeur ne peut pas être placé dans n’importe quel endroit du cache, il est dépendant de l’organisation interne du cache.
|
Table des matières
Introduction
I Avant propos
II Etat de l’art
1 Machines à mémoire partagée
1.1 Introduction
1.2 Taxonomie de Flynn
1.3 Mémoire partagée
1.3.1 Architectures à accès mémoire non uniforme
1.3.2 Mémoires à organisation hiérarchique
1.4 Mémoire cache
1.4.1 Les niveaux du cache
1.4.2 Principe de fonctionnement du cache
1.4.3 Lignes de cache et associativité
1.4.4 Les défauts de cache
1.4.5 Les algorithmes de remplacement
1.4.6 Cohérence du cache
2 Programmation parallèle
2.1 Introduction
2.2 Programmation parallèle par passage de messages
2.3 Programmation parallèle par tâches
2.3.1 Modèle de programmation par graphe de tâches
2.3.2 Graphes de tâches
2.3.3 Heuristiques d’ordonnancement de tâches
2.3.4 Ordonnancement par liste décentralisée
2.3.4.1 Gestion de la DEQueue
2.3.4.2 Vol de travail et choix de la victime
2.3.4.3 Grain de vol
2.3.5 Environnements de programmation parallèle basés sur un équilibre de tâches dynamique par ordonnancement de listes
2.3.5.1 La norme OpenMP
2.3.5.2 Cilk
2.3.5.3 IntelTBB
2.3.5.4 XKAAPI
2.4 Les langages PGAS, des langages émergents
2.5 Parallélisme et optimisation du cache
2.5.1 La localité du cache
2.5.2 Optimisation de la localité du cache par réorganisation des données en mémoire
2.5.2.1 Modification du placement des données en mémoire
2.5.2.2 Re-numérotation du maillage
2.5.2.3 Les Space-filling curves
2.5.2.4 Les algorithmes Cache-oblivious
2.5.2.5 Caractérisation de l’ordre d’utilisation des données
2.5.3 Optimisation de la localité du cache par transformation de boucles
2.5.4 Parallélisme imbriqué efficace dans le cache
3 Un peu de mécanique
3.1 Cinématique
3.1.1 Description Lagrangienne
3.1.2 Description Eulérienne
3.1.3 Formalisme général : Description ALE
3.2 Discrétisation en espace
3.2.1 Méthode des éléments finis
3.3 Discrétisation en temps
3.3.1 Schéma explicite
3.3.2 Schéma implicite
III Contributions
4 Etat des lieux
4.1 Contexte architectural
4.2 EUROPLEXUS
4.3 Organisation du code
4.3.1 Algorithme général
4.3.2 Périmètre applicatif et caractéristiques algorithmiques
4.3.3 Profiling
4.3.4 Structure de données
4.4 Stratégie parallèle dans EUROPLEXUS
4.4.1 Parallélisme à mémoire distribuée et mémoire partagée dans EPX
4.4.2 Parallélisme à mémoire partagée
4.4.3 Variation de la fréquence des processeurs
4.5 Choix d’un cas de calcul de démonstration
5 Optimisation du cache
5.1 Objectifs
5.2 Approche Par_gpe
5.2.1 Classification des données
5.2.2 Construction des groupes
5.2.3 Extension des groupes
5.3 Version séquentielle de l’approche Par_gpe
5.3.1 Implémentation
5.3.2 Étude expérimentale
5.3.2.1 Influence de l’affinité CPU
5.3.2.2 Évaluation du temps d’exécution séquentiel
5.4 Version parallèle de l’approche Par_gpe
5.4.1 Implémentation
5.4.2 Étude expérimentale
5.4.2.1 Évaluation du temps d’exécution parallèle
5.4.2.2 Évaluation de l’accélération
5.4.2.3 Évaluation du nombre de défauts de cache
5.5 Conclusion
6 Parallélisme imbriqué
6.1 Principe et implémentation
6.2 Évaluation expérimentale
6.2.1 Définition de la taille du grain séquentiel
6.2.1.1 Étude théorique
6.2.1.2 Validation expérimentale
6.2.2 Version 2-foreach versus version 1-foreach
6.2.2.1 Accélération des calculs élémentaires
6.2.2.2 Évaluation des temps d’exécution de Outer_loop
6.2.2.3 L’approche Par_gpe et les architectures Xeon Phi
6.3 Conclusion
IV Conclusion
